Opened 4 years ago
Closed 23 months ago
#19517 closed defect (fixed)
Graphs: canonical_label() and several errors
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  d8dc267 (Commits)  Commit:  d8dc2670e73fa83f7b40f82e73b2b5028449cfac 
Dependencies:  Stopgaps: 
Description (last modified by )
On generic_graph.py
function canonical_label()
parameter return_graph
:
 The parameter has no effect when
algorithm='sage'
:
sage: G = Graph({10: [20]}) sage: G.canonical_label(algorithm='sage', return_graph=False) Graph on 2 vertices sage: G.canonical_label(algorithm='sage', return_graph=True) Graph on 2 vertices
compared to
sage: G.canonical_label(algorithm='bliss', return_graph=False) [(1, 0)] sage: G.canonical_label(algorithm='bliss', return_graph=True) Graph on 2 vertices
 Docstring is badly formulated. It should say that it returns list of edges of canonically labelled graph.
 Indentation in docstring is wrong.
 (And is it meaningful? Why not return dictionary of vertex relabeling instead of edges?)
Same function has other problem:
 Canonically relabeled graph forgets vertex positioning. This is contrary to
relabel
that remembers them. This can be seen with
P = graphs.PetersenGraph() P1 = graphs.PetersenGraph() P1.relabel(lambda x: chr(ord('a')+x)) P2 = P1.canonical_label() P.show() P1.show() P2.show()
Change History (32)
comment:1 Changed 4 years ago by
comment:2 followup: ↓ 3 Changed 4 years ago by
There is something strange with bliss
installation, see https://groups.google.com/forum/#!topic/sagedevel/_1OYNuVNltM
return_graph
is not converse of inplace
. I guess. It is badly documented. What is the meaning of it's output? A list of pairs somehow... Try
G = graphs.PetersenGraph() G.relabel(lambda x: chr(ord('a')+x)) G.canonical_label(return_graph=False)
And why it deletes vertex positioning contraty to relabel
? Try for example
G = graphs.PetersenGraph() G.relabel(lambda x: chr(ord('a')+x)) G.show() G = G.canonical_label() G.canonical_label().show()
comment:3 in reply to: ↑ 2 Changed 4 years ago by
There is something strange with
bliss
installation, see https://groups.google.com/forum/#!topic/sagedevel/_1OYNuVNltM
Something like that happened during the last update of bliss, but Jeroen noticed it at the last minute: http://trac.sagemath.org/ticket/19483#comment:15
return_graph
is not converse ofinplace
. I guess. It is badly documented. What is the meaning of it's output?
(assuming that you are talking of 'canonical_label')
return_graph
tells whether or not you want the actual graph. Somethimes you only need the labelling, and not the whole graph.
A list of pairs somehow... Try
G = graphs.PetersenGraph() G.relabel(lambda x: chr(ord('a')+x)) G.canonical_label(return_graph=False)
These pairs are the edges of the relabeled graph
sage: Graph(G.canonical_label(return_graph=False)) == graphs.PetersenGraph().canonical_label() True
Can't say that I see the point to return this instead of a Graph
object...
And why it deletes vertex positioning contraty to
relabel
? Try for example
Probably because the graph is built from the list of edges, instead of being built as a relabelled copy of the original graph. Why do you ask these questions like there is a mystical explanation behind? It's a bug, that's all. It just needs to be fixed.
Nathann
comment:4 Changed 4 years ago by
 Description modified (diff)
OK, modified the description. I do not think that forgetting vertex positions is necessarily a bug. But to remember them on relabel()
and to forget on canonical_label()
is.
comment:5 Changed 23 months ago by
 Branch set to u/jmantysalo/graphcanlabelpos
comment:6 Changed 23 months ago by
 Cc dcoudert added; ncohen removed
 Commit set to 753b8e03e2ea177bd51ae49711ed762172f32730
Getting back to this old ticket... First of all I changed the check for parameters to better understand what happens. Now algorithm='bliss'
will always raise an error if Bliss is not installed, even when the graph has multiedges and Bliss could not be used anyway.
I think that this should just compute canonical relabeling and call .relabel()
. That would take care the problem of vertex positions.
New commits:
753b8e0  Modify parameter checking.

