#15181: Treewidth (lazy implementation)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.3
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | fad9254d311c815f25b80ce6103d1f7c916683da
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/15181 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Hello,
After a really long time, I finally have some time to review patchs.
I have successfully rebased this patch with current develop version
(6.3.beta8), compiled and executed the code. I have not yet tried to build
the documentation.
I have a few remarks:
1. The description of outputs is incomplete. A call to {{{G.treewidth()}}}
returns the treewidth.
2. You should add examples/tests such as:
{{{
sage: graphs.PetersenGraph().treewidth(k=2)
False
sage: graphs.PetersenGraph().treewidth(k=6)
True
sage: graphs.Grid2DGraph(2,5).treewidth()
2
sage: graphs.Grid2DGraph(3,5).treewidth()
3
sage: graphs.PetersenGraph().treewidth(certificate=True).is_tree()
True
sage: graphs.PetersenGraph().treewidth(k=3,certificate=True)
False
sage: graphs.PetersenGraph().treewidth(k=4,certificate=True)
Graph on 7 vertices
}}}
3. It could be useful to add simple tests such as {{{if G.is_tree():
return 1}}} or {{{if G.is_clique(): return G.order()-1}}}.
4. How can I double check the results?? The results are correct for all
the graphs I have tried and for which I know the treewidth. This could of
course be done later, e.g., when a tree_decomposition module will be
created with alternative methods.
5. Typos:
- tree-decompostion itself -> tree-decomposition itself
--
Ticket URL: <http://trac.sagemath.org/ticket/15181#comment:7>
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.
