Graph-theoretic partition backtrack functions

EXAMPLES:

sage: 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)

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

sage.groups.perm_gps.partn_ref.refinement_graphs.coarsest_equitable_refinement(G, partition, directed)

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]]

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)

EXAMPLES:

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

sage: for n in [0..6]:
....:     print(generate_dense_graphs_edge_addition(n,1))
1
2
6
20
90
544
5096

sage: for n in [0..7]:
....:     print(generate_dense_graphs_edge_addition(n,0))
1
1
2
4
11
34
156
1044
sage: generate_dense_graphs_edge_addition(8,0)  # long time (about 14 seconds at 2.4 GHz)
12346

sage.groups.perm_gps.partn_ref.refinement_graphs.generate_dense_graphs_vert_addition(n, base_G=None, construct=False, indicate_mem_err=True)

EXAMPLES:

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

sage: for n in [0..7]:
....:   generate_dense_graphs_vert_addition(n)
1
2
4
8
19
53
209
1253
sage: generate_dense_graphs_vert_addition(8)  # long time
13599

sage.groups.perm_gps.partn_ref.refinement_graphs.get_orbits(gens, n)

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]]

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

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: G.add_edge(0,1)
sage: isomorphic(G, H, [[0,1,2]], [0,1,2], 0, 1)
False
sage: H.add_edge(1,2)
sage: isomorphic(G, H, [[0,1,2]], [0,1,2], 0, 1)
{0: 1, 1: 2, 2: 0}

sage.groups.perm_gps.partn_ref.refinement_graphs.orbit_partition(gamma, list_perm=False)

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]]

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

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)

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

Graphs on zero vertices:

sage: G = Graph()
sage: 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)

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: G.add_edge(0,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)

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: G.add_edge(0,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)

The Dodecahedron has automorphism group of size 120:

sage: G = graphs.DodecahedralGraph()
sage: Pi = [range(20)]
sage: st(G, Pi, order=True)[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

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():
....:  GD.add_arc(i,j); GD.add_arc(j,i)
....:  GS.add_arc(i,j); GS.add_arc(j,i)
sage: Pi = [range(20)]
sage: a,b = st(G, Pi)
sage: asp,bsp = st(GS, Pi)
sage: ade,bde = st(GD, Pi)
sage: bsg = Graph()
sage: bdg = Graph()
sage: for i in range(20):
....:    for j in range(20):
....:        if bsp.has_arc(i,j):
....:            bsg.add_edge(i,j)
....:        if bde.has_arc(i,j):
....:            bdg.add_edge(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
sage: a == ade
True
sage: b == bsg
True
sage: 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

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

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

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]]