Directed graph base class. More...

#include <base.hpp>

Collaboration diagram for dg::DGraphBase< EdgeT, IDT >:

Public Member Functions
	DGraphBase ()=default
	Construct a new DGraphBase object. More...

bool	hasNode (IDT id) const noexcept
	Check if the graph has a node with id. More...

bool	hasEdge (IDT from_id, IDT to_id) const noexcept
	Check if the graph has an edge linking from_id and to_id. More...

size_t	numNodes () const noexcept
	The total number of nodes in the graph. More...

size_t	numEdges () const noexcept
	The total number of edges in the graph. More...

size_t	size () const noexcept
	The total number of nodes in the graph. More...

EdgeT	edge (IDT from_id, IDT to_id) const
	Get the edge data between two nodes. More...

EdgeT_R	edge (IDT from_id, IDT to_id)
	Get the edge data reference between two nodes. More...

template<typename Ret , NonFunc Fn, typename... Args> requires EdgeVT<EdgeT>
Ret	edge (IDT from_id, IDT to_id, Fn func, Args... args) const
	Get the edge data after processing with a Lambda expression. More...

template<typename Ret , typename... Args> requires EdgeVT<EdgeT>
Ret	edge (IDT from_id, IDT to_id, std::function< Ret(EdgeT_, Args...)> func, Args... args) const
	Get the edge data after processing with a `std::function`. More...

bool	strictCheck () const
	Check if the graph is strictly valid. More...

std::vector< IDT >	nodesID () const
	Get all nodes IS in the graph. More...

std::vector< std::pair< IDT, IDT > >	edges () const
	Get all edge connections in the graph. More...

void	insertNode (IDT id)
	Insert a node. More...

void	insertNode (IDT id, const std::map< IDT, EdgeT > &map, bool nodes_exist=false)
	Insert a node with edge data. More...

void	removeNode (IDT id, bool keep_edge=false)
	Remove the node from the graph. More...

void	removeNodeIfExists (IDT id, bool keep_edge=false)
	Remove the node from the graph if it exists. More...

void	insertEdgeToExists (IDT from_id, IDT to_id)

void	insertEdgeToExists (IDT from_id, IDT to_id, EdgeT_CR data)

void	insertEdge (IDT from_id, IDT to_id, bool to_exists=false)
	Insert an edge to the graph without data. More...

void	insertEdge (IDT from_id, IDT to_id, EdgeT_CR data, bool to_exists=false)
	Insert an edge to the graph with data. More...

bool	isConnected (IDT from_id, IDT to_id) const
	Check whether to node are connected. More...

std::pair< EdgeT_, std::vector< IDT > >	maxWeightPath (IDT from_id, IDT to_id) const
	Obtain the maximum weight and its corresponding path between two nodes. More...

template<typename Ret , NonFunc Fn, typename... Args> requires EdgeVT<EdgeT>
std::pair< Ret, std::vector< IDT > >	maxWeightPath (IDT from_id, IDT to_id, Fn func, Args... args) const
	Obtain the maximum weight and its corresponding path between two nodes. More...

template<typename Ret , typename... Args> requires EdgeVT<EdgeT>
std::pair< Ret, std::vector< IDT > >	maxWeightPath (IDT from_id, IDT to_id, std::function< Ret(EdgeT_, Args...)> func, Args... args) const
	Obtain the maximum weight and its corresponding path between two nodes. More...

std::pair< EdgeT_, std::vector< IDT > >	minWeightPath (IDT from_id, IDT to_id) const
	Obtain the minimum weight and its corresponding path between two nodes. More...

template<typename Ret , NonFunc Fn, typename... Args> requires EdgeVT<EdgeT>
std::pair< Ret, std::vector< IDT > >	minWeightPath (IDT from_id, IDT to_id, Fn func, Args... args) const
	Obtain the minimum weight and its corresponding path between two nodes. More...

template<typename Ret , typename... Args> requires EdgeVT<EdgeT>
std::pair< Ret, std::vector< IDT > >	minWeightPath (IDT from_id, IDT to_id, std::function< Ret(EdgeT_, Args...)> func, Args... args) const
	Obtain the minimum weight and its corresponding path between two nodes. More...

void	insertSubGraph (const DGraphBase< EdgeT, IDT > &dg)
	Insert subgraph into the main graph. More...

void	insertSubGraph (const DGraphBase< EdgeT, IDT > &dg, IDT id)
	Insert a subgraph at a node. More...

