#18839: Boost Dominator Tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_info
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 | 20a8625d9085eea4a3851471d2df2aa59e76703b
Dependencies: #18811, #18564 | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_info
Comment:
Now it's working and I'm trying to understand the expected behavior of the
method.
- is it normal that the resulting tree is always a star ?
{{{
sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: H = G.dominator_tree(0, return_dict=False)
sage: H.is_tree() and H.diameter()<=2
True
sage: H = G.dominator_tree(193, return_dict=False)
sage: H.is_tree() and H.diameter()<=2
True
}}}
- I suggest to set parameter `return_dict=False` by default. Well I don't
know which is the most useful
- There is a labeling problem with the root.
{{{
sage: G = graphs.Grid2dGraph(4,4)
sage: G.dominator_tree((0,0), return_dict=False).vertices()
[0,
(0, 1),
(0, 2),
(0, 3),
(1, 0),
(1, 1),
(1, 2),
(1, 3),
(2, 0),
(2, 1),
(2, 2),
(2, 3),
(3, 0),
(3, 1),
(3, 2),
(3, 3)]
sage: G.dominator_tree((1,1), return_dict=False).vertices()
[5,
(0, 0),
(0, 1),
(0, 2),
(0, 3),
(1, 0),
(1, 2),
(1, 3),
(2, 0),
(2, 1),
(2, 2),
(2, 3),
(3, 0),
(3, 1),
(3, 2),
(3, 3)]
}}}
- Try also this. The output digraph is not connected and you have some
labeling problems.
{{{
sage: D = digraphs.DeBruijn(2,4)
sage: D.dominator_tree('0000', return_dict=False).show()
}}}
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/18839#comment:27>
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.
