Implement LexM traversal

[giorgosgiapis]

The algorithm is described here: http://dept-info.labri.fr/~gavoille/article/DG07. Using this traversal we can approximate the tree-length of an arbitrary graph. The complexity of this algorithm will be O(nm) where n is the number of vertices and m the number of edges if implemented properly in Cython.

Component: graph theory

Keywords: gsoc19

Author: Georgios Giapitzakis Tzintanos

Branch/Commit: aed4aac

Reviewer: David Coudert

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

[giorgosgiapis]

Branch: public/graphs/28271_implement_lexM

[giorgosgiapis]

Changed branch from public/graphs/28271_implement_lexM to none

[giorgosgiapis]

Branch: u/gh-giorgosgiapis/lexM

[giorgosgiapis]

Changed branch from u/gh-giorgosgiapis/lexM to public/graphs/28271_implement_lexM

[giorgosgiapis]

Changed branch from public/graphs/28271_implement_lexM to none

[giorgosgiapis]

Branch: public/graphs/28271_implement_lexM

[sagetrac-git]

Commit: 24a6fc2

[sagetrac-git]

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

fe62167	Added LexUP
e15a4c6	Added LexUP traversal
08b55aa	Added proper description for LexUP
42266b4	Revert "Added proper description for LexUP"
e8653df	Added description and reference for LexUP
acaaf6f	Added Lex Down traversal
9836457	fixed typos and added alias for lex_DOWN in generic_graph.py
5bb3dd9	Added SEEALSO blocks
f27f600	Added wikipedia reference for lex_BFS
24a6fc2	Added description for LexM

[sagetrac-git]

Changed commit from 24a6fc2 to 32b970b

[sagetrac-git]

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

32b970b

improved description

[sagetrac-git]

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

550b376	Fixed typo in comment
ce5208c	Merge branch 'u/gh-giorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM
a110585	Added doctests
cbb7da0	Merge branch 'u/gh-giorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM
636b9e7	First implementation of LexM

[sagetrac-git]

Changed commit from 32b970b to 636b9e7

[giorgosgiapis]

comment:10

This implementation of lexM is far from OK but some comments and thoughts on the algorithm and the way it is implemented would be very helpful.

[giorgosgiapis]

comment:11

I think that this method should only work for undirected graphs since triangulation and tree decomposition are only meaningful in undirected graphs. Also, the tree parameter is not useful since LexM doesn't produce a spanning tree like all the other traversals do.

[dcoudert]

comment:12

It's not easy to check the validity of the code. Can you comment it.
You tried to follow the algorithm from Dourisboure and Gavoille, right ? It's not easy to recognize it.

I tried the algorithm and I doubt it is correct. For a PetersenGraph, the ordering is 0, 1, .., 9.

Also I don't like the way you manipulate strings. You could directly have string labels, no ?

You should read the original paper by Rose, Tarjan and Luecker 1976 https://epubs.siam.org/doi/10.1137/0205021 .
It provides other algorithms.

I have now a working implementation of the algorithms in sections 4 and 5.3. Both versions give same orders, but the one of section 5.3 is of course way faster. I'm not claiming the orders I produce are correct. Not easy to guess what the output should be.

I will push my code to save you time, but before if want to understand what you did and if there is an error and where. So please add some comments.

[giorgosgiapis]

comment:13

Replying to @dcoudert:

It's not easy to check the validity of the code. Can you comment it.
You tried to follow the algorithm from Dourisboure and Gavoille, right ? It's not easy to recognize it.

I tried the algorithm and I doubt it is correct. For a PetersenGraph, the ordering is 0, 1, .., 9.

Also I don't like the way you manipulate strings. You could directly have string labels, no ?

The reason I didn't choose to have string labels in the first place is that the labels will be used for the tree decomposition later so strings would only make the parsing harder. Also, the conversion to string is needed if we want to use C++ queue.

You should read the original paper by Rose, Tarjan and Luecker 1976 https://epubs.siam.org/doi/10.1137/0205021 .
It provides other algorithms.

I have now a working implementation of the algorithms in sections 4 and 5.3. Both versions give same orders, but the one of section 5.3 is of course way faster. I'm not claiming the orders I produce are correct. Not easy to guess what the output should be.

I will push my code to save you time, but before if want to understand what you did and if there is an error and where. So please add some comments.

