# Graph-theoretic partition backtrack functions#

EXAMPLES:

sage: import sage.groups.perm_gps.partn_ref.refinement_graphs

>>> from sage.all import *
>>> import sage.groups.perm_gps.partn_ref.refinement_graphs


REFERENCE:

• [1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium, Vol. 30 (1981), pp. 45-87.

class sage.groups.perm_gps.partn_ref.refinement_graphs.GraphStruct#

Bases: object

sage.groups.perm_gps.partn_ref.refinement_graphs.all_labeled_graphs(n)[source]#

Return all labeled graphs on n vertices {0,1,…,n-1}.

Used in classifying isomorphism types (naive approach), and more importantly in benchmarking the search algorithm.

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import all_labeled_graphs
sage: st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree
sage: Glist = {}
sage: Giso  = {}
sage: for n in [1..5]:  # long time (4s on sage.math, 2011)
....:  Glist[n] = all_labeled_graphs(n)
....:  Giso[n] = []
....:  for g in Glist[n]:
....:      a, b = st(g, [range(n)])
....:      inn = False
....:      for gi in Giso[n]:
....:          if b == gi:
....:              inn = True
....:      if not inn:
....:          Giso[n].append(b)
sage: for n in Giso:  # long time
....:    print("{} {}".format(n, len(Giso[n])))
1 1
2 2
3 4
4 11
5 34

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_graphs import all_labeled_graphs
>>> st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree
>>> Glist = {}
>>> Giso  = {}
>>> for n in (ellipsis_range(Integer(1),Ellipsis,Integer(5))):  # long time (4s on sage.math, 2011)
...  Glist[n] = all_labeled_graphs(n)
...  Giso[n] = []
...  for g in Glist[n]:
...      a, b = st(g, [range(n)])
...      inn = False
...      for gi in Giso[n]:
...          if b == gi:
...              inn = True
...      if not inn:
...          Giso[n].append(b)
>>> for n in Giso:  # long time
...    print("{} {}".format(n, len(Giso[n])))
1 1
2 2
3 4
4 11
5 34

sage.groups.perm_gps.partn_ref.refinement_graphs.coarsest_equitable_refinement(G, partition, directed)[source]#

Return the coarsest equitable refinement of partition for G.

This is a helper function for the graph function of the same name.

DOCTEST (More thorough testing in sage/graphs/graph.py):

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import coarsest_equitable_refinement
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: coarsest_equitable_refinement(SparseGraph(7), [[0], [1,2,3,4], [5,6]], 0)
[[0], [1, 2, 3, 4], [5, 6]]

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_graphs import coarsest_equitable_refinement
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> coarsest_equitable_refinement(SparseGraph(Integer(7)), [[Integer(0)], [Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(5),Integer(6)]], Integer(0))
[[0], [1, 2, 3, 4], [5, 6]]

sage.groups.perm_gps.partn_ref.refinement_graphs.generate_dense_graphs_edge_addition(n, loops, G=None, depth=None, construct=False, indicate_mem_err=True)[source]#

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import generate_dense_graphs_edge_addition

>>> from sage.all import *

sage: for n in [0..6]:
1
2
6
20
90
544
5096

>>> from sage.all import *
>>> for n in (ellipsis_range(Integer(0),Ellipsis,Integer(6))):
1
2
6
20
90
544
5096

sage: for n in [0..7]:
1
1
2
4
11
34
156
1044
12346

>>> from sage.all import *
>>> for n in (ellipsis_range(Integer(0),Ellipsis,Integer(7))):
1
1
2
4
11
34
156
1044
12346


EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import generate_dense_graphs_vert_addition

>>> from sage.all import *

sage: for n in [0..7]:
1
2
4
8
19
53
209
1253
13599

>>> from sage.all import *
>>> for n in (ellipsis_range(Integer(0),Ellipsis,Integer(7))):
1
2
4
8
19
53
209
1253
13599

sage.groups.perm_gps.partn_ref.refinement_graphs.get_orbits(gens, n)[source]#

Compute orbits given a list of generators of a permutation group, in list format.

This is a helper function for automorphism groups of graphs.

DOCTEST (More thorough testing in sage/graphs/graph.py):

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import get_orbits
sage: get_orbits([[1,2,3,0,4,5], [0,1,2,3,5,4]], 6)
[[0, 1, 2, 3], [4, 5]]

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_graphs import get_orbits
>>> get_orbits([[Integer(1),Integer(2),Integer(3),Integer(0),Integer(4),Integer(5)], [Integer(0),Integer(1),Integer(2),Integer(3),Integer(5),Integer(4)]], Integer(6))
[[0, 1, 2, 3], [4, 5]]

sage.groups.perm_gps.partn_ref.refinement_graphs.isomorphic(G1, G2, partn, ordering2, dig, use_indicator_function, sparse=False)[source]#

Test whether two graphs are isomorphic.

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import isomorphic

sage: G = Graph(2)
sage: H = Graph(2)
sage: isomorphic(G, H, [[0,1]], [0,1], 0, 1)
{0: 0, 1: 1}
sage: isomorphic(G, H, [[0,1]], [0,1], 0, 1)
{0: 0, 1: 1}
sage: isomorphic(G, H, [[0],[1]], [0,1], 0, 1)
{0: 0, 1: 1}
sage: isomorphic(G, H, [[0],[1]], [1,0], 0, 1)
{0: 1, 1: 0}

sage: G = Graph(3)
sage: H = Graph(3)
sage: isomorphic(G, H, [[0,1,2]], [0,1,2], 0, 1)
{0: 0, 1: 1, 2: 2}
sage: isomorphic(G, H, [[0,1,2]], [0,1,2], 0, 1)
False
sage: isomorphic(G, H, [[0,1,2]], [0,1,2], 0, 1)
{0: 1, 1: 2, 2: 0}

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_graphs import isomorphic

>>> G = Graph(Integer(2))
>>> H = Graph(Integer(2))
>>> isomorphic(G, H, [[Integer(0),Integer(1)]], [Integer(0),Integer(1)], Integer(0), Integer(1))
{0: 0, 1: 1}
>>> isomorphic(G, H, [[Integer(0),Integer(1)]], [Integer(0),Integer(1)], Integer(0), Integer(1))
{0: 0, 1: 1}
>>> isomorphic(G, H, [[Integer(0)],[Integer(1)]], [Integer(0),Integer(1)], Integer(0), Integer(1))
{0: 0, 1: 1}
>>> isomorphic(G, H, [[Integer(0)],[Integer(1)]], [Integer(1),Integer(0)], Integer(0), Integer(1))
{0: 1, 1: 0}

>>> G = Graph(Integer(3))
>>> H = Graph(Integer(3))
>>> isomorphic(G, H, [[Integer(0),Integer(1),Integer(2)]], [Integer(0),Integer(1),Integer(2)], Integer(0), Integer(1))
{0: 0, 1: 1, 2: 2}
>>> isomorphic(G, H, [[Integer(0),Integer(1),Integer(2)]], [Integer(0),Integer(1),Integer(2)], Integer(0), Integer(1))
False
>>> isomorphic(G, H, [[Integer(0),Integer(1),Integer(2)]], [Integer(0),Integer(1),Integer(2)], Integer(0), Integer(1))
{0: 1, 1: 2, 2: 0}

sage.groups.perm_gps.partn_ref.refinement_graphs.orbit_partition(gamma, list_perm=False)[source]#

Assuming that G is a graph on vertices 0,1,…,n-1, and gamma is an element of SymmetricGroup(n), returns the partition of the vertex set determined by the orbits of gamma, considered as action on the set 1,2,…,n where we take 0 = n. In other words, returns the partition determined by a cyclic representation of gamma.

INPUT:

• list_perm – if True, assumes gamma is a list representing the map $$i \mapsto gamma[i]$$

EXAMPLES:

sage: # needs sage.groups
sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import orbit_partition
sage: G = graphs.PetersenGraph()
sage: S = SymmetricGroup(10)
sage: gamma = S('(10,1,2,3,4)(5,6,7)(8,9)')
sage: orbit_partition(gamma)
[[1, 2, 3, 4, 0], [5, 6, 7], [8, 9]]
sage: gamma = S('(10,5)(1,6)(2,7)(3,8)(4,9)')
sage: orbit_partition(gamma)
[[1, 6], [2, 7], [3, 8], [4, 9], [5, 0]]

>>> from sage.all import *
>>> # needs sage.groups
>>> from sage.groups.perm_gps.partn_ref.refinement_graphs import orbit_partition
>>> G = graphs.PetersenGraph()
>>> S = SymmetricGroup(Integer(10))
>>> gamma = S('(10,1,2,3,4)(5,6,7)(8,9)')
>>> orbit_partition(gamma)
[[1, 2, 3, 4, 0], [5, 6, 7], [8, 9]]
>>> gamma = S('(10,5)(1,6)(2,7)(3,8)(4,9)')
>>> orbit_partition(gamma)
[[1, 6], [2, 7], [3, 8], [4, 9], [5, 0]]

sage.groups.perm_gps.partn_ref.refinement_graphs.random_tests(num=10, n_max=60, perms_per_graph=5)[source]#

Tests to make sure that C(gamma(G)) == C(G) for random permutations gamma and random graphs G, and that isomorphic returns an isomorphism.

INPUT:

• num – run tests for this many graphs

• n_max – test graphs with at most this many vertices

• perms_per_graph – test each graph with this many random permutations

DISCUSSION:

This code generates num random graphs G on at most n_max vertices. The density of edges is chosen randomly between 0 and 1.

For each graph G generated, we uniformly generate perms_per_graph random permutations and verify that the canonical labels of G and the image of G under the generated permutation are equal, and that the isomorphic function returns an isomorphism.

sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree(G_in, partition, lab=True, dig=False, dict_rep=False, certificate=False, verbosity=0, use_indicator_function=True, sparse=True, base=False, order=False)[source]#

Compute canonical labels and automorphism groups of graphs.

INPUT:

• G_in – a Sage graph

• partition – a list of lists representing a partition of the vertices

• lab – if True, compute and return the canonical label in addition to the automorphism group

• dig – set to True for digraphs and graphs with loops. If True, does not use optimizations based on Lemma 2.25 in [1] that are valid only for simple graphs.

• dict_rep – if True, return a dictionary with keys the vertices of the input graph G_in and values elements of the set the permutation group acts on. (The point is that graphs are arbitrarily labelled, often 0..n-1, and permutation groups always act on 1..n. This dictionary maps vertex labels (such as 0..n-1) to the domain of the permutations.)

• certificate – if True, return the permutation from G to its canonical label.

• verbosity – currently ignored

• use_indicator_function – option to turn off indicator function (True is generally faster)

• sparse – whether to use sparse or dense representation of the graph (ignored if G is already a CGraph - see sage.graphs.base)

• base – whether to return the first sequence of split vertices (used in computing the order of the group)

• order – whether to return the order of the automorphism group

OUTPUT:

Depends on the options. If more than one thing is returned, they are in a tuple in the following order:

• list of generators in list-permutation format – always

• dict – if dict_rep

• graph – if lab

• dict – if certificate

• list – if base

• integer – if order

EXAMPLES:

sage: st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree
sage: from sage.graphs.base.dense_graph import DenseGraph
sage: from sage.graphs.base.sparse_graph import SparseGraph

>>> from sage.all import *
>>> st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree
>>> from sage.graphs.base.dense_graph import DenseGraph
>>> from sage.graphs.base.sparse_graph import SparseGraph


Graphs on zero vertices:

sage: G = Graph()
sage: st(G, [[]], order=True)
([], Graph on 0 vertices, 1)

>>> from sage.all import *
>>> G = Graph()
>>> st(G, [[]], order=True)
([], Graph on 0 vertices, 1)


Graphs on one vertex:

sage: G = Graph(1)
sage: st(G, [[0]], order=True)
([], Graph on 1 vertex, 1)

>>> from sage.all import *
>>> G = Graph(Integer(1))
>>> st(G, [[Integer(0)]], order=True)
([], Graph on 1 vertex, 1)


Graphs on two vertices:

sage: G = Graph(2)
sage: st(G, [[0,1]], order=True)
([[1, 0]], Graph on 2 vertices, 2)
sage: st(G, [[0],[1]], order=True)
([], Graph on 2 vertices, 1)
sage: st(G, [[0,1]], order=True)
([[1, 0]], Graph on 2 vertices, 2)
sage: st(G, [[0],[1]], order=True)
([], Graph on 2 vertices, 1)

>>> from sage.all import *
>>> G = Graph(Integer(2))
>>> st(G, [[Integer(0),Integer(1)]], order=True)
([[1, 0]], Graph on 2 vertices, 2)
>>> st(G, [[Integer(0)],[Integer(1)]], order=True)
([], Graph on 2 vertices, 1)
>>> st(G, [[Integer(0),Integer(1)]], order=True)
([[1, 0]], Graph on 2 vertices, 2)
>>> st(G, [[Integer(0)],[Integer(1)]], order=True)
([], Graph on 2 vertices, 1)


Graphs on three vertices:

sage: G = Graph(3)
sage: st(G, [[0,1,2]], order=True)
([[0, 2, 1], [1, 0, 2]], Graph on 3 vertices, 6)
sage: st(G, [[0],[1,2]], order=True)
([[0, 2, 1]], Graph on 3 vertices, 2)
sage: st(G, [[0],[1],[2]], order=True)
([], Graph on 3 vertices, 1)
sage: st(G, [range(3)], order=True)
([[1, 0, 2]], Graph on 3 vertices, 2)
sage: st(G, [[0],[1,2]], order=True)
([], Graph on 3 vertices, 1)
sage: st(G, [[0,1],[2]], order=True)
([[1, 0, 2]], Graph on 3 vertices, 2)

>>> from sage.all import *
>>> G = Graph(Integer(3))
>>> st(G, [[Integer(0),Integer(1),Integer(2)]], order=True)
([[0, 2, 1], [1, 0, 2]], Graph on 3 vertices, 6)
>>> st(G, [[Integer(0)],[Integer(1),Integer(2)]], order=True)
([[0, 2, 1]], Graph on 3 vertices, 2)
>>> st(G, [[Integer(0)],[Integer(1)],[Integer(2)]], order=True)
([], Graph on 3 vertices, 1)
>>> st(G, [range(Integer(3))], order=True)
([[1, 0, 2]], Graph on 3 vertices, 2)
>>> st(G, [[Integer(0)],[Integer(1),Integer(2)]], order=True)
([], Graph on 3 vertices, 1)
>>> st(G, [[Integer(0),Integer(1)],[Integer(2)]], order=True)
([[1, 0, 2]], Graph on 3 vertices, 2)


The Dodecahedron has automorphism group of size 120:

sage: G = graphs.DodecahedralGraph()
sage: Pi = [range(20)]
sage: st(G, Pi, order=True)[2]
120

>>> from sage.all import *
>>> G = graphs.DodecahedralGraph()
>>> Pi = [range(Integer(20))]
>>> st(G, Pi, order=True)[Integer(2)]
120


The three-cube has automorphism group of size 48:

sage: G = graphs.CubeGraph(3)
sage: G.relabel()
sage: Pi = [G.vertices(sort=False)]
sage: st(G, Pi, order=True)[2]
48

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(3))
>>> G.relabel()
>>> Pi = [G.vertices(sort=False)]
>>> st(G, Pi, order=True)[Integer(2)]
48