void	merge (const DGraphBase< EdgeT, IDT > &dg)
	Merge a graph into the main graph. More...

void	clear ()
	Clear the whole graph. More...

void	clearEdges ()
	Clear all edges of the graph. More...

bool	operator== (const DGraphBase< EdgeT, IDT > &dg) const
	Check if two graphs are identical. More...

bool	operator!= (const DGraphBase< EdgeT, IDT > &dg) const
	Check if two graphs are different. More...

DGraphBase &	operator+= (const DGraphBase< EdgeT, IDT > &dg)
	Merge two graphs. More...

EdgeT	operator() (IDT from_id, IDT to_id) const
	Get the edge data between two nodes. More...

EdgeT_R	operator() (IDT from_id, IDT to_id)
	Get the edge data reference between two nodes. More...

Protected Types
using	_ET = Edge< EdgeT >

using	_CN = std::map< IDT, _ET >

template<typename T = EdgeT>
using	EdgeT__ = typename std::conditional< std::is_void_v< T >, int, T >::type
	Edge type that avoids void. More...

template<typename T = EdgeT>
using	EdgeT_R_ = typename std::conditional< std::is_void_v< T >, int, T >::type &
	Reference to edge type that avoids void. More...

template<typename T = EdgeT>
using	EdgeT_CR_ = const typename std::conditional< std::is_void_v< T >, int, T >::type &
	Const reference to edge type that avoids void. More...

using	EdgeT_ = EdgeT__<>

using	EdgeT_R = EdgeT_R_<>

using	EdgeT_CR = EdgeT_CR_<>

Protected Member Functions
void	insertNode (IDT id, const _CN &cn, bool nodes_exist=false)
	Insert a node. More...

const std::map< IDT, _CN > &	graph () const
	Return the const reference to the graph map. More...

std::map< IDT, _CN > &	graph ()
	Return the reference to the graph map. More...

Private Member Functions
template<typename Ret , typename... Args> requires EdgeVT<EdgeT>
std::pair< Ret, std::vector< IDT > >	minOrMaxWeightPath (bool min, IDT from_id, IDT to_id, std::function< Ret(EdgeT_, Args...)> func, Args... args) const
	Obtain the minimum/maximum weight and its corresponding path between two nodes. More...

size_t	removeNodeConnectedEdges (IDT id)
	Remove edges connected to a node. More...

Private Attributes
std::map< IDT, _CN >	g

Detailed Description

template<typename EdgeT = void, IDVT IDT = std::string>
class dg::DGraphBase< EdgeT, IDT >

Directed graph base class.

If the edge only represents connection, the EdgeT can be void.

Template Parameters

EdgeT	Type of edge.
IDT	Type of ID.

Member Typedef Documentation

◆ _CN

template<typename EdgeT = void, IDVT IDT = std::string>

using dg::DGraphBase< EdgeT, IDT >::_CN = std::map<IDT, _ET>

protected

connection

◆ _ET

template<typename EdgeT = void, IDVT IDT = std::string>

using dg::DGraphBase< EdgeT, IDT >::_ET = Edge<EdgeT>

protected

edge type

◆ EdgeT_

template<typename EdgeT = void, IDVT IDT = std::string>

using dg::DGraphBase< EdgeT, IDT >::EdgeT_ = EdgeT__<>

protected

safe edge type

◆ EdgeT__

template<typename EdgeT = void, IDVT IDT = std::string>

template<typename T = EdgeT>

using dg::DGraphBase< EdgeT, IDT >::EdgeT__ = typename std::conditional<std::is_void_v<T>, int, T>::type

protected

Edge type that avoids void.

Since some operations do not allow void, so we change the void type to a non-void type, while retaining other types as the same.

Template Parameters

T	Same as EdgeT. Do not specify this type yourself.

◆ EdgeT_CR

template<typename EdgeT = void, IDVT IDT = std::string>

using dg::DGraphBase< EdgeT, IDT >::EdgeT_CR = EdgeT_CR_<>

protected

safe edge const reference type

◆ EdgeT_CR_

template<typename EdgeT = void, IDVT IDT = std::string>

template<typename T = EdgeT>

using dg::DGraphBase< EdgeT, IDT >::EdgeT_CR_ = const typename std::conditional<std::is_void_v<T>, int, T>::type&

protected

