CODEWITHSUNDEEP
pythongraphnetworkx
T-800
T-800

Reputation: 1603

Listing All Possible 'Shortest' Paths

I have a combinatorial problem which can be treated as a network search problem. In order to visualize and use already implemented functions, I decided to use networkx package (I actually do not have enough time to implement it in other way).

My problem is unfortunately quite complex. But, I will try to ease the understanding by explaining even the simplest things. In general, I need to find out the combinations to reach the nodes where the tree is ending.

The figure below shows a trivial example:

enter image description here

In this case, B, D, F, H are terminal nodes, whereas starting point is denoted with O. So, a path combination could be:

OAB
OCD
OED
OEF
OH
OGH

However, I actually search for the 'shortest' or 'most favorable' paths to reach the terminal nodes. The diagram (or the edges) does not give any information about the 'cost' of the path. The cost evaluation will be done according to the results of the combinations found. Evaluating the 'actual' costs of the combinations found is computationally very expensive. Although the diagram does not yield much information, one thing is clear: in order to reach H, OH is at any time a better choice than OGH. So, the combination OGH can be eliminated from the possible combinations list. It is essentially like the distance metric.

One more point, in fact, D and F correspond to equivalent points (they are distinct nodes but have the same meaning for my application). Such an information can however only be gained if two nodes

- see each other
- see exactly the same nodes

If looked at the figure carefully, it can also be recognized that C and E are equivalent nodes. So, to state it more specifically: the combinations of OCD and OED are actually the same. Once OCD is added to combination-list, there is not any need to add OED. It can also be seen from the figure, as D and F are the same, once OCD is added to the list, there is not any need to add OCF.

To sum up, the solution in this case would be: 

OAB
anyone of OCD, OED, OCF, OEF
OH

To sketch that digram, I followed the tutorials of networkx and then created the code below:

import networkx as nx
import matplotlib.pyplot as plt

graph = [('O', 'A'), ('O', 'C'),  ('O', 'E'),  ('O', 'G'),  ('O', 'H'),  
         ('A', 'B'), ('A', 'O'),
         ('B', 'A'),
         ('C', 'D'), ('C', 'E'), ('C', 'F'), ('C', 'O'),
         ('D', 'E'), ('D', 'C'), ('D', 'F'),  
         ('E', 'C'), ('E', 'D'), ('E', 'F'), ('E', 'O'),
         ('F', 'C'), ('F', 'D'), ('F', 'E'),
         ('G', 'H'), ('G', 'O'), 
         ('H', 'G'), ('H', 'O')]

G=nx.DiGraph()
for edge in graph:
    G.add_edge(edge[0], edge[1])

pos=nx.graphviz_layout(G,prog='dot')
nx.draw(G, pos)
plt.show()

So, my question is to list up such sequences using any toolbox, but preferably networkx. The first step to do is probably simplifying (or reducing) the graph before creating a Graph object. Once the simplified graph is obtained, using nx.all_simple_path command, all the alternative paths can be listed. I need your help in doing such a graph reduction.

My graphs are not deep, they are generally about the same size as given in the example.

Upvotes: 2

Views: 644

Answers (1)

T-800
T-800

Reputation: 1603

I have read the complete module handbook and I tried different search algorithms, but I couldn't find an existing implementation, or any workaround for such a specific case.

So, with the advice gained from the comments, I wrote my own simplifier and removed all of the 'redundant' nodes before creating the graph. I did it just by transforming the lists in sets and then by comparing whether they are identical. Afterwards, I created the graph and listed up all the solutions using nx.all_simple_paths command. Once I got the paths, this time I searched for whether there are any paths (like OGH) when whose letter before the last, i.e. index [-2], is removed the resulting path (OH) is also in the list of nx.all_simple_paths. If yes, then I removed that solution out.

The script I coded is quite unorganized, and doesn't involve special techniques. Therefore, I have chosen to write the solution methodology.

Upvotes: 1

Related Questions