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