comment:7 Changed 23 months ago by
 Milestone changed from sage6.10 to sage8.1
 Reviewers set to David Coudert
It's true that this method needs significant cleaning.
 The first line of description is not standard and could be
Return a canonical labeling of the vertices of this (di)graph
.  In the INPUT block, the parameters could be better explained
 an OUTPUT block could be useful as the output depends on the parameters
etc.
one doctest fails because I have bliss installed. So you could do:
 sage: G.canonical_label(edge_labels=True, certificate=True)  (Graph on 5 vertices, {0: 4, 1: 3, 2: 0, 3: 1, 4: 2}) + sage: G.canonical_label(edge_labels=True, certificate=True, algorithm='sage') + (Graph on 5 vertices, {0: 4, 1: 3, 2: 0, 3: 1, 4: 2}) + sage: G.canonical_label(edge_labels=True, certificate=True, algorithm='bliss') # optional  bliss + (Graph on 5 vertices, {{0: 4, 1: 3, 2: 1, 3: 0, 4: 2})
The last 2 lines might be placed with the examples using bliss.
comment:8 Changed 23 months ago by
 Commit changed from 753b8e03e2ea177bd51ae49711ed762172f32730 to 81f337a4f9a5ff89d4d9ab561441b795bbf40a31
Branch pushed to git repo; I updated commit sha1. New commits:
81f337a  Forbidden parameter combination.

comment:9 Changed 23 months ago by
Ah, I did not notice the line not edge_labels
I removed. Now corrected that one.
(These must also be said in INPUT
section.)
comment:10 Changed 23 months ago by
 Commit changed from 81f337a4f9a5ff89d4d9ab561441b795bbf40a31 to ac925246354752b6f27e6643efd2a7c6fccd0cd5
Branch pushed to git repo; I updated commit sha1. New commits:
ac92524  Docstring formatting.

comment:11 Changed 23 months ago by
Just noticed that Bliss with return_graph=False
returns set of edges, not a dictionary of mapping. Hence we must copy a part of relabel
:
attributes_to_update = ('_pos', '_assoc', '_embedding') for attr in attributes_to_update: if hasattr(self, attr) and getattr(self, attr) is not None: new_attr = {} for v,value in iteritems(getattr(self, attr)): new_attr[perm[v]] = value setattr(self, attr, new_attr)
comment:12 Changed 23 months ago by
Forget, I was blind when writing my last comment.
We could do something like
if algorithm == 'bliss': vert_dict = canonical_form(self, partition, certificate=True)[1] return self.relabel(vert_dict, inplace=not return_graph)
maybe... But what the hell this function is supposed to do??? certificate
seems a wrong word here, but at least certificate=True
works similarly with both algorithm='sage'
and algorithm='bliss'
.
comment:13 followup: ↓ 14 Changed 23 months ago by
Just came here after the sagedevel post by Jori. Is there anything controversial here? Or were you just fishing for reviewers :)
comment:14 in reply to: ↑ 13 Changed 23 months ago by
Replying to jdemeyer:
Just came here after the sagedevel post by Jori. Is there anything controversial here?
I guess not, but not sure, so I write a short message to sagedevel.
Or were you just fishing for reviewers :)
Not really. It would be more helpful to get comments about what this should do. certificate
vs. return_graph
 whaat?
comment:15 Changed 23 months ago by
 Commit changed from ac925246354752b6f27e6643efd2a7c6fccd0cd5 to b233fdf562e91531b70da45e98da9b7e228f6046
Branch pushed to git repo; I updated commit sha1. New commits:
b233fdf  Some corrections.

comment:16 Changed 23 months ago by
Some modifications to docstring. Now also vertex positions are preserved even when Bliss is used.
Must add many tests to this.
comment:17 Changed 23 months ago by
 Commit changed from b233fdf562e91531b70da45e98da9b7e228f6046 to 39ce1ef11371c37708ca72c72b26174136b1c2d7
