Opened 5 years ago

Closed 5 years ago

#23210 closed enhancement (fixed)

immediate dominators and strong articulation points

Reported by: David Coudert Owned by:
Priority: minor Milestone: sage-8.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:

Status badges

Description (last modified by David Coudert)

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. Linear-Time 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 5 years ago by David Coudert

Branch: u/dcoudert/23210
Commit: e054cdde472974fc554dd1779a95ef17589ed89c
Description: modified (diff)
Status: newneeds_review

New commits:

e1ca86etrac #23210: add method immediate_dominators to DiGraph
1b4a759trac #23210: add method strong_articulation_points to DiGraph
59192bbtrac #23210: add entry to module documentation
e054cddtrac #23210: biblio and documentation

comment:2 Changed 5 years ago by git

Commit: e054cdde472974fc554dd1779a95ef17589ed89c43b3970232fe9ab49fb75a28b4aefc0c966a7c19

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

43b3970trac #23210: fix issues in the documentation

comment:3 Changed 5 years ago by Travis Scrimshaw

Quick comments:

  • Use r instead of root 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 = [] to SAP = 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 reversed DiGraph, 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 5 years ago by git

Commit: 43b3970232fe9ab49fb75a28b4aefc0c966a7c196ce69d316c261a00797b5c1a2c3621ea70a1a837

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

6ce69d3trac #23210: reviewers comments

comment:5 Changed 5 years ago by David Coudert

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 5 years ago by David Coudert

Another issue: the current code is not working with immutable graphs...

comment:7 Changed 5 years ago by Travis Scrimshaw

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 5 years ago by David Coudert

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 5 years ago by git

Commit: 6ce69d316c261a00797b5c1a2c3621ea70a1a83708a35a9824ddde635d742c7e57797618c5eaa5a9

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

ab1b167trac #23210: Merged with 8.0.beta10
b071c25trac #23210: cope with mutable graphs
08a35a9trac #23210: add reverse option to immediate_dominators

comment:10 Changed 5 years ago by David Coudert

This should solve our issues.

comment:11 Changed 5 years ago by David Coudert

Ready to review

comment:12 Changed 5 years ago by git

Commit: 08a35a9824ddde635d742c7e57797618c5eaa5a9cb1811a160fb92426feed3ab093ed93973fbd06e

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

4b4570dtrac #23210: Merged with 8.1.beta1
cb1811atrac #23210: move seealso blocks after examples + fix a typo

comment:13 Changed 5 years ago by David Coudert

Description: modified (diff)
Milestone: sage-8.0sage-8.1

comment:14 Changed 5 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Sorry for letting this drop off my radar. LGTM.

comment:15 Changed 5 years ago by David Coudert

Thank you Travis.

comment:16 Changed 5 years ago by Volker Braun

Branch: u/dcoudert/23210cb1811a160fb92426feed3ab093ed93973fbd06e
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.