Recognition of Comparability graphs and Permutation graphs

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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.

Depends on #12816 Depends on #12872

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-5.1.beta2

Issue created by migration from https://trac.sagemath.org/ticket/12874

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Dependencies: 12872

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Author: Nathann Cohen

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1 +1,19 @@
+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.

[dcoudert]

Changed dependencies from 12872 to #12872

[dcoudert]

comment:2

I have the following issues when installing the patch with 5.0.beta14

compote:~/Soft/sage-5.0.beta14/devel/sage-myclone> more sage/graphs/digraph.py.rej 
--- digraph.py
+++ digraph.py
@@ -69,6 +69,7 @@
     :delim: |

     :meth:`~DiGraph.is_directed_acyclic` | Returns whether the digraph is acyclic or not.
+    :meth:`~DiGraph.is_transitive` | Returns whether the digraph is transitive or not.
     :meth:`~DiGraph.level_sets` | Returns the level set decomposition of the digraph.
     :meth:`~DiGraph.topological_sort_generator` | Returns a list of all topological sorts of the digraph if it is acyclic
     :meth:`~DiGraph.topological_sort` | Returns a topological sort of the digraph if it is acyclic
compote:~/Soft/sage-5.0.beta14/devel/sage-myclone> more sage/graphs/pq_trees.py.rej
--- pq_trees.py
+++ pq_trees.py
@@ -4,8 +4,20 @@
 This module implements PQ-Trees and methods to help recognise Interval
 Graphs. It is used by :meth:`is_interval
 <sage.graphs.generic_graph.GenericGraph.is_interval>`.
+
+Author:
+
+- Nathann Cohen
+
 """

+################################################################################
+#      Copyright (C) 2012 Nathann Cohen <nathann.cohen@gail.com>               #
+#                                                                              #
+# Distributed  under  the  terms  of  the  GNU  General  Public  License (GPL) #
+#                         http://www.gnu.org/licenses/                         #
+################################################################################
+
 # Constants, to make the code more readable

 FULL           = 2

Also, the file distances_all_pairs.pxd is not part of this patch.

compote:~/Soft/sage-5.0.beta14/devel/sage-myclone> ../../sage -b

----------------------------------------------------------
sage: Building and installing modified Sage library files.

Installing c_lib
scons: `install' is up to date.
Updating Cython code....
Traceback (most recent call last):
  File "setup.py", line 830, in <module>
    queue = compile_command_list(ext_modules, deps)
  File "setup.py", line 790, in compile_command_list
    dep_file, dep_time = deps.newest_dep(f,m)
  File "setup.py", line 697, in newest_dep
    for f in self.all_deps(filename, ext_module):
  File "setup.py", line 678, in all_deps
    for f in self.immediate_deps(filename, ext_module):
  File "setup.py", line 660, in immediate_deps
    self._deps[filename] = self.parse_deps(filename, ext_module)
  File "setup.py", line 648, in parse_deps
    raise IOError, msg
IOError: could not find dependency sage/graphs/distances_all_pairs.pxd included in sage/graphs/comparability.pyx.
Error installing modified sage library code.

[dcoudert]

Reviewer: David Coudert

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:3

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Changed dependencies from #12872 to #12872, #12872

[dcoudert]

comment:4

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 ;-)

[dcoudert]

Changed dependencies from #12872, #12872 to #12816, #12872

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

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

[dcoudert]

comment:6

I still have the same warning. Missing refresh?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

Ok now Sphinx does not want to rebuild the doc, I have to recompile Sage. -_-

Nathann

[dcoudert]

comment:9

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

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

[dcoudert]

comment:11

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 ?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

Fixed !

Nathann

[dcoudert]

comment:13

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 """.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:14

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

[dcoudert]

comment:15

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:16

Patch updated again.

Nathann

[dcoudert]

comment:17

Attachment: trac_12874.patch.gz

All long tests pass, the doc is built and displayed correctly, and I have no other remarks on the code. I give positive review.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:18

Thaaaaaaaaaanks ! :-)

Nathann

[jdemeyer]

Merged: sage-5.1.beta2