Opened 3 years ago
Closed 3 years ago
#28271 closed enhancement (fixed)
Implement LexM traversal
Reported by:  ghgiorgosgiapis  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  graph theory  Keywords:  gsoc19 
Cc:  Merged in:  
Authors:  Georgios Giapitzakis Tzintanos  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  aed4aac (Commits, GitHub, GitLab)  Commit:  aed4aaca2fffd851b5498fdc8f7f2fdeaf6463fb 
Dependencies:  Stopgaps: 
Description
The algorithm is described here: http://deptinfo.labri.fr/~gavoille/article/DG07. Using this traversal we can approximate the treelength 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.
Change History (70)
comment:1 Changed 3 years ago by
 Branch set to public/graphs/28271_implement_lexM
comment:2 Changed 3 years ago by
 Branch public/graphs/28271_implement_lexM deleted
comment:3 Changed 3 years ago by
 Branch set to u/ghgiorgosgiapis/lexM
comment:4 Changed 3 years ago by
 Branch changed from u/ghgiorgosgiapis/lexM to public/graphs/28271_implement_lexM
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
 Branch public/graphs/28271_implement_lexM deleted
 Status changed from needs_review to needs_work
comment:6 Changed 3 years ago by
 Branch set to public/graphs/28271_implement_lexM
comment:7 Changed 3 years ago by
 Commit set to 24a6fc205ec9fd70991a626d9201dc2decbef00d
comment:8 Changed 3 years ago by
 Commit changed from 24a6fc205ec9fd70991a626d9201dc2decbef00d to 32b970b14dd401192d0ffedce6183046d2a2d036
Branch pushed to git repo; I updated commit sha1. New commits:
32b970b  improved description

comment:9 Changed 3 years ago by
 Commit changed from 32b970b14dd401192d0ffedce6183046d2a2d036 to 636b9e7d4ca1b00efed62fef459be38a184eefbf
Branch pushed to git repo; I updated commit sha1. New commits:
550b376  Fixed typo in comment

ce5208c  Merge branch 'u/ghgiorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM

a110585  Added doctests

cbb7da0  Merge branch 'u/ghgiorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM

636b9e7  First implementation of LexM

comment:10 Changed 3 years ago by
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.
comment:11 Changed 3 years ago by
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.
comment:12 followup: ↓ 13 Changed 3 years ago by
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.
comment:13 in reply to: ↑ 12 Changed 3 years ago by
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 BFSlike 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:
).
comment:14 Changed 3 years ago by
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)
comment:15 Changed 3 years ago by
I see now. I should find another way to do it.
comment:16 Changed 3 years ago by
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])
comment:17 Changed 3 years ago by
 Commit changed from 636b9e7d4ca1b00efed62fef459be38a184eefbf to 1bb95ba7b5f699bb40984536c706decc2a4bb930
Branch pushed to git repo; I updated commit sha1. New commits:
1bb95ba  Fixed string conversion

comment:18 Changed 3 years ago by
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.
comment:19 Changed 3 years ago by
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.
comment:20 Changed 3 years ago by
 Commit changed from 1bb95ba7b5f699bb40984536c706decc2a4bb930 to 4ba625e82ed61cfa07ef9afe8f8fcd165d3f3841
comment:21 Changed 3 years ago by
 Reviewers set to David Coudert
I rebased on last beta and did small corrections on your method to make it compliant with Python 3 (I'm working with it).
I have also added my implementation of the same algorithm and a test method. We can remove that later if not needed. I hope it will be useful to correct your implementation as I think it is not correct.
comment:22 Changed 3 years ago by
 Dependencies #28195 deleted
No need for the dependency to #28195, as it is merged in 8.9.beta5.
comment:23 Changed 3 years ago by
Currently, I am having trouble building sage. When running make I am getting error cp: cannot overwrite directory with nondirectory
while building [gap4.10.2.p0]
. Should I post to sagedevel about it?
comment:24 Changed 3 years ago by
Yes, sagedevel is the right place.
comment:25 Changed 3 years ago by
My implementation is actually incorrect. I will try implementing the algorithm described in section 5.3 of the paper Rose.
comment:26 Changed 3 years ago by
The problem with the new implementation is that we cannot directly get the labels assigned to each vertex.
comment:27 Changed 3 years ago by
I will push my code for the algorithm in section 5.3.
Why do we need the labels ? The edges of the triangulation and the order are not enough ?
comment:28 Changed 3 years ago by
Don't we need the labels for the tree decomposition?
comment:29 Changed 3 years ago by
 Commit changed from 4ba625e82ed61cfa07ef9afe8f8fcd165d3f3841 to ebcab15a0147fa3c6e23ee3a8b7a44789caaebaa
Branch pushed to git repo; I updated commit sha1. New commits:
ebcab15  trac #28271: fast implementation of lex_M

comment:30 Changed 3 years ago by
I don't know, I have not checked how to build the treedecomposition from the output of lex_M
.
comment:31 Changed 3 years ago by
I thought that the labels give us a tree decomposition of the graph.
comment:32 Changed 3 years ago by
I guess we could start with this code, add examples and tests and then think about the labels.
comment:33 Changed 3 years ago by
So make a frontend lex_M
method with parameter algorithm
and keep both versions (slow and 53) plus the test function. Feel free to rename the methods if you have more suitable names in mind ;)
comment:34 Changed 3 years ago by
Good idea! I will work on it.
comment:35 Changed 3 years ago by
 Commit changed from ebcab15a0147fa3c6e23ee3a8b7a44789caaebaa to 24fd31438f5e6eb3acfecacd292572970ab55b28
