#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: |
Description (last modified by )
Attachments (2)
Change History (30)
comment:1 follow-ups: 2 7 Changed 9 years ago by
comment:2 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
Status: | new → needs_review |
---|
comment:5 follow-up: 6 Changed 9 years ago by
Nice!
Well for the certificate.. Perhaps not really a certificate but a distance partition.
comment:6 Changed 9 years ago by
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 follow-up: 8 Changed 9 years ago by
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 and 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.
comment:8 Changed 9 years ago by
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: 10 Changed 9 years ago by
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 follow-up: 11 Changed 9 years ago by
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 follow-up: 12 Changed 9 years ago by
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 follow-up: 13 Changed 9 years ago by
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 Changed 9 years ago by
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
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
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:15 follow-up: 16 Changed 9 years ago by
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 Changed 9 years ago by
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: 18 Changed 9 years ago by
almost good to go. I would like this function to appear in the doc !
comment:18 Changed 9 years ago by
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
Description: | modified (diff) |
---|---|
Keywords: | distance added |
Reviewers: | → Frédéric Chapoton |
Status: | needs_review → 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:21 Changed 9 years ago by
Description: | modified (diff) |
---|
comment:22 Changed 9 years ago by
Description: | modified (diff) |
---|
comment:23 Changed 9 years ago by
Status: | positive_review → needs_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
Attachment: | 14619.patch added |
---|
Changed 9 years ago by
Attachment: | 14619-rev.patch added |
---|
comment:24 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → positive_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
Merged in: | → sage-5.12.beta5 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:26 Changed 9 years ago by
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
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 ] ]
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?