在循环中查找边 networkx python

Question

我想写一个算法，来判断在一个无向图中一条边是否属于一个环。我打算使用Python中的networkx库里的cycle_basis函数，来获取图中的所有环。我的问题是，cycle_basis返回的是节点的列表。我该怎么把这些节点转换成边呢？

Answer 1

你可以直接通过 find_cycle 这个方法来获取一个循环中的边。如果你想检查一条边是否属于某个循环，你需要确认这条边的两个端点是否都在同一个循环里。

使用上面答案中的例子：

import networkx as nx

G = nx.Graph()
G.add_cycle([1,2,3,4])
G.add_cycle([10,20,30])
G.add_edge(1,10)
nx.find_cycle(G, 1) # [(1, 2), (2, 3), (3, 4), (4, 1)]
nx.find_cycle(G, 10) # [(10, 20), (20, 30), (30, 10)]

另一方面，边 (2, 3)（或者 (3, 2)，因为你的图是无向的）是属于第一个定义的循环的一部分：

nx.find_cycle(G, 2) # [(2, 1), (1, 4), (4, 3), (3, 2)]

Answer 2

在Aric的帮助下，我用了一点小技巧来检查两个方向，最后做出了这个看起来还不错的东西。

import networkx as nx

G = nx.Graph()

G.add_cycle([1,2,3,4])

G.add_cycle([10,20,30])

G.add_edge(1,10)


def edge_in_cycle(edge, graph):
    u, v = edge
    basis = nx.cycle_basis(graph)
    edges = [zip(nodes,(nodes[1:]+nodes[:1])) for nodes in basis]
    found = False
    for cycle in edges:
        if (u, v) in cycle or (v, u) in cycle:
            found = True            
    return found

for edge in G.edges():
    print edge, 'in a cycle:', edge_in_cycle(edge, G)

输出结果：

(1, 2) in a cycle: True
(1, 4) in a cycle: True
(1, 10) in a cycle: False
(2, 3) in a cycle: True
(3, 4) in a cycle: True
(10, 20) in a cycle: True
(10, 30) in a cycle: True
(20, 30) in a cycle: True

Answer 3

如果你找不到一个好的解决办法，这里有一个不太优雅的方法。

1. 使用 edges() 这个功能，你可以得到一个与循环中的节点相邻的边的列表。不过，遗憾的是，这个列表还包括与循环外的节点相邻的边。
2. 接下来，你可以通过去掉那些连接到不在循环中的节点的边，来过滤这个边的列表。

如果你找到一个更省事的解决方案，请告诉我们哦。

Answer 4

这是我对这个问题的看法，我只用了lambda函数（我超喜欢lambda函数！）：

import networkx as nx

G = nx.Graph()

G.add_cycle([1,2,3,4])

G.add_cycle([10,20,30])

G.add_edge(1,10)


in_path = lambda e, path: (e[0], e[1]) in path or (e[1], e[0]) in path
cycle_to_path = lambda path: list(zip(path+path[:1], path[1:] + path[:1]))
in_a_cycle = lambda e, cycle: in_path(e, cycle_to_path(cycle))
in_any_cycle = lambda e, g: any(in_a_cycle(e, c) for c in nx.cycle_basis(g))

for edge in G.edges():
    print(edge, 'in a cycle:', in_any_cycle(edge, G))

Answer 5

你可以通过连接相邻的节点来构建循环中的边。

In [1]: import networkx as nx

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

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

In [4]: G.add_cycle([10,20,30])

In [5]: basis = nx.cycle_basis(G)

In [6]: basis
Out[6]: [[2, 3, 4, 1], [20, 30, 10]]

In [7]: edges = [zip(nodes,(nodes[1:]+nodes[:1])) for nodes in basis]

In [8]: edges
Out[8]: [[(2, 3), (3, 4), (4, 1), (1, 2)], [(20, 30), (30, 10), (10, 20)]]