Template Numerical Library version\ main:4e6e2c1
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Protected Types | Protected Attributes | List of all members
TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix > Struct Template Reference

Graph class represents a mathematical graph using an adjacency matrix. More...

#include <TNL/Graphs/Graph.h>

Inheritance diagram for TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >:
[legend]
Collaboration diagram for TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >:
[legend]

Public Types

using AdjacencyMatrixType = AdjacencyMatrix
 Type of the adjacency matrix.
using AdjacencyMatrixView = typename AdjacencyMatrixType::ViewType
 Type of the adjacency matrix view.
using ConstAdjacencyMatrixView = typename AdjacencyMatrixType::ConstViewType
 Type of constant view of the adjacency matrix.
using ConstVertexView = typename VertexView::ConstVertexView
 Type of constant graph nodes view.
using ConstViewType = GraphView< std::add_const_t< Value >, Device, Index, Orientation, ConstAdjacencyMatrixView >
 Type of constant view of the adjacency matrix.
using DeviceType = Device
 Type of device where the graph will be operating.
using GraphOrientation = Orientation
 Type of the graph - directed or undirected.
using IndexType = Index
 Type for indexing of the graph nodes.
template<typename Value_ = Value, typename Device_ = Device, typename Index_ = Index, typename Orientation_ = Orientation, template< typename, typename, typename > class Segments_ = Segments, typename AdjacencyMatrix_ = AdjacencyMatrix>
using Self = Graph< Value_, Device_, Index_, Orientation_, Segments_, AdjacencyMatrix_ >
 Helper type for getting self type or its modifications.
using ValueType = std::remove_cv_t< Value >
 Type for weights of the graph edges.
using VertexView = GraphVertexView< AdjacencyMatrixView, Orientation >
 Type of the graph nodes view.
using ViewType = GraphView< Value, Device, Index, Orientation, AdjacencyMatrixView >
 Type of constant view of the adjacency matrix.
Public Types inherited from TNL::Graphs::GraphBase< Value, Device, Index, DirectedGraph, TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, TNL::Algorithms::Segments::CSR >::ViewType >
using AdjacencyMatrixView
 Type of the adjacency matrix view.
using ConstAdjacencyMatrixView
 Type of constant view of the adjacency matrix.
using ConstVertexView
using DeviceType
 Type of device where the graph will be operating.
using GraphOrientation
 Type of the graph - directed or undirected.
using IndexType
 Type for indexing of the graph nodes.
using ValueType
 Type for weights of the graph edges.
using VertexView

Public Member Functions

 Graph ()=default
 Default constructor.
 Graph (AdjacencyMatrixType &&matrix)
 Constructor with adjacency matrix.
 Graph (const AdjacencyMatrixType &matrix)
 Constructor with adjacency matrix.
 Graph (const Graph &)=default
 Copy constructor.
template<typename OtherGraph>
 Graph (const OtherGraph &&other)
 Templated move constructor from another graph type.
template<typename OtherGraph>
 Graph (const OtherGraph &other)
 Templated copy constructor from another graph type.
template<typename T = AdjacencyMatrixType, typename C = std::enable_if_t< Matrices::is_dense_matrix_v< T > >>
 Graph (const std::initializer_list< std::initializer_list< ValueType > > &data, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed)
 Constructor with number of nodes and edges given as nested initializer list (for dense adjacency matrix).
 Graph (Graph &&)=default
 Move constructor.
 Graph (IndexType nodesCount)
 Constructor with number of nodes.
 Graph (IndexType vertexCount, const std::initializer_list< std::tuple< IndexType, IndexType, ValueType > > &data, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed)
 Constructor with number of nodes and edges given as initializer list.
template<typename MapIndex, typename MapValue>
 Graph (IndexType vertexCount, const std::map< std::pair< MapIndex, MapIndex >, MapValue > &map, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed)
 Constructor with number of nodes and edges given as a map.
 ~Graph ()=default
 Destructor.
AdjacencyMatrixType & getAdjacencyMatrix ()
 Returns the modifiable adjacency matrix of the graph.
const AdjacencyMatrixType & getAdjacencyMatrix () const
 Returns the modifiable adjacency matrix of the graph.
ConstViewType getConstView () const
 Returns the constant view of the graph.
ViewType getView ()
 Returns the modifiable view of the graph.
Graph & operator= (const Graph &other)
 Copy-assignment operator.
template<typename OtherGraph, std::enable_if_t< isGraph< OtherGraph >(std::declval< OtherGraph >()) >>
Graph & operator= (const OtherGraph &other)
Graph & operator= (Graph &&other) noexcept
 Move-assignment operator.
void reset ()
 Resets the graph to zero vertices and edges.
void setAdjacencyMatrix (AdjacencyMatrixType &&matrix)
 Sets the adjacency matrix of the graph.
void setAdjacencyMatrix (const AdjacencyMatrixType &matrix)
 Sets the adjacency matrix of the graph.
template<typename Matrix_>
void setAdjacencyMatrix (const Matrix_ &matrix)
 Sets the adjacency matrix of the graph.
template<typename T = AdjacencyMatrixType, typename C = std::enable_if_t< Matrices::is_dense_matrix_v< T > >>
void setDenseEdges (const std::initializer_list< std::initializer_list< ValueType > > &data, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricLower)
 Sets the edges of the graph from a nested initializer list (for dense adjacency matrix).
template<typename Vector>
void setEdgeCounts (const Vector &edgeCounts)
 Sets the edge counts (capacities) for all vertices in the graph.
void setEdges (const std::initializer_list< std::tuple< IndexType, IndexType, ValueType > > &data, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed)
 Sets the edges of the graph from an initializer list.
template<typename MapIndex, typename MapValue>
void setEdges (const std::map< std::pair< MapIndex, MapIndex >, MapValue > &map, Matrices::MatrixElementsEncoding encoding=isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed)
 Sets the edges of the graph from a map.
template<typename Vector>
void setVertexCapacities (const Vector &nodeCapacities)
 Sets the capacities of the graph nodes.
void setVertexCount (IndexType nodesCount)
 Sets the number of nodes in the graph.
Public Member Functions inherited from TNL::Graphs::GraphBase< Value, Device, Index, DirectedGraph, TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, TNL::Algorithms::Segments::CSR >::ViewType >
 GraphBase ()=default
 Default constructor.
 ~GraphBase ()=default
 Destructor.
__cuda_callable__ const AdjacencyMatrixView & getAdjacencyMatrixView () const
 Returns the constant view of adjacency matrix of the graph.
__cuda_callable__ IndexType getEdgeCount () const
 Returns the number of edges in the graph.
__cuda_callable__ ValueType getEdgeWeight (IndexType vertexIdx, IndexType edgeIdx) const
__cuda_callable__ ConstVertexView getVertex (IndexType vertexIdx) const
__cuda_callable__ IndexType getVertexCount () const
 Returns the number of nodes in the graph.
