Adjacency matrix mapped to an adjacency list graph. More...

#include <tpl_matgraph.H>

Collaboration diagram for Aleph::Map_Matrix_Graph< GT, SA >:

Classes
struct	Mat_Entry

Public Types
using	Graph_Type = GT
	The associated graph type.

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

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

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

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

Public Member Functions
void	copy_list_graph (GT &g)
	Copy graph structure to matrix.

	Map_Matrix_Graph (GT &g, SA &&__sa=SA())
	Construct from adjacency list graph.

	Map_Matrix_Graph (GT &g, SA &__sa)
	Construct from adjacency list graph.

	Map_Matrix_Graph (Map_Matrix_Graph &other)
	Copy constructor.

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

Map_Matrix_Graph &	operator= (GT &g)
	Assign from graph.

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

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

Arc *	operator() (Node src_node, Node tgt_node) const
	Get arc by node pointers.

Arc *	operator() (long i, long j) const
	Get arc by indices.

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

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

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

Private Attributes
DynArray< Node * >	nodes

GT *	lgraph = nullptr

size_t	num_nodes = 0

SA	sa

DynArray< Mat_Entry >	mat

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Map_Matrix_Graph< GT, SA >

Adjacency matrix mapped to an adjacency list graph.

Map_Matrix_Graph provides an adjacency matrix view of a graph that is represented using adjacency lists. Matrix entries are pointers to arcs in the underlying graph. A nullptr entry indicates no arc exists.

Key Features

O(1) edge existence check by indices
O(log n) edge check by node pointers (binary search)
Memory proportional to number of arcs (sparse storage)
Read-only view of graph topology

Usage Example

List_Graph<int, double> g;
// ... build graph ...
 
Map_Matrix_Graph<List_Graph<int,double>> mat(g);
 
// Access by indices
auto arc = mat(0, 1);  // Arc from node 0 to node 1
 
// Access by node pointers
auto arc2 = mat(src_node, tgt_node);
 
// Get node by index
auto node = mat(2);

Warning: Changes to the underlying graph are NOT reflected in the matrix. Rebuild the matrix after modifying the graph.; Not suitable for multigraphs or multidigraphs.

Template Parameters

GT	Graph type (derived from List_Graph or similar)
SA	Arc filter (default: show all arcs)

See also: Matrix_Graph For a matrix that stores copies of attributes; Ady_Mat For auxiliary matrices with custom entry types

Definition at line 248 of file tpl_matgraph.H.

Member Typedef Documentation

◆ Arc

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

using Aleph::Map_Matrix_Graph< GT, SA >::Arc = typename GT::Arc

Arc type from the graph.

Definition at line 264 of file tpl_matgraph.H.

◆ Arc_Type

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

using Aleph::Map_Matrix_Graph< GT, SA >::Arc_Type = typename GT::Arc_Type

Arc attribute type from the graph.

Definition at line 258 of file tpl_matgraph.H.

◆ Graph_Type

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

using Aleph::Map_Matrix_Graph< GT, SA >::Graph_Type = GT

The associated graph type.

Definition at line 252 of file tpl_matgraph.H.

◆ Node

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

using Aleph::Map_Matrix_Graph< GT, SA >::Node = typename GT::Node

Node type from the graph.

Definition at line 261 of file tpl_matgraph.H.

◆ Node_Type

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

using Aleph::Map_Matrix_Graph< GT, SA >::Node_Type = typename GT::Node_Type

Node attribute type from the graph.

Definition at line 255 of file tpl_matgraph.H.

Constructor & Destructor Documentation

◆ Map_Matrix_Graph() [1/3]

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

Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph	(	GT &	g,
		SA &&	__sa = `SA()`
	)

inline

Construct from adjacency list graph.

Parameters

g	Source graph
__sa	Arc filter (rvalue reference)

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 296 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph().

◆ Map_Matrix_Graph() [2/3]

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

Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph	(	GT &	g,
		SA &	__sa
	)

inline

Construct from adjacency list graph.

Parameters

g	Source graph
__sa	Arc filter (lvalue reference)

Exceptions

std::bad_alloc if memory allocation fails

Definition at line 308 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph().

◆ Map_Matrix_Graph() [3/3]

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

Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph ( Map_Matrix_Graph< GT, SA > & other )

inline

Copy constructor.

Definition at line 315 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph(), and Aleph::maps().

Member Function Documentation

◆ copy_list_graph()

template<class GT , class SA >

void Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph ( GT & g )

Copy graph structure to matrix.

Rebuilds the matrix from the given graph. Previous contents are cleared.

Parameters

g	Graph to copy from

Definition at line 411 of file tpl_matgraph.H.

References Aleph::DynArray< T >::cut(), GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), nodes, num_nodes, and Aleph::quicksort().

Referenced by Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph(), Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph(), and Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph().

◆ get_list_graph() [1/2]

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

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

