Opened 4 years ago

Closed 4 years ago

#25030 closed enhancement (fixed)

Use boost dominator_tree instead of immediate_dominators

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

Status badges

Description (last modified by dcoudert)

Ticket #23210 adds immediate_dominators method for DiGraph while the Boost method dominator_tree provides the same result and is significantly faster.

With this ticket, we:

  • enable the computation of the dominator tree in the reverse graph. This is done by adding parameter reverse to methods initializing boost graphs
  • use dominator_tree in method strong_articulation_points
  • deprecate method immediate_dominators that is slower and do less than the dominator_tree method.

Change History (5)

comment:1 Changed 4 years ago by dcoudert

  • Branch set to u/dcoudert/25030_use_dominator_tree
  • Cc tscrim added
  • Commit set to 58d90e359fe11a61c42e965bddfb49e398e2d418
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Use boost dominator_tree for immediate_dominators to Use boost dominator_tree instead of immediate_dominators

New commits:

​4c9d8eatrac #25030: add parameter reverse to boost graph
​cc14d3dtrac #25030: use boost dominator tree for strong articulation points
​58d90e3trac #25030: deprecate method immediate_dominators

comment:2 Changed 4 years ago by git

  • Commit changed from 58d90e359fe11a61c42e965bddfb49e398e2d418 to 71bad7c5e2c05f5ec924eb08b79fca150186526f

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

​71bad7ctrac #25030: Merged with 8.3.beta0

comment:3 Changed 4 years ago by dcoudert

  • Milestone changed from sage-8.2 to sage-8.3

comment:4 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:5 Changed 4 years ago by vbraun

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