__cuda_callable__ IndexType getVertexDegree (IndexType nodeIdx) const
GraphBase & operator= (const GraphBase &)=delete
 Copy-assignment operator.
bool operator== (const GraphBase &other) const
 Comparisons operator.
__cuda_callable__ void setEdgeWeight (IndexType vertexIdx, IndexType edgeIdx, const ValueType &value)

Static Public Member Functions

static constexpr bool isDirected ()
 Checks if the graph is directed.
static constexpr bool isUndirected ()
 Checks if the graph is undirected.
Static Public Member Functions inherited from TNL::Graphs::GraphBase< Value, Device, Index, DirectedGraph, TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, TNL::Algorithms::Segments::CSR >::ViewType >
static std::string getSerializationType ()
 Returns the type of serialization used for the graph.
static constexpr bool isDirected ()
 Checks if the graph is directed.
static constexpr bool isUndirected ()
 Checks if the graph is undirected.

Protected Types

using Base = GraphBase< Value, Device, Index, Orientation, typename AdjacencyMatrix::ViewType >

Protected Attributes

AdjacencyMatrixType adjacencyMatrix
Protected Attributes inherited from TNL::Graphs::GraphBase< Value, Device, Index, DirectedGraph, TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, TNL::Algorithms::Segments::CSR >::ViewType >
AdjacencyMatrixView adjacencyMatrixView

Detailed Description

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
struct TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >

Graph class represents a mathematical graph using an adjacency matrix.

By default, the adjacency matrix is stored using a sparse matrix representation. This behavior can be changed by specifying adifferent matrix type as the last template parameter.

When a sparse matrix is used, all matrix elements that are not explicitly stored are interpreted as zero. In the context of graphs, however, it is important to distinguish between the absence of an edge and the presence of an edge with zero weight. To preserve this distinction, edges with zero weight are represented by explicitly stored matrix entries with zero value.

For unweighted graphs, use bool as the Value type. In this case, the sparse adjacency matrix is binary, which only stores the positions of the edges without any associated weights.

If a dense matrix is used as the adjacency matrix, it represents a complete graph, meaning that all possible edges between nodes are present.

