longest.py

from math import sqrt
from graphillion import GraphSet as gs

universe = [
  # 1
  ('1', '2', 1.0),
  ('1', '4', 1.0),
  ('1', '5', sqrt(2)),
  ('1', '6', sqrt(3)),
  ('1', '8', sqrt(3)),
  # 2
  ('2', '4', sqrt(2)),
  ('2', '7', sqrt(3)),
  ('2', '5', 1.0),
  ('2', '3', 1.0),
  ('2', '9', sqrt(3)),
  ('2', '6', sqrt(2)),
  # 3
  ('3', '4', sqrt(3)),
  ('3', '5', sqrt(2)),
  ('3', '8', sqrt(3)),
  ('3', '6', 1.0),
  # 4
  ('4', '5', 1.0),
  ('4', '7', 1.0),
  ('4', '8', sqrt(2)),
  ('4', '9', sqrt(3)),
  # 5
  ('5', '6', 1.0),
  ('5', '7', sqrt(2)),
  ('5', '8', 1.0),
  ('5', '9', sqrt(2)),
  # 6
  ('6', '7', sqrt(3)),
  ('6', '8', sqrt(2)),
  ('6', '9', 1),
  # 7
  ('7', '8', 1.0),
  # 8
  ('8', '9', 1.0),
]
gs.set_universe(universe)

all_node = range(1, 10)

max_weight = 0.0
longest_path = None
start_end = None

for start in all_node:
  for end in all_node:
    if start == end:
      continue

    paths = gs.paths(str(start), str(end))
    longer_path = list(next(paths.max_iter()))

    weight = 0.0
    for edge in longer_path:
      weight += next(w[2] for w in universe if w[0] == edge[0] and w[1] == edge[1])

    if weight >= max_weight:
      start_end = (start, end)
      max_weight = weight
      longest_path = longer_path

print(start_end)
print(max_weight)
print(longest_path)