tpl_ca_graph_automaton.H

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.
*/
 
#ifndef TPL_CA_GRAPH_AUTOMATON_H
#define TPL_CA_GRAPH_AUTOMATON_H
 
#include <array>
#include <cstddef>
#include <functional>
#include <span>
#include <type_traits>
#include <utility>
 
#include <ah-errors.H>
#include <tpl_array.H>
 
#include <ca-traits.H>
#include <tpl_ca_concepts.H>
 
namespace Aleph {
namespace CA {
 
template <typename T>
class Graph_Lattice
{
  static_assert(CellState<T>, "Graph_Lattice requires a CellState type");
 
public:
  using state_type = T;
  using coord_type = Coord_Vec<1>;
  using extents_type = std::array<ca_size_t, 1>;
 
  static constexpr std::size_t rank = 1;
 
private:
  ca_size_t num_nodes_ = 0;
  Array<T> cells_{};
  Array<Array<std::size_t>> adjacency_{};
 
public:
  Graph_Lattice() = default;
 
  explicit Graph_Lattice(const Array<Array<std::size_t>> &adjacency,
                         const T &init = T{})
    : num_nodes_(static_cast<ca_size_t>(adjacency.size()))
    , cells_(num_nodes_, init)
    , adjacency_(num_nodes_, Array<std::size_t>{})
  {
    for (ca_size_t i = 0; i < num_nodes_; ++i)
      {
        const auto &row = adjacency[i];
        Array<std::size_t> r(row.size(), std::size_t{0});
        for (std::size_t k = 0; k < row.size(); ++k)
          {
            ah_out_of_range_error_if(row[k] >= num_nodes_)
              << "Graph_Lattice: neighbour id " << row[k] << " of node " << i
              << " is out of range [0, " << num_nodes_ << ")";
            r[k] = row[k];
          }
        adjacency_[i] = std::move(r);
      }
  }
 
  // -------------------------------------------------------------
  // LatticeLike surface.
  // -------------------------------------------------------------
 
  [[nodiscard]] static constexpr std::size_t dimension() noexcept { return rank; }
 
  [[nodiscard]] ca_size_t size() const noexcept { return num_nodes_; }
 
  [[nodiscard]] ca_size_t size(std::size_t d) const
  {
    ah_out_of_range_error_if(d >= rank)
      << "Graph_Lattice::size: axis " << d << " out of range";
    return num_nodes_;
  }
 
  [[nodiscard]] extents_type extents() const noexcept
  {
    return extents_type{num_nodes_};
  }
 
  [[nodiscard]] T at(const coord_type &c) const
  {
    ah_out_of_range_error_if(c[0] < 0 or static_cast<ca_size_t>(c[0]) >= num_nodes_)
      << "Graph_Lattice::at: id " << c[0] << " out of [0, " << num_nodes_ << ")";
    return cells_[static_cast<ca_size_t>(c[0])];
  }
 
  void set(const coord_type &c, const T &v)
  {
    ah_out_of_range_error_if(c[0] < 0 or static_cast<ca_size_t>(c[0]) >= num_nodes_)
      << "Graph_Lattice::set: id " << c[0] << " out of [0, " << num_nodes_ << ")";
    cells_[static_cast<ca_size_t>(c[0])] = v;
  }
 
  [[nodiscard]] T at_safe(const coord_type &c) const
  {
    if (c[0] < 0 or static_cast<ca_size_t>(c[0]) >= num_nodes_)
      return T{};
    return cells_[static_cast<ca_size_t>(c[0])];
  }
 
  // -------------------------------------------------------------
  // Graph-specific accessors.
  // -------------------------------------------------------------
 
  [[nodiscard]] T at_node(std::size_t n) const
  {
    ah_out_of_range_error_if(n >= num_nodes_)
      << "Graph_Lattice::at_node: id " << n << " out of [0, " << num_nodes_ << ")";
    return cells_[n];
  }
 
  void set_node(std::size_t n, const T &v)
  {
    ah_out_of_range_error_if(n >= num_nodes_)
      << "Graph_Lattice::set_node: id " << n << " out of [0, " << num_nodes_ << ")";
    cells_[n] = v;
  }
 
  [[nodiscard]] std::size_t degree(std::size_t n) const
  {
    ah_out_of_range_error_if(n >= num_nodes_)
      << "Graph_Lattice::degree: id " << n << " out of [0, " << num_nodes_ << ")";
    return adjacency_[n].size();
  }
 
  [[nodiscard]] const Array<std::size_t> &neighbours(std::size_t n) const
  {
    ah_out_of_range_error_if(n >= num_nodes_)
      << "Graph_Lattice::neighbours: id " << n << " out of [0, " << num_nodes_ << ")";
    return adjacency_[n];
  }
 
  [[nodiscard]] std::size_t max_degree() const noexcept
  {
    std::size_t m = 0;
    for (ca_size_t i = 0; i < num_nodes_; ++i)
      if (adjacency_[i].size() > m)
        m = adjacency_[i].size();
    return m;
  }
 
  void fill(const T &value)
  {
    for (ca_size_t i = 0; i < num_nodes_; ++i)
      cells_[i] = value;
  }
 
