NetworkX / Python_igraph: All paths between two no

Question

I am using the function from here :

def find_all_paths(graph, start, end, mode = 'OUT', maxlen = None):
def find_all_paths_aux(adjlist, start, end, path, maxlen = None):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    if maxlen is None or len(path) <= maxlen:
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path, maxlen))
    return paths
adjlist = [set(graph.neighbors(node, mode = mode)) \
    for node in xrange(graph.vcount())]
all_paths = []
start = start if type(start) is list else [start]
end = end if type(end) is list else [end]
for s in start:
    for e in end:
        all_paths.extend(find_all_paths_aux(adjlist, s, e, [], maxlen))
return all_paths

to find all paths between two nodes.

An alternative function is the one here:

def find_all_paths(graph, start, end):
path  = []
paths = []
queue = [(start, end, path)]
while queue:
    start, end, path = queue.pop()
    print 'PATH', path

    path = path + [start]
    if start == end:
        paths.append(path)
    for node in set(graph[start]).difference(path):
        queue.append((node, end, path))
return paths

I would like to extend one of the functions in order to take another argument, which would be a list of "via_nodes".

If a path has one of those via_nodes between its end and start node, it should not be returned.

It would be easy to first calculate all paths with the function as it is now and afterwards exclude the paths meeting above condition, but in order to make it more performant, I would like it to stop the path search once it meets a via_node at an earlier stage.

Any ideas?

Answer 1

Ok, I will answer myself, but will be happy about testing and comments: Taking the second function from above (adapted to work with both python-igraph and networkx), I added the vn argument, so path search stops if a vn node is reached:

import igraph as ig

def find_all_paths2(graph, start, end, vn = []):
        """ 
        Finds all paths between nodes start and end in graph.
        If any node on such a path is within vn, the path is not         
        returned.
        !! start and end node can't be in the vn list !!

        Params:
        --------

        G : igraph graph

        start: start node index

        end : end node index

        vn : list of via- or stop-nodes indices

        Returns:
        --------

        A list of paths (node index lists) between start and end node
        """

    vn = vn if type(vn) is list else [vn]
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        #print 'PATH', path
        path = path + [start]
        #print 'PATH after adding start ', path

        if start in vn:
            print start,' is in vianodes ',str(vn)
            pass#paths.append(path)

        if start == end:
            print 'end'
            paths.append(path)
        #print graph.neighbors(start)
        if start not in vn:
            print start,' not in vianodes ',str(vn)
            for node in set(graph.neighbors(start)).difference(path):
                queue.append((node, end, path))
    return paths

G = ig.Graph()
G.add_vertices(14)
G.add_edges([(13,10),(12,13),(11,12),(10,11),(9,10),(2,9),(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(7,8),(8,6)])#,(0,0)])
#G = G.as_directed()


for p in find_all_paths2(G,0,12,[]):
    print 'path: ',p

path:  [0, 3, 2, 9, 10, 13, 12]
path:  [0, 3, 2, 9, 10, 11, 12]
path:  [0, 1, 2, 9, 10, 13, 12]
path:  [0, 1, 2, 9, 10, 11, 12]

for p in find_all_paths2(G,0,12,[13]):
        print 'path: ',p


path:  [0, 3, 2, 9, 10, 11, 12]
path:  [0, 1, 2, 9, 10, 11, 12]

Answer 2

Delete the nodes from the Graph before you recurse over long paths.

Put them back when you are done.

This takes less memory in highly connected graphs.

import networkx
G = networkx.Graph()
G.add_node(14)
G.add_edges_from([(13,10),(12,13),(11,12),(10,11),(9,10),(2,9),(0,1),(1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(7,8),(8,6)])


def simple_paths_with_node_exclusion(G, source, target, exclude_nodes):
        edge_list = []
        edge_list.extend(G.edges_iter(exclude_nodes))
        G.remove_nodes_from(exclude_nodes)
        value = networkx.all_simple_paths(G, source, target)
        G.add_nodes_from(edge_list)
        return value

print(list(simple_paths_with_node_exclusion(G,0,12,[13])))

• if you are doing time or memory tests I would enjoy hearing about the results with real data in the comments below.