Sage: Ticket #14619: Test if a graph is distance-regular
https://trac.sagemath.org/ticket/14619
<p>
Nothing more that what the title says !
</p>
<p>
Nathann
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14619/14619.patch" title="Attachment '14619.patch' in Ticket #14619">14619.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14619/14619.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14619/14619-rev.patch" title="Attachment '14619-rev.patch' in Ticket #14619">14619-rev.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14619/14619-rev.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14619
Trac 1.2Jernej AzarijaMon, 20 May 2013 13:01:29 GMT
https://trac.sagemath.org/ticket/14619#comment:1
https://trac.sagemath.org/ticket/14619#comment:1
<p>
NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?
</p>
<p>
Also is there a chance we would want to have a certificate for this function as well?
</p>
TicketNathann CohenMon, 20 May 2013 13:05:14 GMT
https://trac.sagemath.org/ticket/14619#comment:2
https://trac.sagemath.org/ticket/14619#comment:2
<p>
Yoooooooooo !
</p>
<blockquote class="citation">
<p>
NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?
</p>
</blockquote>
<p>
Oh ? Well, I would be surprised if NetworkX could beat us for these distance functions
</p>
<blockquote class="citation">
<p>
Also is there a chance we would want to have a certificate for this function as well?
</p>
</blockquote>
<p>
I don't see one. What could be a good certificate ? <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketNathann CohenMon, 20 May 2013 13:10:14 GMT
https://trac.sagemath.org/ticket/14619#comment:3
https://trac.sagemath.org/ticket/14619#comment:3
<p>
Yeah. Precisely <code>:-P</code>
</p>
<pre class="wiki">sage: import networkx
sage: g = graphs.CubeGraph(9)
sage: gn = g.networkx_graph()
sage: %time g.is_distance_regular()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.04 s
True
sage: networkx.is_distance_regular(gn)
True
sage: %time networkx.is_distance_regular(gn)
CPU times: user 2.18 s, sys: 0.02 s, total: 2.20 s
Wall time: 2.20 s
True
</pre><p>
Nathann
</p>
TicketNathann CohenMon, 20 May 2013 13:10:23 GMTstatus changed
https://trac.sagemath.org/ticket/14619#comment:4
https://trac.sagemath.org/ticket/14619#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketJernej AzarijaMon, 20 May 2013 13:13:31 GMT
https://trac.sagemath.org/ticket/14619#comment:5
https://trac.sagemath.org/ticket/14619#comment:5
<p>
Nice!
</p>
<p>
Well for the certificate.. Perhaps not really a certificate but a distance partition.
</p>
TicketNathann CohenMon, 20 May 2013 13:14:54 GMT
https://trac.sagemath.org/ticket/14619#comment:6
https://trac.sagemath.org/ticket/14619#comment:6
<blockquote class="citation">
<p>
Well for the certificate.. Perhaps not really a certificate but a distance partition.
</p>
</blockquote>
<p>
A distance partition ? <code>O_o</code>
</p>
<p>
What do you mean ? You can already get the distribution of distances with <code></code>parameters=True<code></code>, but I don't see what else we could return...
</p>
<p>
Nathann
</p>
TicketDima PasechnikMon, 20 May 2013 13:23:54 GMT
https://trac.sagemath.org/ticket/14619#comment:7
https://trac.sagemath.org/ticket/14619#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14619#comment:1" title="Comment 1">azi</a>:
</p>
<blockquote class="citation">
<p>
NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?
</p>
<p>
Also is there a chance we would want to have a certificate for this function as well?
</p>
</blockquote>
<p>
what do you mean by "certificate"?
</p>
<p>
There is in fact an algebraic certificate of distance regularity, that is, the adjacency matrix A_k of the distance k graph of the original graph G is a polynomial in A_1 (the adjacency matrix of G). And these polynomials can be computed from the "intersection arrays". But that's a long story.
</p>
TicketNathann CohenMon, 20 May 2013 13:32:55 GMT
https://trac.sagemath.org/ticket/14619#comment:8
https://trac.sagemath.org/ticket/14619#comment:8
<blockquote class="citation">
<p>
what do you mean by "certificate"?
</p>
</blockquote>
<p>
Well, usually it is some short data which proves that the result returned is valid. Formally, I think that it is only defined for NP-Hard problems, but well...
</p>
<blockquote class="citation">
<p>
There is in fact an algebraic certificate of distance regularity, that is, the adjacency matrix A_k of the distance k graph of the original graph G is a polynomial in A_1 (the adjacency matrix of G). And these polynomials can be computed from the "intersection arrays". But that's a long story.
</p>
</blockquote>
<p>
Well, that would fit the definition I guess. But I wouldn't know what to make of it <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketJernej AzarijaMon, 20 May 2013 16:56:43 GMT
https://trac.sagemath.org/ticket/14619#comment:9
https://trac.sagemath.org/ticket/14619#comment:9
<p>
From what I know the guys doing distance-regular graphs they use to write "bubbles." They pick a vertex v which is the first "bubble", then they take the neighborhood of v to be the second bubble and then the neighbors at distance 3 from $v$ and so on...
</p>
TicketDima PasechnikMon, 20 May 2013 22:25:32 GMT
https://trac.sagemath.org/ticket/14619#comment:10
https://trac.sagemath.org/ticket/14619#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14619#comment:9" title="Comment 9">azi</a>:
</p>
<blockquote class="citation">
<p>
From what I know the guys doing distance-regular graphs they use to write "bubbles." They pick a vertex v which is the first "bubble", then they take the neighborhood of v to be the second bubble and then the neighbors at distance 3 from $v$ and so on...
</p>
</blockquote>
<p>
sure, one not only wants to know whether the graph is distance regular, but also its parameters
(analog of k, lambda, mu for strongly regular graphs). E.g. GRAPE, a GAP package, does the following:
<a class="ext-link" href="http://www.maths.qmul.ac.uk/~leonard/grape/manual/CHAP004.htm#SECT002"><span class="icon"></span>http://www.maths.qmul.ac.uk/~leonard/grape/manual/CHAP004.htm#SECT002</a>
(see <code>GlobalParameters()</code>).
And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?
</p>
TicketNathann CohenTue, 21 May 2013 07:45:49 GMT
https://trac.sagemath.org/ticket/14619#comment:11
https://trac.sagemath.org/ticket/14619#comment:11
<p>
Yoooooooooo !
</p>
<blockquote class="citation">
<p>
And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?
</p>
</blockquote>
<p>
It is already available in the patch
</p>
<pre class="wiki">sage: graphs.CubeGraph(4).is_distance_regular(parameters = True)
{1: 4, 2: 6, 3: 4, 4: 1}
</pre><p>
nathann
</p>
TicketDima PasechnikTue, 21 May 2013 07:53:10 GMT
https://trac.sagemath.org/ticket/14619#comment:12
https://trac.sagemath.org/ticket/14619#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14619#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yoooooooooo !
</p>
<blockquote class="citation">
<p>
And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?
</p>
</blockquote>
<p>
It is already available in the patch
</p>
<pre class="wiki">sage: graphs.CubeGraph(4).is_distance_regular(parameters = True)
{1: 4, 2: 6, 3: 4, 4: 1}
</pre></blockquote>
<p>
and how about <code>local parameters</code>: i.e. computing parameters w.r.t. just 1 vertex?
This would also allow to return a certificate of non-distance-regularity, i.e. either a vertex for which parameters don't exist, or two vertices with different parameters (for the latter, you can test on complete bipartite graphs with parts of unequal size).
</p>
TicketNathann CohenTue, 21 May 2013 08:08:23 GMT
https://trac.sagemath.org/ticket/14619#comment:13
https://trac.sagemath.org/ticket/14619#comment:13
<blockquote class="citation">
<p>
and how about <code>local parameters</code>: i.e. computing parameters w.r.t. just 1 vertex?
This would also allow to return a certificate of non-distance-regularity, i.e. either a vertex for which parameters don't exist, or two vertices with different parameters (for the latter, you can test on complete bipartite graphs with parts of unequal size).
</p>
</blockquote>
<p>
Oh. Well, we do not have a "distance all vertices" method at Python level, which would return the kind of information you want, though we have it in the backends
</p>
<p>
<a class="ext-link" href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.shortest_path_all_vertices"><span class="icon"></span>http://www.sagemath.org/doc/reference/graphs/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.shortest_path_all_vertices</a>
</p>
<p>
We could return as a NO-certificate a pair of vertices that do not have the same "local parameters", as you say. And I would probably change the output so that it returns a pair, <code>(True/False, certificate)</code> instead.
</p>
<p>
Do you think that it would be useful to expose this <code>distance_all_vertices</code> method at Python level ? And/or only <code>shortest_path_all_vertices</code> ? I don't really like it myself, but if you think that it would be useful ...
</p>
<p>
Nathann
</p>
TicketJeroen DemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14619#comment:14
https://trac.sagemath.org/ticket/14619#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketFrédéric ChapotonThu, 29 Aug 2013 12:00:03 GMT
https://trac.sagemath.org/ticket/14619#comment:15
https://trac.sagemath.org/ticket/14619#comment:15
<p>
ok, looks almost good to me (with my rather basic cython understanding)
</p>
<p>
a few details:
</p>
<ul><li>needs to be rebased (HUNK)
</li><li>a typo in the doc <code>;;</code> instead of <code>::</code>
</li><li>the function does not give the correct result for the connected graph with 2 vertices
</li><li>you should say in the doc that distance-regular means <strong>regular</strong> + the distance condition
</li><li>missing spaces before and after <code>==</code>
</li></ul>
TicketNathann CohenThu, 29 Aug 2013 12:53:09 GMT
https://trac.sagemath.org/ticket/14619#comment:16
https://trac.sagemath.org/ticket/14619#comment:16
<p>
Yoooooooooooooo !!
</p>
<blockquote class="citation">
<ul><li>needs to be rebased (HUNK)
</li></ul></blockquote>
<p>
Done !
</p>
<blockquote class="citation">
<ul><li>a typo in the doc <code>;;</code> instead of <code>::</code>
</li></ul></blockquote>
<p>
Done !
</p>
<blockquote class="citation">
<ul><li>the function does not give the correct result for the connected graph with 2 vertices
</li></ul></blockquote>
<p>
Done ! It was enough to change the <code><= 2</code> to a <code><= 1</code> in the beginning <code>;-)</code>
</p>
<blockquote class="citation">
<ul><li>you should say in the doc that distance-regular means <strong>regular</strong> + the distance condition
</li></ul></blockquote>
<p>
Well, regularity is implied by distance regularity, for if a graph is distance-regular all vertices have "the same number of vertices at distance 1" (i.e. neighbors). I made that clear in an additional sentence of documentation.
</p>
<blockquote class="citation">
<ul><li>missing spaces before and after <code>==</code>
</li></ul></blockquote>
<p>
Fixed. In the whole file.
</p>
<p>
I also noticed that there was an ugly segfault produced when the graph was disconnected. In this case, the "distance" between the two vertices is reported as 65536, but I try to write that in a the 65536th cell of a C array that may be much shorter. I began to write a proper fix to only run this method on connected graphs, and the method would have called itself on each connected component if the graph was not connected from the beginning, but I gave up this approach as it wouldd have added 15 lines of "details" to a code which isn't that clear already. Hence I chosed the lazy approach, which thanks to branch prediction in our CPU may not be that bad.
</p>
<p>
And it can be changed, if this is a problem later on.
</p>
<p>
Here it is ! Former rebased patch, and the answer to your remarks.
</p>
<p>
Thaaaaaaaaaanks !
</p>
<p>
Nathann
</p>
TicketFrédéric ChapotonThu, 29 Aug 2013 15:33:56 GMT
https://trac.sagemath.org/ticket/14619#comment:17
https://trac.sagemath.org/ticket/14619#comment:17
<p>
almost good to go. I would like this function to appear in the doc !
</p>
TicketNathann CohenThu, 29 Aug 2013 15:55:27 GMT
https://trac.sagemath.org/ticket/14619#comment:18
https://trac.sagemath.org/ticket/14619#comment:18
<blockquote class="citation">
<p>
almost good to go. I would like this function to appear in the doc !
</p>
</blockquote>
<p>
Yeah ?... Well it does, doesn't it ?
</p>
<p>
Nathann
</p>
TicketFrédéric ChapotonThu, 29 Aug 2013 16:02:03 GMTstatus, description changed; keywords, reviewer set
https://trac.sagemath.org/ticket/14619#comment:19
https://trac.sagemath.org/ticket/14619#comment:19
<ul>
<li><strong>keywords</strong>
<em>distance</em> added
</li>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14619?action=diff&version=19">diff</a>)
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
ok, I have found it in undirected graphs documentation
</p>
<p>
I am giving a positive review, not waiting for the bot to do its job.
</p>
TicketNathann CohenThu, 29 Aug 2013 16:05:08 GMT
https://trac.sagemath.org/ticket/14619#comment:20
https://trac.sagemath.org/ticket/14619#comment:20
<p>
Cool. Thaaaaaaaaaaaaaaaaaanks ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketFrédéric ChapotonThu, 29 Aug 2013 16:06:55 GMTdescription changed
https://trac.sagemath.org/ticket/14619#comment:21
https://trac.sagemath.org/ticket/14619#comment:21
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14619?action=diff&version=21">diff</a>)
</li>
</ul>
TicketJeroen DemeyerFri, 30 Aug 2013 08:33:43 GMTdescription changed
https://trac.sagemath.org/ticket/14619#comment:22
https://trac.sagemath.org/ticket/14619#comment:22
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14619?action=diff&version=22">diff</a>)
</li>
</ul>
TicketJeroen DemeyerFri, 30 Aug 2013 08:35:24 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/14619#comment:23
https://trac.sagemath.org/ticket/14619#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>patch filenames</em>
</li>
</ul>
<p>
There is something wrong with the filenames of these patches, there are some weird characters at the end. The same issue also happened with the "part5" patch of <a class="closed ticket" href="https://trac.sagemath.org/ticket/14980" title="#14980: enhancement: graph_generators, some more clean up (closed: fixed)">#14980</a>. Please find out why and fix it.
</p>
TicketNathann CohenFri, 30 Aug 2013 08:43:22 GMTattachment set
https://trac.sagemath.org/ticket/14619
https://trac.sagemath.org/ticket/14619
<ul>
<li><strong>attachment</strong>
set to <em>14619.patch</em>
</li>
</ul>
TicketNathann CohenFri, 30 Aug 2013 08:43:51 GMTattachment set
https://trac.sagemath.org/ticket/14619
https://trac.sagemath.org/ticket/14619
<ul>
<li><strong>attachment</strong>
set to <em>14619-rev.patch</em>
</li>
</ul>
TicketNathann CohenFri, 30 Aug 2013 08:45:22 GMTstatus, description changed; work_issues deleted
https://trac.sagemath.org/ticket/14619#comment:24
https://trac.sagemath.org/ticket/14619#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14619?action=diff&version=24">diff</a>)
</li>
<li><strong>work_issues</strong>
<em>patch filenames</em> deleted
</li>
</ul>
<p>
It seems to be a very rare bug that happens when a file is named "trac_14619.patch". No idea on earth of what is happening.
</p>
<p>
I "fixed" it.
</p>
<p>
Nathann
</p>
TicketJeroen DemeyerWed, 04 Sep 2013 08:06:22 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14619#comment:25
https://trac.sagemath.org/ticket/14619#comment:25
<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>merged</strong>
set to <em>sage-5.12.beta5</em>
</li>
</ul>
TicketDima PasechnikMon, 24 Feb 2014 18:34:18 GMT
https://trac.sagemath.org/ticket/14619#comment:26
https://trac.sagemath.org/ticket/14619#comment:26
<p>
I just checked this out, and the definition is not right.
With such a definition e.g. every vertex-transitive graph is
distance-regular, and this is clearly nonsense! I wish I had time to look at this 6 months ago :-(
</p>
<p>
Cf. <a class="ext-link" href="http://permalink.gmane.org/gmane.comp.mathematics.sage.support/33339"><span class="icon"></span>http://permalink.gmane.org/gmane.comp.mathematics.sage.support/33339</a>
where this was pointed out...
</p>
TicketDima PasechnikMon, 24 Feb 2014 19:20:59 GMT
https://trac.sagemath.org/ticket/14619#comment:27
https://trac.sagemath.org/ticket/14619#comment:27
<p>
An example of a graph on 12 vertices which satisfies the wrong definition here, but is not distance-regular, can be constructed using GRAPE (a package of GAP included in Sage). It's vertex-transitive (and even edge-transitive) bipartite graph of diameter 3, which is not distance-regular. Some vertices (e.g. 1 and 6) at distance 2 from each other have 4 common neighbours, and some (e.g. 1 and 2) only 2 common neighbours, whereas this must be a constant across all distance 2 pairs.
Here is the adjacency list (say for a doctest) of this graph (vertices from 1 to 12):
</p>
<pre class="wiki">[ [ 8, 9, 10, 11 ],
[ 7, 9, 10, 12 ],
[ 7, 8, 11, 12 ],
[ 7, 8, 11, 12 ],
[ 7, 9, 10, 12 ],
[ 8, 9, 10, 11 ],
[ 2, 3, 4, 5 ],
[ 1, 3, 4, 6 ],
[ 1, 2, 5, 6 ],
[ 1, 2, 5, 6 ],
[ 1, 3, 4, 6 ],
[ 2, 3, 4, 5 ] ]
</pre><p>
and this is the GAP computation
</p>
<pre class="wiki">$ sage -gap
...
gap> LoadPackage("grape");
gap> gamma := JohnsonGraph(4,2);;
gap> B:=BipartiteDouble(gamma);;
gap> GlobalParameters(B);
[ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ]
gap> a:=AutGroupGraph(B);;
gap> Orbits(a,[1..12]);
[ [ 1, 2, 7, 5, 3, 8, 12, 4, 6, 11, 9, 10 ] ]
gap> ha:=Stabilizer(a,1);;
gap> Orbits(ha,[1..12]);
[ [ 1 ], [ 2, 5, 3, 4 ], [ 6 ], [ 7, 12 ], [ 8, 9, 10, 11 ] ]
gap> List([1..12],x->Adjacency(B,x));
[ [ 8, 9, 10, 11 ], [ 7, 9, 10, 12 ], [ 7, 8, 11, 12 ], [ 7, 8, 11, 12 ], [ 7, 9, 10, 12 ], [ 8, 9, 10, 11 ], [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ],
[ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ]
</pre>
TicketDima PasechnikThu, 27 Feb 2014 10:29:08 GMT
https://trac.sagemath.org/ticket/14619#comment:28
https://trac.sagemath.org/ticket/14619#comment:28
<p>
see <a class="closed ticket" href="https://trac.sagemath.org/ticket/15864" title="#15864: defect: Graph.is_distance_regular is awfully wrong (closed: fixed)">#15864</a> for a fix.
</p>
Ticket