Auxiliary adjacency matrix with custom entry type. More...

#include <tpl_matgraph.H>

Collaboration diagram for Aleph::Ady_Mat< GT, __Entry_Type, SA >:

Public Types
using	Graph_Type = GT
	Graph type.

using	Entry_Type = __Entry_Type
	Entry type stored in matrix.

using	Node_Type = typename GT::Node_Type
	Node attribute type from graph.

using	Arc_Type = typename GT::Arc_Type
	Arc attribute type from graph.

using	Node = typename GT::Node
	Node type from graph.

using	Arc = typename GT::Arc
	Arc type from graph.

Public Member Functions
Node *	operator() (long i)
	Get node pointer by index.

Node *	operator() (long i) const
	Get node pointer by index (const).

long	operator() (Node *node) const
	Get index of node.

Entry_Type &	operator() (long i, long j)
	Access entry by indices (modifiable).

const Entry_Type &	operator() (long i, long j) const
	Access entry by indices (const).

Entry_Type &	operator() (Node src, Node tgt)
	Access entry by node pointers (modifiable).

const Entry_Type &	operator() (Node src, Node tgt) const
	Access entry by node pointers (const).

GT &	get_list_graph () noexcept
	Get reference to underlying graph.

const GT &	get_list_graph () const noexcept
	Get const reference to underlying graph.

const Entry_Type &	null_value () const noexcept
	Get the null value.

size_t	get_num_nodes () const noexcept
	Get number of nodes (matrix dimension)

	Ady_Mat (GT &g)
	Construct from graph without null value.

	Ady_Mat (GT &g, const Entry_Type &null)
	Construct from graph with null value.

void	set_null_value (const Entry_Type &null) noexcept
	Set the null value.

	Ady_Mat (Ady_Mat &other)
	Copy constructor.

Ady_Mat &	operator= (Ady_Mat &other)
	Copy assignment.

template<class Operation >
void	operate_all_arcs_list_graph ()
	Apply operation to all arcs from the graph.

template<class Operation >
void	operate_all_arcs_list_graph (void *ptr)
	Apply operation to all arcs with user data.

template<class Operation >
void	operate_all_arcs_matrix ()
	Apply operation to all matrix entries.

template<class Operation >
void	operate_all_arcs_matrix (void *ptr)
	Apply operation to all matrix entries with user data.

Private Member Functions
void	test_same_graph (const Ady_Mat &other) const

void	copy_nodes (GT &g)

Ady_Mat &	copy (Ady_Mat &other)

Private Attributes
GT *	lgraph = nullptr

DynArray< Node * >	nodes

DynArray< Entry_Type >	mat

size_t	num_nodes = 0

Entry_Type	Null_Value {}

Detailed Description

template<class GT, typename __Entry_Type, class SA = Dft_Show_Arc<GT>>
class Aleph::Ady_Mat< GT, __Entry_Type, SA >

Auxiliary adjacency matrix with custom entry type.

Ady_Mat provides an adjacency matrix with a user-defined entry type, useful for algorithms that need temporary storage or computations different from the graph's native attributes.

Key Features

Custom entry type (not tied to graph arc type)
Associated with an adjacency list graph
Sparse storage (memory proportional to non-null entries)
Operations to iterate over arcs

Common Uses

Floyd-Warshall shortest path algorithm
Transitive closure computation
Any algorithm needing matrix operations on graphs

Usage Example

List_Digraph<std::string, int> g;
// ... build graph ...
 
// Matrix storing distances (int) with infinity as null
Ady_Mat<decltype(g), int> dist(g, INT_MAX);
 
// Initialize from arcs
dist.operate_all_arcs_list_graph<Init_Dist>();
 
// Access entries
dist(0, 1) = 5;
int d = dist(0, 1);

Template Parameters

GT	Graph type
__Entry_Type	Type of matrix entries
SA	Arc filter (default: show all arcs)

See also: Floyd_Warshall.H Usage in Floyd-Warshall algorithm

Definition at line 692 of file tpl_matgraph.H.

Member Typedef Documentation

◆ Arc

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Arc = typename GT::Arc

Arc type from graph.

Definition at line 711 of file tpl_matgraph.H.

◆ Arc_Type

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Arc_Type = typename GT::Arc_Type

Arc attribute type from graph.

Definition at line 705 of file tpl_matgraph.H.

◆ Entry_Type

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Entry_Type = __Entry_Type

Entry type stored in matrix.

Definition at line 699 of file tpl_matgraph.H.

◆ Graph_Type

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Graph_Type = GT

Graph type.

Definition at line 696 of file tpl_matgraph.H.

◆ Node

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Node = typename GT::Node

Node type from graph.

Definition at line 708 of file tpl_matgraph.H.

◆ Node_Type

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

using Aleph::Ady_Mat< GT, __Entry_Type, SA >::Node_Type = typename GT::Node_Type

Node attribute type from graph.

Definition at line 702 of file tpl_matgraph.H.

