Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#14619 closed enhancement (fixed)

Test if a graph is distance-regular

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.12
Component: graph theory Keywords: distance
Cc: dimpase, azi, Slani Merged in: sage-5.12.beta5
Authors: Nathann Cohen Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Nothing more that what the title says !

Nathann

Apply:

Attachments (2)

14619.patch (4.4 KB) - added by ncohen 6 years ago.
14619-rev.patch (6.3 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 follow-ups: Changed 6 years ago by azi

NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?

Also is there a chance we would want to have a certificate for this function as well?

comment:2 in reply to: ↑ 1 Changed 6 years ago by ncohen

Yoooooooooo !

NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?

Oh ? Well, I would be surprised if NetworkX could beat us for these distance functions

Also is there a chance we would want to have a certificate for this function as well?

I don't see one. What could be a good certificate ? O_o

Nathann

comment:3 Changed 6 years ago by ncohen

Yeah. Precisely :-P

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

Nathann

comment:4 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:5 follow-up: Changed 6 years ago by azi

Nice!

Well for the certificate.. Perhaps not really a certificate but a distance partition.

comment:6 in reply to: ↑ 5 Changed 6 years ago by ncohen

Well for the certificate.. Perhaps not really a certificate but a distance partition.

A distance partition ? O_o

What do you mean ? You can already get the distribution of distances with parameters=True, but I don't see what else we could return...

Nathann

comment:7 in reply to: ↑ 1 ; follow-up: Changed 6 years ago by dimpase

Replying to azi:

NetworkX should have a pretty decent test for distance regular graphs. Could you perhaps just verify the performance of yours vs NetworkX?

Also is there a chance we would want to have a certificate for this function as well?

what do you mean by "certificate"?

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.

Last edited 6 years ago by dimpase (previous) (diff)

comment:8 in reply to: ↑ 7 Changed 6 years ago by ncohen

what do you mean by "certificate"?

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

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.

Well, that would fit the definition I guess. But I wouldn't know what to make of it :-P

Nathann

comment:9 follow-up: Changed 6 years ago by azi

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by dimpase

Replying to azi:

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

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: http://www.maths.qmul.ac.uk/~leonard/grape/manual/CHAP004.htm#SECT002 (see GlobalParameters()). And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by ncohen

Yoooooooooo !

And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?

It is already available in the patch

sage: graphs.CubeGraph(4).is_distance_regular(parameters = True)
{1: 4, 2: 6, 3: 4, 4: 1}

nathann

comment:12 in reply to: ↑ 11 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Yoooooooooo !

And you have this kind of info when checking distance regularity anyway, so why not have a corresponding function?

It is already available in the patch

sage: graphs.CubeGraph(4).is_distance_regular(parameters = True)
{1: 4, 2: 6, 3: 4, 4: 1}

and how about local parameters: 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).

comment:13 in reply to: ↑ 12 Changed 6 years ago by ncohen

and how about local parameters: 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).

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

http://www.sagemath.org/doc/reference/graphs/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.shortest_path_all_vertices

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, (True/False, certificate) instead.

Do you think that it would be useful to expose this distance_all_vertices method at Python level ? And/or only shortest_path_all_vertices ? I don't really like it myself, but if you think that it would be useful ...

Nathann

comment:14 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 follow-up: Changed 6 years ago by chapoton

ok, looks almost good to me (with my rather basic cython understanding)

a few details:

  • needs to be rebased (HUNK)
  • a typo in the doc ;; instead of ::
  • the function does not give the correct result for the connected graph with 2 vertices
  • you should say in the doc that distance-regular means regular + the distance condition
  • missing spaces before and after ==

comment:16 in reply to: ↑ 15 Changed 6 years ago by ncohen

Yoooooooooooooo !!

  • needs to be rebased (HUNK)

Done !

  • a typo in the doc ;; instead of ::

Done !

  • the function does not give the correct result for the connected graph with 2 vertices

Done ! It was enough to change the <= 2 to a <= 1 in the beginning ;-)

  • you should say in the doc that distance-regular means regular + the distance condition

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.

  • missing spaces before and after ==

Fixed. In the whole file.

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.

And it can be changed, if this is a problem later on.

Here it is ! Former rebased patch, and the answer to your remarks.

Thaaaaaaaaaanks !

Nathann

comment:17 follow-up: Changed 6 years ago by chapoton

almost good to go. I would like this function to appear in the doc !

comment:18 in reply to: ↑ 17 Changed 6 years ago by ncohen

almost good to go. I would like this function to appear in the doc !

Yeah ?... Well it does, doesn't it ?

Nathann

comment:19 Changed 6 years ago by chapoton

  • Description modified (diff)
  • Keywords distance added
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, I have found it in undirected graphs documentation

I am giving a positive review, not waiting for the bot to do its job.

comment:20 Changed 6 years ago by ncohen

Cool. Thaaaaaaaaaaaaaaaaaanks ! :-)

Nathann

comment:21 Changed 6 years ago by chapoton

  • Description modified (diff)

comment:22 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:23 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to patch filenames

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 #14980. Please find out why and fix it.

Changed 6 years ago by ncohen

Changed 6 years ago by ncohen

comment:24 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to positive_review
  • Work issues patch filenames deleted

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.

I "fixed" it.

Nathann

comment:25 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.12.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:26 Changed 6 years ago by dimpase

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 :-(

Cf. http://permalink.gmane.org/gmane.comp.mathematics.sage.support/33339 where this was pointed out...

comment:27 Changed 6 years ago by dimpase

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

[ [   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 ] ]

and this is the GAP computation

$ 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 ] ]

comment:28 Changed 6 years ago by dimpase

see #15864 for a fix.

Note: See TracTickets for help on using tickets.