Bit matrix for graph connectivity. More...

#include <tpl_matgraph.H>

Inheritance diagram for Aleph::Bit_Mat_Graph< GT, SA >:

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

Classes
struct	Proxy
	Proxy for bit access. More...

Public Types
using	Graph_Type = GT
	Graph type.

using	Node = typename GT::Node
	Node type.

using	Arc = typename GT::Arc
	Arc type.

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

	Bit_Mat_Graph ()=default
	Default constructor (empty matrix)

	Bit_Mat_Graph (GT &g)
	Construct from graph.

	Bit_Mat_Graph (const Bit_Mat_Graph &other)
	Copy constructor.

	Bit_Mat_Graph (size_t dim)
	Construct with dimension only.

void	set_list_graph (GT &g)
	Associate with a graph.

GT *	get_list_graph () noexcept
	Get pointer to associated graph (nullptr if none)

const GT *	get_list_graph () const noexcept
	Get pointer to associated graph (const)

Bit_Mat_Graph &	operator= (const Bit_Mat_Graph &other)
	Copy assignment.

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

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

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

Proxy	operator() (long i, long j)
	Access bit by indices.

Proxy	operator() (long i, long j) const
	Access bit by indices (const)

Proxy	operator() (Node src_node, Node tgt_node)
	Access bit by node pointers.

Proxy	operator() (Node src_node, Node tgt_node) const
	Access bit by node pointers (const)

Private Member Functions
void	copy_list_graph (GT &g)

Private Attributes
BitArray	bit_array

GT *	lgraph = nullptr

DynArray< typename GT::Node * >	nodes

size_t	n = 0

Detailed Description

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

Bit matrix for graph connectivity.

Bit_Mat_Graph provides a compact bit matrix representation for connectivity queries. Each entry uses only 1 bit: 1 indicates an arc exists, 0 indicates no arc.

Key Features

Minimal memory: n²/8 bytes for n nodes
O(1) edge existence check
Can be created without a graph (just dimension)
Modifiable entries

Usage Example

List_Graph<int, int> g;
// ... build graph ...
 
Bit_Mat_Graph<decltype(g)> bits(g);
 
// Check connectivity
if (bits(0, 1))
  std::cout << "Edge exists\n";
 
// Modify
bits(0, 2) = 1;  // Add edge
bits(0, 1) = 0;  // Remove edge

Template Parameters

GT	Graph type
SA	Arc filter

See also: BitArray Underlying bit array implementation; warshall_compute_transitive_closure()

Definition at line 1067 of file tpl_matgraph.H.

Member Typedef Documentation

◆ Arc

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

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

Arc type.

Definition at line 1077 of file tpl_matgraph.H.

◆ Graph_Type

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

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

Graph type.

Definition at line 1071 of file tpl_matgraph.H.

◆ Node

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

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

Node type.

Definition at line 1074 of file tpl_matgraph.H.

Constructor & Destructor Documentation

◆ Bit_Mat_Graph() [1/4]

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

Aleph::Bit_Mat_Graph< GT, SA >::Bit_Mat_Graph ( )

default

Default constructor (empty matrix)

◆ Bit_Mat_Graph() [2/4]

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

Aleph::Bit_Mat_Graph< GT, SA >::Bit_Mat_Graph ( GT & g )

inlineexplicit

Construct from graph.

Parameters

g	Source graph

Definition at line 1147 of file tpl_matgraph.H.

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

◆ Bit_Mat_Graph() [3/4]

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

Aleph::Bit_Mat_Graph< GT, SA >::Bit_Mat_Graph ( const Bit_Mat_Graph< GT, SA > & other )

inline

Copy constructor.

Definition at line 1154 of file tpl_matgraph.H.

◆ Bit_Mat_Graph() [4/4]

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

Aleph::Bit_Mat_Graph< GT, SA >::Bit_Mat_Graph ( size_t dim )

inlineexplicit

Construct with dimension only.

Parameters

dim	Matrix dimension

Definition at line 1163 of file tpl_matgraph.H.

Member Function Documentation

◆ copy_list_graph()

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

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

inlineprivate

Definition at line 1085 of file tpl_matgraph.H.

References Aleph::Bit_Mat_Graph< GT, SA >::bit_array, Aleph::DynArray< T >::cut(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::matgraph_detail::index_array(), Aleph::maps(), Aleph::Bit_Mat_Graph< GT, SA >::n, Aleph::Bit_Mat_Graph< GT, SA >::nodes, and Aleph::quicksort().

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

◆ get_list_graph() [1/2]

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

const GT * Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph ( ) const

inlinenoexcept

Get pointer to associated graph (const)

Definition at line 1183 of file tpl_matgraph.H.

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

◆ get_list_graph() [2/2]

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

GT * Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph ( )

inlinenoexcept

Get pointer to associated graph (nullptr if none)

Definition at line 1180 of file tpl_matgraph.H.

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

Referenced by TEST_F(), TEST_F(), TEST_F(), and Aleph::warshall_compute_transitive_clausure().

◆ get_num_nodes()

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

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

inlinenoexcept

Get number of nodes (matrix dimension)

Definition at line 1138 of file tpl_matgraph.H.

References Aleph::Bit_Mat_Graph< GT, SA >::n.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), and Aleph::warshall_compute_transitive_clausure().

◆ operator()() [1/6]

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

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

inline

Get node by index.

Parameters

i	Node index

Returns: Pointer to node

Exceptions

std::domain_error	if no graph associated
std::out_of_range	if index out of bounds

Definition at line 1213 of file tpl_matgraph.H.

