Opened 4 years ago

Closed 2 years ago

# Graphs: canonical_label() and several errors

Reported by: Owned by: jmantysalo major sage-8.1 graph theory dcoudert Jori Mäntysalo David Coudert N/A d8dc267 (Commits) d8dc2670e73fa83f7b40f82e73b2b5028449cfac

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

### comment:1 Changed 4 years ago by ncohen

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

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

There is something strange with `bliss` installation, see https://groups.google.com/forum/#!topic/sage-devel/_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 ncohen

There is something strange with `bliss` installation, see https://groups.google.com/forum/#!topic/sage-devel/_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 of `inplace`. 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 jmantysalo

• 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 2 years ago by jmantysalo

• Branch set to u/jmantysalo/graph-can-label-pos

### comment:6 Changed 2 years ago by jmantysalo

• 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 2 years ago by dcoudert

• Milestone changed from sage-6.10 to sage-8.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 2 years ago by git

• Commit changed from 753b8e03e2ea177bd51ae49711ed762172f32730 to 81f337a4f9a5ff89d4d9ab561441b795bbf40a31

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

 ​81f337a `Forbidden parameter combination.`

### comment:9 Changed 2 years ago by jmantysalo

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 2 years ago by git

• Commit changed from 81f337a4f9a5ff89d4d9ab561441b795bbf40a31 to ac925246354752b6f27e6643efd2a7c6fccd0cd5

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

 ​ac92524 `Docstring formatting.`

### comment:11 Changed 2 years ago by jmantysalo

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 2 years ago by jmantysalo

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 follow-up: ↓ 14 Changed 2 years ago by jdemeyer

Just came here after the sage-devel post by Jori. Is there anything controversial here? Or were you just fishing for reviewers :-)

### comment:14 in reply to: ↑ 13 Changed 2 years ago by jmantysalo

Just came here after the sage-devel post by Jori. Is there anything controversial here?

I guess not, but not sure, so I write a short message to sage-devel.

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 2 years ago by git

• Commit changed from ac925246354752b6f27e6643efd2a7c6fccd0cd5 to b233fdf562e91531b70da45e98da9b7e228f6046

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

 ​b233fdf `Some corrections.`

### comment:16 Changed 2 years ago by jmantysalo

Some modifications to docstring. Now also vertex positions are preserved even when Bliss is used.

Must add many tests to this.

### comment:17 Changed 2 years ago by git

• Commit changed from b233fdf562e91531b70da45e98da9b7e228f6046 to 39ce1ef11371c37708ca72c72b26174136b1c2d7

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

 ​39ce1ef `Several minor modifications.`

### comment:18 Changed 2 years ago by jmantysalo

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.

### comment:19 Changed 2 years ago by jmantysalo

• Summary changed from Graphs: canonical_label() and return_graph -parameter to Graphs: canonical_label() and several errors

### comment:20 Changed 2 years ago by dcoudert

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 is `currently 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 2 years ago by git

• Commit changed from 39ce1ef11371c37708ca72c72b26174136b1c2d7 to ea621c672a9b38d0fc80f3b11d4931f5014f5fb6

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

 ​ea621c6 `Modifications.`

### comment:22 Changed 2 years ago by jmantysalo

• Authors set to Jori Mäntysalo

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 2 years ago by git

• Commit changed from ea621c672a9b38d0fc80f3b11d4931f5014f5fb6 to 739a9dfc0e6d76bac1a440fddbbffe26ad91ff6b

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

 ​739a9df `Toc entry.`

### comment:24 Changed 2 years ago by jmantysalo

• 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 follow-up: ↓ 27 Changed 2 years ago by dcoudert

• 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 ? ;)

```-        - ``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 2 years ago by git

• 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 ; follow-up: ↓ 28 Changed 2 years ago by jmantysalo

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.

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 only `Return the canonical graph`.

I changed that.

In general I try to write a one-line 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 equal-sized 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()`.

Last edited 2 years ago by jmantysalo (previous) (diff)

### comment:28 in reply to: ↑ 27 ; follow-up: ↓ 30 Changed 2 years ago by dcoudert

In general I try to write a one-line 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 equal-sized 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.

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.

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 2 years ago by git

• 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 2 years ago by jmantysalo

• Status changed from needs_work to needs_review

Good idea. Done.

### comment:31 Changed 2 years ago by dcoudert

• Status changed from needs_review to positive_review

Good. The doc displays nicely now (I like the \cong stuff).

### comment:32 Changed 2 years ago by vbraun

• Branch changed from u/jmantysalo/graph-can-label-pos to d8dc2670e73fa83f7b40f82e73b2b5028449cfac
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.