Graphs - Gomory Hu tree - Memory blow up and max recursion depth [closed]

edit

Hello,

I am using the graphs part of Sage and encounter a problem using the Gomory Hu tree function, using the alogirthm FF.
Having a graph with more than 1000 vertices triggers the python max depth recursion limit (which I can increase), but being at the max default recursion depth already consumes 17GB of memory. Scaling this linear to the example graph of 30k vertices would require ~500GB of memory, which feels unreasonable, given that Gomory Hu is "just" an iterated min cut algorithm. Can someone help me? Am I using the function wrong?

from sage.all import *
from datetime import datetime
import psutil

# Initialize graph and get starting memory/time
s3 = graphs.SierpinskiGasketGraph(Integer(10))
start_time = datetime.now()
process = psutil.Process(os.getpid())
mem = process.memory_info()[0] / float(2 ** 20)
print("Mem usage at start:", mem, "MiB")
try:
    # Compute
    print("Vertices found:", s3.order(), "and edges:", s3.size())
    # s3.edge_cut(Integer(1), Integer(1000), value_only=True)  # exchange this line for memory comparison
    s3.gomory_hu_tree(algorithm="FF")
except Exception as error:
    print("Error detected:", error)
finally:
    end_time = datetime.now()
    print("Runtime =", end_time - start_time)
    mem = process.memory_info()[0] / float(2 ** 20)
    print("Mem usage at end:", mem, "MiB")

prints:

Mem usage at start: 258.6015625 MiB
Vertices found: 29526 and edges: 59049
Error detected: maximum recursion depth exceeded while calling a Python object
Runtime = 0:05:13.276101
Mem usage at end: 17661.28125 MiB

The max recursion depth error looks like this:

Traceback (most recent call last):
  File "/home/telijas/Documents/python/projects/treewidth-playground/main.py", line 22, in <module>
    s3.gomory_hu_tree(algorithm="FF")
  File "/home/telijas/anaconda3/envs/pythonProject/lib/python3.11/site-packages/sage/graphs/graph.py", line 8592, in gomory_hu_tree
    g = self._gomory_hu_tree(frozenset(self.vertex_iterator()), algorithm=algorithm)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/telijas/anaconda3/envs/pythonProject/lib/python3.11/site-packages/sage/graphs/graph.py", line 8493, in _gomory_hu_tree
    gV_tree = gV._gomory_hu_tree(vertices & frozenset(gV), algorithm=algorithm)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/telijas/anaconda3/envs/pythonProject/lib/python3.11/site-packages/sage/graphs/graph.py", line 8493, in _gomory_hu_tree
    gV_tree = gV._gomory_hu_tree(vertices & frozenset(gV), algorithm=algorithm)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/telijas/anaconda3/envs/pythonProject/lib/python3.11/site-packages/sage/graphs/graph.py", line 8493, in _gomory_hu_tree
    gV_tree = gV._gomory_hu_tree(vertices & frozenset(gV), algorithm=algorithm)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

OS: Ubuntu 22.04.5 LTS
Sage: 10.4
CPU: 3.6 GHz single core