References ah_domain_error_if, Aleph::Bit_Mat_Graph< GT, SA >::lgraph, and Aleph::Bit_Mat_Graph< GT, SA >::nodes.

◆ operator()() [2/6]

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

Proxy Aleph::Bit_Mat_Graph< GT, SA >::operator()	(	long	i,
		long	j
	)

inline

Access bit by indices.

Definition at line 1234 of file tpl_matgraph.H.

◆ operator()() [3/6]

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

Proxy Aleph::Bit_Mat_Graph< GT, SA >::operator()	(	long	i,
		long	j
	)		const

inline

Access bit by indices (const)

Definition at line 1240 of file tpl_matgraph.H.

◆ operator()() [4/6]

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

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

inline

Get index of node.

Parameters

node	Node pointer

Returns: Index in matrix

Exceptions

std::domain_error if no graph associated

Definition at line 1226 of file tpl_matgraph.H.

References ah_domain_error_if, Aleph::Bit_Mat_Graph< GT, SA >::lgraph, Aleph::Bit_Mat_Graph< GT, SA >::n, and Aleph::Bit_Mat_Graph< GT, SA >::nodes.

◆ operator()() [5/6]

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

Proxy Aleph::Bit_Mat_Graph< GT, SA >::operator()	(	Node *	src_node,
		Node *	tgt_node
	)

inline

Access bit by node pointers.

Definition at line 1246 of file tpl_matgraph.H.

References ah_domain_error_if, Aleph::Bit_Mat_Graph< GT, SA >::lgraph, Aleph::Bit_Mat_Graph< GT, SA >::n, and Aleph::Bit_Mat_Graph< GT, SA >::nodes.

◆ operator()() [6/6]

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

Proxy Aleph::Bit_Mat_Graph< GT, SA >::operator()	(	Node *	src_node,
		Node *	tgt_node
	)		const

inline

Access bit by node pointers (const)

Definition at line 1256 of file tpl_matgraph.H.

References ah_domain_error_if, Aleph::Bit_Mat_Graph< GT, SA >::lgraph, Aleph::Bit_Mat_Graph< GT, SA >::n, and Aleph::Bit_Mat_Graph< GT, SA >::nodes.

◆ operator=() [1/2]

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

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

inline

Copy assignment.

Definition at line 1186 of file tpl_matgraph.H.

References Aleph::Bit_Mat_Graph< GT, SA >::bit_array, Aleph::Bit_Mat_Graph< GT, SA >::lgraph, Aleph::maps(), Aleph::Bit_Mat_Graph< GT, SA >::n, and Aleph::Bit_Mat_Graph< GT, SA >::nodes.

◆ operator=() [2/2]

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

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

inline

Assign from graph.

Definition at line 1199 of file tpl_matgraph.H.

References Aleph::Bit_Mat_Graph< GT, SA >::lgraph, and Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph().

◆ set_list_graph()

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

void Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph ( GT & g )

inline

Associate with a graph.

Parameters

g	Graph to associate

Definition at line 1171 of file tpl_matgraph.H.

References Aleph::Bit_Mat_Graph< GT, SA >::bit_array, Aleph::Bit_Mat_Graph< GT, SA >::copy_list_graph(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bit_Mat_Graph< GT, SA >::lgraph, Aleph::maps(), and Aleph::BitArray::set_size().

Referenced by Aleph::Bit_Mat_Graph< GT, SA >::operator=(), TEST_F(), and Aleph::warshall_compute_transitive_clausure().

Member Data Documentation

◆ bit_array

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

BitArray Aleph::Bit_Mat_Graph< GT, SA >::bit_array

private

Definition at line 1080 of file tpl_matgraph.H.

Referenced by Aleph::Bit_Mat_Graph< GT, SA >::copy_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::operator=(), and Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph().

◆ lgraph

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

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

private

Definition at line 1081 of file tpl_matgraph.H.

Referenced by Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator=(), Aleph::Bit_Mat_Graph< GT, SA >::operator=(), and Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph().

◆ n

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

size_t Aleph::Bit_Mat_Graph< GT, SA >::n = 0

mutableprivate

Definition at line 1083 of file tpl_matgraph.H.

Referenced by Aleph::Bit_Mat_Graph< GT, SA >::copy_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::get_num_nodes(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), and Aleph::Bit_Mat_Graph< GT, SA >::operator=().

◆ nodes

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

DynArray<typename GT::Node*> Aleph::Bit_Mat_Graph< GT, SA >::nodes

private

Definition at line 1082 of file tpl_matgraph.H.

Referenced by Aleph::Bit_Mat_Graph< GT, SA >::copy_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), Aleph::Bit_Mat_Graph< GT, SA >::operator()(), and Aleph::Bit_Mat_Graph< GT, SA >::operator=().

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

tpl_matgraph.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Key Features

Usage Example

Member Typedef Documentation

◆ Arc

◆ Graph_Type

◆ Node

Constructor & Destructor Documentation

◆ Bit_Mat_Graph() [1/4]

◆ Bit_Mat_Graph() [2/4]

◆ Bit_Mat_Graph() [3/4]

◆ Bit_Mat_Graph() [4/4]

Member Function Documentation

◆ copy_list_graph()

◆ get_list_graph() [1/2]

◆ get_list_graph() [2/2]

◆ get_num_nodes()

◆ operator()() [1/6]

◆ operator()() [2/6]

◆ operator()() [3/6]

◆ operator()() [4/6]

◆ operator()() [5/6]

◆ operator()() [6/6]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ set_list_graph()

Member Data Documentation

◆ bit_array

◆ lgraph

◆ n

◆ nodes