Implement LexUP and LexDOWN #28195

giorgosgiapis · 2019-07-14T13:18:29Z

Just like in #27928 we continue with the efficient implementation of graph traversal algorithms in Cython. More information about these algorithms and how they work can be found here: https://arxiv.org/pdf/1701.00305.pdf

Depends on #27928

Component: graph theory

Keywords: gsoc19

Author: Georgios Giapitzakis Tzintanos

Branch/Commit: u/gh-giorgosgiapis/more_traversals @ a110585

Reviewer: David Coudert

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

The text was updated successfully, but these errors were encountered:

giorgosgiapis · 2019-07-15T22:30:09Z

Branch: u/gh-giorgosgiapis/more_traversals

giorgosgiapis · 2019-07-15T22:31:05Z

Commit: e15a4c6

giorgosgiapis · 2019-07-15T22:31:05Z

Last 10 new commits:

`df8e94c`	`Added newline at EOF`
`2ae8148`	`trac #27928: Merged with 8.9.beta1`
`a35d7e3`	`trac #27928: reviewer edit`
`5997ed0`	`trac #27928: correct copyright`
`8a8e739`	`trac #27928: missing doctests in lex BFS`
`9f39c33`	`Fixed issue with documentation`
`17a7844`	`Added tests and fixed typo`
`6593331`	`Fixed doctests`
`fe62167`	`Added LexUP`
`e15a4c6`	`Added LexUP traversal`

giorgosgiapis · 2019-07-15T22:47:35Z

comment:4

Should I create a Metaticket about all the newly implemented graph traversal methods?

dcoudert · 2019-07-16T02:39:24Z

comment:5

No need for a meta-ticket, but I guess you have to write a somehow a blog for reporting to GSoC.

Please add a desciption a what is lexUP. UP is not enough to guess what it can be.

giorgosgiapis · 2019-07-16T09:08:57Z

comment:6

I will add a more detailed explanation and a reference to the paper presented in the ticket description under ALGORITHM description. I think this should be enough.

sagetrac-git · 2019-07-17T14:39:49Z

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

`08b55aa`	`Added proper description for LexUP`
`42266b4`	`Revert "Added proper description for LexUP"`

sagetrac-git · 2019-07-17T14:39:49Z

Changed commit from e15a4c6 to 42266b4

sagetrac-git · 2019-07-17T15:49:44Z

Changed commit from 42266b4 to e8653df

sagetrac-git · 2019-07-17T15:49:44Z

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

`e8653df`	`Added description and reference for LexUP`

giorgosgiapis · 2019-07-17T16:48:13Z

comment:9

I can't build the documentation after I modified src/doc/en/reference/references/index.rst. I am getting lots of "Citation not found" errors when running docbuild. Should I run make doc-clean && make?

dcoudert · 2019-07-17T18:17:12Z

comment:10

Yes. The system is far from perfect when you touch the references...

sagetrac-git · 2019-07-19T20:14:26Z

Changed commit from e8653df to acaaf6f

sagetrac-git · 2019-07-19T20:14:26Z

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

`acaaf6f`	`Added Lex Down traversal`

giorgosgiapis · 2019-07-19T20:15:45Z

comment:12

I have added Lex Down traversal. I will try running make doc-clean && make once again to see if it will build the documentation.

giorgosgiapis · 2019-07-19T20:58:51Z

comment:13

Documentation just finished building. Everything seems fine with the way html is displayed.

dcoudert · 2019-07-22T00:44:18Z

comment:14

Please use UP and DOWN everywhere in method names.

in traversals.pyx

-    :meth:`~lex_Up` | Perform a lexicographic up (LexUp) on the graph.
+    :meth:`~lex_UP` | Perform a lexicographic UP search (LexUP) on the graph.

you have not added an alias for lex_DOWN in generic_graph.py
unify the one line description for Lex_DOWN everywhere. The work search is missing, etc.
you can add a SEEALSO block with links to Lex_BFS, Lex_DFS, etc.

dcoudert · 2019-07-22T00:44:18Z

Reviewer: David Coudert

sagetrac-git · 2019-07-22T02:15:51Z

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

`9836457`	`fixed typos and added alias for lex_DOWN in generic_graph.py`
`5bb3dd9`	`Added SEEALSO blocks`

sagetrac-git · 2019-07-22T02:15:51Z

Changed commit from acaaf6f to 5bb3dd9

dcoudert · 2019-07-23T15:13:39Z

comment:17

Why are you referring to lex BFS in lex UP and to lex DFS in lex DOWN ? Are these methods closer ? Otherwise, why not referring to all other methods ?

dcoudert · 2019-07-23T15:14:53Z

comment:18

and you can also add a link to :wikipedia:`Lexicographic_breadth-first_search` in lex BFS.

giorgosgiapis · 2019-07-23T15:20:18Z

comment:19

Replying to @dcoudert:

Why are you referring to lex BFS in lex UP and to lex DFS in lex DOWN ? Are these methods closer ? Otherwise, why not referring to all other methods ?

