#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 ncohen):
Yooooooooooo !!
> After a really long time, I finally have some time to review patchs.
Wow ! I am glad to see something happen on this ticket. I even forgot it
was in `needs_review`... `:-P`
> I have a few remarks:
> 1. The description of outputs is incomplete. A call to
{{{G.treewidth()}}} returns the treewidth.
Right. Fixed.
> 2. You should add examples/tests such as:
Done.
> 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}}}.
This I did not do for two reasons:
1) In order to deal with a specific kind of input graph you do not only
need to know the treewidth but also to input a decomposition directly in
the code, in case the user asks for the treedecomposition itself. It is
not complicated to do in those cases indeed, but it means adding a lot of
lines for easy cases. I don't mind particularly, but it makes it less
appealing, and there is also 2)
2) Somehow those two cases are partially handled already, as when `k=None`
the implementation uses the max clique as a lower bound on the treewidth.
So its first guess on the treewidth of these two instances is already
right, and it will not waste so much time on this input.
Tell me what you think !
> 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.
Ahahahah. Well, yes, I guess that the only way to check the output for
harder instances is to read the code 1000 times, and to try to add more
implementations. There is so much litterature about treewidth problem that
we must have several algorithms to compute it !
> - tree-decompostion itself -> tree-decomposition itself
Done.
Thanks for your work on that !
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15181#comment:8>
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.