Branch pushed to git repo; I updated commit sha1. New commits:
39ce1ef  Several minor modifications.

comment:18 Changed 23 months ago by
Currently Bliss have no verbose mode, and the docstring of search_tree
says "verbosity – currently ignored". Hence I just removed the parameter.
I changed docstring and allowed return_graph=False
only when bliss=True
is explicitly said.
Docstring modified.
Now this needs comments.
comment:19 Changed 23 months ago by
 Summary changed from Graphs: canonical_label() and return_graph parameter to Graphs: canonical_label() and several errors
comment:20 Changed 23 months ago by
In bliss.pyx
:
canonical graph of G. Otherwise, it returns its set of edges.
>canonical graph of `G`. Otherwise, it returns its set of edges.
In generic_graph.py
:
 unfortunately you can not remove parameter
verbosity
like that, although it iscurrently ignored
. A deprecation warning is needed.  In the documentation, you must use
``True``, ``False``
I don't see any place where the certificate
parameter is used, but it might be useful to some users, no ?
put the ticket to needs review when ready.
comment:21 Changed 23 months ago by
 Commit changed from 39ce1ef11371c37708ca72c72b26174136b1c2d7 to ea621c672a9b38d0fc80f3b11d4931f5014f5fb6
Branch pushed to git repo; I updated commit sha1. New commits:
ea621c6  Modifications.

comment:22 Changed 23 months ago by
Found a bug in my code. Deprecation and your suggestions done.
I also tried to make better examples. Still lacking an example of partition, also I will check that the parameter is really used.
comment:23 Changed 23 months ago by
 Commit changed from ea621c672a9b38d0fc80f3b11d4931f5014f5fb6 to 739a9dfc0e6d76bac1a440fddbbffe26ad91ff6b
Branch pushed to git repo; I updated commit sha1. New commits:
739a9df  Toc entry.

comment:24 Changed 23 months ago by
 Status changed from new to needs_review
Maybe these changes should be integrated to Sage now, and get back to this later? One parameter is still missing examples and documentation, but that can be done later.
comment:25 followup: ↓ 27 Changed 23 months ago by
 Status changed from needs_review to needs_work
