Opened 4 years ago
Closed 4 years ago
#23210 closed enhancement (fixed)
immediate dominators and strong articulation points
Reported by:  dcoudert  Owned by:  

Priority:  minor  Milestone:  sage8.1 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  cb1811a (Commits, GitHub, GitLab)  Commit:  cb1811a160fb92426feed3ab093ed93973fbd06e 
Dependencies:  Stopgaps: 
Description (last modified by )
Adds methods immediate_dominators
and strong_articulation_points
for directed graphs.
 The
immediate_dominators
is essentially the same as the NetworkX method. I tried to implement more recent algorithms [1], but the running times were not so good.  The
strong_articulation_points
is as presented in [2].
I let the strong_bridges
method for another ticket.
[1] Loukas Georgiadis. LinearTime Algorithms for Dominators and Related Problems, PhD thesis, Princetown University, (2005). ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
[2] Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science, 447, 74–84 (2012).
Change History (16)
comment:1 Changed 4 years ago by
 Branch set to u/dcoudert/23210
 Commit set to e054cdde472974fc554dd1779a95ef17589ed89c
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from e054cdde472974fc554dd1779a95ef17589ed89c to 43b3970232fe9ab49fb75a28b4aefc0c966a7c19
Branch pushed to git repo; I updated commit sha1. New commits:
43b3970  trac #23210: fix issues in the documentation

comment:3 Changed 4 years ago by
Quick comments:
 Use
r
instead ofroot
in the doc as it gives better latex.  No period (full stop) at the end here:
 ``root``  a vertex of the digraph, the root of the immediate dominators tree.
 ~if not root in self:
to
if root not in self:`.  Stylistic, but I prefer
SAP = []
toSAP = list()
as it is shorter (and IMO, cleaner)  How difficult would it be to modify
immediate_dominators
to have an argument to handle the reversed case? This would make it so you do not have to construct the reversedDiGraph
, which could be very costly in terms of time/memory. At least, this seems like it would be straightforward to do.
I will give more detailed comments later.
comment:4 Changed 4 years ago by
 Commit changed from 43b3970232fe9ab49fb75a28b4aefc0c966a7c19 to 6ce69d316c261a00797b5c1a2c3621ea70a1a837
Branch pushed to git repo; I updated commit sha1. New commits:
6ce69d3  trac #23210: reviewers comments

comment:5 Changed 4 years ago by
Thank you for your comments.
To handle the reversed case in immediate_dominators
, we need a reversed (or backward) depth first search. This is currently implemented only for the c_graph
backend.
What I can do is to check in immediate_dominators
if the backend is c_graph
and raise an error if it is not the case and the reverse parameter is True. Then, in the strong_articulation_points
method, I can make a copy of the digraph using the c_graph
backend if self uses a different backend.
I will also have to check the backend used in strongly_connected_component_subgraphs
.
Do you have other suggestions?
comment:6 Changed 4 years ago by
Another issue: the current code is not working with immutable graphs...
comment:7 Changed 4 years ago by
Ah, right, reversing a dfs is not the same thing on the reverse graph. Then don't worry about it; premature optimization, root of all evil, and whatnot.
comment:8 Changed 4 years ago by
Since I have to take care of 1) immutable graphs and 2) that I should not modify the input graph (I'm currently removing/adding edges to test if r
is a SAP, I must:
 if the input graph is strongly connected: make a mutable copy, preferably using a backend with the reverse DFS option
 for each strongly connected component, get a mutable subgraph, preferably using the good backend
Then in method immediate_dominators
, I could add a parameter reverse
that could be used only if the backend has the desirable method (otherwise raise an error).
do you have other suggestions before I start modifying the code?
comment:9 Changed 4 years ago by
 Commit changed from 6ce69d316c261a00797b5c1a2c3621ea70a1a837 to 08a35a9824ddde635d742c7e57797618c5eaa5a9
comment:10 Changed 4 years ago by
This should solve our issues.
comment:11 Changed 4 years ago by
Ready to review
comment:12 Changed 4 years ago by
 Commit changed from 08a35a9824ddde635d742c7e57797618c5eaa5a9 to cb1811a160fb92426feed3ab093ed93973fbd06e
comment:13 Changed 4 years ago by
 Description modified (diff)
 Milestone changed from sage8.0 to sage8.1
comment:14 Changed 4 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Sorry for letting this drop off my radar. LGTM.
comment:15 Changed 4 years ago by
Thank you Travis.
comment:16 Changed 4 years ago by
 Branch changed from u/dcoudert/23210 to cb1811a160fb92426feed3ab093ed93973fbd06e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #23210: add method immediate_dominators to DiGraph
trac #23210: add method strong_articulation_points to DiGraph
trac #23210: add entry to module documentation
trac #23210: biblio and documentation