I think they are closer since in both lex BFS and lex UP we append to the labels of nodes while in lex DFS and lex DOWN we prepend.

giorgosgiapis · 2019-07-23T15:20:33Z

comment:20

Replying to @dcoudert:

and you can also add a link to :wikipedia:`Lexicographic_breadth-first_search` in lex BFS.

Will do.

dcoudert · 2019-07-23T15:22:21Z

comment:21

I think they are closer since in both lex BFS and lex UP we append to the labels of nodes while in lex DFS and lex DOWN we prepend.

Good point. I admit that It's not easy to understand what these traversals do (the order to expect) and for what usage they are useful.

sagetrac-git · 2019-07-23T15:42:17Z

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

`f27f600`	`Added wikipedia reference for lex_BFS`

sagetrac-git · 2019-07-23T15:42:17Z

Changed commit from 5bb3dd9 to f27f600

sagetrac-git · 2019-07-28T23:08:21Z

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

`550b376`	`Fixed typo in comment`

sagetrac-git · 2019-07-28T23:08:21Z

Changed commit from f27f600 to 550b376

dcoudert · 2019-07-31T14:27:00Z

comment:24

May be we could add an example showing that the resulting orderings are different. For instance:

sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

giorgosgiapis · 2019-07-31T14:29:59Z

comment:25

Replying to @dcoudert:

May be we could add an example showing that the resulting orderings are different. For instance:

sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Good idea! Should I add it to all methods?

dcoudert · 2019-07-31T14:35:45Z

comment:26

it's certainly better.

sagetrac-git · 2019-07-31T14:45:38Z

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

`a110585`	`Added doctests`

sagetrac-git · 2019-07-31T14:45:38Z

Changed commit from 550b376 to a110585

dcoudert · 2019-07-31T16:50:53Z

comment:28

If it's in the tests block, it's true that there is no need for adding these examples in all methods.
One alternative is to put the examples in the examples block of lex_BFS and to remove it from other methods. Sorry for the extra work.

giorgosgiapis · 2019-07-31T17:57:30Z

comment:29

Currently, this test is in the examples block of all methods. Maybe we should leave it that way (I don't think it is bad to have the same example in several methods). If it is better I can remove it from other methods

dcoudert · 2019-08-01T06:57:21Z

comment:30

LGTM.

giorgosgiapis added this to the sage-8.9 milestone Jul 14, 2019

giorgosgiapis added c: graph theory labels Jul 14, 2019

giorgosgiapis added the s: needs review label Jul 15, 2019

dcoudert added s: needs work and removed s: needs review labels Jul 22, 2019

giorgosgiapis added s: needs review and removed s: needs work labels Jul 22, 2019

dcoudert added s: positive review and removed s: needs review labels Aug 1, 2019

vbraun removed the s: positive review label Aug 3, 2019

vbraun closed this as completed in a62d7fa Aug 3, 2019

Implement LexUP and LexDOWN #28195

Implement LexUP and LexDOWN #28195

Comments

giorgosgiapis commented Jul 14, 2019

giorgosgiapis commented Jul 15, 2019

giorgosgiapis commented Jul 15, 2019

giorgosgiapis commented Jul 15, 2019

giorgosgiapis commented Jul 15, 2019

dcoudert commented Jul 16, 2019

giorgosgiapis commented Jul 16, 2019

sagetrac-git mannequin commented Jul 17, 2019

sagetrac-git mannequin commented Jul 17, 2019

sagetrac-git mannequin commented Jul 17, 2019

sagetrac-git mannequin commented Jul 17, 2019

giorgosgiapis commented Jul 17, 2019

dcoudert commented Jul 17, 2019

sagetrac-git mannequin commented Jul 19, 2019

sagetrac-git mannequin commented Jul 19, 2019

giorgosgiapis commented Jul 19, 2019

giorgosgiapis commented Jul 19, 2019

dcoudert commented Jul 22, 2019

dcoudert commented Jul 22, 2019

sagetrac-git mannequin commented Jul 22, 2019

sagetrac-git mannequin commented Jul 22, 2019

dcoudert commented Jul 23, 2019

dcoudert commented Jul 23, 2019

giorgosgiapis commented Jul 23, 2019

giorgosgiapis commented Jul 23, 2019

dcoudert commented Jul 23, 2019

sagetrac-git mannequin commented Jul 23, 2019

sagetrac-git mannequin commented Jul 23, 2019

sagetrac-git mannequin commented Jul 28, 2019

sagetrac-git mannequin commented Jul 28, 2019

dcoudert commented Jul 31, 2019

giorgosgiapis commented Jul 31, 2019

dcoudert commented Jul 31, 2019

sagetrac-git mannequin commented Jul 31, 2019

sagetrac-git mannequin commented Jul 31, 2019

dcoudert commented Jul 31, 2019

giorgosgiapis commented Jul 31, 2019

dcoudert commented Aug 1, 2019