8.3 N.I.C.E. - Nice (as in open source) Isomorphism Check Engine

Module: sage.graphs.graph_isom

N.I.C.E. - Nice (as in open source) Isomorphism Check Engine

Automorphism group computation and isomorphism checking for graphs.

This is an open source implementation of Brendan McKay's algorithm for graph automorphism and isomorphism. McKay released a C version of his algorithm, named nauty (No AUTomorphisms, Yes?) under a license that is not GPL compatible. Although the program is open source, reading the source disallows anyone from recreating anything similar and releasing it under the GPL. Also, many people have complained that the code is difficult to understand. The first main goal of NICE was to produce a genuinely open graph isomorphism program, which has been accomplished. The second goal is for this code to be understandable, so that computed results can be trusted and further derived work will be possible.

To determine the isomorphism type of a graph, it is convenient to define a canonical label for each isomorphism class- essentially an equivalence class representative. Loosely (albeit incorrectly), the canonical label is defined by enumerating all labeled graphs, then picking the maximal one in each isomorphism class. The NICE algorithm is essentially a backtrack search. It searches through the rooted tree of partition nests (where each partition is equitable) for implicit and explicit automorphisms, and uses this information to eliminate large parts of the tree from further searching. Since the leaves of the search tree are all discrete ordered partitions, each one of these corresponds to an ordering of the vertices of the graph, i.e. another member of the isomorphism class. Once the algorithm has finished searching the tree, it will know which leaf corresponds to the canonical label. In the process, generators for the automorphism group are also produced.

Author Log:

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

NOTES: 1. Often we assume that G is a graph on vertices 0,1,...,n-1. 2. There is no s == loads(dumps(s)) type test since none of the classes defined here are meant to be instantiated for longer than the algorithm runs (i.e. pickling is not relevant here).

Module-level Functions

all_labeled_digraphs( )

sage: import sage.graphs.graph_isom
sage: from sage.graphs.graph_isom import search_tree, all_labeled_digraphs
sage: Glist = {}
sage: Giso  = {}
sage: for n in range(1,4):
...       Glist[n] = all_labeled_digraphs(n)
...       Giso[n] = []
...       for g in Glist[n]:
...           a, b = search_tree(g, [range(n)], dig=True)
...           inn = False
...           for gi in Giso[n]:
...               if b == gi:
...                   inn = True
...           if not inn:
...               Giso[n].append(b)
sage: for n in Giso:
...       print n, len(Giso[n])
1 1
2 3
3 16

all_labeled_digraphs_with_loops( )

Returns all labeled digraphs on n vertices 0,1,...,n-1. Used in classifying isomorphism types (naive approach), and more importantly in benchmarking the search algorithm.

sage: import sage.graphs.graph_isom
sage: from sage.graphs.graph_isom import search_tree, all_labeled_digraphs_with_loops
sage: Glist = {}
sage: Giso  = {}
sage: for n in range(1,4):                        
...    Glist[n] = all_labeled_digraphs_with_loops(n)
...    Giso[n] = []
...    for g in Glist[n]:
...        a, b = search_tree(g, [range(n)], dig=True)  
...        inn = False                            
...        for gi in Giso[n]:                     
...            if b == gi:
...                inn = True                     
...        if not inn:                            
...            Giso[n].append(b)                  
sage: for n in Giso:                              
...    print n, len(Giso[n])                      
1 2
2 10
3 104

all_labeled_graphs( )

Returns 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.

