1############################################################################ 2## 3## blocks.gi 4## Copyright (C) 2013-15 James D. Mitchell 5## 6## Licensing information can be found in the README file of this package. 7## 8############################################################################# 9## 10 11############################################################################# 12# Blocks are stored internally as a list consisting of: 13# 14# [ nr of blocks, internal rep of blocks, transverse blocks ] 15# 16# <nr of blocks> is a non-negative integer, <internal rep of blocks>[i] = j if 17# <i> belongs to the <j>th block, <transverse blocks>[j] = 1 if block <j> is 18# transverse and 0 if it is not. 19############################################################################# 20 21############################################################################# 22# GAP level - directly using interface to C/C++ level 23############################################################################# 24 25InstallMethod(LeftBlocks, "for a bipartition", [IsBipartition], 26BIPART_LEFT_BLOCKS); 27 28InstallMethod(RightBlocks, "for a bipartition", [IsBipartition], 29BIPART_RIGHT_BLOCKS); 30 31# for backwards compatibility 32InstallGlobalFunction(BlocksNC, BLOCKS_NC); 33InstallMethod(ExtRepOfObj, "for blocks", [IsBlocks], BLOCKS_EXT_REP); 34 35InstallMethod(ChooseHashFunction, "for blocks", 36[IsBlocks, IsInt], 37function(x, hashlen) 38 return rec(func := BLOCKS_HASH, 39 data := hashlen); 40end); 41 42InstallMethod(DegreeOfBlocks, "for blocks", [IsBlocks], BLOCKS_DEGREE); 43InstallMethod(RankOfBlocks, "for blocks", [IsBlocks], BLOCKS_RANK); 44InstallMethod(NrBlocks, "for blocks", [IsBlocks], BLOCKS_NR_BLOCKS); 45InstallMethod(\=, "for blocks", [IsBlocks, IsBlocks], BLOCKS_EQ); 46InstallMethod(\<, "for blocks", [IsBlocks, IsBlocks], BLOCKS_LT); 47InstallMethod(ProjectionFromBlocks, "for blocks", [IsBlocks], BLOCKS_PROJ); 48InstallMethod(OnRightBlocks, "for blocks and a bipartition", 49[IsBlocks, IsBipartition], BLOCKS_RIGHT_ACT); 50InstallMethod(OnLeftBlocks, "for blocks and a bipartition", 51[IsBlocks, IsBipartition], BLOCKS_LEFT_ACT); 52 53############################################################################# 54# GAP level - NOT directly using interface to C/C++ level 55############################################################################# 56 57InstallMethod(AsDigraph, "for blocks", [IsBlocks], 58function(blocks) 59 local ext, out, block, i; 60 61 ext := ExtRepOfObj(blocks); 62 out := List([1 .. DegreeOfBlocks(blocks)], x -> []); 63 64 for block in ext do 65 if block[1] > 0 then # transverse block 66 for i in block do 67 out[i] := ShallowCopy(block); 68 RemoveSet(out[i], i); 69 od; 70 else 71 for i in block do 72 out[-i] := block * -1; 73 od; 74 fi; 75 od; 76 return Digraph(out); 77end); 78 79InstallMethod(CanonicalBlocks, "for blocks", [IsBlocks], 80function(blocks) 81 local gr, canon, scc, rep, i; 82 83 gr := AsDigraph(blocks); 84 gr := OnDigraphs(gr, BlissCanonicalLabelling(gr)); 85 canon := []; 86 87 scc := DigraphStronglyConnectedComponents(gr).comps; 88 canon := ShallowCopy(scc); 89 90 for i in [1 .. Length(scc)] do 91 rep := scc[i][1]; 92 if IsDigraphEdge(gr, [rep, rep]) then 93 canon[i] := -1 * canon[i]; 94 fi; 95 od; 96 97 return BLOCKS_NC(canon); 98end); 99 100# not a synonym since NrTransverseBlocks applies to a bipartition also 101InstallMethod(NrTransverseBlocks, "for blocks", [IsBlocks], RankOfBlocks); 102 103# Printing, viewing etc . . . 104 105InstallMethod(String, "for blocks", [IsBlocks], 106x -> Concatenation("BlocksNC(", String(ExtRepOfObj(x)), ")")); 107 108InstallMethod(ViewObj, "for blocks", [IsBlocks], 109function(blocks) 110 local ext, str, i; 111 112 ext := ExtRepOfObj(blocks); 113 if Length(ext) > 0 then 114 Print("<blocks: "); 115 if ext[1][1] < 0 then 116 Print(-1 * ext[1]); 117 else 118 str := JoinStringsWithSeparator(List(ext[1], String), "*, "); 119 Print("[ ", str, "* ]"); 120 fi; 121 for i in [2 .. Length(ext)] do 122 if ext[i][1] < 0 then 123 Print(", ", -1 * ext[i]); 124 else 125 str := JoinStringsWithSeparator(List(ext[i], String), "*, "); 126 Print(", [ ", str, "* ]"); 127 fi; 128 od; 129 else 130 Print("<empty blocks"); 131 fi; 132 133 Print(">"); 134 return; 135end); 136 137InstallMethod(PrintObj, "for blocks", [IsBlocks], 10, 138function(blocks) 139 Print(PrintString(blocks)); 140 return; 141end); 142