Const reference to edge type that avoids void.

Since some operations do not allow const void&, so we change the void type to non-void type, while retaining other types as the same const reference.

Template Parameters

T	Same as EdgeT. Do not specify this type yourself.

◆ EdgeT_R

template<typename EdgeT = void, IDVT IDT = std::string>

using dg::DGraphBase< EdgeT, IDT >::EdgeT_R = EdgeT_R_<>

protected

safe edge reference type

◆ EdgeT_R_

template<typename EdgeT = void, IDVT IDT = std::string>

template<typename T = EdgeT>

using dg::DGraphBase< EdgeT, IDT >::EdgeT_R_ = typename std::conditional<std::is_void_v<T>, int, T>::type&

protected

Reference to edge type that avoids void.

Since some operations do not allow void&, so we change the void type to non-void type, while retaining other types as the same reference.

Template Parameters

T	Same as EdgeT. Do not specify this type yourself.

Constructor & Destructor Documentation

◆ DGraphBase()

template<typename EdgeT = void, IDVT IDT = std::string>

dg::DGraphBase< EdgeT, IDT >::DGraphBase ( )

default

Construct a new DGraphBase object.

This is the default constructor.

Member Function Documentation

◆ clear()

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::clear

inline

Clear the whole graph.

Remove all the nodes and the connected edges.

◆ clearEdges()

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::clearEdges

inline

Clear all edges of the graph.

◆ edge() [1/4]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

DGraphBase< EdgeT, IDT >::EdgeT_R dg::DGraphBase< EdgeT, IDT >::edge	(	IDT	from_id,
		IDT	to_id
	)

Get the edge data reference between two nodes.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (EdgeT_R) The edge data reference.

◆ edge() [2/4]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

EdgeT dg::DGraphBase< EdgeT, IDT >::edge	(	IDT	from_id,
		IDT	to_id
	)		const

Get the edge data between two nodes.

Note: The EdgeT should not be void.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (EdgeT) The edge data.

Here is the caller graph for this function:

◆ edge() [3/4]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , NonFunc Fn, typename... Args>
requires EdgeVT<EdgeT>

Ret dg::DGraphBase< EdgeT, IDT >::edge	(	IDT	from_id,
		IDT	to_id,
		Fn	func,
		Args...	args
	)		const

inline

Get the edge data after processing with a Lambda expression.

You can also use the std::function version instead of the Lambda expression.
You need to manually set the return type as the function template argument, for example

// dgb1 is of type DGraphBase<int, std::string>.
int result = dgb1.edge<int>(std::string("n1"), std::string("n2"), [](int weight) {
    return weight + 1;
});

Note: The EdgeT should not be void.

Template Parameters

Ret	The return type of the Lambda expression as well as this function.
Fn	The Lambda expression type.
Args	The argument types of the Lambda expression.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The Lambda expression.
args	The arguments of the Lambda expression.

Returns: (Ret) The result of the Lambda expression.

Here is the call graph for this function:

◆ edge() [4/4]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , typename... Args>
requires EdgeVT<EdgeT>

Ret dg::DGraphBase< EdgeT, IDT >::edge	(	IDT	from_id,
		IDT	to_id,
		std::function< Ret(EdgeT_, Args...)>	func,
		Args...	args
	)		const

inline

Get the edge data after processing with a std::function.

You have to specifically define the std::function, for example

// dgb1 is of type DGraphBase<int, std::string>.
int result = dgb1.edge(std::string("n1"), std::string("n2"),
                       std::function<int(int, int)>([](int weight, int n) { return weight + n; }), 2);

You can also use the Lambda version of the edge method instead of the std::function version.

Note: The EdgeT should not be void.

Template Parameters

Ret	The return type of the `std::function`.
Args	The argument types of the `std::function`.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The `std::function`.
args	The arguments of the `std::function`.

Returns: (Ret) The result of the std::function.

Here is the call graph for this function:

◆ edges()

template<typename EdgeT , IDVT IDT>

std::vector< std::pair< IDT, IDT > > dg::DGraphBase< EdgeT, IDT >::edges

inline

Get all edge connections in the graph.

Returns: (std::vector<std::pair<IDT, IDT>>) A vector of edge connections, in std::pair.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ graph() [1/2]

template<typename EdgeT , IDVT IDT>

std::map< IDT, typename DGraphBase< EdgeT, IDT >::_CN > & dg::DGraphBase< EdgeT, IDT >::graph