sage: import sage.graphs.graph_isom
sage: from sage.graphs.graph_isom import search_tree, all_labeled_graphs
sage: Glist = {}
sage: Giso  = {}
sage: for n in range(1,5):
...    Glist[n] = all_labeled_graphs(n)
...    Giso[n] = []
...    for g in Glist[n]:
...        a, b = search_tree(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:
...    print n, len(Giso[n])
1 1
2 2
3 4
4 11
sage: n = 5
sage: Glist[n] = all_labeled_graphs(n)
sage: Giso[n] = []
sage: for g in Glist[5]:
...    a, b = search_tree(g, [range(n)])
...    inn = False
...    for gi in Giso[n]:
...        if b == gi:
...            inn = True
...    if not inn:
...        Giso[n].append(b)
sage: print n, len(Giso[n]) # long time
5 34
sage: graphs_list.show_graphs(Giso[4])

all_ordered_partitions( )

Returns all ordered partitions of the set 0,1,...,n-1. Used in benchmarking the search algorithm.

sage: from sage.graphs.graph_isom import all_ordered_partitions
sage: all_ordered_partitions(['a', 1, {}])
[[['a'], [1], [{}]],
 [['a'], [{}], [1]],
 [['a'], [{}, 1]],
 [['a'], [1, {}]],
 [[1], ['a'], [{}]],
 [[1], [{}], ['a']],
 [[1], [{}, 'a']],
 [[1], ['a', {}]],
 [[{}], ['a'], [1]],
 [[{}], [1], ['a']],
 [[{}], [1, 'a']],
 [[{}], ['a', 1]],
 [[1, 'a'], [{}]],
 [[{}, 'a'], [1]],
 [['a', 1], [{}]],
 [[{}, 1], ['a']],
 [['a', {}], [1]],
 [[1, {}], ['a']],
 [[{}, 1, 'a']],
 [[1, {}, 'a']],
 [[{}, 'a', 1]],
 [['a', {}, 1]],
 [[1, 'a', {}]],
 [['a', 1, {}]]]

kpow( )

Returns the subset of the power set of listy consisting of subsets of size k. Used in all_ordered_partitions.

sage: from sage.graphs.graph_isom import kpow
sage: kpow(['a', 1, {}], 2)
[[1, 'a'], [{}, 'a'], ['a', 1], [{}, 1], ['a', {}], [1, {}]]

orbit_partition( )

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 \var{gamma}[i]$ .

sage: import sage.graphs.graph_isom
sage: from sage.graphs.graph_isom 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]]

perm_group_elt( )

Given a list permutation of the set 0, 1, ..., n-1, returns the corresponding PermutationGroupElement where we take 0 = n.

sage: from sage.graphs.graph_isom import perm_group_elt
sage: perm_group_elt([0,2,1])
(1,2)
sage: perm_group_elt([1,2,0])
(1,2,3)

search_tree( )

Assumes that the vertex set of G is 0,1,...,n-1 for some n.

Note that this conflicts with the SymmetricGroup we are using to represent automorphisms. The solution is to let the group act on the set 1,2,...,n, under the assumption n = 0.

Input: lab- if True, return the canonical label in addition to the auto- morphism group. dig- if True, does not use Lemma 2.25 in [1], and the algorithm is valid for digraphs and graphs with loops. dict_rep- if True, explain which vertices are which elements of the set 1,2,...,n in the representation of the automorphism group. certify- if True, return the relabeling from G to its canonical label. Forces lab=True. verbosity- 0 - print nothing 1 - display state trace 2 - with timings 3 - display partition nests 4 - display orbit partition 5 - plot the part of the tree traversed during search

use_indicator_function
- option to turn off indicator function (False -> slower)
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

STATE DIAGRAM:

sage: SD = DiGraph( { 1:[18,2], 2:[5,3], 3:[4,6], 4:[7,2], 5:[4], 6:[13,12], 7:[18,8,10], 8:[6,9,10], 9:[6], 10:[11,13], 11:[12], 12:[13], 13:[17,14], 14:[16,15], 15:[2], 16:[13], 17:[15,13], 18:[13] }, implementation='networkx' )
sage: SD.set_edge_label(1, 18, 'discrete')
sage: SD.set_edge_label(4, 7, 'discrete')
sage: SD.set_edge_label(2, 5, 'h = 0')
sage: SD.set_edge_label(7, 18, 'h = 0')
sage: SD.set_edge_label(7, 10, 'aut')
sage: SD.set_edge_label(8, 10, 'aut')
sage: SD.set_edge_label(8, 9, 'label')
sage: SD.set_edge_label(8, 6, 'no label')
sage: SD.set_edge_label(13, 17, 'k > h')
sage: SD.set_edge_label(13, 14, 'k = h')
sage: SD.set_edge_label(17, 15, 'v_k finite')
sage: SD.set_edge_label(14, 15, 'v_k m.c.r.')
sage: posn = {1:[ 3,-3],  2:[0,2],  3:[0, 13],  4:[3,9],  5:[3,3],  6:[16, 13], 7:[6,1],  8:[6,6],  9:[6,11], 10:[9,1], 11:[10,6], 12:[13,6], 13:[16,2], 14:[10,-6], 15:[0,-10], 16:[14,-6], 17:[16,-10], 18:[6,-4]}
sage: SD.plot(pos=posn, vertex_size=400, vertex_colors={'#FFFFFF':range(1,19)}, edge_labels=True).save('search_tree.png')

NOTE: There is a function, called test_refine, that has the same signature as _refine. It calls _refine, then checks to make sure the output is sane. To use this, simply add 'test' to the two places this algorithm calls the function (states 1 and 2).

The following example is due to Chris Godsil:

