Add traveling salesman problem to example gallery (#4874)

Adds an example of the using Christofides to solve the TSP problem to the example galery.

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

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()