mio::GraphBuilder< NodePropertyT, EdgePropertyT > Class Template Reference

A builder class for constructing graphs. More...

#include <graph_builder.h>

Public Types
using	EdgeProperty = EdgePropertyT
using	NodeProperty = NodePropertyT

Public Member Functions
template<class... Args>
void	add_edge (size_t start_node_idx, size_t end_node_idx, Args &&... args)
	Add an edge to the GraphBuilder. More...
template<class... Args>
void	add_node (int id, Args &&... args)
	Add a node to the GraphBuilder. More...
Graph< NodeProperty, EdgeProperty >	build (bool make_unique=false) &&
	Build the graph from the added nodes and edges. More...
	GraphBuilder ()=default
	GraphBuilder (const size_t num_nodes, const size_t num_edges)

Private Member Functions
void	remove_duplicate_edges ()
	Remove duplicate edges from a sorted edge vector. More...
void	sort_edges ()
	Sort the edge vector of a graph. More...

Private Attributes
std::vector< Edge< EdgePropertyT > >	m_edges
std::vector< Node< NodePropertyT > >	m_nodes

Detailed Description

template<class NodePropertyT, class EdgePropertyT>
class mio::GraphBuilder< NodePropertyT, EdgePropertyT >

A builder class for constructing graphs.

This class provides a interface for adding nodes and edges to a graph. It allows for efficient construction of large graphs by reserving space for nodes and edges in advance. The build method finalizes the graph by sorting edges and optionally removing duplicates. The advantage over the :ref add_edge function of the Graph class is that edges are only sorted once during the build process, improving performance when adding many edges.

Template Parameters

NodePropertyT	Type of the node property.
EdgePropertyT	Type of the edge property.

Member Typedef Documentation

EdgeProperty

template<class NodePropertyT , class EdgePropertyT >

using mio::GraphBuilder< NodePropertyT, EdgePropertyT >::EdgeProperty = EdgePropertyT

NodeProperty

template<class NodePropertyT , class EdgePropertyT >

using mio::GraphBuilder< NodePropertyT, EdgePropertyT >::NodeProperty = NodePropertyT

Constructor & Destructor Documentation

GraphBuilder() [1/2]

template<class NodePropertyT , class EdgePropertyT >

mio::GraphBuilder< NodePropertyT, EdgePropertyT >::GraphBuilder ( )

default

GraphBuilder() [2/2]

template<class NodePropertyT , class EdgePropertyT >

mio::GraphBuilder< NodePropertyT, EdgePropertyT >::GraphBuilder ( const size_t  num_nodes, const size_t  num_edges  )

inline

Member Function Documentation

add_edge()

template<class NodePropertyT , class EdgePropertyT >

template<class... Args>

void mio::GraphBuilder< NodePropertyT, EdgePropertyT >::add_edge ( size_t  start_node_idx, size_t  end_node_idx, Args &&...  args  )

inline

Add an edge to the GraphBuilder.

Parameters

start_node_idx	Id of start node
end_node_idx	Id of end node

Template Parameters

args	Additional arguments for edge construction

add_node()

template<class NodePropertyT , class EdgePropertyT >

template<class... Args>

void mio::GraphBuilder< NodePropertyT, EdgePropertyT >::add_node ( int  id, Args &&...  args  )

inline

Add a node to the GraphBuilder.

The property of the node is constructed from arguments.

Parameters

id	Id for the node.

Template Parameters

args	Additional arguments for node construction.

build()

template<class NodePropertyT , class EdgePropertyT >

Graph<NodeProperty, EdgeProperty> mio::GraphBuilder< NodePropertyT, EdgePropertyT >::build ( bool  make_unique = false ) &&

inline

Build the graph from the added nodes and edges.

Sorts the edges and optionally removes duplicate edges (same start and end node indices). Without duplicate removal, multiple edges between the same nodes are allowed and the order of insertion is stable.

Parameters

make_unique

If true, duplicate edges are removed. The last added edge is kept!

Returns

Graph<NodePropertyT, EdgePropertyT> The constructed graph.

remove_duplicate_edges()

template<class NodePropertyT , class EdgePropertyT >

void mio::GraphBuilder< NodePropertyT, EdgePropertyT >::remove_duplicate_edges ( )

inlineprivate

Remove duplicate edges from a sorted edge vector.

Copies all the unique edges to a new vector and replaces the original edge vector with it. Unique means that the start and end node indices are unique. Other edge properties are not checked and may get lost. Only the last edge in the vector is kept.

sort_edges()

template<class NodePropertyT , class EdgePropertyT >

void mio::GraphBuilder< NodePropertyT, EdgePropertyT >::sort_edges ( )

inlineprivate

Sort the edge vector of a graph.

Sorts the edges first by start node index, then by end node index. We use stable_sort to keep the order of insertion for edges with the same start and end node indices.

Member Data Documentation

m_edges

template<class NodePropertyT , class EdgePropertyT >

std::vector<Edge<EdgePropertyT> > mio::GraphBuilder< NodePropertyT, EdgePropertyT >::m_edges

private

m_nodes

template<class NodePropertyT , class EdgePropertyT >

std::vector<Node<NodePropertyT> > mio::GraphBuilder< NodePropertyT, EdgePropertyT >::m_nodes

private