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: |
Description (last modified by )
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 methodstrong_articulation_points
- deprecate method
immediate_dominators
that is slower and do less than thedominator_tree
method.
Change History (5)
comment:1 Changed 4 years ago by
- 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
comment:2 Changed 4 years ago by
- Commit changed from 58d90e359fe11a61c42e965bddfb49e398e2d418 to 71bad7c5e2c05f5ec924eb08b79fca150186526f
Branch pushed to git repo; I updated commit sha1. New commits:
71bad7c | trac #25030: Merged with 8.3.beta0
|
comment:3 Changed 4 years ago by
- Milestone changed from sage-8.2 to sage-8.3
comment:4 Changed 4 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to positive_review
LGTM.
comment:5 Changed 4 years ago by
- 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.
New commits:
trac #25030: add parameter reverse to boost graph
trac #25030: use boost dominator tree for strong articulation points
trac #25030: deprecate method immediate_dominators