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: 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 dcoudert)

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 4 years ago by dcoudert

  • Branch set to u/dcoudert/23210
  • Commit set to e054cdde472974fc554dd1779a95ef17589ed89c
  • Description modified (diff)
  • Status changed from new to needs_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 4 years ago by git

  • Commit changed from e054cdde472974fc554dd1779a95ef17589ed89c to 43b3970232fe9ab49fb75a28b4aefc0c966a7c19

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

43b3970trac #23210: fix issues in the documentation

comment:3 Changed 4 years ago by tscrim

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

  • Commit changed from 43b3970232fe9ab49fb75a28b4aefc0c966a7c19 to 6ce69d316c261a00797b5c1a2c3621ea70a1a837

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

6ce69d3trac #23210: reviewers comments

comment:5 Changed 4 years ago by dcoudert

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 dcoudert

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

comment:7 Changed 4 years ago by tscrim

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 dcoudert

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 git

  • Commit changed from 6ce69d316c261a00797b5c1a2c3621ea70a1a837 to 08a35a9824ddde635d742c7e57797618c5eaa5a9

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 4 years ago by dcoudert

This should solve our issues.

comment:11 Changed 4 years ago by dcoudert

Ready to review

comment:12 Changed 4 years ago by git

  • Commit changed from 08a35a9824ddde635d742c7e57797618c5eaa5a9 to cb1811a160fb92426feed3ab093ed93973fbd06e

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 4 years ago by dcoudert

  • Description modified (diff)
  • Milestone changed from sage-8.0 to sage-8.1

comment:14 Changed 4 years ago by tscrim

  • 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 dcoudert

Thank you Travis.

comment:16 Changed 4 years ago by vbraun

  • Branch changed from u/dcoudert/23210 to cb1811a160fb92426feed3ab093ed93973fbd06e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.