Constructor & Destructor Documentation

◆ Ady_Mat() [1/3]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat ( GT & g )

inlineexplicit

Construct from graph without null value.

Creates matrix with uninitialized entries. Use set_null_value() to define the null value.

Parameters

g	Source graph

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 856 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes().

◆ Ady_Mat() [2/3]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat	(	GT &	g,
		const Entry_Type &	null
	)

inline

Construct from graph with null value.

Parameters

g	Source graph
null	Value indicating no entry

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 868 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes().

◆ Ady_Mat() [3/3]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat ( Ady_Mat< GT, __Entry_Type, SA > & other )

inline

Copy constructor.

Definition at line 878 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy(), and Aleph::maps().

Member Function Documentation

◆ copy()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Ady_Mat & Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy ( Ady_Mat< GT, __Entry_Type, SA > & other )

inlineprivate

Definition at line 739 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes(), Aleph::maps(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::Null_Value, and Aleph::Ady_Mat< GT, __Entry_Type, SA >::test_same_graph().

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator=().

◆ copy_nodes()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes ( GT & g )

inlineprivate

Definition at line 726 of file tpl_matgraph.H.

References Aleph::DynArray< T >::cut(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::lgraph, Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes, Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes, and Aleph::quicksort().

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy().

◆ get_list_graph() [1/2]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

const GT & Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_list_graph ( ) const

inlinenoexcept

Get const reference to underlying graph.

Definition at line 839 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::lgraph.

◆ get_list_graph() [2/2]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

GT & Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_list_graph ( )

inlinenoexcept

Get reference to underlying graph.

Definition at line 836 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::lgraph.

Referenced by Aleph::Initialize_Dist< AM >::operator()(), and TEST_F().

◆ get_num_nodes()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_num_nodes ( ) const

inlinenoexcept

Get number of nodes (matrix dimension)

Definition at line 845 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes.

Referenced by FloydSimpleGraphTest::get_index(), TEST_F(), and TEST_F().

◆ null_value()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

const Entry_Type & Aleph::Ady_Mat< GT, __Entry_Type, SA >::null_value ( ) const

inlinenoexcept

Get the null value.

Definition at line 842 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::Null_Value.

Referenced by TEST_F(), and TEST_F().

◆ operate_all_arcs_list_graph() [1/2]

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph ( )

Apply operation to all arcs from the graph.

Iterates over all arcs in the underlying graph and invokes:

Operation()(mat, arc, i, j, entry)

Aleph::Ady_Mat::mat

DynArray< Entry_Type > mat

Definition tpl_matgraph.H:716

Where:

mat: reference to this matrix
arc: pointer to arc in graph
i, j: indices in matrix
entry: reference to matrix entry

Template Parameters

Operation Functor type with above signature

Definition at line 945 of file tpl_matgraph.H.

References Aleph::matgraph_detail::index_array(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), nodes, num_nodes, and Aleph::DynArray< T >::touch().

Referenced by TEST_F().

◆ operate_all_arcs_list_graph() [2/2]

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph ( void * ptr )

Apply operation to all arcs with user data.

Same as operate_all_arcs_list_graph() but passes additional pointer:

Operation()(mat, arc, i, j, entry, ptr)

Template Parameters

Operation Functor type

Parameters

ptr	User data pointer

Definition at line 968 of file tpl_matgraph.H.

References GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::matgraph_detail::index_array(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), nodes, num_nodes, and Aleph::DynArray< T >::touch().

◆ operate_all_arcs_matrix() [1/2]

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_matrix ( )

Apply operation to all matrix entries.

Iterates over all n×n entries and invokes:

Operation()(mat, src, tgt, i, j, entry)

Warning: This forces all entries to be allocated.

Template Parameters

Operation Functor type

Definition at line 990 of file tpl_matgraph.H.

References Aleph::matgraph_detail::index_array(), Aleph::maps(), nodes, num_nodes, and Aleph::DynArray< T >::touch().

Referenced by TEST_F().

◆ operate_all_arcs_matrix() [2/2]

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_matrix ( void * ptr )

Apply operation to all matrix entries with user data.

Template Parameters

Operation Functor type

Parameters

ptr	User data pointer

Definition at line 1008 of file tpl_matgraph.H.

References Aleph::matgraph_detail::index_array(), Aleph::maps(), nodes, num_nodes, and Aleph::DynArray< T >::touch().

◆ operator()() [1/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator() ( long i )

inline

Get node pointer by index.

Parameters

i	Node index

Returns: Pointer to node in underlying graph

Exceptions

std::out_of_range if index out of bounds

Definition at line 757 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes.

◆ operator()() [2/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator() ( long i ) const

inline

Get node pointer by index (const).

Parameters

i	Node index

Returns: Pointer to node in underlying graph

Exceptions

std::out_of_range if index out of bounds

Definition at line 768 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes.

◆ operator()() [3/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Entry_Type & Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	long	i,
		long	j
	)

inline

Access entry by indices (modifiable).

Parameters

i	Row index
j	Column index

Returns: Reference to entry (creates if needed)

Exceptions

std::out_of_range if indices out of bounds

Definition at line 791 of file tpl_matgraph.H.

References Aleph::matgraph_detail::checked_index_array(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::mat, Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes, and Aleph::DynArray< T >::touch().

◆ operator()() [4/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

const Entry_Type & Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	long	i,
		long	j
	)		const

inline

Access entry by indices (const).

Parameters

i	Row index
j	Column index

Returns: Entry value, or null_value() if not set

Exceptions

std::out_of_range if indices out of bounds

Definition at line 803 of file tpl_matgraph.H.

References Aleph::DynArray< T >::access(), Aleph::matgraph_detail::checked_index_array(), Aleph::DynArray< T >::exist(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::mat, Aleph::Ady_Mat< GT, __Entry_Type, SA >::Null_Value, and Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes.

◆ operator()() [5/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

long Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator() ( Node * node ) const

inline

Get index of node.

Parameters

node	Node pointer

Returns: Index in matrix

Note: O(log n) binary search

Definition at line 779 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes, and Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes.

◆ operator()() [6/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Entry_Type & Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	Node *	src,
		Node *	tgt
	)

inline

Access entry by node pointers (modifiable).

Parameters

src	Source node
tgt	Target node

Returns: Reference to entry

Note: O(log n) for each node lookup

Definition at line 816 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes, and Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes.

◆ operator()() [7/7]

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

const Entry_Type & Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	Node *	src,
		Node *	tgt
	)		const

inline

Access entry by node pointers (const).

Parameters

src	Source node
tgt	Target node

Returns: Entry value, or null_value() if not set

Note: O(log n) for each node lookup

Definition at line 829 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes, and Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes.

◆ operator=()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Ady_Mat & Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator= ( Ady_Mat< GT, __Entry_Type, SA > & other )

inline

Copy assignment.

Definition at line 881 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy(), and Aleph::maps().

◆ set_null_value()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::set_null_value ( const Entry_Type & null )

inlinenoexcept

Set the null value.

Definition at line 875 of file tpl_matgraph.H.

References Aleph::Ady_Mat< GT, __Entry_Type, SA >::Null_Value.

Referenced by TEST_F().

◆ test_same_graph()

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::test_same_graph ( const Ady_Mat< GT, __Entry_Type, SA > & other ) const

inlineprivate

Definition at line 720 of file tpl_matgraph.H.

References ah_domain_error_if, Aleph::Ady_Mat< GT, __Entry_Type, SA >::lgraph, and Aleph::maps().

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy().

Member Data Documentation

◆ lgraph

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

GT* Aleph::Ady_Mat< GT, __Entry_Type, SA >::lgraph = nullptr

private

Definition at line 714 of file tpl_matgraph.H.

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_list_graph(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_list_graph(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::test_same_graph().

◆ mat

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

DynArray<Entry_Type> Aleph::Ady_Mat< GT, __Entry_Type, SA >::mat

private

Definition at line 716 of file tpl_matgraph.H.

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()().

◆ nodes

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

DynArray<Node*> Aleph::Ady_Mat< GT, __Entry_Type, SA >::nodes

private

Definition at line 715 of file tpl_matgraph.H.

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()().

◆ Null_Value

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

Entry_Type Aleph::Ady_Mat< GT, __Entry_Type, SA >::Null_Value {}

mutableprivate

Definition at line 718 of file tpl_matgraph.H.

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::null_value(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::set_null_value().

◆ num_nodes

template<class GT , typename __Entry_Type , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Ady_Mat< GT, __Entry_Type, SA >::num_nodes = 0

mutableprivate

Definition at line 717 of file tpl_matgraph.H.

Referenced by Aleph::Ady_Mat< GT, __Entry_Type, SA >::copy_nodes(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_num_nodes(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()(), and Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()().

The documentation for this class was generated from the following file:

tpl_matgraph.H

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Key Features

Common Uses

Usage Example

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ Entry_Type

◆ Graph_Type

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ Ady_Mat() [1/3]

◆ Ady_Mat() [2/3]

◆ Ady_Mat() [3/3]

Member Function Documentation

◆ copy()

◆ copy_nodes()

◆ get_list_graph() [1/2]

◆ get_list_graph() [2/2]

◆ get_num_nodes()

◆ null_value()

◆ operate_all_arcs_list_graph() [1/2]

◆ operate_all_arcs_list_graph() [2/2]

◆ operate_all_arcs_matrix() [1/2]

◆ operate_all_arcs_matrix() [2/2]

◆ operator()() [1/7]

◆ operator()() [2/7]

◆ operator()() [3/7]

◆ operator()() [4/7]

◆ operator()() [5/7]

◆ operator()() [6/7]

◆ operator()() [7/7]

◆ operator=()

◆ set_null_value()

◆ test_same_graph()

Member Data Documentation

◆ lgraph

◆ mat

◆ nodes

◆ Null_Value

◆ num_nodes