[FIXED] How to automate creating directed graph using networkx or graphviz in Python for all possible paths in a travelling salesman problem?

Issue

I want to create a directed graph showing all possible paths in a travelling salesman problem for four cities I want to explore.

cities = ["Berlin","Hamburg","Dusseldorf","Munich"]

First, I created a skeleton using the graphviz package. The nodes are integers (but in the form of strings). The code looks as follows:

import graphviz

nodes = np.arange(0, 21)

cities = ["Berlin","Dusseldorf","Hamburg","Munich"]


f = graphviz.Digraph()

#Stop 1
for i in range(1, 4):
    f.edge(str(0), str(i))
    
#Stop 2 add edges
for i in range(1,4):   
    for j in range(4,10):
        if j==i*2+2 or j == i*2+3:
            f.edge(str(i), str(j))
            
for i in range(4, 10):
    for j in range(10, 16):
        if j == i+6:
            f.edge(str(i), str(j))

for i in range(10, 16):
    for j in range(16, 22):
        if j == i+6:
            f.edge(str(i), str(j))
            
f

This returned me a following directed graph:

In place of nodes, I want to give the name of cities as labels. The route in travelling salesman problem is assumed to start and end at Berlin. I provided the name (labels) to nodes manually in the code below.

import graphviz

nodes = np.arange(0, 21)

cities = ["Berlin","Dusseldorf","Hamburg","Munich"]


f = graphviz.Digraph()

#Stop 1
for i in range(1, 4):
    f.edge(str(0), str(i))
    
#Stop 2 add edges
for i in range(1,4):   
    for j in range(4,10):
        if j==i*2+2 or j == i*2+3:
            f.edge(str(i), str(j))
            
for i in range(4, 10):
    for j in range(10, 16):
        if j == i+6:
            f.edge(str(i), str(j))

for i in range(10, 16):
    for j in range(16, 22):
        if j == i+6:
            f.edge(str(i), str(j))

#Root node
f.node("0","Berlin")

#Leaves
for i in range(16, 22):
    f.node(str(i), "Berlin")

#Stop 1
for i in range(1,4):
    f.node(str(i), cities[i])

#Stop 2 add nodes
f.node(str(4), "Hamburg")
f.node(str(9), "Hamburg")
f.node(str(11), "Hamburg")
f.node(str(14), "Hamburg")

f.node(str(5), "Munich")
f.node(str(7), "Munich")
f.node(str(10), "Munich")
f.node(str(12), "Munich")

f.node(str(6), "Dusseldorf")
f.node(str(8), "Dusseldorf")
f.node(str(13), "Dusseldorf")
f.node(str(15), "Dusseldorf")
            
f

The resulting plot is as shown, which has all possible paths starting from Berlin and ending at Berlin visiting all rest of the cities once:

I have provided labels to each of the nodes manually. But is there a process I can automate it to give the labels to the individual nodes for this kind of graph? Is it possible to do it using graphviz, NetworkX or with the help any other packages such as pandas in Python?

Solution

networkx seems to have a function for everything:

from itertools import permutations
import networkx as nx

def make_tsp_tree(cities):
    start, *rest = cities
    paths = [(start, *path, start) for path in permutations(rest)]
    G = nx.prefix_tree(paths)
    # remove synthetic root and leaf nodes
    G.remove_nodes_from([0, -1])
    return G

The root node is 1, and the city names are stored in the node attribute source. It should be straightforward to convert it to graphviz or whatever you need.

A quick usage example:

pos = nx.nx_agraph.graphviz_layout(G, "dot", root=1)
nx.draw_networkx_nodes(G, pos, node_color="C1")
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos, labels=dict(G.nodes(data="source")))

Answered By - yut23

Answer Checked By - Mildred Charles (PHPFixing Admin)