Branch pushed to git repo; I updated commit sha1. New commits:
24fd314  Removed incorrect method and improved code and documentation

comment:36 Changed 3 years ago by
I have added INPUT
and OUTPUT
to all methods and also renamed them. We also raise an exception if the given graph is directed. I will also add examples and tests and then start working with the frontend.
comment:37 Changed 3 years ago by
 Commit changed from 24fd31438f5e6eb3acfecacd292572970ab55b28 to 1dd602dc88acc1f828e3f98a3de6e794ba16dff4
Branch pushed to git repo; I updated commit sha1. New commits:
1dd602d  Added examples and tests for all methods

comment:38 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:39 Changed 3 years ago by
I have added examples and tests for both methods. Maybe it would be better to implement the frontend in another ticket. Let me know what you think.
comment:40 Changed 3 years ago by
 Commit changed from 1dd602dc88acc1f828e3f98a3de6e794ba16dff4 to 9c1f8f1b4f34d1ff57483873e2b8f2f09b96dea6
Branch pushed to git repo; I updated commit sha1. New commits:
9c1f8f1  Fixed docstring

comment:41 Changed 3 years ago by
 Commit changed from 9c1f8f1b4f34d1ff57483873e2b8f2f09b96dea6 to 354b8175eab5984d9dcbe11ffececc77390d847a
Branch pushed to git repo; I updated commit sha1. New commits:
354b817  Docstring fix

comment:42 Changed 3 years ago by
The frontend must be in this ticket. No need for another ticket for that.
comment:43 Changed 3 years ago by
 Commit changed from 354b8175eab5984d9dcbe11ffececc77390d847a to df3e2908185381f369ab843075cc6142958f5e07
Branch pushed to git repo; I updated commit sha1. New commits:
df3e290  Added method lex_M in generic_graph.py

comment:44 Changed 3 years ago by
 Commit changed from df3e2908185381f369ab843075cc6142958f5e07 to 8aa1238ca10692db2b89d18e4fc0e3e6062eb818
Branch pushed to git repo; I updated commit sha1. New commits:
8aa1238  Fixed typo in docstring of lex_M_slow

comment:45 Changed 3 years ago by
 Commit changed from 8aa1238ca10692db2b89d18e4fc0e3e6062eb818 to 1f90673a23087e7064c84856513d1b6ce6112c09
Branch pushed to git repo; I updated commit sha1. New commits:
1f90673  Added citation

comment:46 Changed 3 years ago by
 Commit changed from 1f90673a23087e7064c84856513d1b6ce6112c09 to c3df64f3df62430eb2c2ab75bd394e0abd8a10fc
Branch pushed to git repo; I updated commit sha1. New commits:
c3df64f  Added description of method lex_M in generic_graph.py

comment:47 Changed 3 years ago by
 Commit changed from c3df64f3df62430eb2c2ab75bd394e0abd8a10fc to faea6a7b9dbd533a1b347c11016ba833d72aaa3a
Branch pushed to git repo; I updated commit sha1. New commits:
faea6a7  Added tests and examples in method lex_M of generic_graph.py

comment:48 Changed 3 years ago by
Everything is complete now. All methods are documented and have EXAMPLES
and TESTS
blocks. I can't, however, build the documentation (not because of this ticket) so if anyone can do this and confirm that it is displayed nicely it would be helpful.
comment:49 Changed 3 years ago by
 Commit changed from faea6a7b9dbd533a1b347c11016ba833d72aaa3a to 61ad77fcf2a3125542404ae3e139e6247efd337e
Branch pushed to git repo; I updated commit sha1. New commits:
61ad77f  Added doctest

comment:50 followup: ↓ 52 Changed 3 years ago by
 R. Endre Tarjan > Robert Endre Tarjan
 the frontend method can be defined directly in
traversals.pyx
.  in the example
LexM produces an ordering of the vertices
, you should not only check the len of the output, but also that all vertices are in (compare sets)  you can show an ordering in an example
 add explanation for the test
Both algorithms produce a valid LexM ordering
, i.e., what is a valid ordering  The triangulation contains original graph edges, so we can directly do
H = Graph(F, format='list_of_edges')
 I don't like the names
