Linear time implementation of lex_BFS()

[ddestrada]

The current implementation of lex_BFS() is quadratic, which is not optimal. The usual way to do it in linear time is through a clever use of doubly linked lists, but in (1) there is a way with static arrays, which I coded in Python.

There is one thing, though: in (2) there is a new algorithm for is_interval() that avoids PQ-trees, and just uses various passes of lex_BFS() (implemented with doubly linked lists). So maybe in the long run it would be better to do it with doubly linked lists in Cython.

(1) Habib, McConnell?, Paul and Viennot. Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing. TCS 234, 2000.

(2) Corneil, Olariu and Stewart. The LBFS Structure and Recognition of Interval Graphs. SIAMDM 23(4), 2009.

[ncohen]

Hello Diego !!!

Same comment (see #11738) for this patch about the "build/" folder. I also expect that this patch breaks doctests in Sage's library, so please check it too, correcting the doctests themselves if it makes sense :-)

Nathann

[ddestrada]

Replying to ncohen: Thank you! Here I fixed the "build/" thing, but I'm having trouble running the tests (in OSX 10.7 and Ubuntu 11.04), so expect it to break some of them. I'm sorry.

[ncohen]

Thank you! Here I fixed the "build/" thing, but I'm having trouble running the tests (in OSX 10.7 and Ubuntu 11.04), so expect it to break some of them. I'm sorry.

Perhaps I can help you with this test problem ? The thing is that right now the patch does not seem to work :

sage: graphs.RandomInterval(30).is_interval()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/ncohen/sage/devel/sage-3/sage/graphs/<ipython console> in <module>()

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_interval(self, certificate)
   9606         # by the way :-)
   9607 
-> 9608         if not self.is_chordal():
   9609             return False
   9610 

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_chordal(self, certificate)
   9492         for v in peo:
   9493 
-> 9494             if t_peo.out_degree(v)>0:
   9495 
   9496                 x = t_peo.neighbor_out_iterator(v).next()

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/digraph.pyc in out_degree(self, vertices, labels)
   1176             return di
   1177         else:
-> 1178             return list(self.out_degree_iterator(vertices, labels=labels))
   1179 
   1180     def out_degree_iterator(self, vertices=None, labels=False):

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/digraph.pyc in out_degree_iterator(self, vertices, labels)
   1221                 yield (v, d)
   1222         else:
-> 1223             for v in vertices:
   1224                 d = 0
   1225                 for e in self.outgoing_edge_iterator(v):

TypeError: 'int' object is not iterable
sage: graphs.RandomInterval(30).is_interval()
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

/home/ncohen/sage/devel/sage-3/sage/graphs/<ipython console> in <module>()

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_interval(self, certificate)
   9606         # by the way :-)
   9607 
-> 9608         if not self.is_chordal():
   9609             return False
   9610 

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in is_chordal(self, certificate)
   9484                 return all( gg.is_chordal() for gg in self.connected_components_subgraphs() )
   9485 
-> 9486         peo,t_peo = self.lex_BFS(tree=True)
   9487 
   9488         g = self.copy()

/home/ncohen/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in lex_BFS(self, reverse, tree, initial_vertex)
  11617                 if subslice[a] < old_k:
  11618                     subslice[a] = k
> 11619                     slice_head[k] = l
  11620                     k += 1
  11621                 slice_of[l] = subslice[a]

IndexError: list assignment index out of range

On random interval graphs sometimes the is_interval function works, sometimes it does not... ^^;

I tested you patch after having applied #11738 and #11735 but I do not think this is where the bug comes from. Could you also add some comments to your code, along with a reference to the paper you are following for this implementation ? :-)

Nathann

[ddestrada]

Replying to ncohen: Hello Nathann, I think the bug is now fixed (it was a very simple mistake). I added the reference, but the comments are still missing. Thanks!

[ncohen]

Hello !!

This patch still produces many errors when running the doctests...

sage -t  "devel/sage-3/sage/graphs/generic_graph.py"        
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9412:
    sage: (2*g).is_chordal()
Exception raised:
    Traceback (most recent call last):
      File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/ncohen/.Sage/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_137[6]>", line 1, in <module>
        (Integer(2)*g).is_chordal()###line 9412:
    sage: (2*g).is_chordal()
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9474, in is_chordal
        return all( gg.is_chordal() for gg in self.connected_components_subgraphs() )
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9474, in <genexpr>
        return all( gg.is_chordal() for gg in self.connected_components_subgraphs() )
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9488, in is_chordal
        if t_peo.out_degree(v)>0 and g.neighbors(v) not in neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/digraph.py", line 1178, in out_degree
        return list(self.out_degree_iterator(vertices, labels=labels))
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/digraph.py", line 1223, in out_degree_iterator
        for v in vertices:
    TypeError: 'int' object is not iterable
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9436:
    sage: hole
Expected:
    Subgraph of (Petersen graph): Graph on 5 vertices
Got:
    Subgraph of (Petersen graph): Graph on 4 vertices
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9438:
    sage: hole.is_isomorphic(graphs.CycleGraph(5))
Expected:
    True
Got:
    False
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9554:
    sage: g.is_interval()
Expected:
    True
Got:
    False
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9562:
    sage: d = g.is_interval(certificate = True)
Exception raised:
    Traceback (most recent call last):
      File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
...

Perhaps we can help with your problem running doctests ? It something does not work on this side, it is another bug of Sage's ! ;-)

Nathann

[dcoudert]

I was ready to help with the doctests issues, but I'm unable to install the patch on sage-5.0.beta9.

[ddestrada]

Replying to dcoudert:

I was ready to help with the doctests issues, but I'm unable to install the patch on sage-5.0.beta9.

Hello! I'm sorry I disappeared. I will fix this in the next few days.

[ddestrada]

I think this patch is working now and passes all the doctests. I'm sure the errors I get while doctesting are bugs of Sage 4.8 (for example, on both Ubuntu 10.10 and OS X 10.7 I get an error in line 15146 of generic_graph.py: "ValueError?: Database has no tablegraph_data.").

[ncohen]

Helloooooo Diego !!

I'm sorry but your patch can not be applied on top of the latest release of Sage, that is sage-5.0-beta11 (​https://groups.google.com/d/topic/sage-release/XnyN3tx4Bow/discussion). Plenty of stuff has been added in the 5.0-beta? series, and that is probably the explanation :-)

About your path, though : it removes the old code that computed (more slowly) a BFS ordering for the vertices. This being said, I think this code could still be useful to ... check that the new algorithm actually returns a correct BFS ordering ! Of course, as it is slower, this ordering should not be checked by default, but it would be nice to be able to run doctests which check for each computation of BFS ordering whether this ordering is indeed correct. This can be done by actually checking in turn that each vertex of the ordering is maximal at the moment when it is removed.

Do you think it could be possible to comment your code a bit more ? As it is, reading the paper to understand what happens seems to be the only alternative :-)

Nathann

[git]

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

​588c431

trac #11736: convert hg patch to git

[dcoudert]

Hello,

This patch has been sleeping for very very long time.

I did a first git version of the patch with some corrections. This is far from final version and we have currently 2 implementations to ease tests. To use the new version, you need to set parameter new_version=True.

Since the code has no comments, it is hard to know whats going on. I have corrected at least one bug (a missing j = l), but I have the following issue:

sage: g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2))
sage: g.lex_BFS(reverse=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=True, new_version=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=False)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
sage: g.lex_BFS(reverse=False, new_version=True)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]

The new version is more consistant (and also way faster). Furthermore, on this example, both reverse orderings are correct. However, when making the new version the default one, many tests for is_chordal and is_interval are broken.

Any help is welcome.

David.

[git]

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

​12fdf75

Merge branch 'public/11736' in 7.5.b1

[git]

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

​9064386

trac 11736 pep8