# A338487pub.mws
#
# Rainer Rosenthal, 2020-12-02
#
# A338487 counts the CDE-descendants of the "bridge".
# The bridge as smallest h-graph. It has 4 nodes and 5 edges.
#
#            1               | 1  2  3  4
#           / \            --+------------
#          /   \           1 |    0  1  1 
#         3-----4          2 |       1  1 
#          \   /           3 |          1
#           \ /            4 |
#            2
#                          adjacency matrix
#    h-graph "bridge"      netcode: "011111"
#
#
restart: with(combinat):
########################################################################
#
#  Functions [C]onnect, [D]issect and [E]xtend used in
#  function C_D_E to build larger and larger graphs.
#
########################################################################
#
# DISTINGUISHED - the first two nodes A=1 and Z=2 are distinguished.
#
DISTINGUISHED := {1,2}:
#
# ActiveNodes - Which nodes are connected?
#
ActiveNodes := proc(netcode)
   global nodness;
   local N,actnod,pos,i,j;
   N := nodness[length(netcode)];
   actnod := {};
   pos := 1;
   for i to N-1 do
    for j from i+1 to N do
      if netcode[pos] <> "0" then
         actnod := actnod union {i,j};
      fi;
      pos := pos + 1;
    od;
   od;
   return actnod;
end:
#
# Cod2Mat - Convert graph code into adjacency matrix.
#
Cod2Mat := proc(netcode)
   global nodness;
   local N,eMat,pos,i,j,ival;
   N := nodness[length(netcode)];
   eMat := [seq([seq(0,j=1..N)],i=1..N)];
   pos := 1:
   for i to N-1 do
      for j from i+1 to N do
         ival := (sscanf(netcode[pos],"%d"))[1];
         eMat[i][j] := ival;
         eMat[j][i] := ival;
         pos := pos + 1;
      od;
   od;
   return eMat;
end:
#
# Mat2Cod - Convert adjacency matrix into graph code.
#
Mat2Cod := proc(M)
   local erg,i,j,N;
   erg := "";
   N := nops(M);
   for i to N do
      for j from i+1 to N do
         erg := cat(erg,sprintf("%d",M[i][j]));
      od;
   od;
   return erg;
end:
#
# Mat2CodN - Convert adjacency matrix into graph code with N nodes
#
Mat2CodN := proc(M,N)
   local erg,i,j,m;
   erg := "";
   m := nops(M);
   for i to m-1 do
      for j from i+1 to m do
         erg := cat(erg,sprintf("%d",M[i][j]));
      od;
      for j from m+1 to N do
         erg := cat(erg,"0");
      od;
   od;
   for i from m to N-1 do
      for j from i+1 to N do
         erg := cat(erg,"0");
      od;
   od;
   return erg;
end:
#
# Dissect - Replace edge P-Q by P-M-Q with
#           new node M.
#
Dissect := proc(netcode,i1,i2)
   global nodness;
   local N,i,mat,freenodes,newnode,varcode;
   varcode := netcode;
   N := nodness[length(netcode)];
   if i1 = i2 then
      print(_ERROR_EDGE_IS_CYCLE_);
      return "";
   fi;
   freenodes := {seq(i,i=1..N)} minus ActiveNodes(varcode);
   if freenodes = {} then
      #print(_ERROR_NOT_ENOUGH_NODES_);
      #return "";
      N := N + 1;
      varcode := Mat2CodN(Cod2Mat(netcode),N);
      #print(_EXPAND_,netcode,_TO_,varcode);
      freenodes := {seq(i,i=1..N)} minus ActiveNodes(varcode);
   fi;
   newnode := min(op(freenodes));
   mat := Cod2Mat(varcode);
   if mat[i1][i2] = 0 then
      print(_ERROR_EDGE_IS_MISSING_);
      return "";
   fi;
   mat[i1][i2] := mat[i1][i2] - 1;
   mat[i2][i1] := mat[i2][i1] - 1;
   mat[i1][newnode] := 1;
   mat[newnode][i1] := 1;
   mat[i2][newnode] := 1;
   mat[newnode][i2] := 1;
   return Mat2Cod(mat);
