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 jdemeyer)

This ticket implements several improvements in the three method in the summary.

Apply trac_10549_flat.patch.

Attachments (4)

trac_10549_refinements_graphs-cs.patch (21.2 KB) - added by stumpc5 9 years ago.
trac_10549_part2.patch (7.4 KB) - added by rlm 9 years ago.
apply after other patch
trac_10549_refinements_graphs-cs.2.patch (21.2 KB) - added by aschilling 9 years ago.
trac_10549_flat.patch (24.5 KB) - added by rlm 9 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 9 years ago by rlm

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 vertex v, 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.

comment:2 Changed 9 years ago by rlm

  • 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: Changed 9 years ago by rlm

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 stumpc5

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 be for 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 stumpc5

comment:5 Changed 9 years ago by rlm

  • 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 ncohen

  • 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 rlm

  • Status changed from needs_work to needs_review

Changed 9 years ago by rlm

apply after other patch

comment:8 Changed 9 years ago by aschilling

  • Cc aschilling added

Changed 9 years ago by aschilling

comment:9 Changed 9 years ago by aschilling

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 rlm

  • Description modified (diff)

comment:11 Changed 9 years ago by aschilling

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 rlm

  • Authors changed from Christian Stump to Christian Stump, Robert Miller
  • 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 stumpc5

I somehow missed Nathann's message. Thanks for providing a patch!

Best, Christian

comment:14 Changed 9 years ago by jdemeyer

  • 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 jdemeyer

  • 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 jdemeyer

  • Status changed from new to needs_work

Changed 9 years ago by rlm

comment:17 Changed 9 years ago by rlm

  • Description modified (diff)

comment:18 Changed 9 years ago by rlm

  • Description modified (diff)

comment:19 Changed 9 years ago by rlm

  • 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 stumpc5

Apply trac_10549_flat.patch

comment:21 Changed 9 years ago by ncohen

  • 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 jdemeyer

  • Milestone changed from sage-4.7 to sage-4.7.1

comment:23 Changed 9 years ago by jdemeyer

  • Dependencies set to #11181
  • Description modified (diff)

comment:24 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This patch conflicts with #10804.

comment:25 Changed 9 years ago by rlm

  • 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 jdemeyer

  • Merged in set to sage-4.7.1.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.