Return the tree structure of Hamilton paths

tree of Hamilton paths

import networkx as nx
import matplotlib.pyplot as plt

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

def make_tsp_tree(cities):
    """
    Create all Hamilton paths from start to end city from a list of cities.
    Creates a directed prefix tree from a list of the created paths. 
    Remove the root node and nil node.
    """
    start, *rest, end = cities
    paths = [(start, *path, end) for path in permutations(rest)]
    
    #Creates a directed prefix from a list of paths
    G = nx.prefix_tree(paths)
    
    #remove synthetic root node (None) and nil node (NIL)
    G.remove_nodes_from([0, -1])
    
    return G

#Get graph object with all Hamilton paths
G = make_tsp_tree(cities)

#Create node positions for G using Graphviz.
#Available layouts: https://graphviz.org/docs/layouts/
#dot gives hierarchical or layered drawings of directed graphs
#possible layouts: dot, neato, twopi, circo, fdp, osage, patchwork, sfdp
positions = nx.nx_agraph.graphviz_layout(G, "dot")

plt.figure(figsize = (12,8))

#Draw networkx Graph object with labels off
nx.draw_networkx(G,
                 pos = positions,
                 node_color = "mistyrose",
                 with_labels= False)

#Draw NetworkX Graph object with defined labels for each node
nx.draw_networkx_labels(G,
                        pos = positions,
                        labels = dict(G.nodes(data = "source")))

plt.title("Hamilton paths for Berlin, Hamburg, Dusseldorf and Munich.\n Start and end at Berlin.")
plt.axis("off")
plt.show()