tpl_matgraph.H File Reference

Adjacency matrix representations for graphs. More...

#include <tpl_graph.H>
#include <tpl_sort_utils.H>
#include <ah-errors.H>

Include dependency graph for tpl_matgraph.H:

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

Go to the source code of this file.

Classes
class	Aleph::Map_Matrix_Graph< GT, SA >
	Adjacency matrix mapped to an adjacency list graph. More...
struct	Aleph::Map_Matrix_Graph< GT, SA >::Mat_Entry
class	Aleph::Matrix_Graph< GT, SA >
	Adjacency matrix storing copies of graph attributes. More...
class	Aleph::Ady_Mat< GT, __Entry_Type, SA >
	Auxiliary adjacency matrix with custom entry type. More...
class	Aleph::Bit_Mat_Graph< GT, SA >
	Bit matrix for graph connectivity. More...
struct	Aleph::Bit_Mat_Graph< GT, SA >::Proxy
	Proxy for bit access. More...

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

Functions
template<typename GT >
GT::Node *	Aleph::matgraph_detail::get_node (DynArray< typename GT::Node * > &nodes, long i)
	Get node pointer from sorted node array by index.
template<typename GT >
GT::Node *	Aleph::matgraph_detail::get_node (const DynArray< typename GT::Node * > &nodes, long i)
	Get node pointer from sorted node array by index (const version).
template<typename GT >
long	Aleph::matgraph_detail::node_index (const DynArray< typename GT::Node * > &nodes, long n, typename GT::Node *p)
	Find index of node in sorted array using binary search.
long	Aleph::matgraph_detail::index_array (long i, long j, long n) noexcept
	Convert 2D matrix indices to 1D array index.
long	Aleph::matgraph_detail::checked_index_array (long i, long j, long n)
	Validate and convert indices to linear index.
template<typename Entry >
Entry *	Aleph::matgraph_detail::read_matrix (const DynArray< Entry > &mat, long i, long j, long n)
	Read matrix entry if it exists.
template<typename Entry >
void	Aleph::matgraph_detail::write_matrix (DynArray< Entry > &mat, long i, long j, long n, const Entry &entry)
	Write entry to matrix.

Detailed Description

Adjacency matrix representations for graphs.

This file provides several adjacency matrix representations for graphs:

• Map_Matrix_Graph: Maps to an existing adjacency list graph. Entries are pointers to arcs in the list representation.
• Matrix_Graph: Stores copies of node/arc attributes from a graph. Entries contain the arc attribute type.
• Ady_Mat: Auxiliary matrix with user-defined entry type. Useful for algorithms like Floyd-Warshall that need custom data.
• Bit_Mat_Graph: Compact bit matrix for connectivity queries. Uses 1 bit per entry for minimal memory usage.

When to Use Adjacency Matrices

Use adjacency matrices when:

• The graph is dense (many edges relative to vertices)
• O(1) edge existence queries are needed
• Algorithms like Floyd-Warshall are applied

For sparse graphs, prefer adjacency list representations.

See also

tpl_graph.H Adjacency list graph representation

Floyd_Warshall.H Floyd-Warshall algorithm

Author

Leandro Rabindranath León

Definition in file tpl_matgraph.H.