pythongraphnetworkxtraveling-salesmanjsnetworkx

KeyError in nx.algorithms.approximation.traveling_salesman_problem()


I have written a code which generates 10 random graphs and solve the traveling salesman problem using NetworkX. I am getting KeyError: 1.

Following is my code.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import time
import csv
import pandas as pd

# Function to generate a random graph
def generate_random_graph(num_nodes, edge_prob):
    return nx.erdos_renyi_graph(num_nodes, edge_prob)

# Function to solve TSP and track time
def solve_tsp(graph):
    start_time = time.time()
    cycle = nx.algorithms.approximation.traveling_salesman_problem(graph, cycle=True)
    end_time = time.time()
    elapsed_time = end_time - start_time
    return cycle, elapsed_time

# Number of nodes in the graph
num_nodes = 10

data_points = []
csv_data = []

# Generate 10 random graphs, solve TSP, and record data
for i in range(10):
    edge_prob = np.random.rand()  # Random edge probability
    graph = generate_random_graph(num_nodes, edge_prob)
    density = nx.density(graph)
    
    # Solve TSP
    cycle, elapsed_time = solve_tsp(graph)
    
    # Record data
    data_points.append((density, elapsed_time))
    
    # Prepare adjacency matrix for CSV
    adj_matrix = nx.adjacency_matrix(graph).todense().tolist()
    
    csv_data.append([adj_matrix, density, elapsed_time, cycle])

I am getting the following error:

KeyError                                  Traceback (most recent call last)
Cell In[7], line 8
      5 density = nx.density(graph)
      7 # Solve TSP
----> 8 cycle, elapsed_time = solve_tsp(graph)
     10 # Record data
     11 data_points.append((density, elapsed_time))

Cell In[3], line 4, in solve_tsp(graph)
      2 def solve_tsp(graph):
      3     start_time = time.time()
----> 4     cycle = nx.algorithms.approximation.traveling_salesman_problem(graph, cycle=True)
      5     end_time = time.time()
      6     elapsed_time = end_time - start_time

File ~/anaconda3/envs/py39/lib/python3.9/site-packages/networkx/utils/backends.py:412, in _dispatch.__call__(self, backend, *args, **kwargs)
    409 def __call__(self, /, *args, backend=None, **kwargs):
    410     if not backends:
    411         # Fast path if no backends are installed
--> 412         return self.orig_func(*args, **kwargs)
    414     # Use `backend_name` in this function instead of `backend`
    415     backend_name = backend

File ~/anaconda3/envs/py39/lib/python3.9/site-packages/networkx/algorithms/approximation/traveling_salesman.py:320, in traveling_salesman_problem(G, weight, nodes, cycle, method)
    318         if u == v:
    319             continue
--> 320         GG.add_edge(u, v, weight=dist[u][v])
    321 best_GG = method(GG, weight)
    323 if not cycle:
    324     # find and remove the biggest edge

KeyError: 1

How can I resolve it?


Solution

  • The problem is that the traveling salesman algorithm only works for connected graphs, however nx.erdos_renyi_graph might return graphs consisting of multiple connected components. Think of how you would try to find a cycle going through two nodes that do not have a path between them.

    There are two possible solutions, either make sure that your graph is connected or calculate the TSP cycle for each connected component separately.

    To calculate a cycle for each connected component, adapt your solve_tsp(graph) function as follows:

    def solve_tsp(graph):
        start_time = time.time()
    
        cycles = []
        for connected_component in nx.connected_components(graph):
            if len(connected_component) > 1:
                cycles.append(
                    nx.algorithms.approximation.traveling_salesman_problem(graph, nodes=connected_component, cycle=True)
                )
            else:
                cycles.append(list(connected_component))
            
        end_time = time.time()
        elapsed_time = end_time - start_time
        return cycles, elapsed_time
    

    This will now call the TSP algorithm for each connected component individually and return a list of cycles instead of just one cycle. The check on the length of the number of nodes in the connected component is necessary, as traveling_salesman_problem will also fail on graphs of size 0 or 1.

    Alternatively, if you just want to make sure that your random graph is connected - i.e. there is just one connected component and one cycle visiting all nodes - you can calculate the minimum set of edges to make graph connected using nx.k_edge_augmentation and add them to your graph:

    # Function to generate a random connected graph
    def generate_random_graph(num_nodes, edge_prob):
        random_graph = nx.erdos_renyi_graph(num_nodes, edge_prob)
        missing_edges = nx.k_edge_augmentation(random_graph, k=1)
        random_graph.add_edges_from(missing_edges)
        return random_graph