Как извлечь все пути, начиная и заканчивая на одном узле

Question

Я сделал простую сеть:

import networkx as nx
G=nx.Graph()
G.add_node("a")
G.add_nodes_from(["b","c"])

G.add_edge(1,2)
edge = ("d", "e")
G.add_edge(*edge)
edge = ("a", "b")
G.add_edge(*edge)

print("Nodes of graph: ")
print(G.nodes())
print("Edges of graph: ")
print(G.edges())


# adding a list of edges:
G.add_edges_from([("a","c"),("c","d"), ("a",1), (1,"d"), ("a",2)])
nx.draw(G)
plt.show() # display

Я хотел бы составить список всех возможных путей, начинающихся и заканчивающихся в одинаковых узлах для всех узлов. Например, начиная с узла «а» и заканчивая узлом «а» может быть:

a-2-1-a, a-c-b-1-a, ....

начиная с узла "2" и заканчивая узлом "2" может быть:

2-а-1-2, 2-1-д-с-а-2, ....

Как я могу это сделать?

Answer 1

Путь, начинающийся и заканчивающийся в одном и том же узле, называется циклом. Поскольку циклы могут повторяться, всякий раз, когда у вас есть цикл, число возможных путей бесконечно. Вы можете найти список циклов, которые составляют основу для циклов G, вызвав nx.cycle_basis(G).

Если вы хотите явно вычислить все пути без повторений узлов, это можно сделать следующим образом:

import networkx as nx

G=nx.Graph()
G.add_edges_from([("d", "e"), ("a", "b"), ("a","c"), ("c","d"), ("a",1), (1,"d"), ("a",2), (1,2)])

node_to_cycles = {}
for source in G.nodes():
    paths = []
    for target in G.neighbors(source):
        paths += [l + [source] for l in list(nx.all_simple_paths(G, source=source, target=target)) if len(l) > 2]
    node_to_cycles[source] = paths

print(node_to_cycles['a'])

Эта реализация основана на nx.all_simple_paths. Поскольку у простого пути есть только один экземпляр каждого узла, мы ищем пути к каждому соседу узла, а затем объединяем сам узел.