sage: HS = graphs.HoffmanSingletonGraph()
sage: clqs = (HS.complement()).cliques()
sage: alqs = [Set(c) for c in clqs if len(c) == 15]
sage: Y = Graph([alqs, lambda s,t: len(s.intersection(t))==0], implementation='networkx')
sage: Y0,Y1 = Y.connected_components_subgraphs()
sage: Y0.is_isomorphic(Y1)
True
sage: Y0.is_isomorphic(HS)
True

sage: import sage.graphs.graph_isom
sage: from sage.graphs.graph_isom import search_tree
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: from sage.graphs.base.dense_graph import DenseGraph
sage: from sage.groups.perm_gps.permgroup import PermutationGroup
sage: from sage.graphs.graph_isom import perm_group_elt

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 = search_tree(G, Pi)
sage: asp,bsp = search_tree(GS, Pi)
sage: ade,bde = search_tree(GD, Pi)
sage: bsg = Graph(implementation='networkx')
sage: bdg = Graph(implementation='networkx')
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: print 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
sage: c = search_tree(G, Pi, lab=False)
sage: print c
[[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]]
sage: DodecAut = PermutationGroup([perm_group_elt(aa) for aa in a])
sage: DodecAut.character_table()
[                     1                      1                      1      
1                      1                      1                      1     
1                      1                      1]
[                     1                     -1                      1      
1                     -1                      1                     -1     
1                     -1                     -1]
[                     3                     -1                      0      
-1     -zeta5^3 - zeta5^2  zeta5^3 + zeta5^2 + 1                      0    
-zeta5^3 - zeta5^2  zeta5^3 + zeta5^2 + 1                      3]
[                     3                     -1                      0      
-1  zeta5^3 + zeta5^2 + 1     -zeta5^3 - zeta5^2                      0 
zeta5^3 + zeta5^2 + 1     -zeta5^3 - zeta5^2                      3]
[                     3                      1                      0      
-1      zeta5^3 + zeta5^2  zeta5^3 + zeta5^2 + 1                      0    
-zeta5^3 - zeta5^2 -zeta5^3 - zeta5^2 - 1                     -3]
[                     3                      1                      0      
-1 -zeta5^3 - zeta5^2 - 1     -zeta5^3 - zeta5^2                      0 
zeta5^3 + zeta5^2 + 1      zeta5^3 + zeta5^2                     -3]
[                     4                      0                      1      
0                     -1                     -1                      1     
-1                     -1                      4]
[                     4                      0                      1      
0                      1                     -1                     -1     
-1                      1                     -4]
[                     5                      1                     -1      
1                      0                      0                     -1     
0                      0                      5]
[                     5                     -1                     -1      
1                      0                      0                      1     
0                      0                     -5]
sage: DodecAut2 = PermutationGroup([perm_group_elt(cc) for cc in c])
sage: DodecAut2.character_table()
[                     1                      1                      1      
1                      1                      1                      1     
1                      1                      1]
[                     1                     -1                      1      
1                     -1                      1                     -1     
1                     -1                     -1]
[                     3                     -1                      0      
-1     -zeta5^3 - zeta5^2  zeta5^3 + zeta5^2 + 1                      0    
-zeta5^3 - zeta5^2  zeta5^3 + zeta5^2 + 1                      3]
[                     3                     -1                      0      
-1  zeta5^3 + zeta5^2 + 1     -zeta5^3 - zeta5^2                      0 
zeta5^3 + zeta5^2 + 1     -zeta5^3 - zeta5^2                      3]
[                     3                      1                      0      
-1      zeta5^3 + zeta5^2  zeta5^3 + zeta5^2 + 1                      0    
-zeta5^3 - zeta5^2 -zeta5^3 - zeta5^2 - 1                     -3]
[                     3                      1                      0      
-1 -zeta5^3 - zeta5^2 - 1     -zeta5^3 - zeta5^2                      0 
zeta5^3 + zeta5^2 + 1      zeta5^3 + zeta5^2                     -3]
[                     4                      0                      1      
0                     -1                     -1                      1     
-1                     -1                      4]
[                     4                      0                      1      
0                      1                     -1                     -1     
-1                      1                     -4]
[                     5                      1                     -1      
1                      0                      0                     -1     
0                      0                      5]
[                     5                     -1                     -1      
1                      0                      0                      1     
0                      0                     -5]

