NetworkX / Python_igraph: All Paths Between Two Nodes, Limited By List Of Nodes

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 =

Solution 1:

You can create a subgraph that only includes the nodes you would like to see in your paths In Networkx 2.5:

sub_graph = nx.subgraph_view(graph, filter_node:lambda n: n in [start, end] or n not in vn)
return all_simple_paths(sub_graph, start, end)

This will find all simple paths and exclude any nodes in vn since they are not in the subgraph

Solution 2:

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]

Solution 3:

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.