Opened 3 years ago

Closed 3 years ago

#28271 closed enhancement (fixed)

Implement LexM traversal

Reported by: gh-giorgosgiapis Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description

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.

Change History (70)

comment:1 Changed 3 years ago by gh-giorgosgiapis

  • Branch set to public/graphs/28271_implement_lexM

comment:2 Changed 3 years ago by gh-giorgosgiapis

  • Branch public/graphs/28271_implement_lexM deleted

comment:3 Changed 3 years ago by gh-giorgosgiapis

  • Branch set to u/gh-giorgosgiapis/lexM

comment:4 Changed 3 years ago by gh-giorgosgiapis

  • Branch changed from u/gh-giorgosgiapis/lexM to public/graphs/28271_implement_lexM
  • Status changed from new to needs_review

comment:5 Changed 3 years ago by gh-giorgosgiapis

  • Branch public/graphs/28271_implement_lexM deleted
  • Status changed from needs_review to needs_work

comment:6 Changed 3 years ago by gh-giorgosgiapis

  • Branch set to public/graphs/28271_implement_lexM

comment:7 Changed 3 years ago by git

  • Commit set to 24a6fc205ec9fd70991a626d9201dc2decbef00d

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

fe62167Added LexUP
e15a4c6Added LexUP traversal
08b55aaAdded proper description for LexUP
42266b4Revert "Added proper description for LexUP"
e8653dfAdded description and reference for LexUP
acaaf6fAdded Lex Down traversal
9836457fixed typos and added alias for lex_DOWN in generic_graph.py
5bb3dd9Added SEEALSO blocks
f27f600Added wikipedia reference for lex_BFS
24a6fc2Added description for LexM

comment:8 Changed 3 years ago by git

  • Commit changed from 24a6fc205ec9fd70991a626d9201dc2decbef00d to 32b970b14dd401192d0ffedce6183046d2a2d036

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

32b970bimproved description

comment:9 Changed 3 years ago by git

  • Commit changed from 32b970b14dd401192d0ffedce6183046d2a2d036 to 636b9e7d4ca1b00efed62fef459be38a184eefbf

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

550b376Fixed typo in comment
ce5208cMerge branch 'u/gh-giorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM
a110585Added doctests
cbb7da0Merge branch 'u/gh-giorgosgiapis/more_traversals' of git://trac.sagemath.org/sage into lexM
636b9e7First implementation of LexM

comment:10 Changed 3 years ago by gh-giorgosgiapis

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 gh-giorgosgiapis

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 follow-up: Changed 3 years ago by 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 ?

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 gh-giorgosgiapis

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:).

comment:14 Changed 3 years ago by dcoudert

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 gh-giorgosgiapis

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

comment:16 Changed 3 years ago by gh-giorgosgiapis

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 git

  • Commit changed from 636b9e7d4ca1b00efed62fef459be38a184eefbf to 1bb95ba7b5f699bb40984536c706decc2a4bb930

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

1bb95baFixed string conversion

comment:18 Changed 3 years ago by gh-giorgosgiapis

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 dcoudert

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 git

  • Commit changed from 1bb95ba7b5f699bb40984536c706decc2a4bb930 to 4ba625e82ed61cfa07ef9afe8f8fcd165d3f3841

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

cc76405trac #28271: merged with 8.9.beta5
c6d4636trac #28271: review commit and compliance with py3
4ba625etrac #28271: alternative implementation and test method

comment:21 Changed 3 years ago by dcoudert

  • 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 dcoudert

  • 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 gh-giorgosgiapis

Currently, I am having trouble building sage. When running make I am getting error cp: cannot overwrite directory with non-directory while building [gap-4.10.2.p0]. Should I post to sage-devel about it?

comment:24 Changed 3 years ago by dcoudert

Yes, sage-devel is the right place.

comment:25 Changed 3 years ago by gh-giorgosgiapis

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 gh-giorgosgiapis

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 dcoudert

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 gh-giorgosgiapis

Don't we need the labels for the tree decomposition?

comment:29 Changed 3 years ago by git

  • Commit changed from 4ba625e82ed61cfa07ef9afe8f8fcd165d3f3841 to ebcab15a0147fa3c6e23ee3a8b7a44789caaebaa

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

ebcab15trac #28271: fast implementation of lex_M

comment:30 Changed 3 years ago by dcoudert

I don't know, I have not checked how to build the tree-decomposition from the output of lex_M.

comment:31 Changed 3 years ago by gh-giorgosgiapis

I thought that the labels give us a tree decomposition of the graph.

comment:32 Changed 3 years ago by gh-giorgosgiapis

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 dcoudert

So make a front-end 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 gh-giorgosgiapis

Good idea! I will work on it.

comment:35 Changed 3 years ago by git

  • Commit changed from ebcab15a0147fa3c6e23ee3a8b7a44789caaebaa to 24fd31438f5e6eb3acfecacd292572970ab55b28

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

24fd314Removed incorrect method and improved code and documentation

comment:36 Changed 3 years ago by gh-giorgosgiapis

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 front-end.

comment:37 Changed 3 years ago by git

  • Commit changed from 24fd31438f5e6eb3acfecacd292572970ab55b28 to 1dd602dc88acc1f828e3f98a3de6e794ba16dff4

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

1dd602dAdded examples and tests for all methods

comment:38 Changed 3 years ago by gh-giorgosgiapis

  • Status changed from needs_work to needs_review

comment:39 Changed 3 years ago by gh-giorgosgiapis

