b44cef29-61c4-4aab-a2e6-dc3c8c58c1be
commented
4 years ago Commit: 6f92bcf
Open b44cef29-61c4-4aab-a2e6-dc3c8c58c1be opened 4 years ago
b44cef29-61c4-4aab-a2e6-dc3c8c58c1be
commented
4 years ago Commit: 6f92bcf
b44cef29-61c4-4aab-a2e6-dc3c8c58c1be
commented
4 years ago Branch: public/graphs/30456
b44cef29-61c4-4aab-a2e6-dc3c8c58c1be
commented
4 years ago Last 10 new commits:
41a0966 | added some docstrings; changed some code |
a7dc1b5 | completed docstrings and bibliography |
36e6032 | added tests |
a0463d5 | fix docsrtings; renamed module |
5d16394 | renamed in design_catalog |
e6ff3fa | Merge branch 't/30223' into t/30337 |
3e1df8c | added const to half cube |
0d92ec4 | Merge branch 't/30329' into t/30337 |
376d459 | convert matrices in bilinearFormsGraph to integers to lower memory requirements |
6f92bcf | Merge branch 't/30337' into drg_hermitian_cover |
dcoudert
commented
3 years ago needs to be rebased.
dimpase
commented
3 years ago Changed branch from public/graphs/30456 to u/dimpase/graphs/30456
dimpase
commented
3 years ago Last 10 new commits:
c5f0f3d | fixed most sporadic graphs; added some docstring; added method to graphs |
f675f2c | completed sporadic database; added more docstrings; added basic checks |
e4b1d59 | fixed docstring and doctests |
9aa7d07 | fixed existence checks without drg module |
4bba926 | added doctests to _integersection_array_from_graph |
0a9a194 | fix bug; avoid long computations on import - typo fixed |
f9bb39a | Merge branch 'public/graphs/30356' into public/graphs/30386 |
bbb799f | Merge branch 'public/graphs/30386' into public/graphs/30414 |
e615813 | Merge branch 'public/graphs/30414' into public/graphs/30441 |
5ca6545 | Merge branch 'public/graphs/30441' into public/graphs/30456 |
dimpase
commented
3 years ago Reviewer: Dima Pasechnik
dimpase
commented
3 years ago folded_graph() seems to have a bug:
sage: from sage.graphs.generators.distance_regular import hermitian_cover
sage: G = hermitian_cover(2, 3); G
Antipodal 3-cover of K_9: Graph on 27 vertices
sage: G.is_antipodal()
True
sage: G.is_distance_regular(True)
([8, 6, 1, None], [None, 1, 3, 8])
sage: G.folded_graph()
Folded Antipodal 3-cover of K_9: Graph on 9 vertices
sage: H=G.folded_graph()
sage: H.is_isomorphic(graphs.CompleteGraph(9))
False
sage: H
Folded Antipodal 3-cover of K_9: Graph on 9 vertices
sage: H.edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None), (0, 5, None), (0, 6, None), (0, 7, None), (0, 8, None), (1, 2, None), (1, 3, None), (1, 4, None), (1, 5, None), (1, 6, None), (1, 7, None), (1, 8, None), (2, 3, None), (2, 4, None), (2, 5, None), (2, 6, None), (2, 7, None), (2, 8, None), (3, 4, None), (3, 5, None), (3, 6, None), (3, 7, None), (3, 8, None), (4, 6, None), (4, 8, None), (5, 6, None), (5, 7, None), (5, 8, None), (6, 7, None), (6, 8, None), (7, 8, None)]
sage: (4,7,None) in H.edges()
FalseCould be this in folded_graph, if I understand the definition.
for i, j in itertools.combinations(range(numCliques), 2):
- if any(self.has_edge(u, v) for u, v in
+ if any(G.has_edge(u, v) for u, v in
itertools.product(newVertices[i], newVertices[j])):
edges.append((i, j))Replying to @dcoudert:
Could be this in
folded_graph, if I understand the definition.for i, j in itertools.combinations(range(numCliques), 2): - if any(self.has_edge(u, v) for u, v in + if any(G.has_edge(u, v) for u, v in itertools.product(newVertices[i], newVertices[j])): edges.append((i, j))
no, this is OK, as G is antipodality equivalence relation.
Actually, I don't get why it's not implemented as follows
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -9090,21 +9090,7 @@ class Graph(GenericGraph):
sage: G.folded_graph()
Folded Graph: Graph on 1 vertex
"""
- G = self.antipodal_graph()
-
- vertices = set(G)
- newVertices = []
- while vertices:
- v = vertices.pop()
- clique = frozenset(G.neighbor_iterator(v, closed=True))
-
- if check:
- for u in clique:
- if frozenset(G.neighbor_iterator(u, closed=True)) != clique:
- return False
-
- newVertices.append(clique)
- vertices.difference_update(clique)
+ newVertices = self.antipodal_graph().connected_components()
# now newVertices is a map {0, ..., numCliques-1} -> antipodal classes
numCliques = len(newVertices)with the change I propose above, there still a heisenbug there.
dimpase
commented
3 years ago OK, in my code one still needs to check that every component is a clique (if check)
dimpase
commented
3 years ago Also I wonder why
sage: graphs.distance_regular_graph([125, 96, 1, 1, 48, 125])
Antipodal 3-cover of K_126: Graph on 378 verticesfails. Is this graph unknown, or the construction is not implemented, or it's implemented, but buggy?
Ivo, do you recall the story?
b44cef29-61c4-4aab-a2e6-dc3c8c58c1be
commented
3 years ago Replying to @dcoudert: If you think the documentation is hard to understand, then it is worth changing it
Replying to @dimpase: Using connected_components should do the trick. I don't remember any specific reasons for the other implementation.
Replying to @dimpase:
That should work and it does on my old version of sage. If it fails with the latest version, then I would guess that the bug is in sage.graphs.generators.distance_regular.hermitian_cover and not in folded_graph.
hermitian_cover(5,3) should give the antipodal 3-cover of K_126. It relies heavily on GAP, so maybe the newer version of it broke the code.
dimpase
commented
3 years ago Replying to @Ivo-Maffei:
Replying to @dimpase: That should work and it does on my old version of sage. If it fails with the latest version, then I would guess that the bug is in
sage.graphs.generators.distance_regular.hermitian_coverand not infolded_graph.hermitian_cover(5,3)should give the antipodal 3-cover of K_126. It relies heavily on GAP, so maybe the newer version of it broke the code.
sage: from sage.graphs.generators.distance_regular import hermitian_cover
sage: g=hermitian_cover(5,3);g
Antipodal 3-cover of K_126: Graph on 378 vertices
sage: g.is_distance_regular(True)
([125, 96, 1, None], [None, 1, 48, 125])
sage: graphs.distance_regular_graph([125, 96, 1, 1, 48, 125])
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
<ipython-input-4-9d52c5386185> in <module>
----> 1 graphs.distance_regular_graph([Integer(125), Integer(96), Integer(1), Integer(1), Integer(48), Integer(125)])
/home/scratch2/dimpase/sage/sage/local/lib64/python3.7/site-packages/sage/graphs/generators/distance_regular.pyx in sage.graphs.generators.distance_regular.distance_regular_graph (build/cythonized/sage/graphs/generators/distance_regular.c:46604)()
3003 if existence:
3004 return Unknown
-> 3005 raise RuntimeError(
3006 f"No distance-regular graph with intersection array {arr} known")
RuntimeError: No distance-regular graph with intersection array [125, 96, 1, 1, 48, 125] known
sage: graphs.distance_regular_graph([64, 60, 1, 1, 15, 64])
Graph on 325 vertices
sage: graphs.distance_regular_graph([64, 60, 1, 1, 15, 64]).is_distance_regular(True)
([64, 60, 1, None], [None, 1, 15, 64])
sage: from sage.graphs.generators.distance_regular import is_hermitian_cover
sage: is_hermitian_cover([125, 96, 1, 1, 48, 125])
(5, 3)
sage: is_hermitian_cover([64, 60, 1, 1, 15, 64])
(4, 5)the bug is in the code that actually decides whether such a graph exists/can be built by Sage, as you see from above. The (4,5)-cover is recognised, but (5,3) is not, even though both these graphs can be correctly built etc.
dimpase
commented
3 years ago ok, found the fix - I probably removed this line during a merge, by mistake
--- a/src/sage/graphs/generators/distance_regular.pyx
+++ b/src/sage/graphs/generators/distance_regular.pyx
@@ -2856,6 +2856,7 @@ _infinite_families_database = [
(is_pseudo_partition_graph, pseudo_partition_graph),
(is_near_polygon, near_polygon_graph),
(is_from_GQ_spread, graph_from_GQ_spread),
+ (is_hermitian_cover, hermitian_cover),
]
def distance_regular_graph(list arr, existence=False, check=True):It was confusing as [64, 60, 1, 1, 15, 64]-graph can also be built by graph_from_GQ_spread, but [125, 96, 1, 1, 48, 125] cannot.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313
commented
3 years ago 7ed8c4ca-6d56-4ae9-953a-41e42b4ed313
commented
3 years ago Branch pushed to git repo; I updated commit sha1. New commits:
ae0f9a8 | add hermitian_cover to _infinite_families DB |
dimpase
commented
3 years ago can't reproduce the Heisenbug I mention comment:5 reliably on one machine, and not at all on two other. Therefore, good enough for me.
dcoudert
commented
3 years ago With this version of the ticket, all tests pass on my side, but without the last commit, I have errors. So LGTM.
vbraun
commented
3 years ago **********************************************************************
File "src/sage/graphs/generators/distance_regular.pyx", line 2685, in sage.graphs.generators.distance_regular.hermitian_cover
Failed example:
H.is_isomorphic(graphs.CompleteGraph(9))
Expected:
True
Got:
False
**********************************************************************
1 item had failures:
1 of 11 in sage.graphs.generators.distance_regular.hermitian_cover
[225 tests, 1 failure, 246.05 s]The Heisenbug from comment:5 strikes again.
Volker, do you observe this in a non-random fashion? Could you provide more details on the box(es) you see this on?
dcoudert
commented
3 years ago I see the bug on my macOS laptop, but the list of edges is different than the one in comment:5
sage: from sage.graphs.generators.distance_regular import hermitian_cover
sage: G = hermitian_cover(2, 3); G
Antipodal 3-cover of K_9: Graph on 27 vertices
sage: G.is_antipodal()
True
sage: G.is_distance_regular(True)
([8, 6, 1, None], [None, 1, 3, 8])
sage: H = G.folded_graph(); H
Folded Antipodal 3-cover of K_9: Graph on 9 vertices
sage: H.is_isomorphic(graphs.CompleteGraph(9))
False
sage: H.edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None), (0, 5, None), (0, 6, None), (0, 7, None), (0, 8, None), (1, 2, None), (1, 4, None), (1, 5, None), (1, 6, None), (1, 7, None), (1, 8, None), (2, 3, None), (2, 4, None), (2, 5, None), (2, 6, None), (2, 7, None), (2, 8, None), (3, 4, None), (3, 5, None), (3, 6, None), (3, 7, None), (3, 8, None), (4, 5, None), (4, 6, None), (4, 7, None), (4, 8, None), (5, 6, None), (5, 7, None), (5, 8, None), (6, 7, None), (6, 8, None), (7, 8, None)]The current list of optional installed packages displayed while testing tickets is
Using --optional=bliss,build,dochtml,homebrew,pip,python_igraph,sage,sage_numerical_backends_cplex,sage_spkg,texttable.
mkoeppe
commented
3 years ago Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
dimpase
commented
3 years ago David, is the bug still observable for you on 9.3.rc0 ?
dcoudert
commented
3 years ago I tried over 9.3.rc0 and get the following surprising results:
Using --optional=bliss,build,dochtml,homebrew,pip,python_igraph,sage,sage_numerical_backends_cplex,sage_spkg,tdlib,texttable
Doctesting 1 file using 8 threads.
sage -t --long --warn-long 303.6 --random-seed=0 src/sage/graphs/generators/distance_regular.pyx
[225 tests, 157.94 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 158.1 seconds
cpu time: 147.1 seconds
cumulative wall time: 157.9 seconds
sapristi:sage dcoudert$ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.3.rc0, Release Date: 2021-03-23 │
│ Using Python 3.9.2. Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable. ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: from sage.graphs.generators.distance_regular import hermitian_cover
sage: G = hermitian_cover(2, 3); G
Antipodal 3-cover of K_9: Graph on 27 vertices
sage: G.is_antipodal()
True
sage: G.is_distance_regular(True)
([8, 6, 1, None], [None, 1, 3, 8])
sage: H = G.folded_graph(); H
Folded Antipodal 3-cover of K_9: Graph on 9 vertices
sage: H.is_isomorphic(graphs.CompleteGraph(9))
False
sage: H.edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None), (0, 6, None), (0, 7, None), (0, 8, None), (1, 2, None), (1, 3, None), (1, 5, None), (1, 6, None), (1, 7, None), (1, 8, None), (2, 3, None), (2, 4, None), (2, 5, None), (2, 6, None), (2, 7, None), (2, 8, None), (3, 5, None), (3, 6, None), (3, 7, None), (3, 8, None), (4, 6, None), (4, 8, None), (5, 6, None), (5, 8, None), (6, 7, None), (6, 8, None), (7, 8, None)]Setting a new milestone for this ticket based on a cursory review.
dcoudert
commented
3 years ago Today, I don't see the bug on macOS. Is it a good news ?
sapristi:sage dcoudert$ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.5.beta0, Release Date: 2021-08-31 │
│ Using Python 3.9.5. Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable. ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: from sage.graphs.generators.distance_regular import hermitian_cover
sage: G = hermitian_cover(2, 3); G
Antipodal 3-cover of K_9: Graph on 27 vertices
sage: G.is_antipodal()
True
sage: G.is_distance_regular(True)
([8, 6, 1, None], [None, 1, 3, 8])
sage: H = G.folded_graph(); H
Folded Antipodal 3-cover of K_9: Graph on 9 vertices
sage: H.is_isomorphic(graphs.CompleteGraph(9))
True
sage: H.is_clique()
TrueI have the following optional packages installed: bliss,build,dochtml,homebrew,pip,sage,sage_numerical_backends_coin,sage_numerical_backends_cplex,sage_spkg
Added a construction for antipodal covers of complete graphs. The construction is made available through
graphs.distance_regular_graphDepends on #30441
Component: graph theory
Author: Ivo Maffei
Branch/Commit: u/dimpase/graphs/30456 @
ae0f9a8Reviewer: Dima Pasechnik
Issue created by migration from https://trac.sagemath.org/ticket/30456