Python Networkx Implementing Cyclic Directed Graph

673 Views Asked by At

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
0

There are 0 best solutions below