5

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
Tomerikoo
  • 18,379
  • 16
  • 47
  • 61
M. Morgan
  • 93
  • 7
  • 1
    Do you want to find all paths from "Start" to "End"? – Hai Vu Jan 04 '18 at 22:02
  • Is `A-B-C-D-B-C-E-B-F` an acceptable path from `A` to `F`? – Joel Jan 04 '18 at 22:37
  • Specifically, I guess one part of my question is whether it can cross the same edge more than once if it's part of different cycles. – Joel Jan 05 '18 at 02:26
  • Hi, yes I'd like all paths from start to end, and yes, I'm ok if the paths cross the same edge more than once, as long as they don't repeat the same loop once passed. – M. Morgan Jan 05 '18 at 08:35

0 Answers0