NetworkX / Python_igraph：两个节点之间的所有路径，受限于节点列表 [英] NetworkX / Python_igraph: All paths between two nodes, limited by list of nodes

问题描述

我使用这里的功能：

  def find_all_paths（图形，开始，结束，模式='OUT'，maxlen =无）：
 def find_all_paths_aux（adjlist，start，end，path，maxlen = None）：
 path = path + [start] 
 if start == end：
 return [path] 
 paths = [] 
如果maxlen是None或len（path）< ; = maxlen：
为节点在adjlist [开始]  - 设置（路径）：
 paths.extend（find_all_paths_aux（adjlist，node，end，path，maxlen））
返回路径
 adjlist = [set（graph.neighbors（node，mode = mode））\ 
用于xrange中的节点（graph.vcount（））] 
 all_paths = [] 
 start =如果类型（开始）是列表，则开始else [开始] 
结束=结束如果类型（结束）是列表else [结束] 
开始时s：
结束时e 
 all_paths.extend（find_all_paths_aux（adjlist，s，e，[]，maxlen））
 return all_paths 
  

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

另一个函数是这里

a>：

  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）
为集合中的节点（图形[开始]）。差异（路径）：
 queue.append（（节点，结束，路径））
返回路径
  

我想扩展其中的一个函数，以便接受另一个参数，它将是via_nodes的列表。

如果一个路径在其结束节点和开始节点之间有一个via_nodes，就不应该返回。

首先计算所有具有此功能的路径，然后排除满足上述条件的路径，但为了使其性能更高，我希望在遇到via_node时停止路径搜索，这很容易。早期阶段。

有什么想法？

解决方案

你在长路径上递归。

完成后放回去。

pre $ 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）））


def simple_paths_with_node_exclusion（G，source，target，exclude_nodes）：
edge_list = []
edge_list.extend（G.edges_iter （$）
G.remove_nodes_from（exclude_nodes）
value = networkx.all_simple_paths（G，source，target）
G.add_nodes_from（edge_list）
返回值

print（list（simple_paths_with_node_exclusion（G，0,12，[13]）））


• 如果您正在进行时间或记忆测试I在下面的评论中会听到真实数据的结果。

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?

解决方案

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.

这篇关于NetworkX / Python_igraph：两个节点之间的所有路径，受限于节点列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！