CODEWITHSUNDEEP
networkx
chu
chu

Reputation: 79

How to extract all paths, starting from and ending at same node

I made a simple network:

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

I would like to make a list of all possible path starting from and ending in same nodes for all nodes. For example, starting from the node "a" and ending the node "a" can be:

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

starting from the node "2" and ending in the node "2" can be:

2-a-1-2, 2-1-d-c-a-2, ....

How can I do it?

Upvotes: 1

Views: 1584

Answers (1)

zohar.kom
zohar.kom

Reputation: 1845

A path starting and ending at the same node is called a cycle. Since cycles can be repeated, whenever you have a cycle the number of possible paths is infinite. You can find the list of cycles which form a basis for cycles of G, by calling nx.cycle_basis(G).

If you wish to compute explicitly all paths without repetitions of nodes, it can be done as follows: 

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

This implementation is based on nx.all_simple_paths. Since a simple path has only one instance of each node, we search paths to each neighbor of a node, and then concatenate the node itself.

Upvotes: 2

Related Questions