在循环networkx python中查找边

I would like to make an algorithm to find if an edge belongs to a cycle, in an undirected graph, using networkx in Python. I am thinking to use cycle_basis and get all the cycles in the graph. My problem is that cycle_basis returns a list of nodes. How can I convert them to edges?

我想做一个算法，用Python中的networkx，在无向图中找出一条边是否属于一个循环。我在考虑使用cycle_basis来得到图中的所有循环。我的问题是cycle_basis返回一个节点列表。如何将它们转换成边?

4 个解决方案

#1

You can construct the edges from the cycle by connecting adjacent nodes.

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

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

#2

Here is my take at it, using just lambda functions (I love lambda functions!):

这是我的理解，使用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))

#3

in case you don't find a nice solution, here's an ugly one.

如果你找不到一个好的解决方案，这里有一个很丑的。

with edges() you can get a list of edges that are adjacent to nodes in a cycle. unfortunately, this includes edges adjacent to nodes outside the cycle
有了边()，您就可以得到一个循环中与节点相邻的边的列表。不幸的是，这包括在循环之外的节点附近。
you can now filter the list of edges by removing those which connect nodes that are not part of the cycle.
现在，您可以通过删除那些连接不属于循环的节点来过滤边缘列表。

please keep us posted if you find a less wasteful solution.

如果你找到一个不那么浪费的解决方案，请随时通知我们。

#4

With the help of Aric, and a little trick to check both directions, I finally did this that looks ok.

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

output:

输出:

(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

#1