In bliss.pyx
, you changed some ``G``
and G
to `G`
, but this last form is not well taken into account when building the doc. You must also use r"""
. You should also do the same in generic_graph.py
.
In the toc, you added Return the canonically labeled graph.
but this is different from the sentence in the method. I suggest to use only Return the canonical graph
.
You don't want to use canonization but canonicalization, right ? ;)
Some comments on the parameters
  ``certificate``  if ``True``, a dictionary mapping from the  (di)graph to its canonical label will be given. +  ``certificate``  boolean (default: ``False``). When set to ``True``, + a dictionary mapping from the vertices of the (di)graph to its canonical + label will also be returned.
  ``edge_labels``  default ``False``, otherwise allows  only permutations respecting edge labels. +  ``edge_labels``  boolean (default: ``False``). When set to ``True``, + allows only permutations respecting edge labels.
  ``algorithm``, a string  the algorithm to use; currently available: +  ``algorithm``  a string (default: ``None``). The algorithm to use; + currently available:
  ``return_graph``  if set, instead of graph return the list of  edges of the the canonical graph; only available when Bliss is  explicitly set as algorithm +  ``return_graph``  boolean (default: ``True``). When set to ``False``, + returns the list of edges of the the canonical graph instead of the + canonical graph; only available when ``'bliss'`` is explicitly set as + algorithm.
use bliss
and not Bliss
to avoid confusion.
return_graph='false'
> return_graph=False
graph with multiedges
> graph with multiple edges
to be consistent with the names of methods (ok, not with the constructor parameter).
Failing example in generic_graph.py
:
Failed example: g Expected: Graph on 6 vertices Got: Grid Graph for [2, 3]: Graph on 6 vertices
For parameter partition
, I tried the following:
sage: G = graphs.PetersenGraph() sage: C = G.coloring() sage: C [[1, 3, 5, 9], [0, 2, 6], [4, 7, 8]] sage: C[::1] [[4, 7, 8], [0, 2, 6], [1, 3, 5, 9]] sage: A = G.canonical_label(partition=C, algorithm='bliss') sage: B = G.canonical_label(partition=C[::1], algorithm='bliss') sage: A == B False sage: B = G.canonical_label(partition=[C[0], C[2], C[1]], algorithm='bliss') sage: A == B False sage: A = G.canonical_label(partition=C, algorithm='bliss') sage: B = G.canonical_label(partition=[C[0], C[1], C[2][::1]], algorithm='bliss') sage: A == B True
By the way, it's boring to type algorithm='bliss'
when bliss is your default algorithm...
comment:26 Changed 23 months ago by
 Commit changed from 739a9dfc0e6d76bac1a440fddbbffe26ad91ff6b to 4dabccd35885ec9b70a6dcaeb06ab1779c323d81
Branch pushed to git repo; I updated commit sha1. New commits:
4dabccd  Some reviewer comments.

comment:27 in reply to: ↑ 25 ; followup: ↓ 28 Changed 23 months ago by
Replying to dcoudert:
Thanks for comments. I did most of them, but some comments:
In
bliss.pyx
, you changed some``G``
andG
to`G`
, but this last form is not well taken into account when building the doc.
This is sometimes hard to decide. I guess we should use `x`
only when referring to mathematical definition without any connection to the specific function parameters we are documenting.
In the toc, you added
Return the canonically labeled graph.
but this is different from the sentence in the method. I suggest to use onlyReturn the canonical graph
.
I changed that.
In general I try to write a oneline description of the function to TOC when possible. For example is_uniform
is explained as "Return True if all congruences of the lattice consists of equalsized blocks." in TOC, but the function starts with "Return True if the lattice is uniform  " and then explains what is uniform.
You don't want to use canonization but canonicalization, right ? ;)
But then there is Graph canonization, so what to do?
For parameter
partition
, I tried the following:
For that we must first define what means to be "canonical" but still "restrict permutations". That's why I suggest postponing that to another ticket.
By the way, it's boring to type
algorithm='bliss'
when bliss is your default algorithm...
True, but there is no other choise for most examples.
E: I am not sure if the function should keep the graph's name or not. However, now it is consistent with relabel()
.
comment:28 in reply to: ↑ 27 ; followup: ↓ 30 Changed 23 months ago by
In general I try to write a oneline description of the function to TOC when possible. For example
is_uniform
is explained as "Return True if all congruences of the lattice consists of equalsized blocks." in TOC, but the function starts with "Return True if the lattice is uniform  " and then explains what is uniform.
Agreed. A significant effort remains to be done for cleaning the graph module.
You don't want to use canonization but canonicalization, right ? ;)
But then there is Graph canonization, so what to do?
You are right. I did not see that. So let's use graph canonization.
Could you add a link to the wikipedia page ?
For parameter
partition
, I tried the following:For that we must first define what means to be "canonical" but still "restrict permutations". That's why I suggest postponing that to another ticket.
Agreed. It's already much better
E: I am not sure if the function should keep the graph's name or not. However, now it is consistent with
relabel()
.
I have no opinion on that.
comment:29 Changed 23 months ago by
 Commit changed from 4dabccd35885ec9b70a6dcaeb06ab1779c323d81 to d8dc2670e73fa83f7b40f82e73b2b5028449cfac
Branch pushed to git repo; I updated commit sha1. New commits:
d8dc267  Add wikipedia link.

comment:30 in reply to: ↑ 28 Changed 23 months ago by
 Status changed from needs_work to needs_review
comment:31 Changed 23 months ago by
 Status changed from needs_review to positive_review
Good. The doc displays nicely now (I like the \cong stuff).
comment:32 Changed 23 months ago by
 Branch changed from u/jmantysalo/graphcanlabelpos to d8dc2670e73fa83f7b40f82e73b2b5028449cfac
 Resolution set to fixed
 Status changed from positive_review to closed
Hello !
All your remarks seem correct (and easy to fix) but I have no idea what the problem with the bliss package comes from
O_o
Nathann