#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 )
Attachments (2)
Change History (30)
comment:1 follow-ups: ↓ 2 ↓ 7 Changed 8 years ago by
comment:2 in reply to: ↑ 1 Changed 8 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 8 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 8 years ago by
- Status changed from new to needs_review
comment:5 follow-up: ↓ 6 Changed 8 years ago by
Nice!
Well for the certificate.. Perhaps not really a certificate but a distance partition.
comment:6 in reply to: ↑ 5 Changed 8 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 in reply to: ↑ 1 ; follow-up: ↓ 8 Changed 8 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 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.
comment:8 in reply to: ↑ 7 Changed 8 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 8 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 in reply to: ↑ 9 ; follow-up: ↓ 11 Changed 8 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 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 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 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 8 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 in reply to: ↑ 12 Changed 8 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 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:15 follow-up: ↓ 16 Changed 7 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 in reply to: ↑ 15 Changed 7 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 7 years ago by
almost good to go. I would like this function to appear in the doc !
comment:18 in reply to: ↑ 17 Changed 7 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 7 years ago by
- 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 7 years ago by
Cool. Thaaaaaaaaaaaaaaaaaanks ! :-)
Nathann
comment:21 Changed 7 years ago by
- Description modified (diff)
comment:22 Changed 7 years ago by
- Description modified (diff)
comment:23 Changed 7 years ago by
- 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 7 years ago by
Changed 7 years ago by
comment:24 Changed 7 years ago by
- 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 7 years ago by
- Merged in set to sage-5.12.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
comment:26 Changed 7 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 7 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 ] ]
comment:28 Changed 7 years ago by
see #15864 for a fix.
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?