We obtain the same output using different types of Sage graphs:

sage: G = graphs.DodecahedralGraph()
sage: GD = DenseGraph(20)
sage: GS = SparseGraph(20)
sage: for i,j,_ in G.edge_iterator():
sage: Pi = [range(20)]
sage: a,b = st(G, Pi)
sage: asp,bsp = st(GS, Pi)
sage: bsg = Graph()
sage: bdg = Graph()
sage: for i in range(20):
....:    for j in range(20):
....:        if bsp.has_arc(i,j):
....:        if bde.has_arc(i,j):
sage: a, b.graph6_string()
([[0, 19, 3, 2, 6, 5, 4, 17, 18, 11, 10, 9, 13, 12, 16, 15, 14, 7, 8, 1],
[0, 1, 8, 9, 13, 14, 7, 6, 2, 3, 19, 18, 17, 4, 5, 15, 16, 12, 11, 10],
[1, 8, 9, 10, 11, 12, 13, 14, 7, 6, 2, 3, 4, 5, 15, 16, 17, 18, 19, 0]],
'S?[PG__OQ@?_?_?P?CO?_?AE?EC?Ac?@O')
sage: a == asp
True
True
sage: b == bsg
True
sage: b == bdg
True

>>> from sage.all import *
>>> G = graphs.DodecahedralGraph()
>>> GD = DenseGraph(Integer(20))
>>> GS = SparseGraph(Integer(20))
>>> for i,j,_ in G.edge_iterator():
>>> Pi = [range(Integer(20))]
>>> a,b = st(G, Pi)
>>> asp,bsp = st(GS, Pi)
>>> bsg = Graph()
>>> bdg = Graph()
>>> for i in range(Integer(20)):
...    for j in range(Integer(20)):
...        if bsp.has_arc(i,j):
...        if bde.has_arc(i,j):
>>> a, b.graph6_string()
([[0, 19, 3, 2, 6, 5, 4, 17, 18, 11, 10, 9, 13, 12, 16, 15, 14, 7, 8, 1],
[0, 1, 8, 9, 13, 14, 7, 6, 2, 3, 19, 18, 17, 4, 5, 15, 16, 12, 11, 10],
[1, 8, 9, 10, 11, 12, 13, 14, 7, 6, 2, 3, 4, 5, 15, 16, 17, 18, 19, 0]],
'S?[PG__OQ@?_?_?P?CO?_?AE?EC?Ac?@O')
>>> a == asp
True
True
>>> b == bsg
True
>>> b == bdg
True


