Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
Aleph::Matrix_Graph< GT, SA > Class Template Reference
Graphs

Adjacency matrix storing copies of graph attributes. More...

#include <tpl_matgraph.H>

Collaboration diagram for Aleph::Matrix_Graph< GT, SA >:
[legend]

Public Types

using Graph_Type = GT
 Graph type.
 
using Node_Type = typename GT::Node_Type
 Node attribute type.
 
using Arc_Type = typename GT::Arc_Type
 Arc attribute 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)
 
const Arc_Type & null_value () const noexcept
 Get the null value indicating no arc.
 
 Matrix_Graph (GT &g, const Arc_Type &null, SA &&__sa=SA())
 Construct from graph with null value.
 
 Matrix_Graph (GT &g, const Arc_Type &null, SA &__sa)
 
 Matrix_Graph (Matrix_Graph &other)
 Copy constructor.
 
Matrix_Graph & operator= (Matrix_Graph &other)
 Copy assignment.
 
Matrix_Graph & operator= (GT &g)
 Assign from graph.
 
const Arc_Type & operator() (long i, long j) const
 Get arc attribute by indices (const).
 
Node_Type & operator() (long i) const
 Get node attribute by index.
 
Arc_Type & operator() (long i, long j)
 Get/set arc attribute by indices.
 

Private Member Functions

void copy (Matrix_Graph &other)
 
void copy (GT &g)
 

Private Attributes

DynArray< Node_Type > nodes
 
DynArray< Arc_Type > arcs
 
size_t n = 0
 
Arc_Type Null_Value {}
 
SA sa
 

Detailed Description

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

Adjacency matrix storing copies of graph attributes.

Matrix_Graph creates a self-contained adjacency matrix by copying the node and arc attributes from an adjacency list graph. Unlike Map_Matrix_Graph, this matrix does not maintain references to the original graph.

Key Features

  • Stores actual attribute values, not pointers
  • Modifiable entries (can add arcs by setting entries)
  • null_value() indicates absence of arc
  • Memory proportional to number of arcs (sparse storage)

Usage Example

List_Graph<std::string, int> g;
// ... build graph ...
// -1 indicates no arc
Matrix_Graph<List_Graph<std::string,int>> mat(g, -1);
// Read arc weight
int weight = mat(0, 1); // Returns -1 if no arc
// Add/modify arc
mat(0, 2) = 5; // Set arc weight
Aleph::List_Graph
Graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:428
Aleph::Matrix_Graph
Adjacency matrix storing copies of graph attributes.
Definition tpl_matgraph.H:488
Note
Only stores primitive attribute values, not derived node/arc types.
Template Parameters
GTGraph type
SAArc filter (default: show all arcs)
See also
Map_Matrix_Graph For pointer-based matrix
Ady_Mat For auxiliary matrices with custom types

Definition at line 487 of file tpl_matgraph.H.

Member Typedef Documentation

◆ Arc

template<typename GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Matrix_Graph< GT, SA >::Arc = typename GT::Arc

Arc type.

Definition at line 503 of file tpl_matgraph.H.

◆ Arc_Type

template<typename GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Matrix_Graph< GT, SA >::Arc_Type = typename GT::Arc_Type

Arc attribute type.

Definition at line 497 of file tpl_matgraph.H.

◆ Graph_Type

template<typename GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Matrix_Graph< GT, SA >::Graph_Type = GT

Graph type.

Definition at line 491 of file tpl_matgraph.H.

◆ Node

template<typename GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Matrix_Graph< GT, SA >::Node = typename GT::Node

Node type.

Definition at line 500 of file tpl_matgraph.H.

◆ Node_Type

template<typename GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Matrix_Graph< GT, SA >::Node_Type = typename GT::Node_Type

Node attribute type.

Definition at line 494 of file tpl_matgraph.H.

Constructor & Destructor Documentation

