Opened 10 years ago

Closed 9 years ago

Last modified 9 years ago

#14619 closed enhancement (fixed)

Test if a graph is distance-regular

Reported by: Nathann Cohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.12
Component: graph theory Keywords: distance
Cc: Dima Pasechnik, Jernej Azarija, 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:

Status badges

Description (last modified by Nathann Cohen)

Nothing more that what the title says !

Nathann

Apply:

Attachments (2)

14619.patch (4.4 KB) - added by Nathann Cohen 9 years ago.
14619-rev.patch (6.3 KB) - added by Nathann Cohen 9 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 10 years ago by Jernej Azarija

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 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen

Status: newneeds_review

comment:5 Changed 10 years ago by Jernej Azarija

Nice!

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

comment:6 in reply to:  5 Changed 10 years ago by Nathann Cohen

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 ; Changed 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

comment:8 in reply to:  7 Changed 10 years ago by Nathann Cohen

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 Changed 10 years ago by Jernej Azarija

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 ; Changed 10 years ago by Dima Pasechnik

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 ; Changed 10 years ago by Nathann Cohen

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 ; Changed 10 years ago by Dima Pasechnik

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 10 years ago by Nathann Cohen

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 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:15 Changed 9 years ago by Frédéric 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 9 years ago by Nathann Cohen

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 Changed 9 years ago by Frédéric Chapoton

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

comment:18 in reply to:  17 Changed 9 years ago by Nathann Cohen

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 9 years ago by Frédéric Chapoton

Description: modified (diff)
Keywords: distance added
Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_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 9 years ago by Nathann Cohen

Cool. Thaaaaaaaaaaaaaaaaaanks ! :-)

Nathann

comment:21 Changed 9 years ago by Frédéric Chapoton

Description: modified (diff)

comment:22 Changed 9 years ago by Jeroen Demeyer

Description: modified (diff)

comment:23 Changed 9 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work
Work issues: 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 9 years ago by Nathann Cohen

Attachment: 14619.patch added

Changed 9 years ago by Nathann Cohen

Attachment: 14619-rev.patch added

comment:24 Changed 9 years ago by Nathann Cohen

Description: modified (diff)
Status: needs_workpositive_review
Work issues: patch filenames

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 9 years ago by Jeroen Demeyer

Merged in: sage-5.12.beta5
Resolution: fixed
Status: positive_reviewclosed

comment:26 Changed 9 years ago by Dima Pasechnik

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 9 years ago by Dima Pasechnik

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 9 years ago by Dima Pasechnik

see #15864 for a fix.

Note: See TracTickets for help on using tickets.