tpl_ca_graph_automaton_test.cc

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#include <cstdint>
#include <random>
#include <stdexcept>
#include <vector>
 
#include <gtest/gtest.h>
 
#include <ca-traits.H>
#include <tpl_ca_concepts.H>
#include <tpl_ca_graph_automaton.H>
#include <tpl_ca_rule.H>
 
using namespace Aleph;
using namespace Aleph::CA;
 
// ---------------------------------------------------------------------------
// Concept conformance.
// ---------------------------------------------------------------------------
 
static_assert(LatticeLike<Graph_Lattice<int>>);
static_assert(LatticeLike<Graph_Lattice<bool>>);
 
// ---------------------------------------------------------------------------
// Adjacency builders.
// ---------------------------------------------------------------------------
 
TEST(CAGraphBuilders, PathGraphAdjacencyShape)
{
  const auto adj = make_path_graph_adjacency(5);
  ASSERT_EQ(adj.size(), 5u);
  EXPECT_EQ(adj[0], (Array<std::size_t>{1}));
  EXPECT_EQ(adj[1], (Array<std::size_t>{0, 2}));
  EXPECT_EQ(adj[2], (Array<std::size_t>{1, 3}));
  EXPECT_EQ(adj[3], (Array<std::size_t>{2, 4}));
  EXPECT_EQ(adj[4], (Array<std::size_t>{3}));
}
 
TEST(CAGraphBuilders, RingGraphAdjacencyShape)
{
  const auto adj = make_path_graph_adjacency(4, /*cycle=*/true);
  ASSERT_EQ(adj.size(), 4u);
  EXPECT_EQ(adj[0], (Array<std::size_t>{3, 1}));
  EXPECT_EQ(adj[1], (Array<std::size_t>{0, 2}));
  EXPECT_EQ(adj[2], (Array<std::size_t>{1, 3}));
  EXPECT_EQ(adj[3], (Array<std::size_t>{2, 0}));
}
 
TEST(CAGraphBuilders, GridGraphAdjacencyEdgeCount)
{
  const auto adj = make_grid_graph_adjacency(3, 4, /*periodic=*/false);
  // Sum of degrees == 2 * |E|. For a 3x4 open grid, edges = 2*3*4 - 3 - 4 = 17.
  std::size_t total_deg = 0;
  for (const auto &row : adj)
    total_deg += row.size();
  EXPECT_EQ(total_deg, 2u * 17u);
 
  // Corner has degree 2.
  EXPECT_EQ(adj[0].size(), 2u);
  // Centre cell (1, 1) has degree 4.
  EXPECT_EQ(adj[1 * 4 + 1].size(), 4u);
}
 
TEST(CAGraphBuilders, ToroidalGridAlwaysHasFourNeighbours)
{
  const auto adj = make_grid_graph_adjacency(5, 5, /*periodic=*/true);
  for (const auto &row : adj)
    EXPECT_EQ(row.size(), 4u);
}
 
// ---------------------------------------------------------------------------
// Graph_Lattice basics.
// ---------------------------------------------------------------------------
 
TEST(CAGraphLattice, ConstructorRejectsOutOfRangeNeighbour)
{
  Array<Array<std::size_t>> bad = {{1}, {99}};  // 99 is invalid
  EXPECT_THROW({ Graph_Lattice<int> g(bad); (void)g.size(); },
               std::out_of_range);
}
 
TEST(CAGraphLattice, AtAndSetRoundTrip)
{
  Graph_Lattice<int> lat(make_path_graph_adjacency(6), 0);
  EXPECT_EQ(lat.size(), 6u);
  EXPECT_EQ(lat.degree(0), 1u);
  EXPECT_EQ(lat.degree(3), 2u);
  EXPECT_EQ(lat.max_degree(), 2u);
  for (std::size_t n = 0; n < lat.size(); ++n)
    lat.set_node(n, static_cast<int>(n + 1));
  for (std::size_t n = 0; n < lat.size(); ++n)
    EXPECT_EQ(lat.at_node(n), static_cast<int>(n + 1));
}
 