inlinenoexcept

Get reference to underlying graph (const)

Definition at line 384 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::lgraph.

◆ get_list_graph() [2/2]

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

GT & Aleph::Map_Matrix_Graph< GT, SA >::get_list_graph ( )

inlinenoexcept

Get reference to underlying graph.

Definition at line 381 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::lgraph.

Referenced by TEST_F().

◆ get_num_nodes()

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

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

inlinenoexcept

Get number of nodes (matrix dimension)

Definition at line 387 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::num_nodes.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ operator()() [1/4]

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

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

inline

Get node pointer by index.

Parameters

i	Node index

Returns: Pointer to node

Exceptions

std::out_of_range if i >= num_nodes

Definition at line 333 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::nodes.

◆ operator()() [2/4]

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

Arc * Aleph::Map_Matrix_Graph< GT, SA >::operator()	(	long	i,
		long	j
	)		const

inline

Get arc by indices.

Parameters

i	Source node index
j	Target node index

Returns: Arc pointer, or nullptr if no arc exists

Exceptions

std::out_of_range if indices out of bounds

Note: O(1) access

Definition at line 374 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::Mat_Entry::arc, Aleph::Map_Matrix_Graph< GT, SA >::mat, and Aleph::Map_Matrix_Graph< GT, SA >::num_nodes.

◆ operator()() [3/4]

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

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

inline

Get index of node.

Parameters

node	Node pointer

Returns: Index of node in matrix

Note: O(log n) binary search

Definition at line 344 of file tpl_matgraph.H.

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

◆ operator()() [4/4]

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

Arc * Aleph::Map_Matrix_Graph< GT, SA >::operator()	(	Node *	src_node,
		Node *	tgt_node
	)		const

inline

Get arc by node pointers.

Parameters

src_node	Source node
tgt_node	Target node

Returns: Arc pointer, or nullptr if no arc exists

Note: O(log n) for each node lookup

Definition at line 356 of file tpl_matgraph.H.

References Aleph::Map_Matrix_Graph< GT, SA >::Mat_Entry::arc, Aleph::Map_Matrix_Graph< GT, SA >::mat, Aleph::Map_Matrix_Graph< GT, SA >::nodes, and Aleph::Map_Matrix_Graph< GT, SA >::num_nodes.

◆ operator=() [1/2]

template<class GT , class SA >

Map_Matrix_Graph< GT, SA > & Aleph::Map_Matrix_Graph< GT, SA >::operator= ( GT & g )

Assign from graph.

Definition at line 403 of file tpl_matgraph.H.

◆ operator=() [2/2]

template<class GT , class SA >

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

Copy assignment.

Definition at line 394 of file tpl_matgraph.H.

References Aleph::maps().

Member Data Documentation

◆ lgraph

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

GT* Aleph::Map_Matrix_Graph< GT, SA >::lgraph = nullptr

private

Definition at line 275 of file tpl_matgraph.H.

Referenced by Aleph::Map_Matrix_Graph< GT, SA >::get_list_graph(), and Aleph::Map_Matrix_Graph< GT, SA >::get_list_graph().

◆ mat

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

DynArray<Mat_Entry> Aleph::Map_Matrix_Graph< GT, SA >::mat

private

Definition at line 278 of file tpl_matgraph.H.

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

◆ nodes

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

DynArray<Node*> Aleph::Map_Matrix_Graph< GT, SA >::nodes

private

Definition at line 274 of file tpl_matgraph.H.

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

◆ num_nodes

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

size_t Aleph::Map_Matrix_Graph< GT, SA >::num_nodes = 0

mutableprivate

Definition at line 276 of file tpl_matgraph.H.

Referenced by Aleph::Map_Matrix_Graph< GT, SA >::get_num_nodes(), Aleph::Map_Matrix_Graph< GT, SA >::operator()(), Aleph::Map_Matrix_Graph< GT, SA >::operator()(), and Aleph::Map_Matrix_Graph< GT, SA >::operator()().

◆ sa

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

SA Aleph::Map_Matrix_Graph< GT, SA >::sa

private

Definition at line 277 of file tpl_matgraph.H.

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

tpl_matgraph.H

Classes

Public Types

Public Member Functions

Private Attributes

Detailed Description

Key Features

Usage Example

Member Typedef Documentation

◆ Arc

◆ Arc_Type

◆ Graph_Type

◆ Node

◆ Node_Type

Constructor & Destructor Documentation

◆ Map_Matrix_Graph() [1/3]

◆ Map_Matrix_Graph() [2/3]

◆ Map_Matrix_Graph() [3/3]

Member Function Documentation

◆ copy_list_graph()

◆ get_list_graph() [1/2]

◆ get_list_graph() [2/2]

◆ get_num_nodes()

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

Member Data Documentation

◆ lgraph

◆ mat

◆ nodes

◆ num_nodes

◆ sa