sage: G = graphs.PetersenGraph()
sage: Pi=[range(10)]
sage: a,b = search_tree(G, Pi)
sage: print a, b.graph6_string()
[[0, 1, 2, 7, 5, 4, 6, 3, 9, 8], [0, 1, 6, 8, 5, 4, 2, 9, 3, 7], [0, 4, 3,
8, 5, 1, 9, 2, 6, 7], [1, 0, 4, 9, 6, 2, 5, 3, 7, 8]] I@OZCMgs?
sage: c = search_tree(G, Pi, lab=False)
sage: PAut = PermutationGroup([perm_group_elt(aa) for aa in a])
sage: PAut.character_table()
[ 1  1  1  1  1  1  1]
[ 1 -1  1 -1  1 -1  1]
[ 4 -2  0  1  1  0 -1]
[ 4  2  0 -1  1  0 -1]
[ 5  1  1  1 -1 -1  0]
[ 5 -1  1 -1 -1  1  0]
[ 6  0 -2  0  0  0  1]
sage: PAut = PermutationGroup([perm_group_elt(cc) for cc in c])
sage: PAut.character_table()
[ 1  1  1  1  1  1  1]
[ 1 -1  1 -1  1 -1  1]
[ 4 -2  0  1  1  0 -1]
[ 4  2  0 -1  1  0 -1]
[ 5  1  1  1 -1 -1  0]
[ 5 -1  1 -1 -1  1  0]
[ 6  0 -2  0  0  0  1]

sage: G = graphs.CubeGraph(3)
sage: Pi = []
sage: for i in range(8):
...    b = Integer(i).binary()
...    Pi.append(b.zfill(3))
...
sage: Pi = [Pi]
sage: a,b = search_tree(G, Pi)
sage: print a, b.graph6_string()
[[0, 2, 1, 3, 4, 6, 5, 7], [0, 1, 4, 5, 2, 3, 6, 7], [1, 0, 3, 2, 5, 4, 7,
6]] GIQ\T_
sage: c = search_tree(G, Pi, lab=False)

sage: PermutationGroup([perm_group_elt(aa) for aa in a]).order()
48
sage: PermutationGroup([perm_group_elt(cc) for cc in c]).order()
48
sage: DodecAut.order()
120
sage: PAut.order()
120

sage: D = graphs.DodecahedralGraph()
sage: a,b,c = search_tree(D, [range(20)], certify=True)
sage: from sage.plot.plot import GraphicsArray
sage: from sage.graphs.graph_fast import spring_layout_fast
sage: position_D = spring_layout_fast(D)
sage: position_b = {}
sage: for vert in position_D:
...    position_b[c[vert]] = position_D[vert]
sage: graphics_array([D.plot(pos=position_D), b.plot(pos=position_b)]).show()
sage: c
{0: 0, 1: 19, 2: 16, 3: 15, 4: 9, 5: 1, 6: 10, 7: 8, 8: 14, 9: 12, 10: 17,
11: 11, 12: 5, 13: 6, 14: 2, 15: 4, 16: 3, 17: 7, 18: 13, 19: 18}

BENCHMARKS: The following examples are given to check modifications to the algorithm for optimization.

sage: G = Graph({0:[]})
sage: Pi = [[0]]
sage: a,b = search_tree(G, Pi)
sage: print a, b.graph6_string()
[] @
sage: a,b = search_tree(G, Pi, dig=True)
sage: print a, b.graph6_string()
[] @
sage: search_tree(G, Pi, lab=False)
[]

sage: from sage.graphs.graph_isom import all_labeled_graphs, all_ordered_partitions

sage: graph2 = all_labeled_graphs(2)
sage: part2 = all_ordered_partitions(range(2))
sage: for G in graph2:
...    for Pi in part2:
...        a,b = search_tree(G, Pi)
...        c,d = search_tree(G, Pi, dig=True)
...        e = search_tree(G, Pi, lab=False)
...        a = str(a); b = b.graph6_string(); c = str(c); d =
d.graph6_string(); e = str(e)
...        print a.ljust(15), b.ljust(5), c.ljust(15), d.ljust(5),
e.ljust(15)
[]              A?    []              A?    []             
[]              A?    []              A?    []             
[[1, 0]]        A?    [[1, 0]]        A?    [[1, 0]]       
[[1, 0]]        A?    [[1, 0]]        A?    [[1, 0]]       
[]              A_    []              A_    []             
[]              A_    []              A_    []             
[[1, 0]]        A_    [[1, 0]]        A_    [[1, 0]]       
[[1, 0]]        A_    [[1, 0]]        A_    [[1, 0]]