Cubes!:

sage: C = graphs.CubeGraph(1)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
2
sage: C = graphs.CubeGraph(2)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
8
sage: C = graphs.CubeGraph(3)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
48
sage: C = graphs.CubeGraph(4)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
384
sage: C = graphs.CubeGraph(5)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
3840
sage: C = graphs.CubeGraph(6)
sage: gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
46080

>>> from sage.all import *
>>> C = graphs.CubeGraph(Integer(1))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
2
>>> C = graphs.CubeGraph(Integer(2))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
8
>>> C = graphs.CubeGraph(Integer(3))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
48
>>> C = graphs.CubeGraph(Integer(4))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
384
>>> C = graphs.CubeGraph(Integer(5))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
3840
>>> C = graphs.CubeGraph(Integer(6))
>>> gens, order = st(C, [C.vertices(sort=False)], lab=False, order=True); order
46080


One can also turn off the indicator function (note: this will take longer):

sage: D1 = DiGraph({0:[2],2:[0],1:[1]}, loops=True)
sage: D2 = DiGraph({1:[2],2:[1],0:[0]}, loops=True)
sage: a,b = st(D1, [D1.vertices(sort=False)], dig=True, use_indicator_function=False)
sage: c,d = st(D2, [D2.vertices(sort=False)], dig=True, use_indicator_function=False)
sage: b==d
True

