Relabeling a graph with permutation

[f29946bc-ee7b-48cd-9abc-3445948c551d]

This sounds natural:

g.relabel(Permutations(g.order()).random_element())

but it stops with TypeError: i (= 0) must be between 1 and 4. That is because actually a "permutation" used as an argument is an element of permutation group. This should be either documented better or maybe changed.

Also g.relabel() works, but it should be explicitly said that it is not any kind of canonical relabeling.

CC: @fchapoton

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: ad3e34b

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/21585

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/relabeling_a_graph_with_permutation

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Author: Jori Mäntysalo

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: c5186c7

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

I also removed a note, as it makes no sense anyways to have non-injective relabeling.

---

New commits:

c5186c7

Relabeling using a permutation.

[dcoudert]

comment:3

This is working well if vertices are integers in range 0..n-1. However, for other labelings, it has either no effect

sage: g = digraphs.DeBruijn(2,3)
sage: print g.edges(labels=0)
[('000', '000'), ('000', '001'), ('001', '010'), ('001', '011'), ('010', '100'), ('010', '101'), ('011', '110'), ('011', '111'), ('100', '000'), ('100', '001'), ('101', '010'), ('101', '011'), ('110', '100'), ('110', '101'), ('111', '110'), ('111', '111')]
sage: g.relabel(Permutations(g.order()).random_element())
sage: print g.edges(labels=0)
[('000', '000'), ('000', '001'), ('001', '010'), ('001', '011'), ('010', '100'), ('010', '101'), ('011', '110'), ('011', '111'), ('100', '000'), ('100', '001'), ('101', '010'), ('101', '011'), ('110', '100'), ('110', '101'), ('111', '110'), ('111', '111')]
sage: g.relabel(inplace=True)
sage: print g.edges(labels=0)
[(0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 0), (4, 1), (5, 2), (5, 3), (6, 4), (6, 5), (7, 6), (7, 7)]
sage: g.relabel(Permutations(g.order()).random_element())
sage: print g.edges(labels=0)
[(0, 4), (0, 6), (1, 1), (1, 5), (2, 0), (2, 7), (3, 1), (3, 5), (4, 4), (4, 6), (5, 0), (5, 7), (6, 2), (6, 3), (7, 2), (7, 3)]

or affects only a subset of nodes

sage: g = digraphs.DeBruijn(2,3)
sage: print g.edges(labels=0)
[('000', '000'), ('000', '001'), ('001', '010'), ('001', '011'), ('010', '100'), ('010', '101'), ('011', '110'), ('011', '111'), ('100', '000'), ('100', '001'), ('101', '010'), ('101', '011'), ('110', '100'), ('110', '101'), ('111', '110'), ('111', '111')]
sage: g.relabel(Permutations(g.order()).random_element())
sage: print g.edges(labels=0)
[('000', '000'), ('000', '001'), ('001', '010'), ('001', '011'), ('010', '100'), ('010', '101'), ('011', '110'), ('011', '111'), ('100', '000'), ('100', '001'), ('101', '010'), ('101', '011'), ('110', '100'), ('110', '101'), ('111', '110'), ('111', '111')]
sage: g.relabel(inplace=True)
sage: print g.edges(labels=0)
[(0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 0), (4, 1), (5, 2), (5, 3), (6, 4), (6, 5), (7, 6), (7, 7)]
sage: g.relabel(Permutations(g.order()).random_element())
sage: print g.edges(labels=0)
[(0, 4), (0, 6), (1, 1), (1, 5), (2, 0), (2, 7), (3, 1), (3, 5), (4, 4), (4, 6), (5, 0), (5, 7), (6, 2), (6, 3), (7, 2), (7, 3)]

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:4

I modelled the behaviour from what we already have for an element of a permutation group. It is also mentioned in the docstring.

But how should this behave?

[dcoudert]

comment:5

You are right, the behavior is correct but not my usage and my example where not really appropriate.

I tried this and it works well, although looking at the code I don't understand why :P

sage: g = digraphs.DeBruijn(2,3)
sage: g.relabel(Permutations(g.vertices()).random_element())
sage: print g.edges(labels=0)
[('000', '000'), ('000', '011'), ('001', '110'), ('001', '111'), ('010', '010'), ('010', '100'), ('011', '001'), ('011', '101'), ('100', '110'), ('100', '111'), ('101', '010'), ('101', '100'), ('110', '000'), ('110', '011'), ('111', '001'), ('111', '101')]
sage: g.relabel(Permutations(g.vertices()).random_element())
sage: print g.edges(labels=0)
[('000', '100'), ('000', '101'), ('001', '001'), ('001', '010'), ('010', '000'), ('010', '110'), ('011', '011'), ('011', '111'), ('100', '001'), ('100', '010'), ('101', '000'), ('101', '110'), ('110', '011'), ('110', '111'), ('111', '100'), ('111', '101')]

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:6

Replying to @dcoudert:

I tried this and it works well, although looking at the code I don't understand why :P

It is basically just

ddict = {}
for i in range(1,n):
    ddict[i] = perm(i)%n

So, I mark this as needs_review.

[dcoudert]

comment:7

No, it's not. I added some print commands to understand where it goes:

• For any graph, when using g.relabel(Permutations(g.vertices()).random_element()), the input permutation perm is seen as a list or tuple
• For any graph, when using g.relabel(Permutations(g.order()).random_element()), the input permutation perm is seen as PermutationGroupElement or Permutation

Indeed, we have:

sage: isinstance(Permutations(g.vertices()).random_element(), list)
True

Actually, I don't know what we should expect from method random_element since it is not properly documented.

sage: p = Permutations(g.order())
sage: p.random_element??
Signature: p.random_element()
Source:   
    def random_element(self):
        """
        EXAMPLES::

            sage: Permutations(4).random_element()
            [1, 2, 4, 3]
        """
        return self.element_class(self, sample(range(1,self.n+1), self.n))
File:      ~/sage/local/lib/python2.7/site-packages/sage/combinat/permutation.py
Type:      instancemethod
sage: isinstance(p.random_element(), list)
False

So the behavior you propose should not be allowed, but you can document g.relabel(Permutations(g.vertices()).random_element()) which is a nice way to get a random relabeling of the graph.

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:8

Do you plan to find a solution for the problem mentioned above or should we move this ticket to wontfix ?

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:9

Replying to @dcoudert:

Do you plan to find a solution for the problem mentioned above or should we move this ticket to wontfix ?

I guess this can be closed. However, I think we should add a mention about .relabel().

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c5186c7 to f2ffd1d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f2ffd1d

A note about relabel().

[dcoudert]

comment:12

We could also add this example g.relabel(Permutations(g.vertices()).random_element()), no?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ad3e34b

About random relabeling.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f2ffd1d to ad3e34b

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:14

Replying to @dcoudert:

We could also add this example g.relabel(Permutations(g.vertices()).random_element()), no?

Why not. Something like this?

[dcoudert]

comment:15

Perfect, and the doc displays nicely.

[vbraun]

Changed branch from u/jmantysalo/relabeling_a_graph_with_permutation to ad3e34b