sage: graph3 = all_labeled_graphs(3)
sage: part3 = all_ordered_partitions(range(3))
sage: for G in graph3:
...    for Pi in part3:
...        a,b = search_tree(G, Pi)
...        c,d = search_tree(G, Pi, dig=True)
...        e = search_tree(G, Pi, lab=False)
...        a = str(a); b = b.graph6_string(); c = str(c); d =
d.graph6_string(); e = str(e)
...        print a.ljust(15), b.ljust(5), c.ljust(15), d.ljust(5),
e.ljust(15)
[]              B?    []              B?    []             
[]              B?    []              B?    []             
[[0, 2, 1]]     B?    [[0, 2, 1]]     B?    [[0, 2, 1]]    
[[0, 2, 1]]     B?    [[0, 2, 1]]     B?    [[0, 2, 1]]    
[]              B?    []              B?    []             
[]              B?    []              B?    []             
[[2, 1, 0]]     B?    [[2, 1, 0]]     B?    [[2, 1, 0]]    
[[2, 1, 0]]     B?    [[2, 1, 0]]     B?    [[2, 1, 0]]    
[]              B?    []              B?    []             
[]              B?    []              B?    []             
[[1, 0, 2]]     B?    [[1, 0, 2]]     B?    [[1, 0, 2]]    
[[1, 0, 2]]     B?    [[1, 0, 2]]     B?    [[1, 0, 2]]    
[[1, 0, 2]]     B?    [[1, 0, 2]]     B?    [[1, 0, 2]]    
[[2, 1, 0]]     B?    [[2, 1, 0]]     B?    [[2, 1, 0]]    
[[1, 0, 2]]     B?    [[1, 0, 2]]     B?    [[1, 0, 2]]    
[[0, 2, 1]]     B?    [[0, 2, 1]]     B?    [[0, 2, 1]]    
[[2, 1, 0]]     B?    [[2, 1, 0]]     B?    [[2, 1, 0]]    
[[0, 2, 1]]     B?    [[0, 2, 1]]     B?    [[0, 2, 1]]    
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1, 0, 2]] B?    [[0, 2, 1], [1,
0, 2]]
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[]              BO    []              BO    []             
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[0, 2, 1]]     B_    [[0, 2, 1]]     B_    [[0, 2, 1]]    
[]              BG    []              BG    []             
[[0, 2, 1]]     B_    [[0, 2, 1]]     B_    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[[0, 2, 1]]     BG    [[0, 2, 1]]     BG    [[0, 2, 1]]    
[]              BO    []              BO    []             
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BG    []              BG    []             
[[2, 1, 0]]     B_    [[2, 1, 0]]     B_    [[2, 1, 0]]    
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[2, 1, 0]]     B_    [[2, 1, 0]]     B_    [[2, 1, 0]]    
[]              BG    []              BG    []             
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[[2, 1, 0]]     BG    [[2, 1, 0]]     BG    [[2, 1, 0]]    
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bo    []              Bo    []             
[]              Bo    []              Bo    []             
[[1, 0, 2]]     Bo    [[1, 0, 2]]     Bo    [[1, 0, 2]]    
[[1, 0, 2]]     Bo    [[1, 0, 2]]     Bo    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[]              Bg    []              Bg    []             
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[]              Bg    []              Bg    []             
[]              Bg    []              Bg    []             
[]              Bg    []              Bg    []             
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[[1, 0, 2]]     BW    [[1, 0, 2]]     BW    [[1, 0, 2]]    
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              B_    []              B_    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BO    []              BO    []             
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     B_    [[1, 0, 2]]     B_    [[1, 0, 2]]    
[]              BG    []              BG    []             
[[1, 0, 2]]     B_    [[1, 0, 2]]     B_    [[1, 0, 2]]    
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[]              BG    []              BG    []             
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[[1, 0, 2]]     BG    [[1, 0, 2]]     BG    [[1, 0, 2]]    
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bo    []              Bo    []             
[]              Bo    []              Bo    []             
[[2, 1, 0]]     Bo    [[2, 1, 0]]     Bo    [[2, 1, 0]]    
[[2, 1, 0]]     Bo    [[2, 1, 0]]     Bo    [[2, 1, 0]]    
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[]              Bg    []              Bg    []             
[]              Bg    []              Bg    []             
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[]              Bg    []              Bg    []             
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[[2, 1, 0]]     BW    [[2, 1, 0]]     BW    [[2, 1, 0]]    
[]              Bo    []              Bo    []             
[]              Bo    []              Bo    []             
[[0, 2, 1]]     Bo    [[0, 2, 1]]     Bo    [[0, 2, 1]]    
[[0, 2, 1]]     Bo    [[0, 2, 1]]     Bo    [[0, 2, 1]]    
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              BW    []              BW    []             
[]              Bg    []              Bg    []             
[]              Bg    []              Bg    []             
[]              Bg    []              Bg    []             
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[]              Bg    []              Bg    []             
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[[0, 2, 1]]     BW    [[0, 2, 1]]     BW    [[0, 2, 1]]    
[]              Bw    []              Bw    []             
[]              Bw    []              Bw    []             
[[0, 2, 1]]     Bw    [[0, 2, 1]]     Bw    [[0, 2, 1]]    
[[0, 2, 1]]     Bw    [[0, 2, 1]]     Bw    [[0, 2, 1]]    
[]              Bw    []              Bw    []             
[]              Bw    []              Bw    []             
[[2, 1, 0]]     Bw    [[2, 1, 0]]     Bw    [[2, 1, 0]]    
[[2, 1, 0]]     Bw    [[2, 1, 0]]     Bw    [[2, 1, 0]]    
[]              Bw    []              Bw    []             
[]              Bw    []              Bw    []             
[[1, 0, 2]]     Bw    [[1, 0, 2]]     Bw    [[1, 0, 2]]    
[[1, 0, 2]]     Bw    [[1, 0, 2]]     Bw    [[1, 0, 2]]    
[[1, 0, 2]]     Bw    [[1, 0, 2]]     Bw    [[1, 0, 2]]    
[[2, 1, 0]]     Bw    [[2, 1, 0]]     Bw    [[2, 1, 0]]    
[[1, 0, 2]]     Bw    [[1, 0, 2]]     Bw    [[1, 0, 2]]    
[[0, 2, 1]]     Bw    [[0, 2, 1]]     Bw    [[0, 2, 1]]    
[[2, 1, 0]]     Bw    [[2, 1, 0]]     Bw    [[2, 1, 0]]    
[[0, 2, 1]]     Bw    [[0, 2, 1]]     Bw    [[0, 2, 1]]    
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]
[[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1, 0, 2]] Bw    [[0, 2, 1], [1,
0, 2]]