◆ Matrix_Graph() [1/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Aleph::Matrix_Graph< GT, SA >::Matrix_Graph ( GT &  g,
const Arc_Type &  null,
SA &&  __sa = SA() 
)
inline

Construct from graph with null value.

Parameters
gSource graph
nullValue indicating absence of arc
__saArc filter
Exceptions
std::bad_allocif memory allocation fails

Definition at line 575 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::copy().

◆ Matrix_Graph() [2/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Aleph::Matrix_Graph< GT, SA >::Matrix_Graph ( GT &  g,
const Arc_Type &  null,
SA &  __sa 
)
inline

Definition at line 581 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::copy().

◆ Matrix_Graph() [3/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Aleph::Matrix_Graph< GT, SA >::Matrix_Graph ( Matrix_Graph< GT, SA > &  other)
inline

Copy constructor.

Definition at line 588 of file tpl_matgraph.H.

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

Member Function Documentation

◆ copy() [1/2]

template<typename GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Matrix_Graph< GT, SA >::copy ( GT &  g)
inlineprivate

Definition at line 535 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::arcs, GTNodeCommon< NodeInfo >::get_info(), GTArcCommon< ArcInfo >::get_info(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::matgraph_detail::index_array(), Aleph::Matrix_Graph< GT, SA >::n, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::Matrix_Graph< GT, SA >::nodes, Aleph::Matrix_Graph< GT, SA >::Null_Value, Aleph::quicksort(), Aleph::Matrix_Graph< GT, SA >::sa, and Aleph::DynArray< T >::set_default_initial_value().

◆ copy() [2/2]

template<typename GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Matrix_Graph< GT, SA >::copy ( Matrix_Graph< GT, SA > &  other)
inlineprivate

Definition at line 512 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::arcs, Aleph::DynArray< T >::cut(), Aleph::matgraph_detail::index_array(), Aleph::maps(), Aleph::Matrix_Graph< GT, SA >::n, Aleph::Matrix_Graph< GT, SA >::nodes, Aleph::Matrix_Graph< GT, SA >::Null_Value, Aleph::DynArray< T >::set_default_initial_value(), and Aleph::DynArray< T >::touch().

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

◆ get_num_nodes()

template<typename GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Matrix_Graph< GT, SA >::get_num_nodes ( ) const
inlinenoexcept

Get number of nodes (matrix dimension)

Definition at line 563 of file tpl_matgraph.H.

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

Referenced by TEST_F().

◆ null_value()

template<typename GT , class SA = Dft_Show_Arc<GT>>
const Arc_Type & Aleph::Matrix_Graph< GT, SA >::null_value ( ) const
inlinenoexcept

Get the null value indicating no arc.

Definition at line 566 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::Null_Value.

Referenced by TEST_F().

◆ operator()() [1/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Node_Type & Aleph::Matrix_Graph< GT, SA >::operator() ( long  i) const
inline

Get node attribute by index.

Parameters
iNode index
Returns
Reference to node attribute
Exceptions
std::out_of_rangeif i >= n

Definition at line 623 of file tpl_matgraph.H.

References Aleph::DynArray< T >::access(), ah_out_of_range_error_if, Aleph::maps(), Aleph::Matrix_Graph< GT, SA >::n, and Aleph::Matrix_Graph< GT, SA >::nodes.

◆ operator()() [2/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Arc_Type & Aleph::Matrix_Graph< GT, SA >::operator() ( long  i,
long  j 
)
inline

Get/set arc attribute by indices.

Parameters
iSource index
jTarget index
Returns
Reference to arc entry (creates if needed)

Definition at line 636 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::arcs, Aleph::matgraph_detail::checked_index_array(), Aleph::Matrix_Graph< GT, SA >::n, and Aleph::DynArray< T >::touch().

◆ operator()() [3/3]

template<typename GT , class SA = Dft_Show_Arc<GT>>
const Arc_Type & Aleph::Matrix_Graph< GT, SA >::operator() ( long  i,
long  j 
) const
inline

Get arc attribute by indices (const).

Parameters
iSource index
jTarget index
Returns
Arc attribute, or null_value() if no arc
Exceptions
std::out_of_rangeif indices out of bounds

Definition at line 611 of file tpl_matgraph.H.

References Aleph::DynArray< T >::access(), Aleph::Matrix_Graph< GT, SA >::arcs, Aleph::matgraph_detail::checked_index_array(), Aleph::DynArray< T >::exist(), Aleph::Matrix_Graph< GT, SA >::n, and Aleph::Matrix_Graph< GT, SA >::Null_Value.

◆ operator=() [1/2]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Matrix_Graph & Aleph::Matrix_Graph< GT, SA >::operator= ( GT &  g)
inline

Assign from graph.

Definition at line 598 of file tpl_matgraph.H.

References Aleph::Matrix_Graph< GT, SA >::copy().

◆ operator=() [2/2]

template<typename GT , class SA = Dft_Show_Arc<GT>>
Matrix_Graph & Aleph::Matrix_Graph< GT, SA >::operator= ( Matrix_Graph< GT, SA > &  other)
inline

Copy assignment.

Definition at line 591 of file tpl_matgraph.H.

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

Member Data Documentation

◆ arcs

template<typename GT , class SA = Dft_Show_Arc<GT>>
DynArray<Arc_Type> Aleph::Matrix_Graph< GT, SA >::arcs
private

Definition at line 507 of file tpl_matgraph.H.

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

◆ n

template<typename GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Matrix_Graph< GT, SA >::n = 0
mutableprivate

Definition at line 508 of file tpl_matgraph.H.

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

◆ nodes

template<typename GT , class SA = Dft_Show_Arc<GT>>
DynArray<Node_Type> Aleph::Matrix_Graph< GT, SA >::nodes
private

Definition at line 506 of file tpl_matgraph.H.

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

◆ Null_Value

template<typename GT , class SA = Dft_Show_Arc<GT>>
Arc_Type Aleph::Matrix_Graph< GT, SA >::Null_Value {}
mutableprivate

Definition at line 509 of file tpl_matgraph.H.

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

◆ sa

template<typename GT , class SA = Dft_Show_Arc<GT>>
SA Aleph::Matrix_Graph< GT, SA >::sa
private

Definition at line 510 of file tpl_matgraph.H.

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

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