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
