Opened 6 weeks ago
Last modified 9 days ago
#27232 needs_review defect
is_isomorphic broken with keyword edge_labels=True
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  py3, graph, cyclotomic, matrix, permutation_of, graph, is_isomorphic 
Cc:  vdelecroix, tscrim, stumpc5, dcoudert, dimpase  Merged in:  
Authors:  David Coudert  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/dcoudert/27232_fix_morphisms (Commits)  Commit:  46375819947fdfa6f3f9aaaf3e98252979724a1a 
Dependencies:  Stopgaps: 
Description (last modified by )
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]
Change History (21)
comment:1 Changed 6 weeks ago by
comment:2 followup: ↓ 3 Changed 6 weeks ago by
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 6 weeks ago by
Replying to vdelecroix:
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 6 weeks ago by
 Cc dcoudert added
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 6 weeks ago by
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 6 weeks ago by
 Branch set to public/27232_first_trial
 Cc dimpase added
 Commit set to a1f9014ce505baaad8d6bbfb5cb352d09c526690
 Keywords graph is_isomorphic added
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 followup: ↓ 8 Changed 5 weeks ago by
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
 whether labels have a total order (and provide a comparison function)
 whether labels are hashable (and provide a hash function)
 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 4 weeks ago by
 Component changed from algebra to graph theory
Replying to 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
 whether labels have a total order (and provide a comparison function)
 whether labels are hashable (and provide a hash function)
 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 4 weeks ago by
 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 followup: ↓ 11 Changed 11 days ago by
 Branch changed from public/27232_first_trial to u/dcoudert/27232_fix_morphisms
 Commit changed from a1f9014ce505baaad8d6bbfb5cb352d09c526690 to 27ca32d8949849fa36f6c1460c2d5f75cb773b08
 Keywords py3 added
 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 11 days ago by
Replying to dcoudert:
Help needed: I use method
filterfalse
from itertools, but it'ss calledifilterfalse
in Python 2 andfilterfalse
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 11 days ago by
 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 11 days ago by
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 11 days ago by
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 nontrivial automorphisms as in this example).
comment:15 Changed 11 days ago by
 Commit changed from 1b9879a3b60e003813d36fe28f7f2567f6207b7c to c4e8db78ff6813ff32db44d8c824f9ade889e7c2
comment:16 Changed 11 days ago by
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 followup: ↓ 18 Changed 11 days ago by
Maybe functools.cmp_to_key(func) from https://docs.python.org/3/library/functools.html ?
comment:18 in reply to: ↑ 17 ; followup: ↓ 19 Changed 11 days ago by
Replying to dimpase:
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 ; followup: ↓ 20 Changed 10 days ago by
Replying to dcoudert:
Replying to 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 10 days ago by
the comparison used in Python2, I gather.
But we don't have it, right ?
comment:21 Changed 9 days ago by
 Commit changed from c4e8db78ff6813ff32db44d8c824f9ade889e7c2 to 46375819947fdfa6f3f9aaaf3e98252979724a1a
Branch pushed to git repo; I updated commit sha1. New commits:
4637581  trac #27232: pyflakes

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