{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R362",
  "content_hash": null,
  "slug": "ham8-artifact-orbit-weighted-check",
  "type": "artifact",
  "title": "Independent nauty orbit-weighted enumeration",
  "summary": "An isomorph-free generator and automorphism-group calculation give the same labeled total and edge histogram.",
  "relevance": "For Exact Hamiltonicity probability on eight labeled vertices, record ham8-artifact-orbit-weighted-check (“Independent nauty orbit-weighted enumeration”) supplies evidence or a replay used to check the packet. The record states: An isomorph-free generator and automorphism-group calculation give the same labeled total and edge histogram.",
  "relevance_source": "recorded",
  "body": "This check uses tinygraph at commit `97665350689943d64b90ca1501b3291db0538a0a`, the version cited by OEIS A326208, together with nauty 2.6r6. `Graph::enumerate(8, ...)` supplies one representative of every isomorphism class. A separate depth-first search tests for a Hamilton cycle while fixing vertex 0 as the start.\n\nFor each passing representative \\(G\\), nauty computes \\(|\\operatorname{Aut}(G)|\\), and `numLabeledGraphs()` returns \\(8!/|\\operatorname{Aut}(G)|\\). There are 6,196 passing representatives among all 12,346 classes. Their weights sum to 151,676,112. The labeled edge histogram matches the upward-closure histogram at every edge count. Sorted pairs of graph6 records and little-endian orbit weights have FNV-1a fingerprint `16813842364046026506`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all isomorphism classes of simple graphs on eight vertices, generated once each and weighted by 8!/|Aut(G)|",
    "bounds": {
      "vertices": {
        "min": 8,
        "max": 8
      },
      "unlabeled_graphs": {
        "min": 12346,
        "max": 12346
      },
      "unlabeled_hamiltonian_graphs": {
        "min": 6196,
        "max": 6196
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "external_cpp11_orbit_computation",
    "entrypoint": "Compile source_lines as orbit_check.cc against tinygraph Graph.o, Set.o, geng.o and its nauty 2.6r6 objects, then run the resulting executable",
    "runtime": "C++11, tinygraph commit 97665350689943d64b90ca1501b3291db0538a0a, and nauty 2.6r6",
    "citation": {
      "url": "https://github.com/falk-hueffner/tinygraph/tree/97665350689943d64b90ca1501b3291db0538a0a",
      "locator": "Independent C++11 driver executed against tinygraph 9766535 and nauty 2.6r6 on 2026-07-24"
    },
    "outputs": "all_unlabeled=12346 ham_unlabeled=6196 ham_labeled=151676112\norbit_size_hist=1:1,28:1,35:1,56:1,70:1,105:1,168:3,210:4,280:9,315:1,420:6,560:8,630:1,672:2,840:21,1120:4,1260:8,1680:47,2016:4,2520:66,2880:2,3360:127,5040:250,6720:67,10080:975,20160:2255,40320:2330\nedge_hist_unlabeled=8:1,9:3,10:19,11:82,12:256,13:553,14:876,15:1068,16:1051,17:862,18:615,19:384,20:215,21:112,22:55,23:24,24:11,25:5,26:2,27:1,28:1\nedge_hist_labeled=8:2520,9:50400,10:453600,11:2343600,12:7546560,13:16226280,14:24905940,15:28941080,16:26674655,17:20162856,18:12760706,19:6829760,20:3096177,21:1182856,22:376684,23:98280,24:20475,25:3276,26:378,27:28,28:1\nrecords_fnv64=16813842364046026506\n",
    "inline_source": [
      "#include \"Graph.hh\"",
      "#include <algorithm>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <map>",
      "#include <string>",
      "#include <utility>",
      "#include <vector>",
      "",
      "bool extend(const Graph& g, int start, int last, uint64_t used) {",
      "    if (__builtin_popcountll(used) == g.n()) return g.hasEdge(last, start);",
      "    for (int next = 0; next < g.n(); ++next) {",
      "        if (((used >> next) & 1U) == 0 && g.hasEdge(last, next)) {",
      "            if (extend(g, start, next, used | (uint64_t(1) << next))) return true;",
      "        }",
      "    }",
      "    return false;",
      "}",
      "",
      "bool hamiltonian(const Graph& g) {",
      "    if (g.n() < 3) return false;",
      "    return extend(g, 0, 0, 1);",
      "}",
      "",
      "int main() {",
      "    uint64_t all_unlabeled = 0, ham_unlabeled = 0, ham_labeled = 0;",
      "    std::map<uint64_t, uint64_t> orbit_hist;",
      "    uint64_t by_edges_unlabeled[29] = {}, by_edges_labeled[29] = {};",
      "    std::vector<std::pair<std::string, uint64_t>> records;",
      "    Graph::enumerate(8, [&](const Graph& g) {",
      "        ++all_unlabeled;",
      "        if (!hamiltonian(g)) return;",
      "        ++ham_unlabeled;",
      "        uint64_t labels = g.numLabeledGraphs();",
      "        ham_labeled += labels;",
      "        ++orbit_hist[labels];",
      "        ++by_edges_unlabeled[g.m()];",
      "        by_edges_labeled[g.m()] += labels;",
      "        records.emplace_back(g.graph6(), labels);",
      "    });",
      "    std::sort(records.begin(), records.end());",
      "    uint64_t hash = UINT64_C(14695981039346656037);",
      "    auto add = [&](unsigned char byte) {",
      "        hash ^= byte;",
      "        hash *= UINT64_C(1099511628211);",
      "    };",
      "    for (const auto& record : records) {",
      "        for (unsigned char c : record.first) add(c);",
      "        add(0);",
      "        for (int i = 0; i < 8; ++i) add((record.second >> (8 * i)) & 255);",
      "    }",
      "    std::cout << \"all_unlabeled=\" << all_unlabeled",
      "              << \" ham_unlabeled=\" << ham_unlabeled",
      "              << \" ham_labeled=\" << ham_labeled << '\\n';",
      "    std::cout << \"orbit_size_hist=\";",
      "    bool first = true;",
      "    for (auto item : orbit_hist) {",
      "        if (!first) std::cout << ',';",
      "        first = false;",
      "        std::cout << item.first << ':' << item.second;",
      "    }",
      "    std::cout << \"\\nedge_hist_unlabeled=\";",
      "    first = true;",
      "    for (int m = 0; m <= 28; ++m) if (by_edges_unlabeled[m]) {",
      "        if (!first) std::cout << ',';",
      "        first = false;",
      "        std::cout << m << ':' << by_edges_unlabeled[m];",
      "    }",
      "    std::cout << \"\\nedge_hist_labeled=\";",
      "    first = true;",
      "    for (int m = 0; m <= 28; ++m) if (by_edges_labeled[m]) {",
      "        if (!first) std::cout << ',';",
      "        first = false;",
      "        std::cout << m << ':' << by_edges_labeled[m];",
      "    }",
      "    std::cout << \"\\nrecords_fnv64=\" << hash << '\\n';",
      "}"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://github.com/falk-hueffner/tinygraph/tree/97665350689943d64b90ca1501b3291db0538a0a",
    "locator": "Independent C++11 driver executed against tinygraph 9766535 and nauty 2.6r6 on 2026-07-24"
  },
  "models": [],
  "relations": [
    {
      "slug": "R365",
      "title": "Exactly 151,676,112 labeled graphs on eight vertices are Hamiltonian",
      "object_type": "claim",
      "relation": "independently_reproduces",
      "direction": "outgoing"
    },
    {
      "slug": "R363",
      "title": "Replayable 32 MiB upward-closure certificate",
      "object_type": "artifact",
      "relation": "cross_checks",
      "direction": "outgoing"
    },
    {
      "slug": "hamiltonian-graph-probability-eight",
      "title": "hamiltonian graph probability eight",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}