Python网络：如何检查两个节点之间是否只存在一条简单路径？

I am using networkx.all_simple_paths(G,source,dest) to find out all the possible paths between two nodes. I returns multiple lists.

我正在使用networkx.all_simple_paths(G,source,dest)来找出两个节点之间的所有可能路径。我返回多个列表。

Here is my code snippet:

这是我的代码片段:

for path in (nx.all_simple_paths(G,source=node1,target=node2):
         print path 

This gives me multiple lists in which path is stored. I need to find out if there is only a single path between a given pair of nodes.

这给了我存储路径的多个列表。我需要找出给定节点对之间是否只有一条路径。

How can I do this?

我怎样才能做到这一点?

Thanks.

5 个解决方案

#1

Not the absolute cleanest, but here is a function that will look at the iterator. If there is no first element, it returns False. If there is a first element (i.e., there is a path), but no second element, it returns True. If there is a second (i.e., there is more than one path), it returns False. It never checks to see if there are any more.

不是绝对最干净,但这里是一个函数,它将查看迭代器。如果没有第一个元素,则返回False。如果存在第一个元素(即,存在路径),但没有第二个元素,则返回True。如果有第二个(即,存在多个路径),则返回False。它永远不会检查是否还有。

def simple_path(G,source,target):
    iterator = nx.all_simple_paths(G,source=source,target=target)
    try:
        first_path = next(iterator)
    except StopIteration:
        return False
    try:
        second_path = next(iterator)
    except StopIteration:
        return True
    return False

Sample runs:

In [3]: G= nx.Graph()

In [4]: G.add_edges_from([(1,2),(1,3),(2,3),(3,4)])

In [5]: simple_path(G,1,2)
Out[5]: False

In [6]: simple_path(G,1,3)
Out[6]: False

In [7]: simple_path(G,3,4)
Out[7]: True

In [8]: simple_path(G,1,4)
Out[8]: False

#2

You can use zip to match the first two potential paths together (the contents of the list don't matter, that's why I put _). The length of the resulting object is the number of paths found:

您可以使用zip将前两个潜在路径匹配在一起(列表的内容无关紧要,这就是我放_的原因)。结果对象的长度是找到的路径数:

paths = nx.all_simple_paths(G,source=node1,target=node2))
# True, if there was exactly one path, calculates at most 2 paths
is_unique_path = len(zip([_, _], paths)) == 1

#3

If you want to know if there exists a single path between node 0 and 1 for this graph g1, for example:

如果您想知道此图g1的节点0和1之间是否存在单个路径,例如:

len([path for path in nx.all_simple_paths(g1, source=0, target=1)]) == 1  # True

You can extend this to check across all nodes if a particular number of paths exists and return a list of True/False for that particular pair of nodes.

如果存在特定数量的路径,则可以对此进行扩展以检查所有节点,并为该特定节点对返回True / False列表。

import itertools
def number_paths(graph, number):
    # list of all possible pairs. NOTE: there may not be an edge between some pairs
    node_pairs = list(itertools.combinations(graph.nodes(), 2))
    num_path = []
    for pair in node_pairs:
        num_path.append( 
            len([path for path in nx.all_simple_paths(graph, source=pair[0], target=pair[1])]) == number )
    return num_path, node_pairs

So for the graph above you can do:

因此,对于上图,您可以执行以下操作:

print number_paths(g1, 1)  # prints: ([True], [(0, 1)])

A better example is this graph g2:

一个更好的例子是这个图g2:

Does there exist only a single path between pairs of nodes?

节点对之间只存在一条路径吗?

check, nodes = number_paths(g2, 1)
print 'check:', check  # check: [True, False, False, False, False, False]
print 'nodes:', nodes  # nodes: [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

Does there exist only 2 paths between pairs of nodes?

节点对之间只存在2条路径吗?

check, nodes = number_paths(g2, 2)
print 'check:', check  # check: [False, True, True, True, True, True]
print 'nodes:', nodes  # nodes: [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

#4

Inspired by Joel's answer, avoiding generating more than two paths and branching via exception catching:

受Joel的回答启发,避免生成两个以上的路径并通过异常捕获进行分支:

import itertools

def simple_path(G,source,target):
    iterator = nx.all_simple_paths(G,source=source,target=target)
    return sum(1 for _ in itertools.islice(iterator, 2)) == 1

It tries to calculate up to 2 elements from the generator. It should return False is there are zero or two elements, and return True if there is only one.

它尝试从发生器计算最多2个元素。如果有零个或两个元素,它应该返回False,如果只有一个元素,则返回True。

#5

You can use next with its default argument:

您可以使用next的默认参数:

def has_one_path(G, source, target):
    paths = nx.all_simple_paths(G, source, target)
    return next(paths, None) is not None and next(paths, None) is None

I think it's pretty readable and as efficient as you need: a graph has one path from source to target if there is a next path, and there is no next path after that.

我认为它具有可读性和高效性:如果存在下一个路径,则图形具有从源到目标的一条路径,之后没有下一条路径。