is_isomorphic broken with keyword edge_labels=True

[jplab]

This code led to finding this bug in the is_isomorphic method.

Here is a simple working example:

sage: m1 = matrix(ZZ, [[1, -1, -1], [-1, -1, -1], [1, 0, -1]])
sage: m2 = matrix(ZZ, [[-1, -1, -1], [-1, 1, -1], [-1, 1, 0]])

The two matrices are equal up to permutation of rows and columns:

sage: m1.is_permutation_of(m2)
True

But, not over CyclotomicFields:

sage: CF = CyclotomicField(1)
sage: p1 = matrix(CF, [[1, -1, -1], [-1, -1, -1], [1, 0, -1]])
sage: p2 = matrix(CF, [[-1, -1, -1], [-1, 1, -1], [-1, 1, 0]])
sage: p1.is_permutation_of(p2)
False

Even with 2 is also does not work:

sage: CF = CyclotomicField(2)
sage: p1 = matrix(CF, [[1, -1, -1], [-1, -1, -1], [1, 0, -1]])
sage: p2 = matrix(CF, [[-1, -1, -1], [-1, 1, -1], [-1, 1, 0]])
sage: p1.is_permutation_of(p2)
False

This error is provoked at the level of graphs:

sage: g1 = p1.as_bipartite_graph()
sage: g2 = p2.as_bipartite_graph()
sage: sorted(g1.edge_labels())
[1, -1, -1, -1, -1, -1, 1, 0, -1]
sage: sorted(g2.edge_labels())
[-1, -1, -1, -1, 1, -1, -1, 1, 0]

CC: @videlec @tscrim @stumpc5 @dcoudert @dimpase

Component: graph theory

Keywords: cyclotomic, matrix, permutation_of, is_isomorphic

Author: David Coudert

Branch/Commit: b2218f2

Reviewer: Travis Scrimshaw, John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/27232

[jplab]

comment:1

Here is the current issue, sorting is broken on the CyclotomicField:

sage: g1 = p1.as_bipartite_graph()
sage: g2 = p2.as_bipartite_graph()
sage: sorted(g1.edge_labels())
[1, -1, -1, -1, -1, -1, 1, 0, -1]
sage: sorted(g2.edge_labels())
[-1, -1, -1, -1, 1, -1, -1, 1, 0]

[videlec]

comment:2

This code is crap. How can you assume that the elements of your ring could be sorted with respect to some total order?

[jplab]

comment:3

Replying to @videlec:

This code is crap. How can you assume that the elements of your ring could be sorted with respect to some total order?

Right! :-S I was quite puzzled when saw that this was done!!

That step in the _is_isomorphic method of graph with the option edge_labels=True should be repaired so that it makes sense...

The above code came up while looking at two character tables coming from two isomorphic groups. They should be equal up to permutation of columns and rows, but it was returns False !!!

[videlec]

comment:4

This is indeed annoying. Many graphs problem like this one have to be fixed with the switch to Python3 (where comparison might simply throw errors)...

[dcoudert]

comment:5

Agreed. Many progresses have been done in the graph module and a lot remains to be done. Help fixing problems / reviewing tickets is more than welcome :P

