Sage: Ticket #11736: Linear time implementation of lex_BFS()
https://trac.sagemath.org/ticket/11736
<p>
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.
</p>
<p>
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.
</p>
<p>
(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.
</p>
<p>
(2) Corneil, Olariu and Stewart. The LBFS Structure and Recognition of Interval Graphs. SIAMDM 23(4), 2009.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11736
Trac 1.1.6ddestradaWed, 24 Aug 2011 14:19:15 GMTowner, type changed
https://trac.sagemath.org/ticket/11736#comment:1
https://trac.sagemath.org/ticket/11736#comment:1
<ul>
<li><strong>owner</strong>
changed from <em>jason, ncohen, rlm</em> to <em>ddestrada</em>
</li>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>enhancement</em>
</li>
</ul>
TicketddestradaWed, 24 Aug 2011 14:20:44 GMTowner changed
https://trac.sagemath.org/ticket/11736#comment:2
https://trac.sagemath.org/ticket/11736#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>ddestrada</em> to <em>jason, ncohen, rlm</em>
</li>
</ul>
TicketddestradaWed, 24 Aug 2011 14:21:46 GMTdescription changed
https://trac.sagemath.org/ticket/11736#comment:3
https://trac.sagemath.org/ticket/11736#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11736?action=diff&version=3">diff</a>)
</li>
</ul>
TicketncohenFri, 02 Sep 2011 09:06:42 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:4
https://trac.sagemath.org/ticket/11736#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello Diego !!!
</p>
<p>
Same comment (see <a class="closed ticket" href="https://trac.sagemath.org/ticket/11738" title="defect: Various issues in is_interval and is_chordal (closed: fixed)">#11738</a>) 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 <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenFri, 02 Sep 2011 09:06:48 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:5
https://trac.sagemath.org/ticket/11736#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketddestradaTue, 06 Sep 2011 07:11:18 GMTattachment set
https://trac.sagemath.org/ticket/11736
https://trac.sagemath.org/ticket/11736
<ul>
<li><strong>attachment</strong>
set to <em>linear_lex_bfs.patch</em>
</li>
</ul>
TicketddestradaTue, 06 Sep 2011 07:25:53 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:6
https://trac.sagemath.org/ticket/11736#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11736#comment:4" title="Comment 4">ncohen</a>:
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.
</p>
TicketncohenSun, 11 Sep 2011 13:57:12 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:7
https://trac.sagemath.org/ticket/11736#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Perhaps I can help you with this test problem ? The thing is that right now the patch does not seem to work :
</p>
<pre class="wiki">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
</pre><p>
On random interval graphs sometimes the is_interval function works, sometimes it does not... <code>^^;</code>
</p>
<p>
I tested you patch after having applied <a class="closed ticket" href="https://trac.sagemath.org/ticket/11738" title="defect: Various issues in is_interval and is_chordal (closed: fixed)">#11738</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11735" title="defect: Bug in is_chordal (closed: fixed)">#11735</a> 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 ? <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketddestradaWed, 14 Sep 2011 03:44:54 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:8
https://trac.sagemath.org/ticket/11736#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11736#comment:7" title="Comment 7">ncohen</a>:
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!
</p>
TicketncohenWed, 28 Sep 2011 19:10:11 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:9
https://trac.sagemath.org/ticket/11736#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hello !!
</p>
<p>
This patch still produces many errors when running the doctests...
</p>
<pre class="wiki">sage -t "devel/sage-3/sage/graphs/generic_graph.py"
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9412:
sage: (2*g).is_chordal()
Exception raised:
Traceback (most recent call last):
File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/home/ncohen/.Sage/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_137[6]>", line 1, in <module>
(Integer(2)*g).is_chordal()###line 9412:
sage: (2*g).is_chordal()
File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9474, in is_chordal
return all( gg.is_chordal() for gg in self.connected_components_subgraphs() )
File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9474, in <genexpr>
return all( gg.is_chordal() for gg in self.connected_components_subgraphs() )
File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 9488, in is_chordal
if t_peo.out_degree(v)>0 and g.neighbors(v) not in neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/digraph.py", line 1178, in out_degree
return list(self.out_degree_iterator(vertices, labels=labels))
File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/graphs/digraph.py", line 1223, in out_degree_iterator
for v in vertices:
TypeError: 'int' object is not iterable
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9436:
sage: hole
Expected:
Subgraph of (Petersen graph): Graph on 5 vertices
Got:
Subgraph of (Petersen graph): Graph on 4 vertices
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9438:
sage: hole.is_isomorphic(graphs.CycleGraph(5))
Expected:
True
Got:
False
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9554:
sage: g.is_interval()
Expected:
True
Got:
False
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-3/sage/graphs/generic_graph.py", line 9562:
sage: d = g.is_interval(certificate = True)
Exception raised:
Traceback (most recent call last):
File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
...
</pre><p>
Perhaps we can help with your problem running doctests ? It something does not work on this side, it is another bug of Sage's ! <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 26 Mar 2012 16:53:29 GMT
https://trac.sagemath.org/ticket/11736#comment:10
https://trac.sagemath.org/ticket/11736#comment:10
<p>
I was ready to help with the doctests issues, but I'm unable to install the patch on sage-5.0.beta9.
</p>
TicketddestradaMon, 26 Mar 2012 18:01:30 GMT
https://trac.sagemath.org/ticket/11736#comment:11
https://trac.sagemath.org/ticket/11736#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11736#comment:10" title="Comment 10">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
I was ready to help with the doctests issues, but I'm unable to install the patch on sage-5.0.beta9.
</p>
</blockquote>
<p>
Hello! I'm sorry I disappeared. I will fix this in the next few days.
</p>
TicketddestradaTue, 27 Mar 2012 06:05:36 GMTattachment set
https://trac.sagemath.org/ticket/11736
https://trac.sagemath.org/ticket/11736
<ul>
<li><strong>attachment</strong>
set to <em>linear_lex_bfs_fixed.patch</em>
</li>
</ul>
TicketddestradaTue, 27 Mar 2012 06:12:09 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:12
https://trac.sagemath.org/ticket/11736#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketddestradaTue, 27 Mar 2012 06:25:37 GMTcc changed
https://trac.sagemath.org/ticket/11736#comment:13
https://trac.sagemath.org/ticket/11736#comment:13
<ul>
<li><strong>cc</strong>
<em>dcoudert</em> added
</li>
</ul>
TicketddestradaTue, 27 Mar 2012 23:59:14 GMT
https://trac.sagemath.org/ticket/11736#comment:14
https://trac.sagemath.org/ticket/11736#comment:14
<p>
I think this patch is working now and passes all the doctests. I'm sure the errors I get while doctesting are bugs of Sage 4.8 (for example, on both Ubuntu 10.10 and OS X 10.7 I get an error in line 15146 of generic_graph.py: "<a class="missing wiki">ValueError?</a>: Database has no tablegraph_data.").
</p>
TicketncohenFri, 30 Mar 2012 22:22:39 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:15
https://trac.sagemath.org/ticket/11736#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooo Diego !!
</p>
<p>
I'm sorry but your patch can not be applied on top of the latest release of Sage, that is sage-5.0-beta11 (<a class="ext-link" href="https://groups.google.com/d/topic/sage-release/XnyN3tx4Bow/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-release/XnyN3tx4Bow/discussion</a>). Plenty of stuff has been added in the 5.0-beta? series, and that is probably the explanation <code>:-)</code>
</p>
<p>
About your path, though : it removes the old code that computed (more slowly) a BFS ordering for the vertices. This being said, I think this code could still be useful to ... check that the new algorithm actually returns a correct BFS ordering ! Of course, as it is slower, this ordering should not be checked by default, but it would be nice to be able to run doctests which check for each computation of BFS ordering whether this ordering is indeed correct. This can be done by actually checking in turn that each vertex of the ordering is maximal at the moment when it is removed.
</p>
<p>
Do you think it could be possible to comment your code a bit more ? As it is, reading the paper to understand what happens seems to be the only alternative <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/11736#comment:16
https://trac.sagemath.org/ticket/11736#comment:16
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/11736#comment:17
https://trac.sagemath.org/ticket/11736#comment:17
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/11736#comment:18
https://trac.sagemath.org/ticket/11736#comment:18
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/11736#comment:19
https://trac.sagemath.org/ticket/11736#comment:19
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketdcoudertSat, 14 Mar 2015 13:26:02 GMTbranch set
https://trac.sagemath.org/ticket/11736#comment:20
https://trac.sagemath.org/ticket/11736#comment:20
<ul>
<li><strong>branch</strong>
set to <em>public/11736</em>
</li>
</ul>
TicketgitSat, 14 Mar 2015 13:29:10 GMTcommit set
https://trac.sagemath.org/ticket/11736#comment:21
https://trac.sagemath.org/ticket/11736#comment:21
<ul>
<li><strong>commit</strong>
set to <em>588c43140644c9d43cfae2e27e116566eda9ac54</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=588c43140644c9d43cfae2e27e116566eda9ac54"><span class="icon"></span>588c431</a></td><td><code>trac #11736: convert hg patch to git</code>
</td></tr></table>
TicketdcoudertSat, 14 Mar 2015 13:45:37 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:22
https://trac.sagemath.org/ticket/11736#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
This patch has been sleeping for very very long time.
</p>
<p>
I did a first git version of the patch with some corrections. This is far from final version and we have currently 2 implementations to ease tests. To use the new version, you need to set parameter <code>new_version=True</code>.
</p>
<p>
Since the code has no comments, it is hard to know whats going on. I have corrected at least one bug (a missing <code>j = l</code>), but I have the following issue:
</p>
<pre class="wiki">sage: g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2))
sage: g.lex_BFS(reverse=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=True, new_version=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
sage: g.lex_BFS(reverse=False)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
sage: g.lex_BFS(reverse=False, new_version=True)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]
</pre><p>
The new version is more consistant (and also way faster). Furthermore, on this example, both reverse orderings are correct.
However, when making the new version the default one, many tests for <code>is_chordal</code> and <code>is_interval</code> are broken.
</p>
<p>
Any help is welcome.
</p>
<p>
David.
</p>
TicketgitThu, 03 Nov 2016 19:39:58 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:23
https://trac.sagemath.org/ticket/11736#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>588c43140644c9d43cfae2e27e116566eda9ac54</em> to <em>12fdf755595a2a19a333e7928e8d1ef6d2e3f649</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=12fdf755595a2a19a333e7928e8d1ef6d2e3f649"><span class="icon"></span>12fdf75</a></td><td><code>Merge branch 'public/11736' in 7.5.b1</code>
</td></tr></table>
TicketgitThu, 03 Nov 2016 20:11:12 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:24
https://trac.sagemath.org/ticket/11736#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>12fdf755595a2a19a333e7928e8d1ef6d2e3f649</em> to <em>906438689c7b8b32756c8799fb410682b0c1dea8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=906438689c7b8b32756c8799fb410682b0c1dea8"><span class="icon"></span>9064386</a></td><td><code>trac 11736 pep8</code>
</td></tr></table>
TicketdcoudertTue, 11 Aug 2020 18:35:14 GMTstatus, commit, milestone, branch changed; author set
https://trac.sagemath.org/ticket/11736#comment:25
https://trac.sagemath.org/ticket/11736#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>906438689c7b8b32756c8799fb410682b0c1dea8</em> to <em>89af4c2dc2f6a39f1d009c02feb945c00500cd28</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-9.2</em>
</li>
<li><strong>branch</strong>
changed from <em>public/11736</em> to <em>public/graphs/11736_lex_bfs</em>
</li>
<li><strong>author</strong>
set to <em>Diego de Estrada, David Coudert</em>
</li>
</ul>
<p>
New branch based on 9.2.beta8 with:
</p>
<ul><li>corrected (hope so) version of previous trials for implementing the algorithm of Habib et al 2000.
</li><li>several improvements of the existing code
</li></ul><p>
Please test it extensively !
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=89af4c2dc2f6a39f1d009c02feb945c00500cd28"><span class="icon"></span>89af4c2</a></td><td><code>trac #11736: new version</code>
</td></tr></table>
TicketdcoudertWed, 12 Aug 2020 09:02:39 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:26
https://trac.sagemath.org/ticket/11736#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
something wrong :(
</p>
<pre class="wiki">File "src/sage/graphs/generic_graph.py", line 13620, in sage.graphs.generic_graph.GenericGraph.is_interval
Failed example:
[sum(1 for g in graphs(i) if g.is_interval()) for i in range(8)] # long time
Expected:
[1, 1, 2, 4, 10, 27, 92, 369]
Got:
[1, 1, 2, 4, 10, 27, 91, 374]
</pre><p>
At least this graph is not recognized as interval graph (actually, not chordal) when using the new version: <code>Graph("ETzw")</code>.
</p>
TicketgitWed, 12 Aug 2020 13:32:59 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:27
https://trac.sagemath.org/ticket/11736#comment:27
<ul>
<li><strong>commit</strong>
changed from <em>89af4c2dc2f6a39f1d009c02feb945c00500cd28</em> to <em>90d266e73f1f84d8fbae9b64a7ade43b459c80d6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=90d266e73f1f84d8fbae9b64a7ade43b459c80d6"><span class="icon"></span>90d266e</a></td><td><code>trac #11736: fix memory allocation and add documentation</code>
</td></tr></table>
TicketdcoudertWed, 12 Aug 2020 13:33:51 GMTstatus changed
https://trac.sagemath.org/ticket/11736#comment:28
https://trac.sagemath.org/ticket/11736#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The error was a side effect of wrong memory allocation. Should be OK now.
</p>
TicketdcoudertWed, 12 Aug 2020 13:49:36 GMTcc changed
https://trac.sagemath.org/ticket/11736#comment:29
https://trac.sagemath.org/ticket/11736#comment:29
<ul>
<li><strong>cc</strong>
<em>gh-kliem</em> added; <em>ncohen</em> removed
</li>
</ul>
TicketmjoThu, 03 Sep 2020 15:40:38 GMTcc changed
https://trac.sagemath.org/ticket/11736#comment:30
https://trac.sagemath.org/ticket/11736#comment:30
<ul>
<li><strong>cc</strong>
<em>mjo</em> added
</li>
</ul>
<p>
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).
</p>
TicketdcoudertThu, 03 Sep 2020 16:09:44 GMT
https://trac.sagemath.org/ticket/11736#comment:31
https://trac.sagemath.org/ticket/11736#comment:31
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
<p>
One option could be to make an indirect doctest using <code>is_chordal</code> on a random chordal graph, but for that me must be able to specify the lex BFS algorithm to use in <code>is_chordal</code>. Not sure it's the best way.
</p>
<p>
But may be there is an other way to check that a lex BFS ordering is valid ?
</p>
TicketmjoThu, 03 Sep 2020 19:16:28 GMT
https://trac.sagemath.org/ticket/11736#comment:32
https://trac.sagemath.org/ticket/11736#comment:32
<p>
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 <code>_is_lbfs(graph, order)</code> function that could be used to test the outputs of the fast/slow algorithms? Both would return <code>True</code> when fed to <code>_is_lbfs</code>, I expect.
</p>
TickettscrimThu, 03 Sep 2020 23:09:32 GMT
https://trac.sagemath.org/ticket/11736#comment:33
https://trac.sagemath.org/ticket/11736#comment:33
<p>
Minor comment outside of the scope of the ticket: You might be able to do this for a bit more speed:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">- def l_func(x):
- return code[x]
</span>
# The initial_vertex is at position 0 and so named 0 in sd
code[0].append(n + 1)
now = 1
while vertices:
<span class="gd">- v = max(vertices, key=l_func)
</span><span class="gi">+ v = max(vertices, key=code.__getitem__)
</span></pre></div></div>
TicketgitFri, 04 Sep 2020 15:05:54 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:34
https://trac.sagemath.org/ticket/11736#comment:34
<ul>
<li><strong>commit</strong>
changed from <em>90d266e73f1f84d8fbae9b64a7ade43b459c80d6</em> to <em>7609c669194ad947ad7203cb01f65f98d2c15f93</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b9a3ec81ec3343ca94c2b2ea4e6701b5873af715"><span class="icon"></span>b9a3ec8</a></td><td><code>trac #11736: merge with 9.2.beta11</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=7609c669194ad947ad7203cb01f65f98d2c15f93"><span class="icon"></span>7609c66</a></td><td><code>trac #11736: add method to check validity of lexBFS ordering</code>
</td></tr></table>
TicketdcoudertFri, 04 Sep 2020 15:09:05 GMT
https://trac.sagemath.org/ticket/11736#comment:35
https://trac.sagemath.org/ticket/11736#comment:35
<p>
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.
</p>
TicketmjoFri, 04 Sep 2020 20:28:36 GMT
https://trac.sagemath.org/ticket/11736#comment:36
https://trac.sagemath.org/ticket/11736#comment:36
<p>
We're working on getting rid of this, but for now, you have to call <code>set_random_seed()</code> 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.
</p>
TicketmjoFri, 04 Sep 2020 20:30:10 GMT
https://trac.sagemath.org/ticket/11736#comment:37
https://trac.sagemath.org/ticket/11736#comment:37
<p>
Example:
</p>
<pre class="wiki">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
</pre>
TicketgitFri, 04 Sep 2020 22:34:44 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:38
https://trac.sagemath.org/ticket/11736#comment:38
<ul>
<li><strong>commit</strong>
changed from <em>7609c669194ad947ad7203cb01f65f98d2c15f93</em> to <em>52c355e8d8aef1faee2ca5ed17da485e999279b9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=52c355e8d8aef1faee2ca5ed17da485e999279b9"><span class="icon"></span>52c355e</a></td><td><code>trac #11736: set random seed</code>
</td></tr></table>
TicketdcoudertFri, 04 Sep 2020 22:35:07 GMT
https://trac.sagemath.org/ticket/11736#comment:39
https://trac.sagemath.org/ticket/11736#comment:39
<p>
Thank you. I didn't know that.
</p>
TicketmjoSun, 06 Sep 2020 12:56:56 GMT
https://trac.sagemath.org/ticket/11736#comment:40
https://trac.sagemath.org/ticket/11736#comment:40
<p>
I've been playing around with this, here are a few more suggestions:
</p>
<ol><li>You could use <code>ZZ.random_element(G.num_verts())</code> instead of always <code>0</code> for the initial vertex in your random tests; that would improve coverage a bit.
</li></ol><ol start="2"><li>The documentation for the <code>cdef</code> 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 <code>lex_BFS_fast_short_digraph</code>, maybe you want to move them into the main <code>lex_BFS</code> docstring?
</li></ol><ol start="3"><li>(Unrelated to this ticket) While you're in there, please add an extra <code>:</code> to the end of <code>TESTS:</code> in <code>maximum_cardinality_search()</code>. Right now sage doesn't recognize it as a doctest.
</li></ol>
TicketgitSun, 06 Sep 2020 13:27:12 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:41
https://trac.sagemath.org/ticket/11736#comment:41
<ul>
<li><strong>commit</strong>
changed from <em>52c355e8d8aef1faee2ca5ed17da485e999279b9</em> to <em>15a041920a74a2268e98e787cf8da3200562ecc0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=15a041920a74a2268e98e787cf8da3200562ecc0"><span class="icon"></span>15a0419</a></td><td><code>trac #11736: review comments</code>
</td></tr></table>
TicketdcoudertSun, 06 Sep 2020 13:28:58 GMT
https://trac.sagemath.org/ticket/11736#comment:42
https://trac.sagemath.org/ticket/11736#comment:42
<p>
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.
</p>
TicketmjoSun, 06 Sep 2020 19:04:29 GMT
https://trac.sagemath.org/ticket/11736#comment:43
https://trac.sagemath.org/ticket/11736#comment:43
<p>
Thanks! Here are two more small things:
</p>
<p>
First, in the documentation for <code>lex_BFS_fast_short_digraph</code> (and now <code>lex_BFS</code>), there's a LaTeX typo at
</p>
<pre class="wiki">S = `{u | i \leq \sigma(u) \leq j\}
</pre><p>
The opening curly brace isn't escaped, so the formula isn't showing up.
</p>
<p>
Second, in <code>_is_valid_lex_BFS_order</code>, it looks to me like you've figured out the correct directions for the edges to make things work with a digraph, namely <code>ca</code>, <code>cb</code>, <code>da</code>, and <code>db</code>. However the docs still have some of them in a different order from when the result was stated for an undirected graph:
</p>
<pre class="wiki">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`.
</pre>
TicketgitSun, 06 Sep 2020 20:18:46 GMTcommit changed
https://trac.sagemath.org/ticket/11736#comment:44
https://trac.sagemath.org/ticket/11736#comment:44
<ul>
<li><strong>commit</strong>
changed from <em>15a041920a74a2268e98e787cf8da3200562ecc0</em> to <em>332fb8bf3acb23d8cb1a376744665cd25c680c26</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=332fb8bf3acb23d8cb1a376744665cd25c680c26"><span class="icon"></span>332fb8b</a></td><td><code>trac #11736: fix documentation</code>
</td></tr></table>
TicketdcoudertSun, 06 Sep 2020 20:19:20 GMT
https://trac.sagemath.org/ticket/11736#comment:45
https://trac.sagemath.org/ticket/11736#comment:45
<p>
good catch. Hope it will be ok this time.
</p>
TicketmjoMon, 07 Sep 2020 00:14:35 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/11736#comment:46
https://trac.sagemath.org/ticket/11736#comment:46
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Michael Orlitzky</em>
</li>
</ul>
<p>
This looks good to me now, unless anyone else wants to comment. I've checked the implementation of <code>_is_valid_lex_BFS_order</code>. 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.
</p>
<p>
The implementation of <code>lex_BFS_fast_short_digraph</code> 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.
</p>
TicketdcoudertMon, 07 Sep 2020 06:10:47 GMT
https://trac.sagemath.org/ticket/11736#comment:47
https://trac.sagemath.org/ticket/11736#comment:47
<p>
Thank you for your help.
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketslelievreTue, 08 Sep 2020 01:21:42 GMTdescription changed
https://trac.sagemath.org/ticket/11736#comment:48
https://trac.sagemath.org/ticket/11736#comment:48
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11736?action=diff&version=48">diff</a>)
</li>
</ul>
TicketvbraunTue, 15 Sep 2020 22:00:55 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/11736#comment:49
https://trac.sagemath.org/ticket/11736#comment:49
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/graphs/11736_lex_bfs</em> to <em>332fb8bf3acb23d8cb1a376744665cd25c680c26</em>
</li>
</ul>
Ticket