Opened 8 years ago

Closed 7 years ago

#17711 closed enhancement (fixed)

Pre-processing for vertex separation

Reported by: dcoudert Owned by:
Priority: minor Milestone: sage-6.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:

Status badges

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 pre-processing method based on the decomposition of the input digraph into strongly connected components.

Change History (15)

comment:1 Changed 8 years ago by dcoudert

  • Branch set to u/dcoudert/17711/preprocessing

comment:2 Changed 8 years ago by dcoudert

  • Branch changed from u/dcoudert/17711/preprocessing to public/17711

comment:3 Changed 8 years ago by git

  • Commit set to f62716539aaf4c236041d1e31dbf59bcb8bba750

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

ea87914trac #17647: change best_seq from int array to list
8d243ddtrac #17647: reduce the number of temporary bitsets
2f0bf7atrac #17647: update some comments
0bd12bftrac #17647: review commit
cfc96a0Merge branch 'public/17647b' of git://trac.sagemath.org/sage into tmp
8c666aetrac#17711: expose BAB in vertex_separation
62dd7c8trac#17711: Let MILP work with Graph as well
f6f4975trac#17711: Let exp work with Graph as well
d1b63batrac#17711: Let lower_bound to work with Graph as well and clean lots of tests
f627165trac#17711: adds decomposition into strongly connected components

comment:4 Changed 8 years ago by dcoudert

  • 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 follow-up: Changed 8 years ago by ncohen

  • 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 while g.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) (when G 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 in digraphs.<tab> ? O_O

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 8 years ago by dcoudert

Replying to ncohen:

Yooooooooooooo !

Does the job, very few comments (and a small commit at public/17711b):

  • Calling is_strongly_connected is very cheap while g.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) (when G 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

  1. test if the graph is connected. If not, then apply the algorithm on each connected component.
  2. 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 in digraphs.<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 ncohen

So you propose that I

  1. test if the graph is connected. If not, then apply the algorithm on each connected component.
  2. 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 ressource-consuming) 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 dcoudert

  • Branch changed from public/17711 to public/17711b
  • Commit changed from f62716539aaf4c236041d1e31dbf59bcb8bba750 to 085a3cddacc561236db1fde9d42b97eaa085b764

New commits:

085a3cdtrac #17711: Mostly removing trailing whitespaces

comment:9 Changed 8 years ago by git

  • Commit changed from 085a3cddacc561236db1fde9d42b97eaa085b764 to 0d9da78b0d3f7d7ba6caa74f5e51eec82f218302

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

0d9da78trac #17711: handle connected components

comment:10 follow-up: Changed 8 years ago by dcoudert

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

  • Commit changed from 0d9da78b0d3f7d7ba6caa74f5e51eec82f218302 to 6baf83e733555c22f287692f107eec954e494d59

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

6baf83etrac #17711: minor edit

comment:12 Changed 8 years ago by dcoudert

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 ncohen

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

Thanks.

comment:15 Changed 7 years ago by vbraun

  • Branch changed from public/17711b to 6baf83e733555c22f287692f107eec954e494d59
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.