sage: C = graphs.CubeGraph(1)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order()
2
sage: C = graphs.CubeGraph(2)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order()
8
sage: C = graphs.CubeGraph(3)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order()
48
sage: C = graphs.CubeGraph(4)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order()
384
sage: C = graphs.CubeGraph(5)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order()
3840
sage: C = graphs.CubeGraph(6)
sage: gens = search_tree(C, [C.vertices()], lab=False)
sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).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 = search_tree(D1, [D1.vertices()], use_indicator_function=False)
sage: c,d = search_tree(D2, [D2.vertices()], use_indicator_function=False)
sage: b==d
True

Previously a bug, now the output is correct:

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: G.canonical_label() == H.canonical_label()
True

Another former bug:

sage: Graph('Fll^G').canonical_label()
Graph on 7 vertices

sage: g = Graph(21)
sage: g.automorphism_group(return_group=False, order=True)
51090942171709440000

verify_partition_refinement( )

Verify that the refinement is correct.

sage: from sage.graphs.graph_isom import PartitionStack
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: G = SparseGraph(10)
sage: for i,j,_ in graphs.PetersenGraph().edge_iterator():
...    G.add_arc(i,j)
...    G.add_arc(j,i)
sage: P = PartitionStack(10)
sage: P.set_k(1)
sage: P.split_vertex(0)
sage: P.refine(G, [0], 10, 0, 1)
sage: P
(0,2,3,6,7,8,9,1,4,5)
(0|2,3,6,7,8,9|1,4,5)
sage: P.set_k(2)
sage: P.split_vertex(1)

Note that this line implicitly tests the function verify_partition_refinement:

sage: P.refine(G, [7], 10, 0, 1, test=True)
sage: P
(0,3,7,8,9,2,6,1,4,5)
(0|3,7,8,9,2,6|1,4,5)
(0|3,7,8,9|2,6|1|4,5)

Class: OrbitPartition

class OrbitPartition
An OrbitPartition is simply a partition which keeps track of the orbits of the part of the automorphism group so far discovered. Essentially a union-find datastructure.

sage: from sage.graphs.graph_isom import OrbitPartition
sage: K = OrbitPartition(20)
sage: K.find(7)
7
sage: K.union_find(7, 12)
sage: K.find(12)
7
sage: J = OrbitPartition(20)
sage: J.is_finer_than(K, 20)
True
sage: K.is_finer_than(J, 20)
False

sage: from sage.graphs.graph_isom import OrbitPartition
sage: Theta1 = OrbitPartition(10)
sage: Theta2 = OrbitPartition(10)
sage: Theta1.union_find(0,1)
sage: Theta1.union_find(2,3)
sage: Theta1.union_find(3,4)
sage: Theta1.union_find(5,6)
sage: Theta1.union_find(8,9)
sage: Theta2.vee_with(Theta1, 10)
sage: for i in range(10):
...       print i, Theta2.find(i)
0 0
1 0
2 2
3 2
4 2
5 5
6 5
7 7
8 8
9 8