  void swap(Graph_Lattice &other) noexcept
  {
    using std::swap;
    swap(num_nodes_, other.num_nodes_);
    cells_.swap(other.cells_);
    adjacency_.swap(other.adjacency_);
  }
};
 
template <typename T>
inline void swap(Graph_Lattice<T> &a, Graph_Lattice<T> &b) noexcept
{
  a.swap(b);
}
 
// -----------------------------------------------------------------------
// Synchronous engine for graph CAs.
// -----------------------------------------------------------------------
 
template <typename R, typename T>
concept GraphRuleLike = CellState<T>
and (requires(const R &r, const T &s, Neighbor_View<T> v) {
       { r(s, v) } -> std::convertible_to<T>;
     }
     or requires(const R &r, const T &s, Neighbor_View<T> v,
                 const Cell_Context<1> &ctx) {
          { r(s, v, ctx) } -> std::convertible_to<T>;
        });
 
template <typename Lattice, typename Rule>
class Graph_Synchronous_Engine
{
public:
  using lattice_type = Lattice;
  using state_type = typename Lattice::state_type;
 
private:
  static_assert(GraphRuleLike<Rule, state_type>,
                "Graph_Synchronous_Engine requires a GraphRuleLike rule");
 
  Lattice cur_buf_;
  Lattice nxt_buf_;
  Rule rule_;
  Array<state_type> nbuf_;  
  std::function<void(std::size_t, const Lattice &)> pre_hook_;
  std::function<void(std::size_t, const Lattice &)> post_hook_;
  std::size_t step_count_ = 0;
 
public:
  Graph_Synchronous_Engine(Lattice initial, Rule r)
    : cur_buf_(std::move(initial)), nxt_buf_(cur_buf_), rule_(std::move(r))
  {
    nbuf_.reserve(cur_buf_.max_degree());
  }
 
  [[nodiscard]] const Lattice &frame() const noexcept { return cur_buf_; }
 
  [[nodiscard]] std::size_t steps_run() const noexcept { return step_count_; }
 
  template <typename F>
  void on_pre_step(F &&f)
  {
    pre_hook_ = std::forward<F>(f);
  }
 
  template <typename F>
  void on_post_step(F &&f)
  {
    post_hook_ = std::forward<F>(f);
  }
 
  void step()
  {
    if (pre_hook_)
      pre_hook_(step_count_, cur_buf_);
 
    const ca_size_t n = cur_buf_.size();
    for (ca_size_t node = 0; node < n; ++node)
      {
        const auto &neigh_ids = cur_buf_.neighbours(node);
        const std::size_t deg = neigh_ids.size();
        // Aleph::Array has no `resize(n)`; grow by appending value-
        // initialised cells until capacity is reached. Size only
        // grows monotonically (max_degree is bounded), so this is
        // amortised O(1) per node.
        while (nbuf_.size() < deg)
          nbuf_.append(state_type{});
 
        for (std::size_t k = 0; k < deg; ++k)
          nbuf_[k] = cur_buf_.at_node(neigh_ids[k]);
 
        const state_type *const view_ptr = deg > 0 ? &nbuf_[0] : nullptr;
        const Neighbor_View<state_type> view(view_ptr, deg);
        const Cell_Context<1> ctx{step_count_, {static_cast<ca_index_t>(node)}};
        nxt_buf_.set_node(node,
                          apply_rule(rule_, cur_buf_.at_node(node), view, ctx));
      }
 
    cur_buf_.swap(nxt_buf_);
    ++step_count_;
 
    if (post_hook_)
      post_hook_(step_count_, cur_buf_);
  }
 
  void run(const std::size_t steps)
  {
    for (std::size_t i = 0; i < steps; ++i)
      step();
  }
};
 
// -----------------------------------------------------------------------
// Graph builders for common test patterns.
// -----------------------------------------------------------------------
 
[[nodiscard]] inline Array<Array<std::size_t>> make_grid_graph_adjacency(
  std::size_t rows, std::size_t cols, bool periodic = false)
{
  Array<Array<std::size_t>> adj(rows * cols, Array<std::size_t>{});
  auto idx = [cols](std::size_t i, std::size_t j) { return i * cols + j; };
  for (std::size_t i = 0; i < rows; ++i)
    for (std::size_t j = 0; j < cols; ++j)
      {
        auto &row = adj[idx(i, j)];
        // North
        if (i > 0)
          row.append(idx(i - 1, j));
        else if (periodic)
          row.append(idx(rows - 1, j));
        // South
        if (i + 1 < rows)
          row.append(idx(i + 1, j));
        else if (periodic)
          row.append(idx(0, j));
        // West
        if (j > 0)
          row.append(idx(i, j - 1));
        else if (periodic)
          row.append(idx(i, cols - 1));
        // East
        if (j + 1 < cols)
          row.append(idx(i, j + 1));
        else if (periodic)
          row.append(idx(i, 0));
      }
  return adj;
}
 
[[nodiscard]] inline Array<Array<std::size_t>> make_path_graph_adjacency(
  std::size_t n, bool cycle = false)
{
  Array<Array<std::size_t>> adj(n, Array<std::size_t>{});
  for (std::size_t i = 0; i < n; ++i)
    {
      if (i > 0)
        adj[i].append(i - 1);
      else if (cycle and n > 1)
        adj[i].append(n - 1);
      if (i + 1 < n)
        adj[i].append(i + 1);
      else if (cycle and n > 1)
        adj[i].append(0);
    }
  return adj;
}
 
}  // namespace CA
}  // namespace Aleph
 
#endif  // TPL_CA_GRAPH_AUTOMATON_H