Opened 3 years ago

Closed 3 years ago

#26342 closed enhancement (fixed)

Improve triconnectivity algorithm: avoid recursive calls

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.4
Component: graph theory Keywords:
Cc: meghanamreddy, saiharsh, tscrim Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 2e0ddb3 (Commits, GitHub, GitLab) Commit: 2e0ddb3e8aa7532e3c82c468aba82c8e8cf11e8f
Dependencies: Stopgaps:

Status badges

Description (last modified by dcoudert)

Maximum recursion depth can be reached when applying the spqr_tree method on large graphs. We improve the code by avoiding recursive calls.

This is a follow up to #25598.

Change History (10)

comment:1 Changed 3 years ago by dcoudert

  • Branch set to public/26342_remove_recursion_in_triconnectivity
  • Commit set to 5dc9457a76bade840649a6748a89e4ea235d377f

It remains to remove recursion in __path_search. Feel free to do it if you know how :P


New commits:

5dc9457trac #26342: remove recursion in dfs1, dfs2 and path_finder

comment:2 Changed 3 years ago by git

  • Commit changed from 5dc9457a76bade840649a6748a89e4ea235d377f to 3b60c34080b0ef194deccef72459637974693241

Branch pushed to git repo; I updated commit sha1. New commits:

3b60c34trac #26342: remove recursion in path_search

comment:3 Changed 3 years ago by dcoudert

  • Description modified (diff)
  • Status changed from new to needs_review

It was quite frightening to modify __path_search, but I did it ! I tried the new version on quite large graphs and I'm confident on the results.

sage: G = graphs.RandomBarabasiAlbert(10000, 3)
sage: G.order(), G.size()
(10000, 29991)
sage: %time T = G.spqr_tree()
CPU times: user 2.13 s, sys: 68.9 ms, total: 2.2 s
Wall time: 2.2 s
sage: T.vertices()
[('R', Multi-graph on 10000 vertices)]
sage: for u,v in G.edges(labels=False):  # long
....:     G.add_path([u, G.add_vertex(), v])
....:     
sage: G.order(), G.size()
(39991, 89973)
sage: %time T = G.spqr_tree()
CPU times: user 17.8 s, sys: 722 ms, total: 18.5 s
Wall time: 18.7 s
sage: T
SPQR-tree of : Graph on 59983 vertices
sage: from collections import Counter
sage: Counter(u[0] for u in T)
Counter({'P': 29991, 'S': 29991, 'R': 1})
sage: for u,v in G.edges(labels=False): # extremely long
....:     G.add_path([u, G.add_vertex(), v])
....:     
sage: G.order(), G.size()
(129964, 269919)
sage: %time T = G.spqr_tree()
CPU times: user 1min 1s, sys: 5.65 s, total: 1min 7s
Wall time: 1min 8s
sage: Counter(u[0] for u in T)
Counter({'S': 119964, 'P': 89973, 'R': 1})
Last edited 3 years ago by dcoudert (previous) (diff)

comment:4 Changed 3 years ago by git

  • Commit changed from 3b60c34080b0ef194deccef72459637974693241 to 154bcdef24b6d8cd29defa9b463a7859ca20cea1

Branch pushed to git repo; I updated commit sha1. New commits:

154bcdeSome trivial Cythonization and doc improvements.

comment:5 Changed 3 years ago by git

  • Commit changed from 154bcdef24b6d8cd29defa9b463a7859ca20cea1 to 2e0ddb3e8aa7532e3c82c468aba82c8e8cf11e8f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2e0ddb3Some trivial Cythonization and doc improvements.

comment:6 Changed 3 years ago by tscrim

  • Cc tscrim added
  • Reviewers set to Travis Scrimshaw

I did some trivial Cythonization (declaring obvious variable types), and I also did a bunch of doc improvements/standardizations (although almost all of them you cannot see because they are private methods). It is not surprising that my little Cythonization will make for great speed improvements, it is more of setup for the bigger overhaul (which rightly should be on a separate ticket). If my changes are good, then you can set a positive review.

8.4.beta6:

sage: G = graphs.JankoKharaghaniGraph(936)
sage: (G.order(), G.size())
(936, 175500)
sage: %time T = G.spqr_tree()
CPU times: user 6.22 s, sys: 96 ms, total: 6.32 s
Wall time: 6.3 s

Your branch:

sage: %time T = G.spqr_tree()
CPU times: user 6.38 s, sys: 108 ms, total: 6.49 s
Wall time: 6.45 s

My branch

sage: %time T = G.spqr_tree()
CPU times: user 6.27 s, sys: 124 ms, total: 6.4 s
Wall time: 6.34 s

comment:7 Changed 3 years ago by dcoudert

  • Status changed from needs_review to positive_review

Thank you Travis for the improvements. I will to do more Cythonization (e.g., using arrays instead of lists, turn the doubly linked list to some C/C++ data structure, etc.) in other tickets. The number of methods without doctest should also be reduced (to 0), which is not obvious for some internal methods. One step at a time ;)

comment:8 Changed 3 years ago by tscrim

Feel free to cc me and ask questions (I have done a fair bit of cythonization and picked up some tricks). For those helper methods, if you make them cdef, then you don't need to give them doctests. :)

comment:9 Changed 3 years ago by dcoudert

Noted :P

comment:10 Changed 3 years ago by vbraun

  • Branch changed from public/26342_remove_recursion_in_triconnectivity to 2e0ddb3e8aa7532e3c82c468aba82c8e8cf11e8f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.