Opened 6 years ago
Closed 6 years ago
#15181 closed enhancement (fixed)
Treewidth (lazy implementation)
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 06277e4 (Commits) | Commit: | 06277e4d185a8f1c8de0e62d3f785eb6e15aca3a |
Dependencies: | Stopgaps: |
Description
This code is a veeeery lazy implementation of a very lazy algorithm to compute the treewidth of a graph. It can be greatly improved in at least two places.
If it is to be improved later, this implementation will probably remain useful anyway, as we try to always keep many of them alive, just to check whether they all return sound results. Hence it's not so bad if it is a bit wasteful :-P
And well. It's great to have this, too :-P
Nathann
Change History (12)
comment:1 Changed 6 years ago by
- Branch set to u/ncohen/15181
- Component changed from PLEASE CHANGE to graph theory
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
I can't really, for I define a function inside of the main function -- you can't do that in Cython -- and it would behave differently with respect to caching if I moved the function outside.
Plus we're not there yet... If there was a lot of doc to write it would be worth creating a module for only one function, but it isn't deserved here ;-)
Nathann
comment:4 Changed 6 years ago by
- Commit set to fad9254d311c815f25b80ce6103d1f7c916683da
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:fad9254] | Adds Graph.treewidth() |
comment:5 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 follow-up: ↓ 8 Changed 6 years ago by
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:
- The description of outputs is incomplete. A call to
G.treewidth()
returns the treewidth. - 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
- It could be useful to add simple tests such as
if G.is_tree(): return 1
orif G.is_clique(): return G.order()-1
.
- 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.
- Typos:
- tree-decompostion itself -> tree-decomposition itself
comment:8 in reply to: ↑ 7 Changed 6 years ago by
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:
- The description of outputs is incomplete. A call to
G.treewidth()
returns the treewidth.
Right. Fixed.
- You should add examples/tests such as:
Done.
- It could be useful to add simple tests such as
if G.is_tree(): return 1
orif 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 !
- 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
comment:9 Changed 6 years ago by
- Commit changed from fad9254d311c815f25b80ce6103d1f7c916683da to 06277e4d185a8f1c8de0e62d3f785eb6e15aca3a
comment:10 Changed 6 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
I agree that the code is cleaner that way. Adding special tricks could be done later. This implementation will serve as a reference for future additions.
I don't have additional comments. The patch is working correctly, the documentation is OK, we have several tests, etc. So I give positive review ;-)
comment:11 Changed 6 years ago by
Thaaaaaaaaaaaaaanks !
Nathann
comment:12 Changed 6 years ago by
- Branch changed from u/ncohen/15181 to 06277e4d185a8f1c8de0e62d3f785eb6e15aca3a
- Resolution set to fixed
- Status changed from positive_review to closed
Hello,
Since I have not yet started to use git (yes, I'm lazy too), it will take some time before I will be able to review this patch.
However, I have a first remark: you should not add the function to graph.py, but to some treewidth.py or treewidth.pyx file into the
graph_decompositions
directory. This is just to gather methods.David.