TEST(CAGraphLattice, AtSafeOnOutOfRangeReturnsDefault)
{
  Graph_Lattice<int> lat(make_path_graph_adjacency(3), 7);
  using coord_t = typename Graph_Lattice<int>::coord_type;
  EXPECT_EQ(lat.at_safe(coord_t{-1}), 0);
  EXPECT_EQ(lat.at_safe(coord_t{99}), 0);
  EXPECT_EQ(lat.at_safe(coord_t{1}), 7);
  EXPECT_THROW((void)lat.at(coord_t{99}), std::out_of_range);
}
 
TEST(CAGraphLattice, FillResetsEveryCell)
{
  Graph_Lattice<int> lat(make_path_graph_adjacency(4), 0);
  lat.set_node(0, 1);
  lat.set_node(2, 1);
  lat.fill(7);
  for (std::size_t n = 0; n < lat.size(); ++n)
    EXPECT_EQ(lat.at_node(n), 7);
}
 
// ---------------------------------------------------------------------------
// Graph_Synchronous_Engine.
// ---------------------------------------------------------------------------
 
namespace {
 
// Majority rule: cell becomes 1 iff strict majority of neighbours are 1.
// Ties keep the current state.
struct Majority_Functor
{
  [[nodiscard]] int operator()(int current, Neighbor_View<int> neigh) const noexcept
  {
    std::size_t alive = 0;
    for (int v : neigh)
      if (v != 0)
        ++alive;
    const std::size_t deg = neigh.size();
    if (2 * alive > deg)
      return 1;
    if (2 * alive < deg)
      return 0;
    return current;
  }
};
 
// Voter rule: each cell adopts the state of a uniformly random
// neighbour. Determinism is achieved by hashing a monotonically
// increasing per-call counter into the seed: every cell update
// (across every step of the simulation) gets a unique sub-seed.
class Voter_Rule_Driver
{
  std::uint64_t seed_;
  mutable std::uint64_t calls_ = 0;
 
public:
  explicit Voter_Rule_Driver(std::uint64_t seed) noexcept : seed_(seed) {}
 
  [[nodiscard]] int operator()(int current, Neighbor_View<int> neigh) const noexcept
  {
    if (neigh.empty())
      return current;
    std::uint64_t key = seed_;
    key = (key * 1099511628211ull) ^ (calls_ + 1);
    ++calls_;
    std::mt19937_64 rng(key);
    std::uniform_int_distribution<std::size_t> pick(0, neigh.size() - 1);
    return neigh[pick(rng)];
  }
};
 
}  // namespace
 
TEST(CAGraphEngine, MajorityRulePreservesAllZero)
{
  Graph_Lattice<int> seed(make_grid_graph_adjacency(4, 4, /*periodic=*/true), 0);
  using Rule = Majority_Functor;
  Graph_Synchronous_Engine<Graph_Lattice<int>, Rule> eng(seed, Rule{});
  eng.run(10);
  for (std::size_t n = 0; n < eng.frame().size(); ++n)
    EXPECT_EQ(eng.frame().at_node(n), 0);
}
 
TEST(CAGraphEngine, MajorityRulePreservesAllOnes)
{
  Graph_Lattice<int> seed(make_grid_graph_adjacency(3, 3, /*periodic=*/true), 1);
  using Rule = Majority_Functor;
  Graph_Synchronous_Engine<Graph_Lattice<int>, Rule> eng(seed, Rule{});
  eng.run(10);
  for (std::size_t n = 0; n < eng.frame().size(); ++n)
    EXPECT_EQ(eng.frame().at_node(n), 1);
}
 
TEST(CAGraphEngine, MajorityFlipsIsolatedSeedBackToZero)
{
  // Single 1 in a sea of zeros on a ring graph: under strict
  // majority everyone goes back to 0 in one step (the one alive
  // node has neighbours mostly 0 too).
  Graph_Lattice<int> seed(make_path_graph_adjacency(7, /*cycle=*/true), 0);
  seed.set_node(3, 1);
  Graph_Synchronous_Engine<Graph_Lattice<int>, Majority_Functor> eng(
    seed, Majority_Functor{});
  eng.run(1);
  for (std::size_t n = 0; n < eng.frame().size(); ++n)
    EXPECT_EQ(eng.frame().at_node(n), 0);
}
 
