diff options
-rw-r--r-- | examples/drawing/plot_tsp.py | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/examples/drawing/plot_tsp.py b/examples/drawing/plot_tsp.py new file mode 100644 index 00000000..78c731b8 --- /dev/null +++ b/examples/drawing/plot_tsp.py @@ -0,0 +1,52 @@ +""" +========================== +Traveling Salesman Problem +========================== + +This is an example of a drawing solution of the traveling salesman problem + +The function is used to produce the solution is christofides, +where given a set of nodes, it calculates the route of the nodes +that the traveler has to follow in order to minimize the total cost. +""" + +import matplotlib.pyplot as plt +import networkx as nx +import networkx.algorithms.approximation as nx_app +import math + +G = nx.random_geometric_graph(20, radius=0.4, seed=3) +pos = nx.get_node_attributes(G, "pos") + +# Depot should be at (0,0) +pos[0] = (0.5, 0.5) + +H = G.copy() + + +# Calculating the distances between the nodes as edge's weight. +for i in range(len(pos)): + for j in range(i + 1, len(pos)): + dist = math.hypot(pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]) + dist = dist + G.add_edge(i, j, weight=dist) + +cycle = nx_app.christofides(G, weight="weight") +edge_list = list(nx.utils.pairwise(cycle)) + +# Draw closest edges on each node only +nx.draw_networkx_edges(H, pos, edge_color="blue", width=0.5) + +# Draw the route +nx.draw_networkx( + G, + pos, + with_labels=True, + edgelist=edge_list, + edge_color="red", + node_size=200, + width=3, +) + +print("The route of the traveller is:", cycle) +plt.show() |