NetworkX / Python_igraph：两个节点之间的所有路径，受节点列表限制

Question

我正在使用中的函数：

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

找到两个节点之间的所有路径。

另一个函数是 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

我想扩展其中一个函数以获取另一个参数，它是 "via_nodes" 的列表。

如果路径在其结束节点和起始节点之间有 via_nodes 之一，则不应返回。

像现在这样先用函数计算所有路径然后排除满足上述条件的路径会很容易，但为了提高性能，我希望它停止路径搜索一次在较早的阶段遇到 via_node。

有什么想法吗？

Answer 1

好的，我会自己回答，但会很高兴进行测试和评论：采用上面的第二个函数（适用于 python-igraph 和 networkx），我添加了 vn 参数，因此，如果到达 vn 节点，路径搜索将停止：

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

在对长路径进行递归之前从图中删除节点。

完成后放回去。

这在高度连接的图中占用更少的内存。

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])))

如果您正在进行时间或记忆测试，我很乐意在下面的评论中听到真实数据的结果。

Answer 3

您可以创建一个仅包含您希望在路径中看到的节点的子图在 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)

这将找到所有简单路径并排除 vn 中的任何节点，因为它们不在子图中

NetworkX / Python_igraph：两个节点之间的所有路径，受节点列表限制

NetworkX / Python_igraph: All paths between two nodes, limited by list of nodes

python

graph

igraph

networkx

network-analysis