Linear time implementation of lex_BFS()

[diegode]

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.

CC: @dcoudert @kliem @orlitzky

Component: graph theory

Keywords: lexbfs

Author: Diego de Estrada, David Coudert

Branch/Commit: 332fb8b

Reviewer: Michael Orlitzky

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

[nathanncohen]

comment:4

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

[diegode]

Attachment: linear_lex_bfs.patch.gz

[diegode]

comment:6

Replying to @nathanncohen:
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.

[nathanncohen]

comment:7

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

[diegode]

comment:8

Replying to @nathanncohen:
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!

[orlitzky]

comment:30

Is it feasible to generate a small random graph, feed it to both algorithms, and check that their outputs agree in a doctest? That would go a long way towards ensuring that the newer implementation is correct (or at least as correct as the old one).

[dcoudert]

comment:31

The difficulty is that we may have several valid orderings, even with same initial vertex, and that the 2 algorithms may produce different orderings
For instance:

sage: for i in range(100): 
....:     G = graphs.RandomChordalGraph(10) 
....:     F = G.lex_BFS(initial_vertex=0, algorithm="fast") 
....:     S = G.lex_BFS(initial_vertex=0, algorithm="slow") 
....:     print(i, "fast", F) 
....:     print(i, "slow", S) 
....:     if S != F: 
....:         print(G.graph6_string()) 
....:         break 
....:                                                                                                                               
0 fast [0, 1, 5, 9, 6, 4, 7, 2, 8, 3]
0 slow [0, 1, 5, 9, 6, 4, 7, 2, 8, 3]
1 fast [0, 1, 4, 8, 2, 7, 9, 6, 3, 5]
1 slow [0, 1, 4, 8, 2, 7, 9, 6, 3, 5]
2 fast [0, 6, 7, 9, 8, 5, 1, 3, 2, 4]
2 slow [0, 6, 7, 9, 8, 1, 3, 5, 2, 4]
IAHSCEA_w

In this example, the last graph is not connected, but it's the same with connected graphs.
For instance, take a star with center 0. Then any permutation of the leaves lead to a valid lex BFS ordering.

One option could be to make an indirect doctest using is_chordal on a random chordal graph, but for that me must be able to specify the lex BFS algorithm to use in is_chordal. Not sure it's the best way.

But may be there is an other way to check that a lex BFS ordering is valid ?

[orlitzky]

comment:32

Ok, I see the problem. The paper "LexBFS-orderings and powers of graphs" (doi:10.1007/3-540-62559-3_15) has a characterization of LBFS orderings in Lemma 1 that looks pretty easy to implement. What do you think about an _is_lbfs(graph, order) function that could be used to test the outputs of the fast/slow algorithms? Both would return True when fed to _is_lbfs, I expect.

[tscrim]

comment:33

Minor comment outside of the scope of the ticket: You might be able to do this for a bit more speed:

-        def l_func(x):
-            return code[x]
 
         # The initial_vertex is at position 0 and so named 0 in sd
         code[0].append(n + 1)
         now = 1
         while vertices:
-            v = max(vertices, key=l_func)
+            v = max(vertices, key=code.__getitem__)

[sagetrac-git]

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

b9a3ec8	trac #11736: merge with 9.2.beta11
7609c66	trac #11736: add method to check validity of lexBFS ordering

[sagetrac-git]

Changed commit from 90d266e to 7609c66

[dcoudert]

comment:35

I have added a method to check that a lexBFS ordering is valid in (directed) graphs.
I'm not yet 100% convinced that it is enough to check this property, so if you are aware of other tests, let me know.

[orlitzky]

comment:36

We're working on getting rid of this, but for now, you have to call set_random_seed() at the beginning of every doctest where randomness is required (i.e. the ones you've just added). Otherwise the random number generator isn't actually random, and you'll wind up testing the same example every time the tests are run.

[orlitzky]

comment:37

Example:

The nonnegative orthant is a proper cone::

    sage: set_random_seed()
    sage: ambient_dim = ZZ.random_element(10)
    sage: K = cones.nonnegative_orthant(ambient_dim)
    sage: K.is_proper()
    True

[sagetrac-git]

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

52c355e

trac #11736: set random seed

[sagetrac-git]

Changed commit from 7609c66 to 52c355e

[dcoudert]

comment:39

Thank you. I didn't know that.

[orlitzky]

comment:40

I've been playing around with this, here are a few more suggestions:

1. You could use ZZ.random_element(G.num_verts()) instead of always 0 for the initial vertex in your random tests; that would improve coverage a bit.

2. The documentation for the cdef method isn't appearing in the reference manual for me (does anyone know if that's expected?). Since you put a lot of work into the docs for lex_BFS_fast_short_digraph, maybe you want to move them into the main lex_BFS docstring?

3. (Unrelated to this ticket) While you're in there, please add an extra : to the end of TESTS: in maximum_cardinality_search(). Right now sage doesn't recognize it as a doctest.

[sagetrac-git]

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

15a0419

trac #11736: review comments

[sagetrac-git]

Changed commit from 52c355e to 15a0419

[dcoudert]

comment:42

I have implemented your suggestions. For the algorithm, I made a copy of the description without suppressing it from the cdef method. I think it is easier this way for someone interested in this code to understand it.

[orlitzky]

comment:43

Thanks! Here are two more small things:

First, in the documentation for lex_BFS_fast_short_digraph (and now lex_BFS), there's a LaTeX typo at

S = `{u | i \leq \sigma(u) \leq j\}

The opening curly brace isn't escaped, so the formula isn't showing up.

Second, in _is_valid_lex_BFS_order, it looks to me like you've figured out the correct directions for the edges to make things work with a digraph, namely ca, cb, da, and db. However the docs still have some of them in a different order from when the result was stated for an undirected graph:

if `a < b < c` and `ac \in E` and `bc \not\in E`, then there exists `d\in V`                                                                                             
such that `c < d`, `bd \in E` and `ad \not\in E`.

[sagetrac-git]

Changed commit from 15a0419 to 332fb8b

[sagetrac-git]

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

332fb8b

trac #11736: fix documentation

[dcoudert]

comment:45

good catch. Hope it will be ok this time.

[orlitzky]

Reviewer: Michael Orlitzky

[orlitzky]

comment:46

This looks good to me now, unless anyone else wants to comment. I've checked the implementation of _is_valid_lex_BFS_order. It's "obviously correct" for undirected graphs, and probably for directed graphs too although I haven't been able to find the corresponding theorem for digraphs written down.

The implementation of lex_BFS_fast_short_digraph is less scrutable but looks reasonable now that I understand how the algorithm works. I trust the doctests more than I trust myself in any case. Since you've been working on this for 8 years I'm inclined to say let's get it over with.

[dcoudert]

comment:47

Thank you for your help.

To understand the fast algorithm, you need to understand that a slice is nothing else than a label. When creating a subslice of a slice from position p to position q, you place the vertices of the sub slice on positions p...p+I, and the remaining vertices of the original slice at positions p+I+1...q. So the vertices in the sub slice have a larger label than the other vertices of the original slice. The tricks are to associate a position with the current slice name, to maintain the head (left most vertex of a slice) of each slice, and give a name to each newly created subslice.

To check the property on directed graphs, its more tricky, but I'm convinced it is correct. An alternative to check the validity is to modify the slow algorith. That is, instead of selecting a vertex with largest label, we identify all candidates (vertices with same largest label), and check that the next vertex in the given order is in this pool of candidates, then select it, update labels of its neighbors and continue.
We can add that if needed in a future ticket.

[vbraun]

Changed branch from public/graphs/11736_lex_bfs to 332fb8b