Opened 7 years ago

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

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)

trac_12874.patch (45.7 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 7 years ago by ncohen

  • Authors set to Nathann Cohen
  • 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: Changed 7 years ago by dcoudert

  • Dependencies changed from 12872 to #12872
  • Reviewers set to David Coudert

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.

comment:3 in reply to: ↑ 2 Changed 7 years ago by ncohen

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

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

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 7 years ago by dcoudert

I still have the same warning. Missing refresh?

comment:7 Changed 7 years ago by ncohen

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

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

Nathann

comment:9 Changed 7 years ago by dcoudert

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

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 7 years ago by dcoudert

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

Fixed !

Nathann

comment:13 follow-up: Changed 7 years ago by dcoudert

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: Changed 7 years ago by ncohen

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: Changed 7 years ago by dcoudert

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

Patch updated again.

Nathann

Changed 7 years ago by ncohen

comment:17 Changed 7 years ago by dcoudert

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

Thaaaaaaaaaanks ! :-)

Nathann

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.