Opened 10 years ago
Closed 9 years ago
#10549 closed enhancement (fixed)
Improvements in canonical_form, is_isomorphic, and graph_isom_equivalent_non_edge_labeled_graph
Reported by: | stumpc5 | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | critical | Milestone: | sage-4.7.1 |
Component: | graph theory | Keywords: | graph, canonical form, isomorphism |
Cc: | rlm@…, aschilling | Merged in: | sage-4.7.1.alpha1 |
Authors: | Christian Stump, Robert Miller | Reviewers: | Robert Miller, Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11181 | Stopgaps: |
Description (last modified by )
This ticket implements several improvements in the three method in the summary.
Apply trac_10549_flat.patch.
Attachments (4)
Change History (30)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
- Reviewers set to Robert Miller
- Status changed from new to needs_work
Unfortunately, the patch here doeesn't finish the job. For example, on lines 13088--13814, the old translation is still used, and as a result several doctests fail, in sage/graphs/generic_graph.py
and sage/geometry/polyhedra/py
.
comment:3 follow-up: ↓ 4 Changed 9 years ago by
Sorry, that should have been lines 13808--13814.
Same thing also on line 14347.
Another problem is that copying graph backends is not currently implemented. However, it may seem to be when the line G._backend = copy( g._backend )
executes without error. It seems to be simply copying the link address:
sage: G = Graph(sparse=True) sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: G.num_verts() 5 sage: X = G.canonical_label(edge_labels=True) sage: G.num_verts() 10
So that really needs to be fixed.
Also, this could have better coding style: for i in [ v for v in g if v not in G_vertices ]:
. This could be for i in g if i not in G_vertices:
, as there is no need to construct a list there.
comment:4 in reply to: ↑ 3 Changed 9 years ago by
Replying to rlm:
Another problem is that copying graph backends is not currently implemented. However, it may seem to be when the line
G._backend = copy( g._backend )
executes without error.
I now only make G = copy( g ), so this is again quite slow. But I don't see a better way to do it, do you?
Also, this could have better coding style:
for i in [ v for v in g if v not in G_vertices ]:
. This could befor i in g if i not in G_vertices:
, as there is no need to construct a list there.
done.
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
The first patch looks very good. Since the ordering of canonical labels will now change for multi-edge and edge labeled graphs, this might be worth mentioning in the release note. Canonical labels are not in principle supposed to be stable from one release to the next, but they generally are. So it would be good to warn users about this.
As a result, I had to change one of the doctests in species.py
whose canonical label is relabeled. I am certainly happy with the first patch, so if someone can review my patch, then this ticket can be set to positive review.
comment:6 Changed 9 years ago by
- Status changed from needs_review to needs_work
Hellooooooo !!
Only two errors in a -testall -long :
sage -t -long sage-bug/sage/graphs/generic_graph.py ********************************************************************** File "/home/ncohen/sage/devel/sage-bug/sage/graphs/generic_graph.py", line 14686: sage: G.is_isomorphic(H, edge_labels=True) Expected: True Got: False ********************************************************************** File "/home/ncohen/sage/devel/sage-bug/sage/graphs/generic_graph.py", line 14688: sage: G.is_isomorphic(H, edge_labels=True, certify=True) Expected: {0: 1, 1: 2, 2: 3, 3: 4, 4: 0} Got: (False, None) **********************************************************************
(I'm running the latest alpha1)
By the way : would you know of a "cheap/elegant" way to deal with this :
sage: g = graphs.KneserGraph(8,2) sage: h = g.copy() sage: %timeit g.is_isomorphic(h) 125 loops, best of 3: 6.27 ms per loop sage: h.relabel() sage: %timeit g.is_isomorphic(h) 125 loops, best of 3: 4.72 ms per loop sage: g.relabel() sage: %timeit g.is_isomorphic(h) 125 loops, best of 3: 3.13 ms per loop
Or is it just because of the way labels are handled ?
Nathann
comment:7 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:8 Changed 9 years ago by
- Cc aschilling added
Changed 9 years ago by
comment:9 Changed 9 years ago by
I just posted a trivially rebased version of the patch trac_10549_refinements_graphs-cs.2.patch, which should now cleanly apply to sage-4.6.2. The same patch is now also in the sage-combinat queue (with the older version of the patch refinement_graphs-cs.patch disabled).
Anne
comment:10 Changed 9 years ago by
- Description modified (diff)
comment:11 Changed 9 years ago by
trac_10549_part2.patch correctly fixes a bug in isomorphisms of graphs when edge labels are supposed to be considered.
Anne
comment:12 Changed 9 years ago by
- Milestone set to sage-4.7
- Priority changed from major to critical
- Reviewers changed from Robert Miller to Robert Miller, Anne Schilling
- Status changed from needs_review to positive_review
Since you're happy with the second patch and I'm happy with the first, I'm setting this to positive review.
comment:13 Changed 9 years ago by
I somehow missed Nathann's message. Thanks for providing a patch!
Best, Christian
comment:14 Changed 9 years ago by
- Merged in set to sage-4.7.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:15 Changed 9 years ago by
- Merged in sage-4.7.alpha2 deleted
- Resolution fixed deleted
- Status changed from closed to new
Some problems on various Buildbot machines (probably the ones which are 32-bit):
sage -t -long -force_lib devel/sage/sage/combinat/species/species.py ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha2/devel/sage-main/sage/combinat/species/species.py", line 667: sage: list(sorted(labels.items())) Expected: [(Combinatorial species, 1), (Product of (Combinatorial species) and (Combinatorial species), 3), (Singleton species, 0), (Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species)), 2)] Got: [(Combinatorial species, 0), (Product of (Combinatorial species) and (Combinatorial species), 1), (Singleton species, 3), (Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species)), 2)] ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha2/devel/sage-main/sage/combinat/species/species.py", line 672: sage: g.edges() Expected: [(1, 2, None), (2, 0, None), (2, 3, None), (3, 1, None), (3, 1, None)] Got: [(0, 2, None), (1, 0, None), (1, 0, None), (2, 1, None), (2, 3, None)] **********************************************************************
comment:16 Changed 9 years ago by
- Status changed from new to needs_work
Changed 9 years ago by
comment:17 Changed 9 years ago by
- Description modified (diff)
comment:18 Changed 9 years ago by
- Description modified (diff)
comment:19 Changed 9 years ago by
- Status changed from needs_work to needs_review
I'm setting this to needs_review, although note that its dependency #11181 is not quite ready yet.
comment:20 Changed 9 years ago by
Apply trac_10549_flat.patch
comment:21 Changed 9 years ago by
- Status changed from needs_review to positive_review
Positive review to this one !
Passes -testall -long, so I hope the many, many doctests scattered in Sage which use those methods would have gone ballistic in case I missed something dangerous :-)
Nathann
comment:22 Changed 9 years ago by
- Milestone changed from sage-4.7 to sage-4.7.1
comment:23 Changed 9 years ago by
- Dependencies set to #11181
- Description modified (diff)
comment:24 Changed 9 years ago by
- Status changed from positive_review to needs_work
This patch conflicts with #10804.
comment:25 Changed 9 years ago by
- Status changed from needs_work to positive_review
Go ahead and merge this one, I'll rebase the other one.
comment:26 Changed 9 years ago by
- Merged in set to sage-4.7.1.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
More specifically, one improvement this ticket makes is the following:
Before, if given an edge labeled graph, the automorphism group function would first translate this to a non-edge labeled graph of larger size. It would do so by making a vertex
('o',v)
for each original vertexv
, and also other vertices labeled('x', i)
.This ticket includes the optimization of using consecutive integers in the resulting graph instead of tuples to label the vertices. This removes a lot of overhead when translating back and forth, which makes the automorphism group function much faster.