end:
#
# Connect - Connect different nodes P, Q
#           not both distinguished.
#           Allow A-Z for netcode "0", i.e., when
#           there are no more nodes and no edge.
#
Connect := proc(netcode,i1,i2)
   global nodness;
   local mat;
   if {i1,i2} = DISTINGUISHED and netcode <"0" then
      print(_ERROR_DIRECT_A_Z_CONNECT_);
      return "";
   fi;
   if i1 = i2 then
      print(_ERROR_EDGE_IS_CYCLE_);
      return "";
   fi;
   mat := Cod2Mat(netcode);
   mat[i1][i2] := mat[i1][i2] + 1;
   mat[i2][i1] := mat[i2][i1] + 1;
   return Mat2Cod(mat);
end:
#
# Extend - Extend from non-distinguished node
#          to a new node.
#
Extend := proc(netcode,oldnode)
   global nodness,DISTINGUISHED;
   local N,i,mat,newnode,freenodes,varcode;
   varcode := netcode;
   N := nodness[length(netcode)];
   freenodes := {seq(i,i=1..N)} minus ActiveNodes(netcode);
   if freenodes = {} then
      #print(_ERROR_NOT_ENOUGH_NODES_FOR_EXTEND_);
      #return "";
      N := N + 1;
      varcode := Mat2CodN(Cod2Mat(netcode),N);
      #print(_EXPAND_,netcode,_TO_,varcode);
      freenodes := {seq(i,i=1..N)} minus ActiveNodes(varcode);
   fi;
   newnode := min(op(freenodes));
   if member(oldnode,DISTINGUISHED) then
      print(_ERROR_EXTEND_FROM_DISTINGUISHED_NODE_);
      return "";
   fi;
   mat := Cod2Mat(varcode);
   mat[oldnode][newnode] := 1;
   mat[newnode][oldnode] := 1;
   return Mat2Cod(mat);
end:
#
# PossDiss - possible node-pairs for [D]issect operation are
#            the endpoints of edges.
#
PossDiss := proc(netcode)
   local i,j,actnod,erg,mat;
   erg := {};
   mat := Cod2Mat(netcode);
   actnod := sort([op(ActiveNodes(netcode))]);
   for i to nops(actnod) do
      for j from i+1 to nops(actnod) do
         if mat[i,j] > 0 then
            erg := erg union {[actnod[i],actnod[j]]};
         fi;
      od;
   od;
   return erg;
end:
#
# PossConn - possible node-pairs for [C]onnect operation are
#            any existing P != Q with {P,Q} != {"A","Z"}.
#
#            If A (node 1) and Z (node 2) are the only nodes
#            and if they are unconnected, then return {[1,2]}.
#
PossConn := proc(netcode)
   local i,j,actnod,erg;
   if netcode = "0" then
      return {[1,2]};
   fi;
   erg := {};
   actnod := sort([op(ActiveNodes(netcode))]);
   for i to nops(actnod) do
      for j from i+1 to nops(actnod) do
         if {i,j} <> DISTINGUISHED then
            erg := erg union {[actnod[i],actnod[j]]};
         fi;
      od;
   od;
   return erg;
end:
#
# PossExt - possible start nodes for [E]xtend operation are
#           all nodes except for the distinguished A and Z.
# 
PossExt := proc(netcode)
  global DISTINGUISHED;
  return map(Node2Name,ActiveNodes(netcode) minus DISTINGUISHED);
end:
#
# DefineSymmetry - Symmetries of AZ-network: {1,2} is fix, {3,...,V} is fix.
#                  typeOfSym:
#                  INTERCHANGEABLE      nodes 1 and 2 fix as set {1,2}
#                  NONINTERCHANGEABLE   nodes 1 and 2 fix as nodes
#
DefineSymmetry := proc(typeOfSym,maxnodes)
   global AllSymmi,MAXNODES,nodness;
   local symm12,symmrest,i,j,n;
   AllSymmi := [1,2,3,4,5,6,7,8,9,10,11];
   if typeOfSym = INTERCHANGEABLE then
      symm12 := permute([1,2]):
   elif typeOfSym = NONINTERCHANGEABLE then
      symm12 := [[1,2]];:
   else
      print(_ERROR_UNDEFINED_SYMMETRY_,typeOfSym);
   fi;
   for n from 2 to maxnodes do
      symmrest := permute([seq(i,i=3..n)]):
      AllSymmi[n] := []:
      for i to nops(symm12) do
         for j to nops(symmrest) do
            AllSymmi[n] := [op(AllSymmi[n]),[op(symm12[i]),op(symmrest[j])]];
         od;
      od;
   od;
   MAXNODES := maxnodes;
   nodness := [seq(seq(n,j=1..n),n=2..maxnodes)]: # nodes nessessary for codelength L
   return;