lex_M_slow
andlex_M_fast
, and it's quite complicated for users to type. We can keep these names for the methods, but it would be better to find simple and clear names for the algorithms. algorithm == None
>algorithm is None
or simplynot algorithm
 remove the terms efficient and inefficient in the table of methods
 use latex (you also have to replace a
"""
byr"""
 Note that instead of using labels 1, 2, ..., k and adding 1/2, we use labels  2, 4, ..., k and add 1, thus avoiding to use floats or rationals. + Note that instead of using labels `1, 2, \ldots, k` and adding `1/2`, we use labels + `2, 4, \ldots, k` and add `1`, thus avoiding to use floats or rationals.
 a possible improvement, but I'm not sure it makes a difference.
 F.append((int_to_v[v], int_to_v[z])) + if triangulation: + F.append((int_to_v[v], int_to_v[z]))
comment:51 Changed 3 years ago by
 Commit changed from 61ad77fcf2a3125542404ae3e139e6247efd337e to 67d9787b8329602fd48d1036620aa1809cf921da
comment:52 in reply to: ↑ 50 Changed 3 years ago by
Replying to dcoudert:
 the frontend method can be defined directly in
traversals.pyx
.
You mean define it in traversals.pyx
and create an alias in generic_graph.py
? I think this is a good idea
 I don't like the names
lex_M_slow
andlex_M_fast
, and it's quite complicated for users to type. We can keep these names for the methods, but it would be better to find simple and clear names for the algorithms.
I will try to think of a better name. If you have anything in mind let me know.
comment:53 Changed 3 years ago by
 Commit changed from 67d9787b8329602fd48d1036620aa1809cf921da to 6a0ad02961662dd7dc5875e932f61f73ed868dad
Branch pushed to git repo; I updated commit sha1. New commits:
6a0ad02  Moved method lex_M from generic_graph.py to traversals.pyx

comment:54 Changed 3 years ago by
 Commit changed from 6a0ad02961662dd7dc5875e932f61f73ed868dad to a5ee6e628f580f60f0f0178cd3128dd3a26f3dcd
comment:55 Changed 3 years ago by
I did some corrections. Please check. I you agree, you can set to positive review on my behalf.
comment:56 Changed 3 years ago by
Seems OK. Let's wait for the Patchbot. If all tests pass I will set to positive review.
comment:57 Changed 3 years ago by
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
comment:58 Changed 3 years ago by
 Commit changed from a5ee6e628f580f60f0f0178cd3128dd3a26f3dcd to f9009b4d71936e52d45cfd658dd1ed649024f48d
Branch pushed to git repo; I updated commit sha1. New commits:
f9009b4  Fixed docstring

comment:59 Changed 3 years ago by
 Commit changed from f9009b4d71936e52d45cfd658dd1ed649024f48d to 614e901b6023cfdf2b1874ec61850097d734da0f
comment:60 Changed 3 years ago by
I suspect you have not even tried to build the documentation and check if it looks good...
I have done several corrections. Please check.
comment:61 Changed 3 years ago by
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 sagedevel about it.
comment:62 Changed 3 years ago by
 Commit changed from 614e901b6023cfdf2b1874ec61850097d734da0f to a13dda7c1d2188551b955a234faafab1ef830200
Branch pushed to git repo; I updated commit sha1. New commits:
a13dda7  Exception handling

comment:63 Changed 3 years ago by
I have added exceptions for when initial_vertex
is not a graph vertex.
comment:64 followup: ↓ 66 Changed 3 years ago by
why using str(initial_vertex)
? I don't think it's needed.
comment:65 Changed 3 years ago by
 Commit changed from a13dda7c1d2188551b955a234faafab1ef830200 to 4add4415dde9bc4646131d215ae9c555bb1b31e2
Branch pushed to git repo; I updated commit sha1. New commits:
4add441  minor improvement

comment:66 in reply to: ↑ 64 Changed 3 years ago by
Replying to dcoudert:
why using
str(initial_vertex)
? I don't think it's needed.
You are right. Fixed!
comment:67 Changed 3 years ago by
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):
comment:68 Changed 3 years ago by
 Commit changed from 4add4415dde9bc4646131d215ae9c555bb1b31e2 to aed4aaca2fffd851b5498fdc8f7f2fdeaf6463fb
Branch pushed to git repo; I updated commit sha1. New commits:
aed4aac  Fixed doctests

comment:70 Changed 3 years ago by
 Branch changed from public/graphs/28271_implement_lexM to aed4aaca2fffd851b5498fdc8f7f2fdeaf6463fb
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added LexUP
Added LexUP traversal
Added proper description for LexUP
Revert "Added proper description for LexUP"
Added description and reference for LexUP
Added Lex Down traversal
fixed typos and added alias for lex_DOWN in generic_graph.py
Added SEEALSO blocks
Added wikipedia reference for lex_BFS
Added description for LexM