>>> from sage.all import *
>>> D1 = DiGraph({Integer(0):[Integer(2)],Integer(2):[Integer(0)],Integer(1):[Integer(1)]}, loops=True)
>>> D2 = DiGraph({Integer(1):[Integer(2)],Integer(2):[Integer(1)],Integer(0):[Integer(0)]}, loops=True)
>>> a,b = st(D1, [D1.vertices(sort=False)], dig=True, use_indicator_function=False)
>>> c,d = st(D2, [D2.vertices(sort=False)], dig=True, use_indicator_function=False)
>>> b==d
True


This example is due to Chris Godsil:

sage: HS = graphs.HoffmanSingletonGraph()
sage: alqs = [Set(c) for c in (HS.complement()).cliques_maximum()]
sage: Y = Graph([alqs, lambda s,t: len(s.intersection(t))==0])
sage: Y0,Y1 = Y.connected_components_subgraphs()
sage: st(Y0, [Y0.vertices(sort=False)])[1] == st(Y1, [Y1.vertices(sort=False)])[1]
True
sage: st(Y0, [Y0.vertices(sort=False)])[1] == st(HS, [HS.vertices(sort=False)])[1]
True
sage: st(HS, [HS.vertices(sort=False)])[1] == st(Y1, [Y1.vertices(sort=False)])[1]
True

