tpl_ca_graph_automaton.H File Reference

CA whose underlying topology is an arbitrary undirected graph. More...

#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>

Include dependency graph for tpl_ca_graph_automaton.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::CA::Graph_Lattice< T >
	Graph lattice: one cell per node + precomputed adjacency. More...
class	Aleph::CA::Graph_Synchronous_Engine< Lattice, Rule >
	Synchronous double-buffered engine for graph CAs. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::CA

Concepts
concept	Aleph::CA::GraphRuleLike
	Concept satisfied by graph rules.

Functions
template<typename T >
void	Aleph::CA::swap (Graph_Lattice< T > &a, Graph_Lattice< T > &b) noexcept
	Free-function swap so the lattice plays nicely with std::swap.
Array< Array< std::size_t > >	Aleph::CA::make_grid_graph_adjacency (std::size_t rows, std::size_t cols, bool periodic=false)
	Build the adjacency of a 2D 4-neighbour grid graph.
Array< Array< std::size_t > >	Aleph::CA::make_path_graph_adjacency (std::size_t n, bool cycle=false)
	Build the adjacency of a path graph with n nodes.

Detailed Description

CA whose underlying topology is an arbitrary undirected graph.

Phase 6 generalises the rectangular lattice to network CAs:

• the cells are the nodes of an undirected graph,
• the neighbourhood of each cell is the set of nodes adjacent via an edge,
• per-step adjacency is precomputed once at construction time, so the inner loop is a tight pointer-walk with no graph traversal overhead.

Two pieces:

• Graph_Lattice<NodeState> — owns one state_type per node and a precomputed adjacency list (Array<Array<size_t>>). Satisfies LatticeLike with rank 1 so it slots into the same Synchronous_Engine machinery for halo / hooks / iteration. Strict at / set use a single-component coordinate equal to the node id; at_safe returns state_type{} for out-of-range ids.
• Graph_Synchronous_Engine<Lattice, Rule> — analogue of Synchronous_Engine specialised to graph CAs. Iterates the nodes in id order and gathers each node's neighbour states into a small heap-allocated buffer that grows lazily up to the largest degree seen. Buffers are owned by the engine so step() is allocation-free after the first call.

The header does not depend on tpl_graph.H: the user supplies the adjacency directly, which keeps the test surface small and lets callers drive the engine from any graph backend (Aleph List_Graph, random_graph.H, grid.H, or hand-built).

Free helpers make_grid_graph_adjacency and make_path_graph_adjacency are provided so common test cases fit in two lines of user code.

Author

Leandro Rabindranath Leon

Definition in file tpl_ca_graph_automaton.H.