Functions: find,$ \,$ incorporate_permutation,$ \,$ is_finer_than,$ \,$ union_find,$ \,$ vee_with

find( )

Returns an element of the cell which depends only on the cell.

sage: from sage.graphs.graph_isom import OrbitPartition
sage: K = OrbitPartition(20)

0 and 1 begin in different cells:

sage: K.find(0)
0
sage: K.find(1)
1

Now we put them in the same cell:

sage: K.union_find(0,1)
sage: K.find(0)
0
sage: K.find(1)
0

incorporate_permutation( )

Unions the cells of self which contain common elements of some orbit of gamma.

Input:

gamma
- a permutation, in list notation

sage: from sage.graphs.graph_isom import OrbitPartition
sage: O = OrbitPartition(9)
sage: O.incorporate_permutation([0,1,3,2,5,6,7,4,8])
sage: for i in range(9):
...    print i, O.find(i)
0 0
1 1
2 2
3 2
4 4
5 4
6 4
7 4
8 8

is_finer_than( )

Partition P is finer than partition Q if every cell of P is a subset of a cell of Q.

sage: from sage.graphs.graph_isom import OrbitPartition
sage: K = OrbitPartition(20)
sage: K.find(7)
7
sage: K.union_find(7, 12)
sage: K.find(12)
7
sage: J = OrbitPartition(20)
sage: J.is_finer_than(K, 20)
True
sage: K.is_finer_than(J, 20)
False

union_find( )

Merges the cells containing a and b.

sage: from sage.graphs.graph_isom import OrbitPartition
sage: K = OrbitPartition(20)

0 and 1 begin in different cells:

sage: K.find(0)
0
sage: K.find(1)
1

Now we put them in the same cell:

sage: K.union_find(0,1)
sage: K.find(0)
0
sage: K.find(1)
0

vee_with( )

Merges the minimal number of cells such that other is finer than self.

sage: from sage.graphs.graph_isom import OrbitPartition
sage: K = OrbitPartition(20)
sage: K.union_find(7, 12)
sage: J = OrbitPartition(20)
sage: J.is_finer_than(K, 20)
True
sage: K.is_finer_than(J, 20)
False
sage: J.vee_with(K, 20)
sage: K.is_finer_than(J, 20)
True

Class: PartitionStack

class PartitionStack
TODO: documentation

sage: from sage.graphs.graph_isom import PartitionStack
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)
sage: P.is_discrete()
1
sage: P.set_k(6)
sage: P.is_discrete()
0

sage: G = SparseGraph(10)
sage: for i,j,_ in graphs.PetersenGraph().edge_iterator():
...    G.add_arc(i,j)
...    G.add_arc(j,i)
sage: P = PartitionStack(10)
sage: P.set_k(1)
sage: P.split_vertex(0)
sage: P.refine(G, [0], 10, 0, 1)
sage: P
(0,2,3,6,7,8,9,1,4,5)
(0|2,3,6,7,8,9|1,4,5)
sage: P.set_k(2)
sage: P.split_vertex(1)
sage: P.refine(G, [7], 10, 0, 1)
sage: P
(0,3,7,8,9,2,6,1,4,5)
(0|3,7,8,9,2,6|1,4,5)
(0|3,7,8,9|2,6|1|4,5)

Functions: clear,$ \,$ degree,$ \,$ is_discrete,$ \,$ num_cells,$ \,$ percolate,$ \,$ refine,$ \,$ repr_at_k,$ \,$ sat_225,$ \,$ set_k,$ \,$ sort_by_function,$ \,$ split_vertex

clear( )

Merges all cells in the partition stack.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P
(0,9,8,7,6,5,4,3,2,1)
(0,9,8,7,6,5,4,3,2,1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5|0,2,8,6|4|3)
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5|0,2,8,6|4|3)
sage: P.clear()
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5,0,2,8,6,4,3)

degree( )

Returns the number of edges in G from self.entries[v] to a vertex in W.

sage: from sage.graphs.graph_isom import PartitionStack
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: P = PartitionStack([range(9, -1, -1)])
sage: P
(0,9,8,7,6,5,4,3,2,1)
sage: G = SparseGraph(10)
sage: G.add_arc(2,9)
sage: G.add_arc(3,9)
sage: G.add_arc(4,9)
sage: P.degree(G, 1, 0)
3

is_discrete( )

Returns whether the partition consists of only singletons.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)
sage: P.is_discrete()
True
sage: P.set_k(2)
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
sage: P.is_discrete()
False

num_cells( )

