Graph lattice: one cell per node + precomputed adjacency. More...

#include <tpl_ca_graph_automaton.H>

Collaboration diagram for Aleph::CA::Graph_Lattice< T >:

Public Types
using	state_type = T

using	coord_type = Coord_Vec< 1 >

using	extents_type = std::array< ca_size_t, 1 >

Public Member Functions
	Graph_Lattice ()=default
	Construct an empty graph lattice (0 nodes).

	Graph_Lattice (const Array< Array< std::size_t > > &adjacency, const T &init=T{})
	Build a graph lattice from an adjacency list.

ca_size_t	size () const noexcept

ca_size_t	size (std::size_t d) const

extents_type	extents () const noexcept

T	at (const coord_type &c) const

void	set (const coord_type &c, const T &v)

T	at_safe (const coord_type &c) const
	Boundary-aware read.

T	at_node (std::size_t n) const
	Direct read at node id `n`.

void	set_node (std::size_t n, const T &v)
	Direct write at node id `n`.

std::size_t	degree (std::size_t n) const
	Degree of node `n`.

const Array< std::size_t > &	neighbours (std::size_t n) const
	Neighbour ids of node `n` in the order supplied at construction.

std::size_t	max_degree () const noexcept
	Maximum degree across the graph (computed in O(N)).

void	fill (const T &value)
	Set every cell to `value`.

void	swap (Graph_Lattice &other) noexcept
	O(1) swap with another graph lattice of the same type.

Static Public Member Functions
static constexpr std::size_t	dimension () noexcept

Static Public Attributes
static constexpr std::size_t	rank = 1
	Rank-1 lattice: node id is the only axis.

Private Attributes
ca_size_t	num_nodes_ = 0

Array< T >	cells_ {}

Array< Array< std::size_t > >	adjacency_ {}

Detailed Description

template<typename T>
class Aleph::CA::Graph_Lattice< T >

Graph lattice: one cell per node + precomputed adjacency.

Satisfies LatticeLike as a rank-1 lattice whose coord_type is Coord_Vec<1> and whose extents_type is std::array<ca_size_t, 1>. Component 0 is interpreted as the node id.

Adjacency is stored as Array<Array<size_t>>: row n lists the ids of the neighbours of node n. The list is what the engine hands to the rule, in the order supplied by the constructor. Self-loops are accepted but have no special semantics: they show up as the node's own id in its own adjacency list.

Template Parameters

T	cell state type, must satisfy `CellState`.

Definition at line 107 of file tpl_ca_graph_automaton.H.

Member Typedef Documentation

◆ coord_type

template<typename T >

using Aleph::CA::Graph_Lattice< T >::coord_type = Coord_Vec<1>

Definition at line 113 of file tpl_ca_graph_automaton.H.

◆ extents_type

template<typename T >

using Aleph::CA::Graph_Lattice< T >::extents_type = std::array<ca_size_t, 1>

Definition at line 114 of file tpl_ca_graph_automaton.H.

◆ state_type

template<typename T >

using Aleph::CA::Graph_Lattice< T >::state_type = T

Definition at line 112 of file tpl_ca_graph_automaton.H.

Constructor & Destructor Documentation

◆ Graph_Lattice() [1/2]

template<typename T >

Aleph::CA::Graph_Lattice< T >::Graph_Lattice ( )

default

Construct an empty graph lattice (0 nodes).

◆ Graph_Lattice() [2/2]

template<typename T >

Aleph::CA::Graph_Lattice< T >::Graph_Lattice	(	const Array< Array< std::size_t > > &	adjacency,
		const T &	init = `T{}`
	)

inlineexplicit

Build a graph lattice from an adjacency list.

Parameters

[in]	adjacency	one row per node listing neighbour ids.
[in]	init	initial value for every cell (default `T{}`).

Exceptions

std::out_of_range	if a neighbour id is `>= adjacency.size()`.
std::bad_alloc	on allocation failure.

Complexity: O(N + E), where N is the node count and E the number of edges.

Definition at line 139 of file tpl_ca_graph_automaton.H.

Member Function Documentation

◆ at()

template<typename T >

T Aleph::CA::Graph_Lattice< T >::at ( const coord_type & c ) const

inline

Definition at line 180 of file tpl_ca_graph_automaton.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Graph_Lattice< T >::cells_, and Aleph::CA::Graph_Lattice< T >::num_nodes_.

◆ at_node()

template<typename T >

T Aleph::CA::Graph_Lattice< T >::at_node ( std::size_t n ) const

inline

Direct read at node id n.

Definition at line 209 of file tpl_ca_graph_automaton.H.

References ah_out_of_range_error_if, Aleph::CA::Graph_Lattice< T >::cells_, and Aleph::CA::Graph_Lattice< T >::num_nodes_.

◆ at_safe()

template<typename T >

T Aleph::CA::Graph_Lattice< T >::at_safe ( const coord_type & c ) const

inline

Boundary-aware read.

For graphs the only meaningful interpretation is "out-of-range cells return the default value", which mirrors OpenBoundary on a rectangular lattice.

Definition at line 197 of file tpl_ca_graph_automaton.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Graph_Lattice< T >::cells_, and Aleph::CA::Graph_Lattice< T >::num_nodes_.