Opened 3 years ago

Closed 13 months ago

#19517 closed defect (fixed)

Graphs: canonical_label() and several errors

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-8.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 jmantysalo)

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 3 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: Changed 3 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 3 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 3 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 14 months ago by jmantysalo

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

comment:6 Changed 14 months 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:

753b8e0Modify parameter checking.

comment:7 Changed 14 months 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 14 months ago by git

  • Commit changed from 753b8e03e2ea177bd51ae49711ed762172f32730 to 81f337a4f9a5ff89d4d9ab561441b795bbf40a31

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

81f337aForbidden parameter combination.

comment:9 Changed 14 months 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 INPUTsection.)

comment:10 Changed 14 months ago by git

  • Commit changed from 81f337a4f9a5ff89d4d9ab561441b795bbf40a31 to ac925246354752b6f27e6643efd2a7c6fccd0cd5

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

ac92524Docstring formatting.

comment:11 Changed 14 months 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 14 months 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: Changed 14 months 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 14 months ago by jmantysalo

Replying to jdemeyer:

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 14 months ago by git

  • Commit changed from ac925246354752b6f27e6643efd2a7c6fccd0cd5 to b233fdf562e91531b70da45e98da9b7e228f6046

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

b233fdfSome corrections.

comment:16 Changed 14 months 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 13 months ago by git

  • Commit changed from b233fdf562e91531b70da45e98da9b7e228f6046 to 39ce1ef11371c37708ca72c72b26174136b1c2d7

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

39ce1efSeveral minor modifications.

comment:18 Changed 13 months 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.

Now this needs comments.

comment:19 Changed 13 months ago by jmantysalo

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

comment:20 Changed 13 months 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 13 months ago by git

  • Commit changed from 39ce1ef11371c37708ca72c72b26174136b1c2d7 to ea621c672a9b38d0fc80f3b11d4931f5014f5fb6

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

ea621c6Modifications.

comment:22 Changed 13 months 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 13 months ago by git

  • Commit changed from ea621c672a9b38d0fc80f3b11d4931f5014f5fb6 to 739a9dfc0e6d76bac1a440fddbbffe26ad91ff6b

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

739a9dfToc entry.

comment:24 Changed 13 months 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: Changed 13 months 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 ? ;)

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 13 months ago by git

  • Commit changed from 739a9dfc0e6d76bac1a440fddbbffe26ad91ff6b to 4dabccd35885ec9b70a6dcaeb06ab1779c323d81

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

4dabccdSome reviewer comments.

comment:27 in reply to: ↑ 25 ; follow-up: Changed 13 months ago by jmantysalo

Replying to dcoudert:

Thanks for comments. I did most of them, but some comments:

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 13 months ago by jmantysalo (previous) (diff)

comment:28 in reply to: ↑ 27 ; follow-up: Changed 13 months 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.

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 13 months ago by git

  • Commit changed from 4dabccd35885ec9b70a6dcaeb06ab1779c323d81 to d8dc2670e73fa83f7b40f82e73b2b5028449cfac

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

d8dc267Add wikipedia link.

comment:30 in reply to: ↑ 28 Changed 13 months ago by jmantysalo

  • Status changed from needs_work to needs_review

Replying to dcoudert:

Could you add a link to the wikipedia page ?

Good idea. Done.

comment:31 Changed 13 months 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 13 months 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.