Opened 8 years ago
Closed 7 years ago
#17711 closed enhancement (fixed)
Preprocessing for vertex separation
Reported by:  dcoudert  Owned by:  

Priority:  minor  Milestone:  sage6.5 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  David Coudert  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  6baf83e (Commits, GitHub, GitLab)  Commit:  6baf83e733555c22f287692f107eec954e494d59 
Dependencies:  #17647  Stopgaps: 
Description
This patch cleans the module sage.graphs.graph_decompositions.vertex_separation
to expose the new branch and bound algorithm #17647 and other methods into the vertex_separation
method, as for the path_decomposition
method. It makes the branch and bound the default method since it is the fastest one. It also adds a generic preprocessing method based on the decomposition of the input digraph into strongly connected components.
Change History (15)
comment:1 Changed 8 years ago by
 Branch set to u/dcoudert/17711/preprocessing
comment:2 Changed 8 years ago by
 Branch changed from u/dcoudert/17711/preprocessing to public/17711
comment:3 Changed 8 years ago by
 Commit set to f62716539aaf4c236041d1e31dbf59bcb8bba750
comment:4 Changed 8 years ago by
 Cc ncohen added
 Dependencies set to #17647
 Status changed from new to needs_review
Unless I mixed up something with my commits, this patch is ready to be reviewed.
comment:5 followup: ↓ 6 Changed 8 years ago by
 Status changed from needs_review to needs_info
Yooooooooooooo !
Does the job, very few comments (and a small commit at public/17711b
):
 Calling
is_strongly_connected
is very cheap whileg.strongly_connected_components_digraph
actually copies the whole graph
sage: g=digraphs.DeBruijn(5,3) sage: %timeit g.is_strongly_connected() 10000 loops, best of 3: 129 µs per loop sage: %timeit g.strongly_connected_components_digraph() 1000 loops, best of 3: 1.31 ms per loop
Better to only copy it if necessary.
 Is there any reason why you only deal with digraphs ?
Digraph(G)
(whenG
is a graph) is not always strongly connected:G
may not be connected. The same code could handle everything at once, couldn't it ?
 (unrelated) what on earth is this
random_DAG
function doing in the global namespace instead of being indigraphs.<tab>
?O_O
Nathann
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 8 years ago by
Replying to ncohen:
Yooooooooooooo !
Does the job, very few comments (and a small commit at
public/17711b
):
 Calling
is_strongly_connected
is very cheap whileg.strongly_connected_components_digraph
actually copies the whole graphsage: g=digraphs.DeBruijn(5,3) sage: %timeit g.is_strongly_connected() 10000 loops, best of 3: 129 µs per loop sage: %timeit g.strongly_connected_components_digraph() 1000 loops, best of 3: 1.31 ms per loopBetter to only copy it if necessary.
 Is there any reason why you only deal with digraphs ?
Digraph(G)
(whenG
is a graph) is not always strongly connected:G
may not be connected. The same code could handle everything at once, couldn't it ?
So you propose that I
 test if the graph is connected. If not, then apply the algorithm on each connected component.
 If G is directed, test if is strongly connected. If not, then apply the algorithm on each scc
Is that correct?
 (unrelated) what on earth is this
random_DAG
function doing in the global namespace instead of being indigraphs.<tab>
?O_O
I had the same remark while reviewing patch #12181 (and certainly other tickets). Nothing has been done since. I don't even know where is the code. In fact, we have many random<TAB> stuff in global namespace...
David.
comment:7 in reply to: ↑ 6 Changed 8 years ago by
So you propose that I
 test if the graph is connected. If not, then apply the algorithm on each connected component.
 If G is directed, test if is strongly connected. If not, then apply the algorithm on each scc
I had something simpler (and a it more ressourceconsuming) in mind: 1) If you have a graph, test if it is connected. If it is not, turn it into a digraph 2) Now the scc code for digraphs will handle each connected component independently
So you get it for free, more or less.
I had the same remark while reviewing patch #12181 (and certainly other tickets). Nothing has been done since. I don't even know where is the code. In fact, we have many random<TAB> stuff in global namespace...
Pffff.. It comes from the "sandpile" module and I am not even sure that any of that code is useful to anything.
Plus I am not very eager to move 'random_DAG' to digraphs.<tab>
because I do not agree with the way it generates the random dag. Also, some random 'weights' are involved.
I will probably end up removing the imports into the global namespace, and that will be all.
I'll cc you if I do.
Nathann
comment:8 Changed 8 years ago by
 Branch changed from public/17711 to public/17711b
 Commit changed from f62716539aaf4c236041d1e31dbf59bcb8bba750 to 085a3cddacc561236db1fde9d42b97eaa085b764
New commits:
085a3cd  trac #17711: Mostly removing trailing whitespaces

comment:9 Changed 8 years ago by
 Commit changed from 085a3cddacc561236db1fde9d42b97eaa085b764 to 0d9da78b0d3f7d7ba6caa74f5e51eec82f218302
Branch pushed to git repo; I updated commit sha1. New commits:
0d9da78  trac #17711: handle connected components

comment:10 followup: ↓ 13 Changed 8 years ago by
 Status changed from needs_info to needs_review
I have implemented an alternative approach preventing conversion Graph to DiGraph?. I hope you will like it.
David.
comment:11 Changed 8 years ago by
 Commit changed from 0d9da78b0d3f7d7ba6caa74f5e51eec82f218302 to 6baf83e733555c22f287692f107eec954e494d59
Branch pushed to git repo; I updated commit sha1. New commits:
6baf83e  trac #17711: minor edit

comment:12 Changed 8 years ago by
Sorry, I erased some of your modifications in my last commit. This is corrected.
comment:13 in reply to: ↑ 10 Changed 8 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
I have implemented an alternative approach preventing conversion Graph to DiGraph?. I hope you will like it.
Perfect!
Thanks,
Nathann
comment:14 Changed 8 years ago by
Thanks.
comment:15 Changed 7 years ago by
 Branch changed from public/17711b to 6baf83e733555c22f287692f107eec954e494d59
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
trac #17647: change best_seq from int array to list
trac #17647: reduce the number of temporary bitsets
trac #17647: update some comments
trac #17647: review commit
Merge branch 'public/17647b' of git://trac.sagemath.org/sage into tmp
trac#17711: expose BAB in vertex_separation
trac#17711: Let MILP work with Graph as well
trac#17711: Let exp work with Graph as well
trac#17711: Let lower_bound to work with Graph as well and clean lots of tests
trac#17711: adds decomposition into strongly connected components