First time here? Check out the FAQ!

Ask Your Question
1

Error while computing gomory hu tree of graph using LP [closed]

asked 0 years ago

Telijas gravatar image

updated 0 years ago

Max Alekseyev gravatar image

Hello,

I have an issue with the Gomory Hu tree computation and hope that someone can help me. I load a graph and pass it to the gomory hu tree computation function using the algorithm „LP“, after around 10 seconds I get the following error and the computation aborts.

Traceback (most recent call last):
  File ".../treewidth-playground/main.py", line 13, in <module>
    hu = graph.gomory_hu_tree(algorithm="LP")
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/.../anaconda3/envs/sage2/lib/python3.11/site-packages/sage/graphs/graph.py", line 8697, in gomory_hu_tree
    g = self._gomory_hu_tree(frozenset(self.vertex_iterator()), algorithm=algorithm)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/.../anaconda3/envs/sage2/lib/python3.11/site-packages/sage/graphs/graph.py", line 8579, in _gomory_hu_tree
    for uu, vv, capacity in edges:
        ^^^^^^^^^^^^^^^^
ValueError: not enough values to unpack (expected 3, got 2)

an executable example can be found here under the tag „Sage_question_01“: https://gitlab.com/Telijas/treewidth-...

The applications basically consists of loading the graph and applying the algorithm:

import load.file_loader as file_loader
import processing.process
from sage.all import *

# file_name = "./resources/USA-road-d.NY.gr"
file_name = "./resources/AProVE07-03.gaifman.gr"


graph = file_loader.load(file_name)
print("Vertices found:", graph.order(), "and edges:", graph.size())
print("Start computation of gomory hu")
hu = graph.gomory_hu_tree(algorithm="LP")
print("Done computation of gomory hu")
print("Done")
Preview: (hide)

Closed for the following reason the question is answered, right answer was accepted by Telijas
close date 2024-09-26 23:11:03.864653

1 Answer

Sort by » oldest newest most voted
1

answered 0 years ago

Max Alekseyev gravatar image

It's a bug in Sage. I've reported it at https://github.com/sagemath/sage/issu... Meanwhile, please use other values for algorithm - e.g., algorithm='FF'.

Preview: (hide)
link

Comments

Thanks a lot for the help and effort in simplifying the example.

Telijas gravatar imageTelijas ( 0 years ago )

Question Tools

1 follower

Stats

Asked: 0 years ago

Seen: 235 times

Last updated: Sep 25 '24