I’m trying to find all paths through the following cyclic directed graph. I would like to be able to include the paths which pass through the cycles once, but not include the possibility of infinitely cycling through one path.
Start -> [1];
1 -> [2];
2 -> [3, 4];
3 -> [6];
4 -> [7];
5 -> [3,8];
6 -> [5,8];
7 -> [10];
8 -> [9];
9 -> [End];
10 -> [8].
I have found all of the simple paths, however, there are three more paths which do not repeat the cycles, however, are able to travel through a cycle once. I would like to be able to find these, using Python??
I have included the code developed to date below.
import networkx as nx
#Build a dummy dictionary to represent a graph, nodes as keys, edges to the node as paired arrays
#Page 1
Demo_Bussines_Process_Diagram = {"Start" : ["1"], "1":["2"], "2":["3","4"],
"3":["6"], "4":["7"], "5":["3","8"], "6":["5","8"],
"7":["10"],"8":["9"],"9":["End"],"10":["8","4"]}
#Build an empty directed graph
Business_Process = nx.MultiDiGraph()
#place each node into the graph, unconnected
for node in Demo_Bussines_Process_Diagram:
Business_Process.add_node(node)
#Build the edges between the nodes of the graph
for source_node in Demo_Bussines_Process_Diagram:
for edge_node in Demo_Bussines_Process_Diagram[source_node]:
Business_Process.add_edge(source_node,edge_node,weight=1)
#Freeze the diagram, locking down any possible modifications
nx.freeze(Business_Process)
#Calculate the order (total nodes)
order = Business_Process.order()
print("Total nodes in the graph =", order)
#Find all of the edges in the proces
total_edges = Business_Process.edges()
print("Total conections in the graph =", len(total_edges))
#Find all decisions in the diagram
Decisions = {}
for node in Business_Process:
if Business_Process.out_degree(node)>1:
Decisions[node] = [Business_Process.out_degree(node),Business_Process.out_edges(node)]
print("Total decisions =",len(Decisions))
#Find all cycles
cycles = nx.simple_cycles(Business_Process)
counter = 0
cyclic_decisions = {}
for cycle in cycles:
decision_nodes = []
counter += 1
decimal_cycle = ".".join(cycle)
cyclic_decisions[decimal_cycle] = cycle
print("Cycle", counter,"is",cycle)
decision_node = None
print("Total cyclic decisions =",counter)
#Find all, non-cyclic, paths
paths = nx.all_simple_paths(Business_Process, source="Start", target="End")
counter = 1
for path in paths:
print("Path", counter,"is",path)
counter += 1