inlineprotected

Return the reference to the graph map.

Returns: (std::map<IDT, _CN>&) reference to the graph map.

◆ graph() [2/2]

template<typename EdgeT , IDVT IDT>

const std::map< IDT, typename DGraphBase< EdgeT, IDT >::_CN > & dg::DGraphBase< EdgeT, IDT >::graph

inlineprotected

Return the const reference to the graph map.

Returns: (const std::map<IDT, _CN>&) Const reference to the graph map.

◆ hasEdge()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::hasEdge	(	IDT	from_id,
		IDT	to_id
	)		const

inlinenoexcept

Check if the graph has an edge linking from_id and to_id.

If either from_id or to_id node does not exist, we conclude there is no such edge.

Parameters

from_id	The from node id.
to_id	The to node id.

Return values

true	There exists the edge in the graph.
false	There does not exist the edge in the graph.

Here is the caller graph for this function:

◆ hasNode()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::hasNode ( IDT id ) const

inlinenoexcept

Check if the graph has a node with id.

Parameters

id	The node id (which should be unique).

Return values

true	There exists the node in the graph.
false	There does not exist the node in the graph.

Here is the caller graph for this function:

◆ insertEdge() [1/2]

template<typename EdgeT , IDVT IDT>
requires std::is_void_v<EdgeT>

void dg::DGraphBase< EdgeT, IDT >::insertEdge	(	IDT	from_id,
		IDT	to_id,
		bool	to_exists = `false`
	)

Insert an edge to the graph without data.

Parameters

from_id	The from node id. If it does not exist, it will be created automatically.
to_id	The to node id. If it does not exist, it will be created automatically.
to_exists	Whether the to node exists before insertion. If this is set to true, the from node graph will not be updated. Please be sure before setting this to true.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insertEdge() [2/2]

template<typename EdgeT = void, IDVT IDT = std::string>

void dg::DGraphBase< EdgeT, IDT >::insertEdge	(	IDT	from_id,
		IDT	to_id,
		EdgeT_CR	data,
		bool	to_exists = `false`
	)

Insert an edge to the graph with data.

Parameters

from_id	The from node id. If it does not exist, it will be created automatically.
to_id	The to node id. If it does not exist, it will be created automatically.
data	The edge data.
to_exists	Whether the to node exists before insertion. If this is set to true, the from node graph will not be updated. Please be sure before setting this to true.

◆ insertEdgeToExists() [1/2]

template<typename EdgeT , IDVT IDT>
requires std::is_void_v<EdgeT>

void dg::DGraphBase< EdgeT, IDT >::insertEdgeToExists	(	IDT	from_id,
		IDT	to_id
	)

inline

Here is the caller graph for this function:

◆ insertEdgeToExists() [2/2]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

void dg::DGraphBase< EdgeT, IDT >::insertEdgeToExists	(	IDT	from_id,
		IDT	to_id,
		EdgeT_CR	data
	)

inline

◆ insertNode() [1/3]

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::insertNode ( IDT id )

Insert a node.

If the node id exists before, its edge connections will be cleared. If the node id does not exist, it will be created.

Parameters

id	The node id.

Here is the caller graph for this function:

◆ insertNode() [2/3]

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::insertNode	(	IDT	id,
		const _CN &	cn,
		bool	nodes_exist = `false`
	)

protected

Insert a node.

Parameters

id	The node id.
cn	The edge connections.
nodes_exist	Whether the node exists before insertion.