I tried the example with Python 2 and 3 and the answer is False in both cases and it is effectively due to the test if edge_labels and sorted(self.edge_labels()) != sorted(other.edge_labels()): that is False here for the reason explained above (#comment:2).

Do you have any suggestion on how to compare the 2 lists of edge labels knowing that edge labels can be unhashable ?

May be this ticket could be moved to the graph component as it will only touch method is_isomorphic ? Could make it easier to trac changes in the graph module...

[dcoudert]

Commit: a1f9014

[dcoudert]

Branch: public/27232_first_trial

[dcoudert]

Changed keywords from cyclotomic, matrix, permutation_of to cyclotomic, matrix, permutation_of, is_isomorphic

[dcoudert]

comment:6

I tried many stuff today without success. This is really one of the major issue of the graph module.

We can do a simple hack to replace the test sorted(self.edge_labels()) != sorted(other.edge_labels()) in method is_isomorphic of generic_graph.py. This is not nice/efficient but it does the job.

                def same_edge_labels(self_labels, other_labels):
                    """
                    Check that the lists have exactly the same content.
                    This is slower than sorting and checking equality, but safe
                    for Python3.
                    """
                    for label in self_labels:
                        if label in other_labels:
                            other_labels.remove(label)
                        else:
                            return False
                    return not other_labels

However, this is far from enough as method graph_isom_equivalent_non_edge_labeled_graph sorts many times lists of edge labels. I tried to remove these sortings, but I don't have a sufficient understanding of the methods to know what is correct, what is not and more importantly, what is assumed as input/output of other methods like those of sage.groups.perm_gps.partn_ref.refinement_graphs, etc.

I'm pushing in a public branch what I tried to do. Feel free to modify/correct/etc. and even suppress if you believe it is not a good approach to fix the problem. It's breaking doctests in is_isomorphic and canonical_label...

PS: The cost to pay for accepting anything as an edge label is really high :(

---

New commits:

a1f9014

trac #27232: first trial

[videlec]

comment:7

There is indeed a general problem with labels (not only for graphs). Ideally, when one has a structure with labels, one should be able to specify

1. whether labels have a total order (and provide a comparison function)
2. whether labels are hashable (and provide a hash function)
3. if neither 1. nor 2. applies, be prepared for costly checks

In the current situation, if 1. applies, you can use sort and if 2. applies you can use Python set.

[jplab]

comment:8

Replying to @videlec:

There is indeed a general problem with labels (not only for graphs). Ideally, when one has a structure with labels, one should be able to specify

1. whether labels have a total order (and provide a comparison function)
2. whether labels are hashable (and provide a hash function)
3. if neither 1. nor 2. applies, be prepared for costly checks

In the current situation, if 1. applies, you can use sort and if 2. applies you can use Python set.

That sounds like a reasonable ideal. It does not sound too idealistic either.

[dcoudert]

Changed branch from public/27232_first_trial to u/dcoudert/27232_fix_morphisms

[dcoudert]

comment:10

I pushed a new branch to fix the issues with is_isomorphic, and in particular with graph_isom_equivalent_non_edge_labeled_graph. It seems to fix all remaining failing doctests in generic_graph.py in Python 3.

It took me some time to understand the method, and in particular why and when sort is needed. I reduced the number of places where sort is used, and used sorted(..., key=str) to sort hazardous objects (i.e., list of edge labels). For sure some users will invent another kind of edge labels for which this will not work, but unless we implement everywhere the remarks of #comment:7, and so force the user to specify the sort method, I don't see how we can magically answer all requirements.

Help needed: I use method filterfalse from itertools, but it'ss called ifilterfalse in Python 2 and filterfalse in Python 3. I used a try .. except to import it, but there is certainly a smarter way.

Please review, check, double check, do some tests, etc.

---

New commits:

27ca32d

trac #27232: fix **morphism**

[dcoudert]

Author: David Coudert

[dcoudert]

Changed commit from a1f9014 to 27ca32d

[tscrim]

comment:11

Replying to @dcoudert:

Help needed: I use method filterfalse from itertools, but it'ss called ifilterfalse in Python 2 and filterfalse in Python 3. I used a try .. except to import it, but there is certainly a smarter way.

Get rid of filterfalse:

-    for label in filterfalse(edge_labels.__contains__, G.edge_labels()):
+    for label in G.edge_labels():
+        if label in edge_labels:
+            continue

Although I might also unroll G.edge_labels() and do

    for _,_,label in G.edge_iterator():
        if label in edge_labels:
            continue

[sagetrac-git]

Changed commit from 27ca32d to 1b9879a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1b9879a

trac #27232: get rid of filterfalse

[dcoudert]

comment:13

done.

There is this doctest error:

sage -t --long src/sage/combinat/root_system/coxeter_matrix.py
**********************************************************************
File "src/sage/combinat/root_system/coxeter_matrix.py", line 1041, in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
Failed example:
    CoxeterMatrix(CoxeterType(['A',10,1]).coxeter_graph()).coxeter_type()
Expected:
    Coxeter type of ['A', 10, 1]
Got:
    Coxeter type of ['A', 10, 1] relabelled by {0: 2, 1: 3, 2: 4, 3: 5, 4: 6, 5: 7, 6: 8, 7: 9, 8: 10, 9: 0, 10: 1}

Can anyone tell if it's something serious or if it is sufficient to replace the expected output or the example.

[tscrim]

comment:14

You should not update the output for this test. Here there is an implicit ordering on the vertices and it is not detecting that they should match (instead it is a rotation of the cycle graph by 2 steps). This might be a case where we should force the isomorphism test to (attempt to) sort the output as we need this labeling to be canonical (as there are generally non-trivial automorphisms as in this example).

[sagetrac-git]

Changed commit from 4637581 to 94ebadf

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

94ebadf

trac #27232: Merged with 8.9.beta1

[dcoudert]

comment:25

Rebased on last beta.

This ticket is certainly the last big py3 issue in the graph module.
So any comment / help / /idea for improving / etc. is more than welcome :)

[jhpalmieri]

comment:26

What do you think about these minor changes?

diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index 00e39838fe..71424d5e2b 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -23995,13 +23995,13 @@ def graph_isom_equivalent_non_edge_labeled_graph(g, partition=None, standard_lab
             edge_partition = [el[1] for el in edge_partition]
             edge_partition = [list(chain(*edge_partition))]
 
-        # An edge between u and v with label l and multiplicity k being encoded
-        # as an uv edge with label [l,k], we must not assume that an edge with
-        # multiplicity 2 is equivalent to a simple edge !
-        # Hence, we still distinguish edges with different multiplicity
-        if g_has_multiple_edges:
+        else: # g_has_multiple_edges
+            # An edge between u and v with label l and multiplicity k being encoded
+            # as an uv edge with label [l,k], we must not assume that an edge with
+            # multiplicity 2 is equivalent to a simple edge!
+            # Hence, we still distinguish edges with different multiplicity.
 
-            # Gather the partitions of edges with same multiplicity
+            # Gather the partitions of edges with same multiplicity.
             tmp = {}
             for el, part in edge_partition:
                 # The multiplicity of a label is the number of edges from u to v

I don't have any other comments. Is everyone else happy with this branch?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

deca71a	trac #27232: Merged with 8.9.beta2
c871bcf	trac #27232: implement reviewer suggestion

[sagetrac-git]

Changed commit from 94ebadf to c871bcf

[dcoudert]

comment:28

I followed your idea and now it's if g_has_multiple_edges: .... else: ...

[jhpalmieri]

comment:29

Great! As I said, I'm happy. Others have looked more carefully at this, so I would like to hear from them before setting this to positive review.

[jhpalmieri]

Changed branch from u/dcoudert/27232_fix_morphisms to u/jhpalmieri/27232_fix_morphisms

[jhpalmieri]

Changed commit from c871bcf to 2fb0b52

[jhpalmieri]

Reviewer: Travis Scrimshaw, Dima Pasechnik, John Palmieri

[jhpalmieri]

comment:31

I found the documentation a little confusing, so here are some changes. @dcoudert, if you are happy with them, then I think we can set this to positive review.

---

New commits:

2fb0b52

trac 27232: some documentation changes

[dimpase]

Changed reviewer from Travis Scrimshaw, Dima Pasechnik, John Palmieri to Travis Scrimshaw, John Palmieri

[dimpase]

comment:32

Sorry, I'll better let this to others, not enough time before going on vacation.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

27046de

trac 27232: some documentation changes

[sagetrac-git]

Changed commit from 2fb0b52 to 27046de

[dcoudert]

comment:34

A small typo

-    edge labeled with a list ``[[label1, multiplicity], [label1,
+    edge labeled with a list ``[[label1, multiplicity], [label2,

[dcoudert]

Changed commit from 27046de to b2218f2

[dcoudert]

comment:35

I did the correction and pushed to a new branch in public/

---

New commits:

b2218f2

trac #27232: a small typo

[dcoudert]

Changed branch from u/jhpalmieri/27232_fix_morphisms to public/graphs/27232_fix_morphisms

[dcoudert]

comment:36

I'm happy with all these modification. The code is much better now and fix py3 failing doctests. Further improvements are certainly possible, but let's do them in another patch.

Thank you all for the help.

[vbraun]

Changed branch from public/graphs/27232_fix_morphisms to b2218f2