Opened 3 years ago

Closed 3 years ago

# is_isomorphic broken with keyword edge_labels=True

Reported by: Owned by: jipilab major sage-8.9 graph theory py3, graph, cyclotomic, matrix, permutation_of, graph, is_isomorphic vdelecroix, tscrim, stumpc5, dcoudert, dimpase David Coudert Travis Scrimshaw, John Palmieri N/A b2218f2 b2218f2211d995dd44daeabe3ad9e18f5f3c4a9a

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 `CyclotomicField`s:

```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]
```

### comment:1 Changed 3 years ago by jipilab

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]
```

### comment:2 follow-up: ↓ 3 Changed 3 years ago by vdelecroix

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

### comment:3 in reply to: ↑ 2 Changed 3 years ago by jipilab

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` !!!

### comment:4 Changed 3 years ago by vdelecroix

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

### comment:5 Changed 3 years ago by dcoudert

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...

### comment:6 Changed 3 years ago by dcoudert

• Branch set to public/27232_first_trial

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`

### comment:7 follow-up: ↓ 8 Changed 3 years ago by vdelecroix

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`.

### comment:8 in reply to: ↑ 7 Changed 3 years ago by jipilab

• Component changed from algebra to graph theory

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.

### comment:9 Changed 3 years ago by jipilab

• Description modified (diff)
• Summary changed from is_permutation_of broken for matrices over cyclotomic fields to is_isomorphic broken with keyword edge_labels=True

### comment:10 follow-up: ↓ 11 Changed 3 years ago by dcoudert

• Authors set to David Coudert
• Branch changed from public/27232_first_trial to u/dcoudert/27232_fix_morphisms
• Commit changed from a1f9014ce505baaad8d6bbfb5cb352d09c526690 to 27ca32d8949849fa36f6c1460c2d5f75cb773b08
• Status changed from new to needs_review

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**`

### comment:11 in reply to: ↑ 10 Changed 3 years ago by tscrim

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
```

### comment:12 Changed 3 years ago by git

• Commit changed from 27ca32d8949849fa36f6c1460c2d5f75cb773b08 to 1b9879a3b60e003813d36fe28f7f2567f6207b7c

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

 ​1b9879a `trac #27232: get rid of filterfalse`

### comment:13 Changed 3 years ago by dcoudert

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.

### comment:14 Changed 3 years ago by tscrim

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

### comment:15 Changed 3 years ago by git

• Commit changed from 1b9879a3b60e003813d36fe28f7f2567f6207b7c to c4e8db78ff6813ff32db44d8c824f9ade889e7c2

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

 ​0df542d `trac #27232: Merged with 8.7.beta7` ​c4e8db7 `trac #27232: fix issue in coxeter_matrix`

### comment:16 Changed 3 years ago by dcoudert

Right, we need a method returning a total ordering of hashable (vertices) or unhashable (labels) objects. It's the only way to ensure the correctness of the methods here. But how to write something reasonably fast ? and where to put it ?

### comment:17 follow-up: ↓ 18 Changed 3 years ago by dimpase

Maybe functools.cmp_to_key(func) from https://docs.python.org/3/library/functools.html ?

### comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 3 years ago by dcoudert

Maybe functools.cmp_to_key(func) from https://docs.python.org/3/library/functools.html ?

But what should be the function ?

### comment:19 in reply to: ↑ 18 ; follow-up: ↓ 20 Changed 3 years ago by dimpase

Maybe functools.cmp_to_key(func) from https://docs.python.org/3/library/functools.html ?

But what should be the function ?

the comparison used in Python2, I gather.

### comment:20 in reply to: ↑ 19 Changed 3 years ago by dcoudert

the comparison used in Python2, I gather.

But we don't have it, right ?

### comment:21 Changed 3 years ago by git

• Commit changed from c4e8db78ff6813ff32db44d8c824f9ade889e7c2 to 46375819947fdfa6f3f9aaaf3e98252979724a1a

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

 ​4637581 `trac #27232: pyflakes`

### comment:22 Changed 3 years ago by embray

• Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

### comment:23 Changed 3 years ago by embray

• Milestone changed from sage-8.8 to sage-8.9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

### comment:24 Changed 3 years ago by git

• Commit changed from 46375819947fdfa6f3f9aaaf3e98252979724a1a to 94ebadffc21bfabb7ab29fbfe6e5fb3e4f24739d

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

 ​94ebadf `trac #27232: Merged with 8.9.beta1`

### comment:25 Changed 3 years ago by dcoudert

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

### comment:26 Changed 3 years ago by jhpalmieri

What do you think about these minor changes?

• ## src/sage/graphs/generic_graph.py

```diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index 00e39838fe..71424d5e2b 100644```
 a 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?

### comment:27 Changed 3 years ago by git

• Commit changed from 94ebadffc21bfabb7ab29fbfe6e5fb3e4f24739d to c871bcf8a1075419814e951603f9f02dd4a58c0a

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`

### comment:28 Changed 3 years ago by dcoudert

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

### comment:29 Changed 3 years ago by jhpalmieri

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.

### comment:30 Changed 3 years ago by jhpalmieri

• Branch changed from u/dcoudert/27232_fix_morphisms to u/jhpalmieri/27232_fix_morphisms

### comment:31 Changed 3 years ago by jhpalmieri

• Commit changed from c871bcf8a1075419814e951603f9f02dd4a58c0a to 2fb0b526d6f408d529dee597e6b8414ed6c4d19d
• Reviewers set to Travis Scrimshaw, Dima Pasechnik, John Palmieri

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`

### comment:32 Changed 3 years ago by dimpase

• Reviewers changed from Travis Scrimshaw, Dima Pasechnik, John Palmieri to Travis Scrimshaw, John Palmieri

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

### comment:33 Changed 3 years ago by git

• Commit changed from 2fb0b526d6f408d529dee597e6b8414ed6c4d19d to 27046de75e34d67f536462c00bcd1550d2a0fb63

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

 ​27046de `trac 27232: some documentation changes`

### comment:34 Changed 3 years ago by dcoudert

A small typo

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

### comment:35 Changed 3 years ago by dcoudert

• Branch changed from u/jhpalmieri/27232_fix_morphisms to public/graphs/27232_fix_morphisms
• Commit changed from 27046de75e34d67f536462c00bcd1550d2a0fb63 to b2218f2211d995dd44daeabe3ad9e18f5f3c4a9a

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

New commits:

 ​b2218f2 `trac #27232: a small typo`

### comment:36 Changed 3 years ago by dcoudert

• Status changed from needs_review to positive_review

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.

### comment:37 Changed 3 years ago by vbraun

• Branch changed from public/graphs/27232_fix_morphisms to b2218f2211d995dd44daeabe3ad9e18f5f3c4a9a
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.