Template Parameters
Valueis type for weights of the graph edges.
Deviceis type of device where the graph will be operating.
Indexis type for indexing of the graph nodes.
Orientationis type of the graph - directed or undirected.
Segmentsis template for segments type used to store adjacency matrix.
AdjacencyMatrixis type of matrix used to store the adjacency matrix of the graph.
Example
#include <iostream>
#include <TNL/Graphs/Graph.h>
#include <TNL/Matrices/DenseMatrix.h>
#include <TNL/Devices/Host.h>
#include <TNL/Devices/Cuda.h>
#include <TNL/Devices/Hip.h>
#include <TNL/Containers/Vector.h>
template< typename Device >
void
constructorsExample()
{
using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
using DenseGraphType = TNL::Graphs::Graph<
float,
Device,
int,
TNL::Graphs::DirectedGraph,
TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
TNL::Matrices::DenseMatrix< float, Device, int > >;
/***
* Example 1: Default constructor
*/
std::cout << "Example 1: Default constructor\n";
GraphType graph1;
std::cout << "Empty graph - vertices: " << graph1.getVertexCount() << ", edges: " << graph1.getEdgeCount() << "\n\n";
/***
* Example 2: Constructor with number of vertices
*/
std::cout << "Example 2: Constructor with vertex count\n";
GraphType graph2( 5 ); // 5 vertices, no edges
std::cout << "Graph with 5 vertices - vertices: " << graph2.getVertexCount() << ", edges: " << graph2.getEdgeCount()
<< "\n\n";
/***
* Example 3: Constructor with vertices and edges (initializer list - sparse graph)
*/
std::cout << "Example 3a: Constructor with initializer list (sparse graph)\n";
// clang-format off
GraphType graph3a( 5, // number of vertices
{ // definition of edges with weights
{ 0, 1, 10.0 }, { 0, 2, 20.0 },
{ 1, 2, 30.0 }, { 1, 3, 40.0 },
{ 2, 3, 50.0 },
{ 3, 0, 60.0 }, { 3, 4, 70.0 } } );
// clang-format on
std::cout << "Sparse graph:\n" << graph3a << '\n';
/***
* Example 3b: Constructor for undirected graph
*/
std::cout << "Example 3b: Undirected graph constructor\n";
// clang-format off
UndirectedGraphType graph3b( 4,
{ // only need to specify edges once for undirected graph
{ 0, 1, 1.0 }, { 0, 2, 2.0 },
{ 1, 2, 3.0 },
{ 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
// clang-format on
std::cout << "Undirected graph:\n" << graph3b << '\n';
/***
* Example 3c: Constructor with initializer list only for dense adjacency matrix.
* For dense matrix graphs, one can also use nested initializer lists {{row1}, {row2}, ...}
*/
std::cout << "\nExample 3c: Constructor with initializer list (dense adjacency matrix)\n";
// clang-format off
DenseGraphType graph3c( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
{ 0.0, 0.0, 30.0, 40.0, 0.0 }, // edges from vertex 1
{ 0.0, 0.0, 0.0, 50.0, 0.0 }, // edges from vertex 2
{60.0, 0.0, 0.0, 0.0, 70.0 }, // edges from vertex 3
{ 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
// clang-format on
std::cout << "Dense graph (complete graph with weighted edges):\n" << graph3c << '\n';
/***
* Example 4: Constructor with vertices and edges (map)
*/
std::cout << "\nExample 4: Constructor with std::map\n";
std::map< std::pair< int, int >, float > edgeMap;
edgeMap[ { 0, 1 } ] = 1.5;
edgeMap[ { 0, 2 } ] = 2.5;
edgeMap[ { 1, 2 } ] = 3.5;
edgeMap[ { 2, 3 } ] = 4.5;
GraphType graph4( 4, edgeMap );
std::cout << "Graph from map:\n" << graph4 << '\n';
/***
* Example 5: Copy constructor
*/
std::cout << "Example 5: Copy constructor\n";
GraphType graph5( graph3a ); // NOLINT(performance-unnecessary-copy-initialization)
std::cout << "Copied graph - vertices: " << graph5.getVertexCount() << ", edges: " << graph5.getEdgeCount() << "\n\n";
/***
* Example 6: Constructor from adjacency matrix
*/
std::cout << "Example 6: Constructor from adjacency matrix\n";
using MatrixType = typename GraphType::AdjacencyMatrixType;
MatrixType matrix( 3, 3 );
// clang-format off
matrix.setElements( { { 0, 1, 1.0 }, { 0, 2, 2.0 },
{ 1, 2, 3.0 },
{ 2, 0, 4.0 } } );
// clang-format on
GraphType graph6( matrix );
std::cout << "Graph from adjacency matrix:\n" << graph6 << '\n';
}
int
main( int argc, char* argv[] )
{
std::cout << "Running on host:\n";
constructorsExample< TNL::Devices::Host >();
#ifdef __CUDACC__
std::cout << "Running on CUDA device:\n";
constructorsExample< TNL::Devices::Cuda >();
#endif
#ifdef __HIP__
std::cout << "Running on HIP device:\n";
constructorsExample< TNL::Devices::Hip >();
#endif
return EXIT_SUCCESS;
}
TNL::Algorithms::Segments::CSR
Data structure for CSR segments.
Definition CSR.h:37
TNL::Matrices::DenseMatrix
Implementation of dense matrix, i.e. matrix storing explicitly all of its elements including zeros.
Definition DenseMatrix.h:31
TNL::Matrices::MatrixElementsEncoding::SymmetricMixed
@ SymmetricMixed
Definition MatrixBase.h:38
TNL::Graphs::DirectedGraph
Type tag for directed graphs.
Definition GraphOrientation.h:65
TNL::Graphs::Graph
Graph class represents a mathematical graph using an adjacency matrix.
Definition Graph.h:57
Output
Running on host:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4
Running on CUDA device:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4

Constructor & Destructor Documentation

◆ Graph() [1/3]

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::Graph ( IndexType vertexCount,
const std::initializer_list< std::tuple< IndexType, IndexType, ValueType > > & data,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed )

Constructor with number of nodes and edges given as initializer list.

Parameters
vertexCountis the number of nodes in the graph.
datais the initializer list of tuples (source node, target node, edge weight).
encodingis the encoding for symmetric matrices (used only for undirected graphs).

If the graph is undirected, the adjacency matrix can be symmetric. In this case, the parameter encoding specifies whether the lower or upper part of the matrix is provided. If the graph is undirected and the adjacency matrix type is not symmetric, the constructor will create a symmetric adjacency matrix by adding both (source, target) and (target, source) entries for each edge.

Example
1#include <iostream>
2#include <TNL/Graphs/Graph.h>
3#include <TNL/Matrices/DenseMatrix.h>
4#include <TNL/Devices/Host.h>
5#include <TNL/Devices/Cuda.h>
6#include <TNL/Devices/Hip.h>
7#include <TNL/Containers/Vector.h>
8
9template< typename Device >
10void
11constructorsExample()
12{
14 using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
16
18 using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
20
22 using DenseGraphType = TNL::Graphs::Graph<
23 float,
24 Device,
25 int,
26 TNL::Graphs::DirectedGraph,
27 TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
28 TNL::Matrices::DenseMatrix< float, Device, int > >;
30
32 /***
33 * Example 1: Default constructor
34 */
35 std::cout << "Example 1: Default constructor\n";
36 GraphType graph1;
37 std::cout << "Empty graph - vertices: " << graph1.getVertexCount() << ", edges: " << graph1.getEdgeCount() << "\n\n";
39
41 /***
42 * Example 2: Constructor with number of vertices
43 */
44 std::cout << "Example 2: Constructor with vertex count\n";
45 GraphType graph2( 5 ); // 5 vertices, no edges
46 std::cout << "Graph with 5 vertices - vertices: " << graph2.getVertexCount() << ", edges: " << graph2.getEdgeCount()
47 << "\n\n";
49
51 /***
52 * Example 3: Constructor with vertices and edges (initializer list - sparse graph)
53 */
54 std::cout << "Example 3a: Constructor with initializer list (sparse graph)\n";
55 // clang-format off
56 GraphType graph3a( 5, // number of vertices
57 { // definition of edges with weights
58 { 0, 1, 10.0 }, { 0, 2, 20.0 },
59 { 1, 2, 30.0 }, { 1, 3, 40.0 },
60 { 2, 3, 50.0 },
61 { 3, 0, 60.0 }, { 3, 4, 70.0 } } );
62 // clang-format on
63 std::cout << "Sparse graph:\n" << graph3a << '\n';
65
67 /***
68 * Example 3b: Constructor for undirected graph
69 */
70 std::cout << "Example 3b: Undirected graph constructor\n";
71 // clang-format off
72 UndirectedGraphType graph3b( 4,
73 { // only need to specify edges once for undirected graph
74 { 0, 1, 1.0 }, { 0, 2, 2.0 },
75 { 1, 2, 3.0 },
76 { 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
77 // clang-format on
78 std::cout << "Undirected graph:\n" << graph3b << '\n';
80
82 /***
83 * Example 3c: Constructor with initializer list only for dense adjacency matrix.
84 * For dense matrix graphs, one can also use nested initializer lists {{row1}, {row2}, ...}
85 */
86 std::cout << "\nExample 3c: Constructor with initializer list (dense adjacency matrix)\n";
87 // clang-format off
88 DenseGraphType graph3c( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
89 { 0.0, 0.0, 30.0, 40.0, 0.0 }, // edges from vertex 1
90 { 0.0, 0.0, 0.0, 50.0, 0.0 }, // edges from vertex 2
91 {60.0, 0.0, 0.0, 0.0, 70.0 }, // edges from vertex 3
92 { 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
93 // clang-format on
94 std::cout << "Dense graph (complete graph with weighted edges):\n" << graph3c << '\n';
96
98 /***
99 * Example 4: Constructor with vertices and edges (map)
100 */
101 std::cout << "\nExample 4: Constructor with std::map\n";
102 std::map< std::pair< int, int >, float > edgeMap;
103 edgeMap[ { 0, 1 } ] = 1.5;
104 edgeMap[ { 0, 2 } ] = 2.5;
105 edgeMap[ { 1, 2 } ] = 3.5;
106 edgeMap[ { 2, 3 } ] = 4.5;
107
108 GraphType graph4( 4, edgeMap );
109 std::cout << "Graph from map:\n" << graph4 << '\n';
111
113 /***
114 * Example 5: Copy constructor
115 */
116 std::cout << "Example 5: Copy constructor\n";
117 GraphType graph5( graph3a ); // NOLINT(performance-unnecessary-copy-initialization)
118 std::cout << "Copied graph - vertices: " << graph5.getVertexCount() << ", edges: " << graph5.getEdgeCount() << "\n\n";
120
122 /***
123 * Example 6: Constructor from adjacency matrix
124 */
125 std::cout << "Example 6: Constructor from adjacency matrix\n";
126 using MatrixType = typename GraphType::AdjacencyMatrixType;
127 MatrixType matrix( 3, 3 );
128 // clang-format off
129 matrix.setElements( { { 0, 1, 1.0 }, { 0, 2, 2.0 },
130 { 1, 2, 3.0 },
131 { 2, 0, 4.0 } } );
132 // clang-format on
134
135 GraphType graph6( matrix );
136 std::cout << "Graph from adjacency matrix:\n" << graph6 << '\n';
137}
138
139int
140main( int argc, char* argv[] )
141{
142 std::cout << "Running on host:\n";
143 constructorsExample< TNL::Devices::Host >();
144
145#ifdef __CUDACC__
146 std::cout << "Running on CUDA device:\n";
147 constructorsExample< TNL::Devices::Cuda >();
148#endif
149
150#ifdef __HIP__
151 std::cout << "Running on HIP device:\n";
152 constructorsExample< TNL::Devices::Hip >();
153#endif
154
155 return EXIT_SUCCESS;
156}
Output
Running on host:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4
Running on CUDA device:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4

◆ Graph() [2/3]

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename T = AdjacencyMatrixType, typename C = std::enable_if_t< Matrices::is_dense_matrix_v< T > >>
TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::Graph ( const std::initializer_list< std::initializer_list< ValueType > > & data,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed )

Constructor with number of nodes and edges given as nested initializer list (for dense adjacency matrix).

This constructor is only available when the adjacency matrix is a dense matrix type. The edges are specified as a nested initializer list where each inner list represents all edge weights from a single vertex. The number of vertices is inferred from the size of the outer list.

Parameters
datais the nested initializer list where data[i] contains all edge weights from vertex i. Use 0.0 for non-existent edges.
encodingis the encoding for symmetric matrices (used only for undirected graphs).

For dense matrices, the graph represents a complete graph where all possible edges are present. Zero-weighted edges does not indicate the absence of an edge in the logical graph structure.

Example
1#include <iostream>
2#include <TNL/Graphs/Graph.h>
3#include <TNL/Matrices/DenseMatrix.h>
4#include <TNL/Devices/Host.h>
5#include <TNL/Devices/Cuda.h>
6#include <TNL/Devices/Hip.h>
7#include <TNL/Containers/Vector.h>
8
9template< typename Device >
10void
11constructorsExample()
12{
14 using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
16
18 using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
20
22 using DenseGraphType = TNL::Graphs::Graph<
23 float,
24 Device,
25 int,
26 TNL::Graphs::DirectedGraph,
27 TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
28 TNL::Matrices::DenseMatrix< float, Device, int > >;
30
32 /***
33 * Example 1: Default constructor
34 */
35 std::cout << "Example 1: Default constructor\n";
36 GraphType graph1;
37 std::cout << "Empty graph - vertices: " << graph1.getVertexCount() << ", edges: " << graph1.getEdgeCount() << "\n\n";
39
41 /***
42 * Example 2: Constructor with number of vertices
43 */
44 std::cout << "Example 2: Constructor with vertex count\n";
45 GraphType graph2( 5 ); // 5 vertices, no edges
46 std::cout << "Graph with 5 vertices - vertices: " << graph2.getVertexCount() << ", edges: " << graph2.getEdgeCount()
47 << "\n\n";
49
51 /***
52 * Example 3: Constructor with vertices and edges (initializer list - sparse graph)
53 */
54 std::cout << "Example 3a: Constructor with initializer list (sparse graph)\n";
55 // clang-format off
56 GraphType graph3a( 5, // number of vertices
57 { // definition of edges with weights
58 { 0, 1, 10.0 }, { 0, 2, 20.0 },
59 { 1, 2, 30.0 }, { 1, 3, 40.0 },
60 { 2, 3, 50.0 },
61 { 3, 0, 60.0 }, { 3, 4, 70.0 } } );
62 // clang-format on
63 std::cout << "Sparse graph:\n" << graph3a << '\n';
65
67 /***
68 * Example 3b: Constructor for undirected graph
69 */
70 std::cout << "Example 3b: Undirected graph constructor\n";
71 // clang-format off
72 UndirectedGraphType graph3b( 4,
73 { // only need to specify edges once for undirected graph
74 { 0, 1, 1.0 }, { 0, 2, 2.0 },
75 { 1, 2, 3.0 },
76 { 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
77 // clang-format on
78 std::cout << "Undirected graph:\n" << graph3b << '\n';
80
82 /***
83 * Example 3c: Constructor with initializer list only for dense adjacency matrix.
84 * For dense matrix graphs, one can also use nested initializer lists {{row1}, {row2}, ...}
85 */
86 std::cout << "\nExample 3c: Constructor with initializer list (dense adjacency matrix)\n";
87 // clang-format off
88 DenseGraphType graph3c( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
89 { 0.0, 0.0, 30.0, 40.0, 0.0 }, // edges from vertex 1
90 { 0.0, 0.0, 0.0, 50.0, 0.0 }, // edges from vertex 2
91 {60.0, 0.0, 0.0, 0.0, 70.0 }, // edges from vertex 3
92 { 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
93 // clang-format on
94 std::cout << "Dense graph (complete graph with weighted edges):\n" << graph3c << '\n';
96
98 /***
99 * Example 4: Constructor with vertices and edges (map)
100 */
101 std::cout << "\nExample 4: Constructor with std::map\n";
102 std::map< std::pair< int, int >, float > edgeMap;
103 edgeMap[ { 0, 1 } ] = 1.5;
104 edgeMap[ { 0, 2 } ] = 2.5;
105 edgeMap[ { 1, 2 } ] = 3.5;
106 edgeMap[ { 2, 3 } ] = 4.5;
107
108 GraphType graph4( 4, edgeMap );
109 std::cout << "Graph from map:\n" << graph4 << '\n';
111
113 /***
114 * Example 5: Copy constructor
115 */
116 std::cout << "Example 5: Copy constructor\n";
117 GraphType graph5( graph3a ); // NOLINT(performance-unnecessary-copy-initialization)
118 std::cout << "Copied graph - vertices: " << graph5.getVertexCount() << ", edges: " << graph5.getEdgeCount() << "\n\n";
120
122 /***
123 * Example 6: Constructor from adjacency matrix
124 */
125 std::cout << "Example 6: Constructor from adjacency matrix\n";
126 using MatrixType = typename GraphType::AdjacencyMatrixType;
127 MatrixType matrix( 3, 3 );
128 // clang-format off
129 matrix.setElements( { { 0, 1, 1.0 }, { 0, 2, 2.0 },
130 { 1, 2, 3.0 },
131 { 2, 0, 4.0 } } );
132 // clang-format on
134
135 GraphType graph6( matrix );
136 std::cout << "Graph from adjacency matrix:\n" << graph6 << '\n';
137}
138
139int
140main( int argc, char* argv[] )
141{
142 std::cout << "Running on host:\n";
143 constructorsExample< TNL::Devices::Host >();
144
145#ifdef __CUDACC__
146 std::cout << "Running on CUDA device:\n";
147 constructorsExample< TNL::Devices::Cuda >();
148#endif
149
150#ifdef __HIP__
151 std::cout << "Running on HIP device:\n";
152 constructorsExample< TNL::Devices::Hip >();
153#endif
154
155 return EXIT_SUCCESS;
156}
Output
Running on host:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4
Running on CUDA device:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4

◆ Graph() [3/3]

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename MapIndex, typename MapValue>
TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::Graph ( IndexType vertexCount,
const std::map< std::pair< MapIndex, MapIndex >, MapValue > & map,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed )

Constructor with number of nodes and edges given as a map.

Parameters
vertexCountis the number of nodes in the graph.
mapis the map with keys as (source node, target node) pairs and values as edge weights.
encodingis the encoding for symmetric matrices (used only for undirected graphs).

If the graph is undirected, the adjacency matrix can be symmetric. In this case, the parameter encoding specifies whether the lower or upper part of the matrix is provided. If the graph is undirected and the adjacency matrix type is not symmetric, the constructor will create a symmetric adjacency matrix by adding both (source, target) and (target, source) entries for each edge.

Example
1#include <iostream>
2#include <TNL/Graphs/Graph.h>
3#include <TNL/Matrices/DenseMatrix.h>
4#include <TNL/Devices/Host.h>
5#include <TNL/Devices/Cuda.h>
6#include <TNL/Devices/Hip.h>
7#include <TNL/Containers/Vector.h>
8
9template< typename Device >
10void
11constructorsExample()
12{
14 using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
16
18 using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
20
22 using DenseGraphType = TNL::Graphs::Graph<
23 float,
24 Device,
25 int,
26 TNL::Graphs::DirectedGraph,
27 TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
28 TNL::Matrices::DenseMatrix< float, Device, int > >;
30
32 /***
33 * Example 1: Default constructor
34 */
35 std::cout << "Example 1: Default constructor\n";
36 GraphType graph1;
37 std::cout << "Empty graph - vertices: " << graph1.getVertexCount() << ", edges: " << graph1.getEdgeCount() << "\n\n";
39
41 /***
42 * Example 2: Constructor with number of vertices
43 */
44 std::cout << "Example 2: Constructor with vertex count\n";
45 GraphType graph2( 5 ); // 5 vertices, no edges
46 std::cout << "Graph with 5 vertices - vertices: " << graph2.getVertexCount() << ", edges: " << graph2.getEdgeCount()
47 << "\n\n";
49
51 /***
52 * Example 3: Constructor with vertices and edges (initializer list - sparse graph)
53 */
54 std::cout << "Example 3a: Constructor with initializer list (sparse graph)\n";
55 // clang-format off
56 GraphType graph3a( 5, // number of vertices
57 { // definition of edges with weights
58 { 0, 1, 10.0 }, { 0, 2, 20.0 },
59 { 1, 2, 30.0 }, { 1, 3, 40.0 },
60 { 2, 3, 50.0 },
61 { 3, 0, 60.0 }, { 3, 4, 70.0 } } );
62 // clang-format on
63 std::cout << "Sparse graph:\n" << graph3a << '\n';
65
67 /***
68 * Example 3b: Constructor for undirected graph
69 */
70 std::cout << "Example 3b: Undirected graph constructor\n";
71 // clang-format off
72 UndirectedGraphType graph3b( 4,
73 { // only need to specify edges once for undirected graph
74 { 0, 1, 1.0 }, { 0, 2, 2.0 },
75 { 1, 2, 3.0 },
76 { 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
77 // clang-format on
78 std::cout << "Undirected graph:\n" << graph3b << '\n';
80
82 /***
83 * Example 3c: Constructor with initializer list only for dense adjacency matrix.
84 * For dense matrix graphs, one can also use nested initializer lists {{row1}, {row2}, ...}
85 */
86 std::cout << "\nExample 3c: Constructor with initializer list (dense adjacency matrix)\n";
87 // clang-format off
88 DenseGraphType graph3c( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
89 { 0.0, 0.0, 30.0, 40.0, 0.0 }, // edges from vertex 1
90 { 0.0, 0.0, 0.0, 50.0, 0.0 }, // edges from vertex 2
91 {60.0, 0.0, 0.0, 0.0, 70.0 }, // edges from vertex 3
92 { 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
93 // clang-format on
94 std::cout << "Dense graph (complete graph with weighted edges):\n" << graph3c << '\n';
96
98 /***
99 * Example 4: Constructor with vertices and edges (map)
100 */
101 std::cout << "\nExample 4: Constructor with std::map\n";
102 std::map< std::pair< int, int >, float > edgeMap;
103 edgeMap[ { 0, 1 } ] = 1.5;
104 edgeMap[ { 0, 2 } ] = 2.5;
105 edgeMap[ { 1, 2 } ] = 3.5;
106 edgeMap[ { 2, 3 } ] = 4.5;
107
108 GraphType graph4( 4, edgeMap );
109 std::cout << "Graph from map:\n" << graph4 << '\n';
111
113 /***
114 * Example 5: Copy constructor
115 */
116 std::cout << "Example 5: Copy constructor\n";
117 GraphType graph5( graph3a ); // NOLINT(performance-unnecessary-copy-initialization)
118 std::cout << "Copied graph - vertices: " << graph5.getVertexCount() << ", edges: " << graph5.getEdgeCount() << "\n\n";
120
122 /***
123 * Example 6: Constructor from adjacency matrix
124 */
125 std::cout << "Example 6: Constructor from adjacency matrix\n";
126 using MatrixType = typename GraphType::AdjacencyMatrixType;
127 MatrixType matrix( 3, 3 );
128 // clang-format off
129 matrix.setElements( { { 0, 1, 1.0 }, { 0, 2, 2.0 },
130 { 1, 2, 3.0 },
131 { 2, 0, 4.0 } } );
132 // clang-format on
134
135 GraphType graph6( matrix );
136 std::cout << "Graph from adjacency matrix:\n" << graph6 << '\n';
137}
138
139int
140main( int argc, char* argv[] )
141{
142 std::cout << "Running on host:\n";
143 constructorsExample< TNL::Devices::Host >();
144
145#ifdef __CUDACC__
146 std::cout << "Running on CUDA device:\n";
147 constructorsExample< TNL::Devices::Cuda >();
148#endif
149
150#ifdef __HIP__
151 std::cout << "Running on HIP device:\n";
152 constructorsExample< TNL::Devices::Hip >();
153#endif
154
155 return EXIT_SUCCESS;
156}
Output
Running on host:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4
Running on CUDA device:
Example 1: Default constructor
Empty graph - vertices: 0, edges: 0
Example 2: Constructor with vertex count
Graph with 5 vertices - vertices: 5, edges: 0
Example 3a: Constructor with initializer list (sparse graph)
Sparse graph:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40
Row: 2 -> 3:50
Row: 3 -> 0:60 4:70
Row: 4 ->
Example 3b: Undirected graph constructor
Undirected graph:
Row: 0 -> 1:1 2:2
Row: 1 -> 0:1 2:3
Row: 2 -> 0:2 1:3 3:4
Row: 3 -> 2:4
Example 3c: Constructor with initializer list (dense adjacency matrix)
Dense graph (complete graph with weighted edges):
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:0
Row: 2 -> 0:0 1:0 2:0 3:50 4:0
Row: 3 -> 0:60 1:0 2:0 3:0 4:70
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 4: Constructor with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5
Row: 2 -> 3:4.5
Row: 3 ->
Example 5: Copy constructor
Copied graph - vertices: 5, edges: 7
Example 6: Constructor from adjacency matrix
Graph from adjacency matrix:
Row: 0 -> 1:1 2:2
Row: 1 -> 2:3
Row: 2 -> 0:4

Member Function Documentation

◆ reset()

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::reset ( )

Resets the graph to zero vertices and edges.

This method resets the adjacency matrix to zero dimensions, effectively removing all vertices and edges from the graph.

◆ setAdjacencyMatrix()

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename Matrix_>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setAdjacencyMatrix ( const Matrix_ & matrix)

Sets the adjacency matrix of the graph.

Template Parameters
Matrix_is type of the input adjacency matrix.
Parameters
matrixis the input adjacency matrix.

The method makes a copy of the provided adjacency matrix and so the type if the input matrix can be different from the type of the adjacency matrix of the graph.

◆ setDenseEdges()

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename T = AdjacencyMatrixType, typename C = std::enable_if_t< Matrices::is_dense_matrix_v< T > >>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setDenseEdges ( const std::initializer_list< std::initializer_list< ValueType > > & data,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricLower )

Sets the edges of the graph from a nested initializer list (for dense adjacency matrix).

This method is only available when the adjacency matrix is a dense matrix type. The edges are specified as a nested initializer list where each inner list represents all edge weights from a single vertex.

The edge values are given as nested lists data: { { weight_0_0, weight_0_1, weight_0_2, ... }, // edges from vertex 0 { weight_1_0, weight_1_1, weight_1_2, ... }, // edges from vertex 1 ... }.

Parameters
datais a nested initializer list where data[i][j] is the weight of edge from vertex i to vertex j. Use 0.0 for non-existent edges.
encodingdefines encoding for symmetric matrices (used only for undirected graphs).

See TNL::Matrices::DenseMatrix::setElements for details on how the encoding parameter works.

Example
#include <iostream>
#include <TNL/Graphs/Graph.h>
#include <TNL/Matrices/DenseMatrix.h>
#include <TNL/Devices/Host.h>
#include <TNL/Devices/Cuda.h>
#include <TNL/Devices/Hip.h>
template< typename Device >
void
setEdgesExample()
{
using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
/***
* Example 1: setEdges with initializer list (sparse graph)
*/
std::cout << "Example 1: setEdges with initializer list (sparse graph)\n";
GraphType graph1;
graph1.setVertexCount( 5 );
graph1.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 3, 1, 2, 0 } ) );
// clang-format off
graph1.setEdges( {
{ 0, 1, 10.0 }, { 0, 2, 20.0 },
{ 1, 2, 30.0 }, { 1, 3, 40.0 }, { 1, 4, 50.0 },
{ 2, 3, 60.0 },
{ 3, 0, 70.0 }, { 3, 4, 80.0 } } );
// clang-format on
std::cout << "Sparse graph after setEdges:\n" << graph1 << '\n';
/***
* Example 1b: setEdges with initializer list (dense adjacency matrix)
* For dense matrix graphs, use nested initializer lists {{row1}, {row2}, ...}
*/
std::cout << "\nExample 1b: setEdges with initializer list (dense adjacency matrix)\n";
using DenseGraphType = TNL::Graphs::Graph<
float,
Device,
int,
TNL::Graphs::DirectedGraph,
TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
TNL::Matrices::DenseMatrix< float, Device, int > >;
DenseGraphType graph1b;
graph1b.setVertexCount( 4 );
// clang-format off
graph1b.setDenseEdges( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
{ 0.0, 0.0, 30.0, 40.0, 50.0 }, // edges from vertex 1
{ 0.0, 0.0, 0.0, 60.0, 0.0 }, // edges from vertex 2
{ 70.0, 0.0, 0.0, 0.0, 80.0 }, // edges from vertex 3
{ 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
// clang-format on
std::cout << "Dense graph after setDenseEdges:\n" << graph1b << '\n';
/***
* Example 2: setEdges with std::map
*/
std::cout << "Example 2: setEdges with std::map\n";
GraphType graph2;
graph2.setVertexCount( 4 );
graph2.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 1, 1 } ) );
std::map< std::pair< int, int >, float > edgeMap;
edgeMap[ { 0, 1 } ] = 1.5;
edgeMap[ { 0, 2 } ] = 2.5;
edgeMap[ { 1, 2 } ] = 3.5;
edgeMap[ { 1, 3 } ] = 4.5;
edgeMap[ { 2, 3 } ] = 5.5;
edgeMap[ { 3, 0 } ] = 6.5;
graph2.setEdges( edgeMap );
std::cout << "Graph from map:\n" << graph2 << '\n';
/***
* Example 3: Updating edges
*/
std::cout << "Example 3: Updating edges\n";
// clang-format off
GraphType graph3( 4, { { 0, 1, 1.0 },
{ 1, 2, 2.0 },
{ 2, 3, 3.0 } } );
// clang-format on
std::cout << "Original graph:\n" << graph3 << '\n';
// Update with new edges (preserving the structure)
// clang-format off
graph3.setEdges( { { 0, 1, 10.0 },
{ 1, 2, 20.0 },
{ 2, 3, 30.0 } } );
// clang-format on
std::cout << "Updated graph:\n" << graph3 << '\n';
/***
* Example 4: setEdges for undirected graph
*/
std::cout << "Example 4: setEdges for undirected graph\n";
using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
UndirectedGraphType graph4;
graph4.setVertexCount( 4 );
graph4.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 2, 2 } ) );
// For undirected graphs, each edge is stored in both directions
// clang-format off
graph4.setEdges( {
{ 0, 1, 1.0 }, { 0, 2, 2.0 },
{ 1, 2, 3.0 },
{ 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
// clang-format on
}
int
main( int argc, char* argv[] )
{
std::cout << "Running on host:\n";
setEdgesExample< TNL::Devices::Host >();
#ifdef __CUDACC__
std::cout << "Running on CUDA device:\n";
setEdgesExample< TNL::Devices::Cuda >();
#endif
#ifdef __HIP__
std::cout << "Running on HIP device:\n";
setEdgesExample< TNL::Devices::Hip >();
#endif
return EXIT_SUCCESS;
}
TNL::Containers::Vector
Vector extends Array with algebraic operations.
Definition Vector.h:37
TNL::Graphs::Graph::setVertexCount
void setVertexCount(IndexType nodesCount)
Sets the number of nodes in the graph.
Output
Running on host:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph
Running on CUDA device:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph

◆ setEdgeCounts()

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename Vector>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setEdgeCounts ( const Vector & edgeCounts)

Sets the edge counts (capacities) for all vertices in the graph.

Template Parameters
Vectoris type of the vector holding the edge counts.
Parameters
edgeCountsis the vector holding the number of edges for each vertex.

This method sets the row capacities of the adjacency matrix to the provided edge counts. For undirected graphs with symmetric adjacency matrix, only capacities for edges in one direction should be provided.

◆ setEdges() [1/2]

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setEdges ( const std::initializer_list< std::tuple< IndexType, IndexType, ValueType > > & data,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed )

Sets the edges of the graph from an initializer list.

The edge values are given as a list data of triples: { { source1, target1, weight1 }, { source2, target2, weight2 }, ... }.

Parameters
datais an initializer list of tuples representing edges (source, target, weight).
encodingdefines encoding for symmetric matrices (used only for undirected graphs).

See TNL::Matrices::SparseMatrix::setElements for details on how the encoding parameter works.

Example
#include <iostream>
#include <TNL/Graphs/Graph.h>
#include <TNL/Matrices/DenseMatrix.h>
#include <TNL/Devices/Host.h>
#include <TNL/Devices/Cuda.h>
#include <TNL/Devices/Hip.h>
template< typename Device >
void
setEdgesExample()
{
using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
/***
* Example 1: setEdges with initializer list (sparse graph)
*/
std::cout << "Example 1: setEdges with initializer list (sparse graph)\n";
GraphType graph1;
graph1.setVertexCount( 5 );
graph1.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 3, 1, 2, 0 } ) );
// clang-format off
graph1.setEdges( {
{ 0, 1, 10.0 }, { 0, 2, 20.0 },
{ 1, 2, 30.0 }, { 1, 3, 40.0 }, { 1, 4, 50.0 },
{ 2, 3, 60.0 },
{ 3, 0, 70.0 }, { 3, 4, 80.0 } } );
// clang-format on
std::cout << "Sparse graph after setEdges:\n" << graph1 << '\n';
/***
* Example 1b: setEdges with initializer list (dense adjacency matrix)
* For dense matrix graphs, use nested initializer lists {{row1}, {row2}, ...}
*/
std::cout << "\nExample 1b: setEdges with initializer list (dense adjacency matrix)\n";
using DenseGraphType = TNL::Graphs::Graph<
float,
Device,
int,
TNL::Graphs::DirectedGraph,
TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
TNL::Matrices::DenseMatrix< float, Device, int > >;
DenseGraphType graph1b;
graph1b.setVertexCount( 4 );
// clang-format off
graph1b.setDenseEdges( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
{ 0.0, 0.0, 30.0, 40.0, 50.0 }, // edges from vertex 1
{ 0.0, 0.0, 0.0, 60.0, 0.0 }, // edges from vertex 2
{ 70.0, 0.0, 0.0, 0.0, 80.0 }, // edges from vertex 3
{ 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
// clang-format on
std::cout << "Dense graph after setDenseEdges:\n" << graph1b << '\n';
/***
* Example 2: setEdges with std::map
*/
std::cout << "Example 2: setEdges with std::map\n";
GraphType graph2;
graph2.setVertexCount( 4 );
graph2.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 1, 1 } ) );
std::map< std::pair< int, int >, float > edgeMap;
edgeMap[ { 0, 1 } ] = 1.5;
edgeMap[ { 0, 2 } ] = 2.5;
edgeMap[ { 1, 2 } ] = 3.5;
edgeMap[ { 1, 3 } ] = 4.5;
edgeMap[ { 2, 3 } ] = 5.5;
edgeMap[ { 3, 0 } ] = 6.5;
graph2.setEdges( edgeMap );
std::cout << "Graph from map:\n" << graph2 << '\n';
/***
* Example 3: Updating edges
*/
std::cout << "Example 3: Updating edges\n";
// clang-format off
GraphType graph3( 4, { { 0, 1, 1.0 },
{ 1, 2, 2.0 },
{ 2, 3, 3.0 } } );
// clang-format on
std::cout << "Original graph:\n" << graph3 << '\n';
// Update with new edges (preserving the structure)
// clang-format off
graph3.setEdges( { { 0, 1, 10.0 },
{ 1, 2, 20.0 },
{ 2, 3, 30.0 } } );
// clang-format on
std::cout << "Updated graph:\n" << graph3 << '\n';
/***
* Example 4: setEdges for undirected graph
*/
std::cout << "Example 4: setEdges for undirected graph\n";
using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
UndirectedGraphType graph4;
graph4.setVertexCount( 4 );
graph4.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 2, 2 } ) );
// For undirected graphs, each edge is stored in both directions
// clang-format off
graph4.setEdges( {
{ 0, 1, 1.0 }, { 0, 2, 2.0 },
{ 1, 2, 3.0 },
{ 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
// clang-format on
}
int
main( int argc, char* argv[] )
{
std::cout << "Running on host:\n";
setEdgesExample< TNL::Devices::Host >();
#ifdef __CUDACC__
std::cout << "Running on CUDA device:\n";
setEdgesExample< TNL::Devices::Cuda >();
#endif
#ifdef __HIP__
std::cout << "Running on HIP device:\n";
setEdgesExample< TNL::Devices::Hip >();
#endif
return EXIT_SUCCESS;
}
Output
Running on host:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph
Running on CUDA device:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph

◆ setEdges() [2/2]

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename MapIndex, typename MapValue>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setEdges ( const std::map< std::pair< MapIndex, MapIndex >, MapValue > & map,
Matrices::MatrixElementsEncoding encoding = isDirected() ? Matrices::MatrixElementsEncoding::Complete :Matrices::MatrixElementsEncoding::SymmetricMixed )

Sets the edges of the graph from a map.

Template Parameters
MapIndexis type for indexing of the nodes in the map.
MapValueis type for weights of the edges in the map.
Parameters
mapis the map with keys as (source node, target node) pairs and values as edge weights.
encodingdefines encoding for symmetric matrices (used only for undirected graphs).

See TNL::Matrices::SparseMatrix::setElements for details on how the encoding parameter works.

Example
1#include <iostream>
2#include <TNL/Graphs/Graph.h>
3#include <TNL/Matrices/DenseMatrix.h>
4#include <TNL/Devices/Host.h>
5#include <TNL/Devices/Cuda.h>
6#include <TNL/Devices/Hip.h>
7
8template< typename Device >
9void
10setEdgesExample()
11{
12 using GraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::DirectedGraph >;
13
15 /***
16 * Example 1: setEdges with initializer list (sparse graph)
17 */
18 std::cout << "Example 1: setEdges with initializer list (sparse graph)\n";
19 GraphType graph1;
20 graph1.setVertexCount( 5 );
21 graph1.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 3, 1, 2, 0 } ) );
22
23 // clang-format off
24 graph1.setEdges( {
25 { 0, 1, 10.0 }, { 0, 2, 20.0 },
26 { 1, 2, 30.0 }, { 1, 3, 40.0 }, { 1, 4, 50.0 },
27 { 2, 3, 60.0 },
28 { 3, 0, 70.0 }, { 3, 4, 80.0 } } );
29 // clang-format on
30
31 std::cout << "Sparse graph after setEdges:\n" << graph1 << '\n';
33
35 /***
36 * Example 1b: setEdges with initializer list (dense adjacency matrix)
37 * For dense matrix graphs, use nested initializer lists {{row1}, {row2}, ...}
38 */
39 std::cout << "\nExample 1b: setEdges with initializer list (dense adjacency matrix)\n";
40 using DenseGraphType = TNL::Graphs::Graph<
41 float,
42 Device,
43 int,
44 TNL::Graphs::DirectedGraph,
45 TNL::Algorithms::Segments::CSR, // Type of segments is ignored for dense matrices
46 TNL::Matrices::DenseMatrix< float, Device, int > >;
47 DenseGraphType graph1b;
48 graph1b.setVertexCount( 4 );
49
50 // clang-format off
51 graph1b.setDenseEdges( { { 0.0, 10.0, 20.0, 0.0, 0.0 }, // edges from vertex 0
52 { 0.0, 0.0, 30.0, 40.0, 50.0 }, // edges from vertex 1
53 { 0.0, 0.0, 0.0, 60.0, 0.0 }, // edges from vertex 2
54 { 70.0, 0.0, 0.0, 0.0, 80.0 }, // edges from vertex 3
55 { 0.0, 0.0, 0.0, 0.0, 0.0 } } ); // edges from vertex 4
56 // clang-format on
57
58 std::cout << "Dense graph after setDenseEdges:\n" << graph1b << '\n';
60
62 /***
63 * Example 2: setEdges with std::map
64 */
65 std::cout << "Example 2: setEdges with std::map\n";
66 GraphType graph2;
67 graph2.setVertexCount( 4 );
68 graph2.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 1, 1 } ) );
69
70 std::map< std::pair< int, int >, float > edgeMap;
71 edgeMap[ { 0, 1 } ] = 1.5;
72 edgeMap[ { 0, 2 } ] = 2.5;
73 edgeMap[ { 1, 2 } ] = 3.5;
74 edgeMap[ { 1, 3 } ] = 4.5;
75 edgeMap[ { 2, 3 } ] = 5.5;
76 edgeMap[ { 3, 0 } ] = 6.5;
77
78 graph2.setEdges( edgeMap );
79 std::cout << "Graph from map:\n" << graph2 << '\n';
81
82 /***
83 * Example 3: Updating edges
84 */
85 std::cout << "Example 3: Updating edges\n";
86 // clang-format off
87 GraphType graph3( 4, { { 0, 1, 1.0 },
88 { 1, 2, 2.0 },
89 { 2, 3, 3.0 } } );
90 // clang-format on
91
92 std::cout << "Original graph:\n" << graph3 << '\n';
93
94 // Update with new edges (preserving the structure)
95 // clang-format off
96 graph3.setEdges( { { 0, 1, 10.0 },
97 { 1, 2, 20.0 },
98 { 2, 3, 30.0 } } );
99 // clang-format on
100 std::cout << "Updated graph:\n" << graph3 << '\n';
101
102 /***
103 * Example 4: setEdges for undirected graph
104 */
105 std::cout << "Example 4: setEdges for undirected graph\n";
106 using UndirectedGraphType = TNL::Graphs::Graph< float, Device, int, TNL::Graphs::UndirectedGraph >;
107 UndirectedGraphType graph4;
108 graph4.setVertexCount( 4 );
109 graph4.setEdgeCounts( TNL::Containers::Vector< int, Device >( { 2, 2, 2, 2 } ) );
110
111 // For undirected graphs, each edge is stored in both directions
112 // clang-format off
113 graph4.setEdges( {
114 { 0, 1, 1.0 }, { 0, 2, 2.0 },
115 { 1, 2, 3.0 },
116 { 2, 3, 4.0 } }, TNL::Matrices::MatrixElementsEncoding::SymmetricMixed );
117 // clang-format on
118}
119
120int
121main( int argc, char* argv[] )
122{
123 std::cout << "Running on host:\n";
124 setEdgesExample< TNL::Devices::Host >();
125
126#ifdef __CUDACC__
127 std::cout << "Running on CUDA device:\n";
128 setEdgesExample< TNL::Devices::Cuda >();
129#endif
130
131#ifdef __HIP__
132 std::cout << "Running on HIP device:\n";
133 setEdgesExample< TNL::Devices::Hip >();
134#endif
135
136 return EXIT_SUCCESS;
137}
Output
Running on host:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph
Running on CUDA device:
Example 1: setEdges with initializer list (sparse graph)
Sparse graph after setEdges:
Row: 0 -> 1:10 2:20
Row: 1 -> 2:30 3:40 4:50
Row: 2 -> 3:60
Row: 3 -> 0:70 4:80
Row: 4 ->
Example 1b: setEdges with initializer list (dense adjacency matrix)
Dense graph after setDenseEdges:
Row: 0 -> 0:0 1:10 2:20 3:0 4:0
Row: 1 -> 0:0 1:0 2:30 3:40 4:50
Row: 2 -> 0:0 1:0 2:0 3:60 4:0
Row: 3 -> 0:70 1:0 2:0 3:0 4:80
Row: 4 -> 0:0 1:0 2:0 3:0 4:0
Example 2: setEdges with std::map
Graph from map:
Row: 0 -> 1:1.5 2:2.5
Row: 1 -> 2:3.5 3:4.5
Row: 2 -> 3:5.5
Row: 3 -> 0:6.5
Example 3: Updating edges
Original graph:
Row: 0 -> 1:1
Row: 1 -> 2:2
Row: 2 -> 3:3
Row: 3 ->
Updated graph:
Row: 0 -> 1:10
Row: 1 -> 2:20
Row: 2 -> 3:30
Row: 3 ->
Example 4: setEdges for undirected graph

◆ setVertexCapacities()

template<typename Value, typename Device, typename Index, typename Orientation = DirectedGraph, template< typename, typename, typename > class Segments = TNL::Algorithms::Segments::CSR, typename AdjacencyMatrix = TNL::Matrices::SparseMatrix< Value, Device, Index, TNL::Matrices::GeneralMatrix, Segments >>
template<typename Vector>
void TNL::Graphs::Graph< Value, Device, Index, Orientation, Segments, AdjacencyMatrix >::setVertexCapacities ( const Vector & nodeCapacities)

Sets the capacities of the graph nodes.

Parameters
nodeCapacitiesis the vector holding the node capacities.

The method sets the row capacities of the adjacency matrix to the provided node capacities. It is not necessary to call this method if the adjacency matrix is dense. If the adjacency matrix is sparse and symmetric, capacity only for edges in one direction (e.g., lower part) should be provided.

The documentation for this struct was generated from the following file:
Generated on for Template Numerical Library by doxygen 1.16.1