The general idea is that when we assign a number to a vertex we start a BFS-like procedure from that vertex. In the queue, we are keeping two things: the vertex and the maximum label in the path from our initial vertex to this one. We take care of the case when a vertex is already numbered or examined earlier (if int_neighbor in vertices and not int_neighbor in seen:).

[dcoudert]

comment:14

What you want to do with this string is not correct. See the example below where the second label is larger than the first one (lexicographic order).

sage: label = [[9, 2], [10, 2]]
sage: s0 = "".join(str(code) for code in label[0])
sage: s1 = "".join(str(code) for code in label[1])
sage: s0, s1, s0 > s1, label[0] > label[1]
('92', '102', True, False)

[giorgosgiapis]

comment:15

I see now. I should find another way to do it.

[giorgosgiapis]

comment:16

Well, I found one solution:

sage: label = [[9, 2], [10, 2]]
sage: s0 = ",".join(str(code) for code in label[0])
sage: s1 = ",".join(str(code) for code in label[1])
sage: l1 = list(map(int, s0.split(",")))
sage: l2 = list(map(int, s1.split(",")))
sage: label[0], label[1], l1, l2
([9, 2], [10, 2], [9, 2], [10, 2])

[sagetrac-git]

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

1bb95ba

Fixed string conversion

[sagetrac-git]

Changed commit from 636b9e7 to 1bb95ba

[giorgosgiapis]

comment:18

Do you have any examples with graphs and their corresponding LexM orderings to test my code? I could create some but if there are any verified examples it would help me a lot.

[dcoudert]

comment:19

In the paper by Rose, Tarjan and Luecker, there is this graph G = Graph({1: [2, 5], 2: [3, 4, 6], 3: [7], 4: [5, 6, 8], 5: [8], 6: [7, 9], 7: [9], 8: [9]}), but I'm not sure we can get the same labels.

[sagetrac-git]

Changed commit from 67d9787 to 6a0ad02

[sagetrac-git]

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

6a0ad02

Moved method lex_M from generic_graph.py to traversals.pyx

[sagetrac-git]

Changed commit from 6a0ad02 to a5ee6e6

[sagetrac-git]

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

6ba9df6	trac #28271: Merged with 8.9.beta7
a5ee6e6	trac #28271: reviewer edit

[dcoudert]

comment:55

I did some corrections. Please check. I you agree, you can set to positive review on my behalf.

[giorgosgiapis]

comment:56

Seems OK. Let's wait for the Patchbot. If all tests pass I will set to positive review.

[dcoudert]

comment:57

There is an error when building the html documentation. Could be

-    :meth:`~lex_M` | Return an ordering of the vertices of G according the LexM graph traversal.
+    :meth:`~GenericGraph.lex_M` | Return an ordering of the vertices of G according the LexM graph traversal.

Please check

[sagetrac-git]

Changed commit from a5ee6e6 to f9009b4

[sagetrac-git]

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

f9009b4

Fixed docstring

[sagetrac-git]

Changed commit from f9009b4 to 614e901

[sagetrac-git]

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

719cdd0	trac #28271: fix construction of html documentation
dd9a1c5	trac #28271: small improvements
614e901	trac #28271: further improvements

[dcoudert]

comment:60

I suspect you have not even tried to build the documentation and check if it looks good...

I have done several corrections. Please check.

[giorgosgiapis]

comment:61

I can't seem to get the documentation to build on my MacBook and I currently don't have access to my desktop. I will post to sage-devel about it.

[sagetrac-git]

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

a13dda7

Exception handling

[sagetrac-git]

Changed commit from 614e901 to a13dda7

[giorgosgiapis]

comment:63

I have added exceptions for when initial_vertex is not a graph vertex.

[dcoudert]

comment:64

why using str(initial_vertex) ? I don't think it's needed.

[sagetrac-git]

Changed commit from a13dda7 to 4add441

[sagetrac-git]

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

4add441

minor improvement

[giorgosgiapis]

comment:66

Replying to @dcoudert:

why using str(initial_vertex) ? I don't think it's needed.

You are right. Fixed!

[dcoudert]

comment:67

You have again not tested your commit !!!

-        ValueError: 'foo' is not a graph vertex dad
+        ValueError: 'foo' is not a graph vertex

and everywhere:

-        Traceback (most recent call last)
+        Traceback (most recent call last):

[sagetrac-git]

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

aed4aac

Fixed doctests

[sagetrac-git]

Changed commit from 4add441 to aed4aac

[dcoudert]

comment:69

LGTM.

[vbraun]

Changed branch from public/graphs/28271_implement_lexM to aed4aac