Opened 6 years ago

Closed 5 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 ncohen

  • 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 dcoudert

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.

comment:3 Changed 6 years ago by ncohen

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 git

  • Commit set to fad9254d311c815f25b80ce6103d1f7c916683da

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:fad9254]Adds Graph.treewidth()

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 follow-up: Changed 5 years ago 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
    
  1. 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.
  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.
  1. Typos:
  • tree-decompostion itself -> tree-decomposition itself

comment:8 in reply to: ↑ 7 Changed 5 years ago 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.

  1. You should add examples/tests such as:

Done.

  1. 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 !

  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.

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 5 years ago by git

  • Commit changed from fad9254d311c815f25b80ce6103d1f7c916683da to 06277e4d185a8f1c8de0e62d3f785eb6e15aca3a

Branch pushed to git repo; I updated commit sha1. New commits:

02def56trac #15181: Merged with 6.3.beta8
06277e4trac #15181: Reviewer's remarks

comment:10 Changed 5 years ago by dcoudert

  • 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 5 years ago by ncohen

Thaaaaaaaaaaaaaanks !

Nathann

comment:12 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/15181 to 06277e4d185a8f1c8de0e62d3f785eb6e15aca3a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.