I have added examples and tests for both methods. Maybe it would be better to implement the front-end in another ticket. Let me know what you think.

comment:40 Changed 3 years ago by git

  • Commit changed from 1dd602dc88acc1f828e3f98a3de6e794ba16dff4 to 9c1f8f1b4f34d1ff57483873e2b8f2f09b96dea6

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

9c1f8f1Fixed docstring

comment:41 Changed 3 years ago by git

  • Commit changed from 9c1f8f1b4f34d1ff57483873e2b8f2f09b96dea6 to 354b8175eab5984d9dcbe11ffececc77390d847a

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

354b817Docstring fix

comment:42 Changed 3 years ago by dcoudert

The front-end must be in this ticket. No need for another ticket for that.

comment:43 Changed 3 years ago by git

  • Commit changed from 354b8175eab5984d9dcbe11ffececc77390d847a to df3e2908185381f369ab843075cc6142958f5e07

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

df3e290Added method lex_M in generic_graph.py

comment:44 Changed 3 years ago by git

  • Commit changed from df3e2908185381f369ab843075cc6142958f5e07 to 8aa1238ca10692db2b89d18e4fc0e3e6062eb818

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

8aa1238Fixed typo in docstring of lex_M_slow

comment:45 Changed 3 years ago by git

  • Commit changed from 8aa1238ca10692db2b89d18e4fc0e3e6062eb818 to 1f90673a23087e7064c84856513d1b6ce6112c09

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

1f90673Added citation

comment:46 Changed 3 years ago by git

  • Commit changed from 1f90673a23087e7064c84856513d1b6ce6112c09 to c3df64f3df62430eb2c2ab75bd394e0abd8a10fc

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

c3df64fAdded description of method lex_M in generic_graph.py

comment:47 Changed 3 years ago by git

  • Commit changed from c3df64f3df62430eb2c2ab75bd394e0abd8a10fc to faea6a7b9dbd533a1b347c11016ba833d72aaa3a

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

faea6a7Added tests and examples in method lex_M of generic_graph.py

comment:48 Changed 3 years ago by gh-giorgosgiapis

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 git

  • Commit changed from faea6a7b9dbd533a1b347c11016ba833d72aaa3a to 61ad77fcf2a3125542404ae3e139e6247efd337e

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

61ad77fAdded doctest

comment:50 follow-up: Changed 3 years ago by dcoudert

  • R. Endre Tarjan -> Robert Endre Tarjan
  • the front-end 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 and lex_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 simply not algorithm
  • remove the terms efficient and inefficient in the table of methods
  • use latex (you also have to replace a """ by r"""
    -    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 git

  • Commit changed from 61ad77fcf2a3125542404ae3e139e6247efd337e to 67d9787b8329602fd48d1036620aa1809cf921da

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

60020baFixed citation
67d9787Improvements in code and documentation

comment:52 in reply to: ↑ 50 Changed 3 years ago by gh-giorgosgiapis

Replying to dcoudert:

  • the front-end 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 and lex_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 git

  • Commit changed from 67d9787b8329602fd48d1036620aa1809cf921da to 6a0ad02961662dd7dc5875e932f61f73ed868dad

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

6a0ad02Moved method lex_M from generic_graph.py to traversals.pyx

comment:54 Changed 3 years ago by git

  • Commit changed from 6a0ad02961662dd7dc5875e932f61f73ed868dad to a5ee6e628f580f60f0f0178cd3128dd3a26f3dcd

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

6ba9df6trac #28271: Merged with 8.9.beta7
a5ee6e6trac #28271: reviewer edit

comment:55 Changed 3 years ago by dcoudert

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 gh-giorgosgiapis

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 dcoudert

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 git

  • Commit changed from a5ee6e628f580f60f0f0178cd3128dd3a26f3dcd to f9009b4d71936e52d45cfd658dd1ed649024f48d

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

f9009b4Fixed docstring

comment:59 Changed 3 years ago by git

  • Commit changed from f9009b4d71936e52d45cfd658dd1ed649024f48d to 614e901b6023cfdf2b1874ec61850097d734da0f

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

719cdd0trac #28271: fix construction of html documentation
dd9a1c5trac #28271: small improvements
614e901trac #28271: further improvements

comment:60 Changed 3 years ago by dcoudert

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 gh-giorgosgiapis

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.

comment:62 Changed 3 years ago by git

  • Commit changed from 614e901b6023cfdf2b1874ec61850097d734da0f to a13dda7c1d2188551b955a234faafab1ef830200

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

a13dda7Exception handling

comment:63 Changed 3 years ago by gh-giorgosgiapis

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

comment:64 follow-up: Changed 3 years ago by dcoudert

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

comment:65 Changed 3 years ago by git

  • Commit changed from a13dda7c1d2188551b955a234faafab1ef830200 to 4add4415dde9bc4646131d215ae9c555bb1b31e2

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

4add441minor improvement

comment:66 in reply to: ↑ 64 Changed 3 years ago by gh-giorgosgiapis

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 dcoudert

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 git

  • Commit changed from 4add4415dde9bc4646131d215ae9c555bb1b31e2 to aed4aaca2fffd851b5498fdc8f7f2fdeaf6463fb

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

aed4aacFixed doctests

comment:69 Changed 3 years ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:70 Changed 3 years ago by vbraun

  • Branch changed from public/graphs/28271_implement_lexM to aed4aaca2fffd851b5498fdc8f7f2fdeaf6463fb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.