end:
#
# bauMatSym - Perform CDE-symmetry on the adjacency matrix
#             of the netcode-graph.
#
bauMatSym := proc(netcode,sym)
   global nodness;
   local N,eMat,pos,i,j,si,sj,ival;
   N := nodness[length(netcode)];
   eMat := [seq([seq(0,j=1..N)],i=1..N)];
   pos := 1:
   for i to N-1 do
      for j from i+1 to N do
         si := sym[i];
         sj := sym[j];
         ival := (sscanf(netcode[pos],"%d"))[1];
         eMat[si][sj] := ival;
         eMat[sj][si] := ival;
         pos := pos + 1;
      od;
   od;
   return eMat;
end:
#
# Kumpel - Find all equivalent graphs under CDE-symmetries.
# 
Kumpel := proc(netcode)
   global nodness,AllSymmi,AllSymm,erg;
   local i;
   erg := {};
   AllSymm := AllSymmi[nodness[length(netcode)]];
   for i to nops(AllSymm) do
      erg := erg union {Mat2Cod(bauMatSym(netcode,AllSymm[i]))};
   od;
   return erg;
end:
#
# CDEstep - add a new edge to any graph in oldlist,
#           using [D]issect, [C]onnect and [E]xtend.
#           Result is newlist with the larger graphs.
#
#
# Cstep - add a new edge to any graph in oldset,
#         using [C]onnect.
#         Result is newset with the larger graphs.
#
Cstep := proc(oldset)
   local newset,netcode,Poss,neurein,pair,prob;
   newset := {};
   for netcode in oldset do
      Poss := PossConn(netcode);
      for pair in Poss do
         prob := Connect(netcode,op(pair));
         neurein := max(op(Kumpel(prob)));
         newset := newset union {neurein};
      od:
   od:
   return newset;
end:
#
# Dstep - add a new edge to any graph in oldset,
#         using [D]issect.
#         Result is newset with the larger graphs.
#
Dstep := proc(oldset)
   local newset,netcode,Poss,neurein,pair,prob;
   newset := {};
   for netcode in oldset do
      Poss := PossDiss(netcode);
      for pair in Poss do
         prob := Dissect(netcode,op(pair));
         neurein := max(op(Kumpel(prob)));
         newset := newset union {neurein};
      od:
   od:
   return newset;
end:
#
# Estep - add a new edge to any graph in oldset,
#         using [E]xtend.
#         Result is newset with the larger graphs.
#
Estep := proc(oldset)
   local newset,netcode,Poss,neurein,stnode,prob;
   newset := {};
   for netcode in oldset do
      Poss := ActiveNodes(netcode) minus DISTINGUISHED;
      for stnode in Poss do
         prob := Extend(netcode,stnode);
         neurein := max(op(Kumpel(prob)));
         newset := newset union {neurein};
      od:
   od:
   return newset;
end:
#
# C_D_E - add a new edge to any graph in oldset,
#         using [D]issect, [C]onnect and [E]xtend.
#         Result is newset with the larger graphs.
#
C_D_E := x -> Cstep(x) union Dstep(x) union Estep(x);

MAXNODES := 8:
MAXEDGES := 9:
DefineSymmetry(INTERCHANGEABLE,MAXNODES):

for n to 4 do
   SetA338487(n) := {};
od:
SetA338487(5) := {"011111"}: # "bridge" adjacency matrix coded
for n from 6 to MAXEDGES do
   SetA338487(n) := C_D_E(SetA338487(n-1));
od:
seq(nops(SetA338487(n)),n=1..MAXEDGES);