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
) |
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
) |
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
) |
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])
) |
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, {}]]]
) |
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, {}]]
) |
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:
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]]
) |
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)
) |
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
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 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
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
) |
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
) |
Unions the cells of self which contain common elements of some orbit of gamma.
Input:
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
) |
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
) |
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
) |
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
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
) |
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)
) |
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
) |
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
) |
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
) |
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)
) |
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)
) |
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)'
) |
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
) |
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 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)
) |
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__
) |
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.