79191566

Date: 2024-11-15 08:32:53
Score: 0.5
Natty:
Report link

I consistently get shorter paths when the weight parameter is named weight:

import shapely
import networkx as nx
import matplotlib.pyplot as plt

# Make a 10x10 grid

vert = shapely.geometry.MultiLineString([[(x, 0), (x, 100)] for x in range(0, 110, 10)])
hori = shapely.affinity.rotate(vert, 90)
grid = shapely.unary_union([vert, hori])

params = ["weight", "distance"]
paths = []

for param in params:

    # Turn it into a graph

    graph = nx.Graph()
    graph.add_edges_from([(*line.coords, {param: line.length}) for line in grid.geoms])
    
    # Select nodes and visit them via TSP
    
    nodes = [(20., 20.), (30., 30.), (20., 80.), (80., 20.), (50., 50.), (60., 10.), (40., 40.), (50., 40.), (50, 30)]
    
    path = nx.approximation.traveling_salesman_problem(
        graph,
        weight=param,
        nodes=nodes,
        cycle=False,
        method=nx.approximation.christofides
    )
    
    paths.append(shapely.geometry.LineString(path))

# Plot results

fig, axes = plt.subplots(1, 2, figsize=(10, 5), sharey=True)

for ax, param, path, c in zip(axes, params, paths, ["b", "r"]):
    for line in grid.geoms:
        ax.plot(*line.xy, c="k", lw=.25)
    ax.scatter(*zip(*nodes), c="k")
    ax.plot(*path.xy, c=c)
    ax.set_title(f"Param={param}, length={path.length}")
    ax.set_aspect("equal")

chart of paths and nodes

or with cycle=True:

chart of paths and nodes

So it looks a bit like a bug to me at the moment.

Reasons:
  • Probably link only (1):
  • Long answer (-1):
  • Has code block (-0.5):
  • Self-answer (0.5):
  • Low reputation (0.5):
Posted by: user2950747