>>> from sage.all import *
>>> HS = graphs.HoffmanSingletonGraph()
>>> alqs = [Set(c) for c in (HS.complement()).cliques_maximum()]
>>> Y = Graph([alqs, lambda s,t: len(s.intersection(t))==Integer(0)])
>>> Y0,Y1 = Y.connected_components_subgraphs()
>>> st(Y0, [Y0.vertices(sort=False)])[Integer(1)] == st(Y1, [Y1.vertices(sort=False)])[Integer(1)]
True
>>> st(Y0, [Y0.vertices(sort=False)])[Integer(1)] == st(HS, [HS.vertices(sort=False)])[Integer(1)]
True
>>> st(HS, [HS.vertices(sort=False)])[Integer(1)] == st(Y1, [Y1.vertices(sort=False)])[Integer(1)]
True


Certain border cases need to be tested as well:

sage: G = Graph('Fll^G')
sage: a,b,c = st(G, [range(G.num_verts())], order=True); b
Graph on 7 vertices
sage: c
48
sage: G = Graph(21)
sage: st(G, [range(G.num_verts())], order=True)[2] == factorial(21)
True

sage: G = Graph('^????????????????????{??N??@w??FaGa?PCO@CP?AGa?_QO?Q@G?CcA??cc????Bo????{????F_')
sage: perm = {3:15, 15:3}
sage: H = G.relabel(perm, inplace=False)
sage: st(G, [range(G.num_verts())])[1] == st(H, [range(H.num_verts())])[1]
True

sage: st(Graph(':Dkw'), [range(5)], lab=False, dig=True)
[[4, 1, 2, 3, 0], [0, 2, 1, 3, 4]]

>>> from sage.all import *
>>> G = Graph('Fll^G')
>>> a,b,c = st(G, [range(G.num_verts())], order=True); b
Graph on 7 vertices
>>> c
48
>>> G = Graph(Integer(21))
>>> st(G, [range(G.num_verts())], order=True)[Integer(2)] == factorial(Integer(21))
True

>>> G = Graph('^????????????????????{??N??@w??FaGa?PCO@CP?AGa?_QO?Q@G?CcA??cc????Bo????{????F_')
>>> perm = {Integer(3):Integer(15), Integer(15):Integer(3)}
>>> H = G.relabel(perm, inplace=False)
>>> st(G, [range(G.num_verts())])[Integer(1)] == st(H, [range(H.num_verts())])[Integer(1)]
True

>>> st(Graph(':Dkw'), [range(Integer(5))], lab=False, dig=True)
[[4, 1, 2, 3, 0], [0, 2, 1, 3, 4]]