◆ insertNode() [3/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

void dg::DGraphBase< EdgeT, IDT >::insertNode	(	IDT	id,
		const std::map< IDT, EdgeT > &	map,
		bool	nodes_exist = `false`
	)

Insert a node with edge data.

If the node id exists before, its edge connections will be cleared. If the node id does not exist, it will be created.
If nodes_exist is set to true, the node graph will not be updated. Otherwise (the default behavior) the node graph will be updated by checking all connected edges.

Note: nodes_exist does not mean whether the node with id exists. It specifies whether the connected nodes exist.; EdgeT should not be void.

Parameters

id	The node id.
map	The edge data map.
nodes_exist	Whether all nodes in edge connections exist before insertion (default as false). You should be sure when setting this to true. Otherwise there can be unexpected behaviors.

Here is the call graph for this function:

◆ insertSubGraph() [1/2]

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::insertSubGraph ( const DGraphBase< EdgeT, IDT > & dg )

inline

Insert subgraph into the main graph.

This is an alias for merge();

Parameters

dg	The subgraph.

Here is the call graph for this function:

◆ insertSubGraph() [2/2]

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::insertSubGraph	(	const DGraphBase< EdgeT, IDT > &	dg,
		IDT	id
	)

inline

Insert a subgraph at a node.

This is equivalent to remove a node and insert a subgraph.

Parameters

dg	The subgraph.
id	The node id.

Here is the call graph for this function:

◆ isConnected()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::isConnected	(	IDT	from_id,
		IDT	to_id
	)		const

inline

Check whether to node are connected.

Parameters

from_id	The from node id.
to_id	The to node id.

Return values

true	There exists a path.
false	There does not exist a path.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ maxWeightPath() [1/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT> && std::is_arithmetic_v<EdgeT>

std::pair< typename DGraphBase< EdgeT, IDT >::EdgeT_, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::maxWeightPath	(	IDT	from_id,
		IDT	to_id
	)		const

inline

Obtain the maximum weight and its corresponding path between two nodes.

This finds the maximum weight path with the Djkstra algorithm. So all weights should be non-negative.
Example use:

DGraphBase<double> dgb3;
dgb3.insertEdge("A", "B", 1.2);
dgb3.insertEdge("A", "C", 0.5);
dgb3.insertEdge("C", "B", 1.5);
auto [w, n] = dgb3.maxWeightPath("A", "B"); // w is weight, n is path

Note: EdgeT should be arithmetic, i.e. edge data represents the weight.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (std::pair<EdgeT, std::vector<IDT>>) The maximum weight and its corresponding path.

Here is the caller graph for this function:

◆ maxWeightPath() [2/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , NonFunc Fn, typename... Args>
requires EdgeVT<EdgeT>

std::pair< Ret, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::maxWeightPath	(	IDT	from_id,
		IDT	to_id,
		Fn	func,
		Args...	args
	)		const

inline

Obtain the maximum weight and its corresponding path between two nodes.

This finds the maximum weight path with the Djkstra algorithm. So all weights should be non-negative.
Example use:

struct DataT {
    double data = 0;
    int foo     = 0;
};
DGraphBase<DataT> dgb2;
dgb2.insertEdge("A", "B", DataT{ 1.2, 1 });
dgb2.insertEdge("A", "C", DataT{ 0.5, 1 });
dgb2.insertEdge("C", "B", DataT{ 1.5, 1 });
auto [w, n] = dgb2.maxWeightPath<double>("A", "B", [](DataT x) { return x.data; });

Template Parameters

Ret	The weight type, i.e. Lambda function return type.
Fn	The Lambda expression type.
Args	The Lambda expression argument types.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The Lambda expression.
args	The Lambda expression arguments.

Returns: (std::pair<Ret, std::vector<IDT>>) The maximum weight and its corresponding path.

◆ maxWeightPath() [3/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , typename... Args>
requires EdgeVT<EdgeT>

std::pair< Ret, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::maxWeightPath	(	IDT	from_id,
		IDT	to_id,
		std::function< Ret(EdgeT_, Args...)>	func,
		Args...	args
	)		const

inline

Obtain the maximum weight and its corresponding path between two nodes.

This finds the maximum weight path with the Djkstra algorithm. So all weights should be non-negative.

Template Parameters

Ret	The weight type, i.e. `std::function` return type.
Args	`std::function` argument types.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The `std::function`.
args	The `std::function` arguments.

Returns: (std::pair<Ret, std::vector<IDT>>) The maximum weight and its corresponding path.

◆ merge()

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::merge ( const DGraphBase< EdgeT, IDT > & dg )

inline

Merge a graph into the main graph.

Parameters

dg	The graph to be merged.

Here is the caller graph for this function:

◆ minOrMaxWeightPath()

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , typename... Args>
requires EdgeVT<EdgeT>

std::pair< Ret, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::minOrMaxWeightPath	(	bool	min,
		IDT	from_id,
		IDT	to_id,
		std::function< Ret(EdgeT_, Args...)>	func,
		Args...	args
	)		const

inlineprivate

Obtain the minimum/maximum weight and its corresponding path between two nodes.

Template Parameters

Ret	The weight type, i.e. Lambda function return type.
Args	`std::function` argument types.

Parameters

min	Whether to find the minimum or maximum weight.
from_id	The from node id.
to_id	The to node id.
func	The `std::function`.
args	The `std::function` arguments.

Returns: (std::pair<Ret, std::vector<IDT>>) The minimum/maximum weight and its corresponding path.

Here is the call graph for this function:

◆ minWeightPath() [1/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT> && std::is_arithmetic_v<EdgeT>

std::pair< typename DGraphBase< EdgeT, IDT >::EdgeT_, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::minWeightPath	(	IDT	from_id,
		IDT	to_id
	)		const

inline

Obtain the minimum weight and its corresponding path between two nodes.

This finds the minimum weight path with the Djkstra algorithm. So all weights should be non-negative.
Example see maxWeightPath().

Note: EdgeT should be arithmetic, i.e. edge data represents the weight.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (std::pair<EdgeT, std::vector<IDT>>) The minimum weight and its corresponding path.

Here is the caller graph for this function:

◆ minWeightPath() [2/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , NonFunc Fn, typename... Args>
requires EdgeVT<EdgeT>

std::pair< Ret, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::minWeightPath	(	IDT	from_id,
		IDT	to_id,
		Fn	func,
		Args...	args
	)		const

inline

Obtain the minimum weight and its corresponding path between two nodes.

This finds the minimum weight path with the Djkstra algorithm. So all weights should be non-negative.
Example see maxWeightPath().

Template Parameters

Ret	The weight type, i.e. Lambda function return type.
Fn	The Lambda expression type.
Args	The Lambda expression argument types.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The Lambda expression.
args	The Lambda expression arguments.

Returns: (std::pair<Ret, std::vector<IDT>>) The maximum weight and its corresponding path.

◆ minWeightPath() [3/3]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

template<typename Ret , typename... Args>
requires EdgeVT<EdgeT>

std::pair< Ret, std::vector< IDT > > dg::DGraphBase< EdgeT, IDT >::minWeightPath	(	IDT	from_id,
		IDT	to_id,
		std::function< Ret(EdgeT_, Args...)>	func,
		Args...	args
	)		const

inline

Obtain the minimum weight and its corresponding path between two nodes.

This finds the minimum weight path with the Djkstra algorithm. So all weights should be non-negative.

Template Parameters

Ret	The weight type, i.e. `std::function` return type.
Args	`std::function` argument types.

Parameters

from_id	The from node id.
to_id	The to node id.
func	The `std::function`.
args	The `std::function` arguments.

Returns: (std::pair<Ret, std::vector<IDT>>) The minimum weight and its corresponding path.

◆ nodesID()

template<typename EdgeT , IDVT IDT>

std::vector< IDT > dg::DGraphBase< EdgeT, IDT >::nodesID

Get all nodes IS in the graph.

Returns: (std::vector<IDT>) A vector of nodes ID.

Here is the caller graph for this function:

◆ numEdges()

template<typename EdgeT , IDVT IDT>

size_t dg::DGraphBase< EdgeT, IDT >::numEdges

inlinenoexcept

The total number of edges in the graph.

Returns: (size_t) The number of edges.

Here is the caller graph for this function:

◆ numNodes()

template<typename EdgeT , IDVT IDT>

size_t dg::DGraphBase< EdgeT, IDT >::numNodes

inlinenoexcept

The total number of nodes in the graph.

Returns: (size_t) The number of nodes.

Here is the caller graph for this function:

◆ operator!=()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::operator!= ( const DGraphBase< EdgeT, IDT > & dg ) const

inline

Check if two graphs are different.

Parameters

dg	Another graph.

Return values

true	The two graphs are different.
false	The two graphs are identical.

Here is the caller graph for this function:

◆ operator()() [1/2]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

DGraphBase< EdgeT, IDT >::EdgeT_R dg::DGraphBase< EdgeT, IDT >::operator()	(	IDT	from_id,
		IDT	to_id
	)

inline

Get the edge data reference between two nodes.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (EdgeT_R) The edge data reference.

Here is the call graph for this function:

◆ operator()() [2/2]

template<typename EdgeT , IDVT IDT>
requires EdgeVT<EdgeT>

EdgeT dg::DGraphBase< EdgeT, IDT >::operator()	(	IDT	from_id,
		IDT	to_id
	)		const

inline

Get the edge data between two nodes.

Note: EdgeT should not be void.

Parameters

from_id	The from node id.
to_id	The to node id.

Returns: (EdgeT) The edge data.

Here is the call graph for this function:

◆ operator+=()

template<typename EdgeT , IDVT IDT>

DGraphBase< EdgeT, IDT > & dg::DGraphBase< EdgeT, IDT >::operator+= ( const DGraphBase< EdgeT, IDT > & dg )

inline

Merge two graphs.

This is an alias for merge().

Parameters

dg	Another graph.

Returns: (DGraphBase&) The merged graph (as a reference).

Here is the call graph for this function:

◆ operator==()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::operator== ( const DGraphBase< EdgeT, IDT > & dg ) const

inline

Check if two graphs are identical.

All nodes and edges should be the same.

Parameters

dg	Another graph.

Return values

true	The two graphs are identical.
false	The two graphs are different.

Here is the caller graph for this function:

◆ removeNode()

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::removeNode	(	IDT	id,
		bool	keep_edge = `false`
	)

Remove the node from the graph.

Exceptions

dg::node_not_exists Removes a non-existent node. Use removeNodeIfExists() to avoid the exception.

Parameters

id	The node id.
keep_edge	Whether keeps the connected edges after removing the node (default as false).

Here is the call graph for this function:

Here is the caller graph for this function:

◆ removeNodeConnectedEdges()

template<typename EdgeT , IDVT IDT>

size_t dg::DGraphBase< EdgeT, IDT >::removeNodeConnectedEdges ( IDT id )

private

Remove edges connected to a node.

Parameters

id	The node id.

Returns: (size_t) The number of removed edges.

Here is the caller graph for this function:

◆ removeNodeIfExists()

template<typename EdgeT , IDVT IDT>

void dg::DGraphBase< EdgeT, IDT >::removeNodeIfExists	(	IDT	id,
		bool	keep_edge = `false`
	)

Remove the node from the graph if it exists.

Nothing will be done if the node does not exist.

Parameters

id	The node id.
keep_edge	Whether keeps the connected edges after removing the node (default as false).

Here is the call graph for this function:

◆ size()

template<typename EdgeT , IDVT IDT>

size_t dg::DGraphBase< EdgeT, IDT >::size

inlinenoexcept

The total number of nodes in the graph.

This is the alias for numNodes().

Returns: (size_t) The number of edges.

Here is the call graph for this function:

◆ strictCheck()

template<typename EdgeT , IDVT IDT>

bool dg::DGraphBase< EdgeT, IDT >::strictCheck

inline

Check if the graph is strictly valid.

A graph is strictly valid if:

All nodes set by the edges are in the graph.
Return values

true

false

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ g

template<typename EdgeT = void, IDVT IDT = std::string>

std::map<IDT, _CN> dg::DGraphBase< EdgeT, IDT >::g

private

the main graph

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

include/dg-cpp/base.hpp

Public Member Functions

Protected Types

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ _CN

◆ _ET

◆ EdgeT_

◆ EdgeT__

◆ EdgeT_CR

◆ EdgeT_CR_

◆ EdgeT_R

◆ EdgeT_R_

Constructor & Destructor Documentation

◆ DGraphBase()

Member Function Documentation

◆ clear()

◆ clearEdges()

◆ edge() [1/4]

◆ edge() [2/4]

◆ edge() [3/4]

◆ edge() [4/4]

◆ edges()

◆ graph() [1/2]

◆ graph() [2/2]

◆ hasEdge()

◆ hasNode()

◆ insertEdge() [1/2]

◆ insertEdge() [2/2]

◆ insertEdgeToExists() [1/2]

◆ insertEdgeToExists() [2/2]

◆ insertNode() [1/3]

◆ insertNode() [2/3]

◆ insertNode() [3/3]

◆ insertSubGraph() [1/2]

◆ insertSubGraph() [2/2]

◆ isConnected()

◆ maxWeightPath() [1/3]

◆ maxWeightPath() [2/3]

◆ maxWeightPath() [3/3]

◆ merge()

◆ minOrMaxWeightPath()

◆ minWeightPath() [1/3]

◆ minWeightPath() [2/3]

◆ minWeightPath() [3/3]

◆ nodesID()

◆ numEdges()

◆ numNodes()

◆ operator!=()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator+=()

◆ operator==()

◆ removeNode()

◆ removeNodeConnectedEdges()

◆ removeNodeIfExists()

◆ size()

◆ strictCheck()

Member Data Documentation

◆ g