#18839: Boost Dominator Tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Dominator tree, | Merged in:
Boost | Reviewers: Nathann Cohen, David
Authors: Michele Borassi | Coudert
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/borassi/boost_dominator_tree | 512cfdf27fc1bd53f0bc3e06ba032fd23895ac01
Dependencies: #18811, #18564 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dcoudert):
Replying to [comment:31 borassi]:
> Hellooooo!
>
> Replying to [comment:30 dcoudert]:
>
> > So for undirected graphs, we can first test if is it connected. If
true, then we can directly construct and return the star (or the dict)
without using boost, right? If False, then what's the output ?
>
> Well, not connected but biconnected.
OK, I see. Could you mention this in the description of the method? and
perhaps add a simple example of a graph with 2 biconnected components. For
Instance
{{{
sage: G = 2*graphs.CycleGraph(3)
sage: G.add_edge(0,3)
sage: G.dominator_tree(0, return_dict=True)
{0: None, 1: 0, 2: 0, 3: 0, 4: 3, 5: 3}
}}}
> In any case, probably the dominator tree in the undirected case can be
found by computing biconnected components and cut vertices. There is a
linear algorithm for biconnected components, but it is not very easy to
implement, and the Boost algorithm is O(m log m), which is not much worse
than O(m). Is the linear algorithm for BCC implemented in the
hyperbolicity algorithm?
For undirected graphs, we have `B,C = G.blocks_and_cut_vertices()`, where
`B` is the list of blocks (list of vertices of each biconnected component)
and `C` is the list of cut vertices. It's a Python implementation, but
it's efficient. We use it for the hyperbolicity and many other algorithms.
However, now that I have a better understanding of the method, I think it
is better to let it as it is. So improve the doc and it should be ok.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/18839#comment:32>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
