non recursive version of method `gomory_hu_tree` for graphs

[dcoudert]

trafficstars

This PR implements a non recursive version of method gomory_hu_tree for graphs. This fixes the max recursion depth error reported in https://ask.sagemath.org/question/79577/graphs-gomory-hu-tree-memory-blow-up-and-max-recursion-depth/. The memory consumption is seriously reduced.

Without this PR:

sage: def test(g):
....:     from datetime import datetime
....:     import psutil
....:     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:
....:         print("Vertices found:", g.order(), "and edges:", g.size())
....:         T = g.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")
....: 
sage: test(graphs.SierpinskiGasketGraph(5))
Mem usage at start: 241.0234375 MiB
Vertices found: 123 and edges: 243
Runtime = 0:00:00.243477
Mem usage at end: 252.1171875 MiB
sage: test(graphs.SierpinskiGasketGraph(6))
Mem usage at start: 252.1171875 MiB
Vertices found: 366 and edges: 729
Runtime = 0:00:02.050924
Mem usage at end: 324.30078125 MiB
sage: test(graphs.SierpinskiGasketGraph(7))
Mem usage at start: 324.30078125 MiB
Vertices found: 1095 and edges: 2187
Runtime = 0:00:21.207451
Mem usage at end: 968.97265625 MiB
sage: test(graphs.SierpinskiGasketGraph(8))
Mem usage at start: 950.25390625 MiB
Vertices found: 3282 and edges: 6561
Error detected: maximum recursion depth exceeded
Runtime = 0:04:36.154550
Mem usage at end: 6767.39453125 MiB

With this PR

sage: test(graphs.SierpinskiGasketGraph(5))
Mem usage at start: 246.0859375 MiB
Vertices found: 123 and edges: 243
Runtime = 0:00:00.219925
Mem usage at end: 246.7109375 MiB
sage: test(graphs.SierpinskiGasketGraph(6))
Mem usage at start: 247.0234375 MiB
Vertices found: 366 and edges: 729
Runtime = 0:00:01.900761
Mem usage at end: 248.2734375 MiB
sage: test(graphs.SierpinskiGasketGraph(7))
Mem usage at start: 248.5859375 MiB
Vertices found: 1095 and edges: 2187
Runtime = 0:00:18.535145
Mem usage at end: 252.4921875 MiB
sage: test(graphs.SierpinskiGasketGraph(8))
Mem usage at start: 253.1171875 MiB
Vertices found: 3282 and edges: 6561
Runtime = 0:02:57.325506
Mem usage at end: 265.15234375 MiB
sage: test(graphs.SierpinskiGasketGraph(9))
Mem usage at start: 263.625 MiB
Vertices found: 9843 and edges: 19683
Runtime = 0:29:03.321870
Mem usage at end: 296.8359375 MiB
sage: test(graphs.SierpinskiGasketGraph(10))
Mem usage at start: 303.11328125 MiB
Vertices found: 29526 and edges: 59049
Runtime = 5:01:45.355463
Mem usage at end: 399.3984375 MiB

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [ ] I have created tests covering the changes.
• [x] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

[github-actions[bot]]

Documentation preview for this PR (built with commit b844daadecf3200b3da49f191ff69310d07c444e; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[dcoudert]

@maxale, this is ready to be reviewed.

[dimpase]

I'm slow to respond in the coming few days. We've just moved Oxford U. -> Northwestern U.