TEST(CAGraphEngine, VoterModelConvergesOnConnectedNonBipartiteGraph)
{
  // A "bowtie": three triangles glued at a common hub. The graph
  // is connected and non-bipartite (every triangle is a 3-cycle),
  // so the synchronous voter model cannot get trapped in a parity
  // oscillation. With a fixed seed the chain reaches consensus
  // within a few thousand steps.
  Array<Array<std::size_t>> adj(7, Array<std::size_t>{});
  auto edge = [&](std::size_t a, std::size_t b)
  {
    adj[a].append(b);
    adj[b].append(a);
  };
  edge(0, 1); edge(0, 2); edge(1, 2);
  edge(0, 3); edge(0, 4); edge(3, 4);
  edge(0, 5); edge(0, 6); edge(5, 6);
 
  Graph_Lattice<int> seed(adj, 0);
  seed.set_node(1, 1); seed.set_node(2, 1);
  seed.set_node(5, 1); seed.set_node(6, 1);
 
  Voter_Rule_Driver driver(/*seed=*/2026u);
  Graph_Synchronous_Engine<Graph_Lattice<int>, Voter_Rule_Driver> eng(
    seed, driver);
  eng.run(10000);
 
  const int v0 = eng.frame().at_node(0);
  for (std::size_t n = 1; n < eng.frame().size(); ++n)
    EXPECT_EQ(eng.frame().at_node(n), v0)
      << "voter model did not reach consensus on the bowtie graph";
}
 
TEST(CAGraphEngine, HookFiringSemantics)
{
  Graph_Lattice<int> seed(make_path_graph_adjacency(5, /*cycle=*/true), 0);
  seed.set_node(0, 1);
  Graph_Synchronous_Engine<Graph_Lattice<int>, Majority_Functor> eng(
    seed, Majority_Functor{});
 
  std::size_t pre = 0;
  std::size_t post = 0;
  std::size_t last_pre = 0;
  std::size_t last_post = 0;
  eng.on_pre_step([&](std::size_t s, const Graph_Lattice<int> &) {
    ++pre;
    last_pre = s;
  });
  eng.on_post_step([&](std::size_t s, const Graph_Lattice<int> &) {
    ++post;
    last_post = s;
  });
 
  eng.run(4);
  EXPECT_EQ(pre, 4u);
  EXPECT_EQ(post, 4u);
  EXPECT_EQ(last_pre, 3u);
  EXPECT_EQ(last_post, 4u);
  EXPECT_EQ(eng.steps_run(), 4u);
}
 
TEST(CAGraphEngine, EquivalenceWithSequentialEngineOnGrid)
{
  // A graph CA over a 4x4 toroidal grid graph + Outer_Totalistic_Rule
  // with the GoL functor coincides with the rectangular-Lattice
  // engine using a Von_Neumann<2,1> neighbourhood (4 neighbours,
  // toroidal). This validates the graph engine against the existing
  // rectangular pipeline.
  using NodeState = int;
  using GLat = Graph_Lattice<NodeState>;
  using Rule = Outer_Totalistic_Rule<Game_Of_Life_Functor>;
 
  // Seed the same pattern in both engines.
  std::vector<int> initial(16, 0);
  initial[5] = 1;
  initial[6] = 1;
  initial[9] = 1;
  initial[10] = 1;  // a still-life block
 
  GLat seed(make_grid_graph_adjacency(4, 4, /*periodic=*/true), 0);
  for (std::size_t n = 0; n < seed.size(); ++n)
    seed.set_node(n, initial[n]);
 
  Graph_Synchronous_Engine<GLat, Rule> eng(seed, Rule{Game_Of_Life_Functor{}});
  eng.run(5);
 
  // Block is a still life: stable under any "B/S over 4 neighbours" rule
  // that contains S2 in the survival set... GoL is B3/S23 so S2 counts.
  // We just assert the four block cells stayed 1 and the rest stayed 0.
  for (std::size_t n = 0; n < eng.frame().size(); ++n)
    EXPECT_EQ(eng.frame().at_node(n), initial[n])
      << "block at node " << n << " was not still under graph engine";
}