Я хотел бы создать алгоритм, чтобы определить, принадлежит ли ребро циклу в неориентированном графе, используя networkx в Python. Я думаю использовать cycle_basis
и получить все циклы на графике. Моя проблема в том, что cycle_basis
возвращает список узлов. Как я могу преобразовать их в края?
Найти ребра в цикле networkx python
Ответы (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)]]
Вот мой взгляд на это, используя только лямбда-функции (я люблю лямбда-функции!):
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))
на случай, если вы не найдете хорошего решения, вот уродливое.
- с
edges()
< /a> можно получить список ребер, смежных с узлами в цикле. к сожалению, это включает в себя ребра, смежные с узлами вне цикла - теперь вы можете отфильтровать список ребер, удалив те, которые соединяют узлы, не являющиеся частью цикла.
пожалуйста, держите нас в курсе, если вы найдете менее расточительное решение.
С помощью Арика и небольшого трюка, чтобы проверить оба направления, я, наконец, сделал это, и это выглядит нормально.
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
Вы можете напрямую получить ребра в цикле с помощью 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)]