Return the number of cells in the finest partition.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5|0,2,8,6|4|3)
sage: P.num_cells()
4
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P
(5,9,1,7,0,2,8,6,4,3)
(5,9,1,7|0,2,8,6|4|3)
(5,9|1,7|0,2,8,6|4|3)
sage: P.num_cells()
5

percolate( )

Perform one round of bubble sort, moving the smallest element to the front.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P
(0,9,8,7,6,5,4,3,2,1)
sage: P.percolate(2,7)
sage: P
(0,9,3,8,7,6,5,4,2,1)

refine( )

Implementation of Algorithm 2.5 in [1].

sage: from sage.graphs.graph_isom import PartitionStack
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)
sage: P.is_discrete()
1
sage: P.set_k(6)
sage: P.is_discrete()
0

sage: G = SparseGraph(10)
sage: for i,j,_ in graphs.PetersenGraph().edge_iterator():
...    G.add_arc(i,j)
...    G.add_arc(j,i)
sage: P = PartitionStack(10)
sage: P.set_k(1)
sage: P.split_vertex(0)
sage: P.refine(G, [0], 10, 0, 1)
sage: P
(0,2,3,6,7,8,9,1,4,5)
(0|2,3,6,7,8,9|1,4,5)
sage: P.set_k(2)
sage: P.split_vertex(1)
sage: P.refine(G, [7], 10, 0, 1)
sage: P
(0,3,7,8,9,2,6,1,4,5)
(0|3,7,8,9,2,6|1,4,5)
(0|3,7,8,9|2,6|1|4,5)

repr_at_k( )

Return the k-th line of the representation of self, i.e. the k-th partition in the stack.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)

sage: P.repr_at_k(0)
'(5,9,7,1,6,2,8,0,4,3)'
sage: P.repr_at_k(1)
'(5,9,7,1|6,2,8,0|4|3)'

sat_225( )

Whether the finest partition satisfies the hypotheses of Lemma 2.25 in [1].

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P
(0,9,8,7,6,5,4,3,2,1)
sage: P.sat_225(10)
False
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5|0,2,8,6|4|3)
sage: P.sat_225(10)
False
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P
(5,9,1,7,0,2,8,6,4,3)
(5,9,1,7|0,2,8,6|4|3)
(5,9|1,7|0,2,8,6|4|3)
sage: P.sat_225(10)
False
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P
(5,9,1,7,2,6,0,8,4,3)
(5,9,1,7|2,6,0,8|4|3)
(5,9|1,7|2,6,0,8|4|3)
(5,9|1,7|2,6|0,8|4|3)
sage: P.sat_225(10)
True

set_k( )

Sets self.k, the index of the finest partition.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)

sage: P.set_k(2)
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)

sort_by_function( )

Sort the cell starting at start using a counting sort, where degrees is the function giving the sort. Result is the cell is subdivided into cells which have elements all of the same 'degree,' in order.

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P
(0,9,8,7,6,5,4,3,2,1)
(0,9,8,7,6,5,4,3,2,1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P
(1,9,7,5,0,2,8,6,4,3)
(1,9,7,5|0,2,8,6|4|3)

split_vertex( )

Splits the cell in self(k) containing v, putting new cells in place in self(k).

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P
(0,9,8,7,6,5,4,3,2,1)
sage: P.split_vertex(2)
sage: P
(2|0,9,8,7,6,5,4,3,1)

Special Functions: __repr__

__repr__( )

sage: from sage.graphs.graph_isom import PartitionStack
sage: P = PartitionStack([range(9, -1, -1)])
sage: P.set_k(1)
sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 10)
0
sage: P.set_k(2)
sage: P.sort_by_function(0, [2,1,2,1], 10)
0
sage: P.set_k(3)
sage: P.sort_by_function(4, [2,1,2,1], 10)
4
sage: P.set_k(4)
sage: P.sort_by_function(0, [0,1], 10)
0
sage: P.set_k(5)
sage: P.sort_by_function(2, [1,0], 10)
2
sage: P.set_k(6)
sage: P.sort_by_function(4, [1,0], 10)
4
sage: P.set_k(7)
sage: P.sort_by_function(6, [1,0], 10)
6
sage: P
(5,9,7,1,6,2,8,0,4,3)
(5,9,7,1|6,2,8,0|4|3)
(5,9|7,1|6,2,8,0|4|3)
(5,9|7,1|6,2|8,0|4|3)
(5|9|7,1|6,2|8,0|4|3)
(5|9|7|1|6,2|8,0|4|3)
(5|9|7|1|6|2|8,0|4|3)
(5|9|7|1|6|2|8|0|4|3)

See About this document... for information on suggesting changes.