(*****************************************************************************
 *    Procedures for generating and counting minimally rigid graphs in 3d     *
 *                              with <=11 vertices                             *
 *                        (by Georg Grasegger, 2018)                          *
 *   based on https://oeis.org/A227117/a227117_2.txt by Christoph Koutschan   *
 *****************************************************************************)

Mat2G::usage="Mat2G[m] transforms adjeceny matrix m to integer representation of the graph.";
Mat2G[mat_] := FromDigits[Flatten[MapIndexed[Drop[#1, #2[[1]]]&, mat]], 2];
G2Mat::usage="G2Mat[g] transforms integer representation g to adjeceny matrix of the graph.";
G2Mat[g_Integer, n_Integer] := (# + Transpose[#])&[PadLeft[
  Table[Take[#, {(2n-i)*(i-1)/2+1, (2n-i-1)*i/2}], {i, n}]&[PadLeft[IntegerDigits[g, 2], n*(n-1)/2]], {n, n}]];
G2Mat[g_Integer] := G2Mat[g, Floor[(3 + Sqrt[8*Floor[Log[2, g]] + 1]) / 2]];

GraphNormalForm::usage="GraphNormalForm[m] computes a unique representative of the graph given by adjecency matrix m within its class of isomorphic graphs.\n"
GraphNormalForm[gr1_List] :=Normal[AdjacencyMatrix[CanonicalGraph[G2Edges[Mat2G[gr1]]]]];

(* Transform a graph to a list of edges and vice versa. *)
G2Edges::usage="G2Edges[g] Transforms integer representation g to edge list of the graph.";
G2Edges[g_Integer] := Select[Position[G2Mat[g], 1], Less @@ # &];

(*Henneberg 3D constructions using only Typ I and II*)
Henneberg3d12::usage="Henneberg3d12[g] constructs all graphs that can be otianed from g (in integer representation) by a single Henneberg step in 3d if Type I or II.";
Henneberg3d12[g_] :=
Module[{gr},
  Union[Flatten[{Henneberg3d1[g],Henneberg3d2[g]}]]  
];
(* Doing the Henneberg type I steps. *)
Henneberg3d1::usage="Henneberg3d1[g] constructs all graphs that can be obtianed from g (in integer representation) by a single Henneberg I step in 3d.";
Henneberg3d1[g_] :=
Module[{gr,n},
  gr = G2Mat[g];
  n = Length[gr]+1;
  gr = PadRight[gr, {n, n}];
  Union[Flatten[
    (* Perform all possible type I Henneberg moves. *)
    Table[Mat2G[GraphNormalForm[ReplacePart[gr, {{v1, n} -> 1, {n, v1} -> 1, {v2, n} -> 1, {n, v2} -> 1, {v3, n} -> 1, {n, v3} -> 1}]]],
      {v1, n - 1}, {v2, v1 + 1, n - 1}, {v3, v2+1,n-1}]
  ]]];
(* Similar as before, but only with Henneberg type II moves. *)
Henneberg3d2::usage="Henneberg3d2[g] constructs all graphs that can be obtianed from g (in integer representation) by a single Henneberg II step in 3d.";
Henneberg3d2[g_Integer] :=
Module[{gr, ed, n},
  gr = G2Mat[g];
  n = Length[gr]+1;
  gr = PadRight[gr, {n, n}];
  ed = G2Edges[g];
  Union[Flatten[
    (* Perform all possible type II Henneberg moves. *)
    Table[
      {v1, v2} = ed[[k]];
      Mat2G[GraphNormalForm[ReplacePart[gr, 
     {{v1, v2} -> 0, {v2, v1} -> 0, {v1, n} -> 1, {n, v1} -> 1,
        {v2, n} -> 1, {n, v2} -> 1, 
        {#[[1]], n} -> 1, {n, #[[1]]} -> 1,
        {#[[2]], n} -> 1, {n, #[[2]]} -> 1
      }]]]& /@ Subsets[Complement[Range[n - 1], {v1, v2}],{2}],
      {k, Length[ed]}]
  ]]];
  
(* Compute a list of minimally rigid graphs in 3D for n<=11 vertices. *)
H12GeiringerGraphs[4] = {63};
H12GeiringerGraphs[n_ /; n > 4&&n<=11] := H12GeiringerGraphs[n] = Union @@ (Henneberg3d12[#]& /@ H12GeiringerGraphs[n - 1]);