Opened 9 years ago
Closed 8 years ago
#12874 closed enhancement (fixed)
Recognition of Comparability graphs and Permutation graphs
Reported by: | ncohen | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-5.1 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-5.1.beta2 | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12816, #12872 | Stopgaps: |
Description (last modified by )
This ticket is a bit large, but everything inside is related. Here is what it does :
- Creates a module graph/comparability.pyx whose purpose is to contain everything related to comparability graphs, and to permutation graphs (which are comparability graphs).
- Implements two recognition algorithms for comparability graphs, the first one being a greedy algorithm and the second an integer linear program, made to check the results from the first one
- Adds a
is_transivite
function to DiGraph? objects
- Updated Graph.is_bipartite so that it can return negative certificates (odd cycles)
- Add a PermutationGraph? constructor, that lets one build a Permutation graph from a permutation
- A crazy amount of documentation
A few notes :
- This patch may be long, but I tried to make it very clean. In particular, results are checked many, many times before being returned, and there are two versions of the main algorithm (is_comparability) so that we can easily track wrong results that may (in some magical way) get through the cracks.
- This ticket depends on #12872, which I wrote while working on this patch.
- My first intent was to write a *real implementation* for this recognition algorithm, and use the greedy one to check the results. As writing this greedy algorithm was already not that straightforward (and I also had to learn how it worked from a few papers) I did not write a "more efficient version", and this implementation is pretty "lose" with ressources. I think this can be done in a later patch, considering that the results from the greedy algorithms can already be checked by the Linear Program, and that the present patch is already large enough
:-)
Heeeeeeeeeeeeeere it is !!!!!!!!!
Oh, and funnily enough the OEIS does not contain the "number of comparability graphs on n vertices" or the "number of permutation graphs on n vertices". And there does not seem to be any code on internet to do that kind of work.
Attachments (1)
Change History (20)
comment:1 Changed 9 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Dependencies set to 12872
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 9 years ago by
- Dependencies changed from 12872 to #12872
- Reviewers set to David Coudert
comment:3 in reply to: ↑ 2 Changed 9 years ago by
- Dependencies changed from #12872 to #12872, #12872
Hellooooooo !!!
I have the following issues when installing the patch with 5.0.beta14
Argggggg !! Of course, I forgot to add 12872 as a dependency !
Also, the file
distances_all_pairs.pxd
is not part of this patch.
-_-
And of course I removed beta13 and installed beta14 since. Well, at least this file is short. It happened once to me when I rewrote the whole GLPK backend. I sent the patch without adding the file to mercurial, and I deleted the branch.
Patch updated ! :-)
Nathann
comment:4 Changed 9 years ago by
- Dependencies changed from #12872, #12872 to #12816, #12872
I'm now able to install the patch and all tests pass.
I have a warning in docbuild:
docstring of sage.graphs.comparability.is_permutation:72: WARNING: Literal block expected; none found.
Also, in sage/graphs/pq_trees.py, you could put 'Authors'.
Last, I have corrected the dependencies ;-)
comment:5 Changed 9 years ago by
Hellooooooooo !!!
Oh, right. That's fixed :-)
And about the bold in authors : I had a patch refused recently because of that. It was #12816, actually :-)
Nathann
comment:6 Changed 9 years ago by
I still have the same warning. Missing refresh?
comment:7 Changed 9 years ago by
Nope O_o I increased the indentation level in the NOTE field of is_permutation, and it looks like the patch I uploaded is good. I'll give it a try on my machine again.
comment:8 Changed 9 years ago by
Ok now Sphinx does not want to rebuild the doc, I have to recompile Sage. -_-
Nathann
comment:9 Changed 9 years ago by
Sorry about that.
In function is_comparability, you have:
EXAMPLE::
I suppose you can remove one :
In function is_permutation, you have:
... break Then with MILP:: Trying random permutations, first with the greedy algorithm:: sage: from sage.graphs.comparability import is_permutation
Removing "Trying random permutations, first with the greedy algorithm::" solves the docbuild problem.
Apparently, indentation can also be improved in many places in the file, but I don't know how critical are the spaces before the sage: blah
in examples and tests.
comment:10 Changed 9 years ago by
Hellooooooooo !!
With this patch (without the 'trying random permutation [...]' line) I get no warning. I hope that it does not mean I should reinstall Sage again :-D
Nathann
comment:11 Changed 9 years ago by
The documentation is now build without warnings and is well displayed. However, I found some typos.
In comparability.pyx
- "incmparable" -> "incomparable"
- "paralell" -> "parallel"
- "thee two edges" -> "the two edges" or "these two edges"
- "tranitive" -> "transitive"
- "i.e" -> "i.e."
- "cocomparability" -> "co-comparability" (x2)
- In the documentation, the sentence "But the Bull graph is" appears without ":" at the end, but the sentence "The 5-cycle or the Petersen Graph are not transitively orientable:" has. This is certainly due to white space between "But the Bull graph is" and "::" in the source code.
- "Beware, for this implementation is unable to return negative certificates" -> "Beware, this implementation is unable to return negative certificates !"
- "returned indeed create the expected" -> "returned indeed creates the expected" ?
Some methods have examples but no tests. Are examples handled as tests when applying tests to the module ?
In graph.py
- lines 2500 - 2502 could be put in 80 cols
- line 2514 - ... : why are your using lists that are later converted to sets? shouldn't you directly use sets ?
comment:12 Changed 9 years ago by
Fixed !
Nathann
comment:13 follow-up: ↓ 14 Changed 9 years ago by
In comparability.pyx:
- "greedy_is_comparability": instead of using both variables cu and cv, you could use index j in second loop and then call directly h.add_edge( (u,i), (v,j) ). OK, your choice.
- "greedy_is_comparability_with_certificate": it would be nicer to use "gg = g.copy()" rather than "g = g.copy()". This is correct but...
- is_transitive": something is missing in the for loops since you always test the first n values of the distances array. May be a c_distances = c_distances+n?
In graph.py:
- in the example with RandomGNP graph, I suggest to add a set_random_seed(some value you like) before. Although the probability for having a bipartite graph is extremely low, it is not null ;)
- "for w in self.neighbors(v)" -> "for w in self.neighbor_iterator(v)" ?
Last, you could remove empty lines after """.
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 9 years ago by
Hellooooo !!
- "greedy_is_comparability": instead of using both variables cu and cv, you could use index j in second loop and then call directly h.add_edge( (u,i), (v,j) ). OK, your choice.
Done.
- "greedy_is_comparability_with_certificate": it would be nicer to use "gg = g.copy()" rather than "g = g.copy()". This is correct but...
I really do not think it makes any difference, but I did it anyway :-P
- is_transitive": something is missing in the for loops since you always test the first n values of the distances array. May be a c_distances = c_distances+n?
Oh my GOD O_O;;;
In graph.py:
- in the example with RandomGNP graph, I suggest to add a set_random_seed(some value you like) before. Although the probability for having a bipartite graph is extremely low, it is not null ;)
I should always use Petersen's graph in the examples.
- "for w in self.neighbors(v)" -> "for w in self.neighbor_iterator(v)" ?
Done.
Last, you could remove empty lines after """.
I only found an empty line in the last method of comparability.pyx, if that is what you had in mind I removed it.
Nathann
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 9 years ago by
You need a coffee ;-)
I really do not think it makes any difference, but I did it anyway
:-P
- is_transitive": something is missing in the for loops since you always test the first n values of the distances array. May be a c_distances = c_distances+n?
Oh my GOD
O_O;;;
Well, now there is a # in front of c_distances += n, so no difference.
Last, you could remove empty lines after """.
I only found an empty line in the last method of comparability.pyx, if that is what you had in mind I removed it.
check in digraph.py, function is_transitive
comment:16 in reply to: ↑ 15 Changed 9 years ago by
Patch updated again.
Nathann
Changed 9 years ago by
comment:17 Changed 9 years ago by
- Status changed from needs_review to positive_review
All long tests pass, the doc is built and displayed correctly, and I have no other remarks on the code. I give positive review.
comment:18 Changed 9 years ago by
Thaaaaaaaaaanks ! :-)
Nathann
comment:19 Changed 8 years ago by
- Merged in set to sage-5.1.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
I have the following issues when installing the patch with 5.0.beta14
Also, the file
distances_all_pairs.pxd
is not part of this patch.