dsf::Network< node_t, edge_t > Class Template Reference

Public Member Functions
	Network ()=default
	Construct a new empty Network object.
auto	nodes () const noexcept
	Get the nodes as a view of (id, pointer to const node) pairs.
auto	nodes () noexcept
	Get the nodes as a view of (id, pointer to node) pairs.
auto	edges () const noexcept
	Get the edges as a view of (id, pointer to const edge) pairs.
auto	edges () noexcept
	Get the edges as a view of (id, pointer to edge) pairs.
auto	nNodes () const noexcept
	Get the number of nodes.
auto	nEdges () const noexcept
	Get the number of edges.
template<typename TNode = node_t, typename... TArgs> requires (std::is_base_of_v<node_t, TNode> && std::constructible_from<TNode, TArgs...>)
void	addNode (TArgs &&... args)
template<typename TNode = node_t> requires (std::is_base_of_v<node_t, TNode>)
void	addNDefaultNodes (std::size_t const n)
template<typename TEdge = edge_t, typename TNode = node_t, typename... TArgs> requires (std::is_base_of_v<edge_t, TEdge> && std::is_base_of_v<node_t, TNode> && std::constructible_from<TEdge, Id, std::pair <Node*, Node*>, TArgs...>)
TEdge &	addEdge (Id const edgeId, std::pair< Id, Id > const nodeIds, TArgs &&... args)
	Add an edge between two nodes, creating the missing ones.
virtual void	setEdgeWeight (std::string_view const strv_weight, std::optional< double > const threshold=std::nullopt)=0
const auto &	node (Id const nodeId) const
	Get a node by id.
auto &	node (Id const nodeId)
	Get a node by id.
const auto &	edge (Id const edgeId) const
	Get an edge by id.
auto &	edge (Id const edgeId)
	Get an edge by id.
edge_t &	edge (Id const source, Id const target) const
template<typename TNode> requires (std::is_base_of_v<node_t, TNode>)
auto &	node (Id const nodeId)
	Get a node by id and cast it to a derived type.
template<typename TEdge> requires (std::is_base_of_v<edge_t, TEdge>)
auto &	edge (Id const edgeId)
	Get an edge by id and cast it to a derived type.
PathCollection	allPathsTo (Id const targetId) const
	Perform a global Dijkstra search to a target node from all other nodes in the graph.
PathCollection	shortestPath (Id const sourceId, Id const targetId) const
	Find the shortest path between two nodes using Dijkstra's algorithm.
void	computeBetweennessCentralities ()
	Compute node weighted betweenness centralities using Brandes' algorithm.
void	computeEdgeBetweennessCentralities ()
	Compute edge weighted betweenness centralities using Brandes' algorithm.
void	computeEdgeKBetweennessCentralities (std::size_t const K)
	Compute edge betweenness centralities using Yen's K-shortest paths.

Protected Member Functions
edge_t *	m_findEdge (Id const source, Id const target) const
	Find the edge going from source to target.
template<typename TNode, typename... TArgs> requires (std::is_base_of_v<node_t, TNode> && std::constructible_from<TNode, node_t const&, TArgs...>)
TNode &	m_replaceNode (std::unique_ptr< node_t > &pNode, TArgs &&... args)
	Replace a node with a new object of type TNode, built from the old one.

Static Protected Member Functions
static constexpr auto	m_cantorHash (Id u, Id v) noexcept
static constexpr auto	m_cantorHash (std::pair< Id, Id > const &idPair) noexcept
static auto	m_inEdges (node_t const &node) noexcept
static auto	m_outEdges (node_t const &node) noexcept
static node_t *	m_targetOf (edge_t const &edge) noexcept

Protected Attributes
std::unordered_map< Id, std::unique_ptr< node_t > >	m_nodes
std::unordered_map< Id, std::unique_ptr< edge_t > >	m_edges
std::function< double(edge_t const &)>	m_weightFunction
std::optional< double >	m_weightThreshold = std::nullopt

Member Function Documentation

addEdge()

template<typename node_t, typename edge_t>
requires (std::is_base_of_v<edge_t, TEdge> && std::is_base_of_v<node_t, TNode> && std::constructible_from<TEdge, Id, std::pair
<Node*, Node*>, TArgs...>)

template<typename TEdge, typename TNode, typename... TArgs>
requires (std::is_base_of_v<edge_t, TEdge> && std::is_base_of_v<node_t, TNode> && std::constructible_from<TEdge, Id, std::pair
<Node*, Node*>, TArgs...>)

TEdge & dsf::Network< node_t, edge_t >::addEdge	(	Id const	edgeId,
		std::pair< Id, Id > const	nodeIds,
		TArgs &&...	args )

Add an edge between two nodes, creating the missing ones.

Template Parameters

TEdge	The type of the edge
TNode	The type of the nodes created for the edge

Parameters

edgeId	The edge's id
nodeIds	The ids of the edge's (source, target) nodes
args	Extra arguments forwarded to TEdge's constructor, after the nodes

Returns

TEdge& A reference to the new edge

Exceptions

std::invalid_argument

if an edge with the same id already exists

allPathsTo()

template<typename node_t, typename edge_t>
requires (std::is_base_of_v<Node, node_t> && std::is_base_of_v<Edge, edge_t>)

PathCollection dsf::Network< node_t, edge_t >::allPathsTo ( Id const targetId ) const

inline

Perform a global Dijkstra search to a target node from all other nodes in the graph.

Parameters

threshold

Relative tolerance on full path cost from each node to the target

Returns

A map where each key is a node id and the value is a vector of next hop node ids toward the target

Exceptions

std::out_of_range

if the target node does not exist

Keeps only transitions that strictly decrease the precomputed shortest distance to target. This makes the hop graph acyclic, so PathCollection::explode remains finite.

computeEdgeKBetweennessCentralities()

template<typename node_t, typename edge_t>
requires (std::is_base_of_v<Node, node_t> && std::is_base_of_v<Edge, edge_t>)

void dsf::Network< node_t, edge_t >::computeEdgeKBetweennessCentralities

(

std::size_t const

K

)

Compute edge betweenness centralities using Yen's K-shortest paths.

For every ordered source–target pair (s, t) with s ≠ t the method finds up to K loopless shortest paths using Yen's algorithm. Each edge e that appears in at least one of those paths receives an increment equal to the number of those K paths that traverse it. After all pairs are processed the raw counts are normalised by (N−1)·(N−2), the number of ordered pairs in a directed graph of N nodes (same denominator used by the standard Brandes formulation).

The computation is parallelised over source nodes with Intel TBB: each thread maintains its own accumulator map, which are merged sequentially once all threads finish.

Parameters

K	Maximum number of shortest paths per (s, t) pair. K = 1 reproduces single-shortest-path betweenness.

edge() [1/3]

template<typename node_t, typename edge_t>

template<typename TEdge>
requires (std::is_base_of_v<edge_t, TEdge>)

auto & dsf::Network< node_t, edge_t >::edge ( Id const edgeId )

inline

Get an edge by id and cast it to a derived type.

Template Parameters

TEdge

The expected type of the edge

Parameters

edgeId

The id of the edge to get

Returns

TEdge& A reference to the edge with the given id, cast to the expected type

edge() [2/3]

template<typename node_t, typename edge_t>

auto & dsf::Network< node_t, edge_t >::edge ( Id const edgeId )

inline

Get an edge by id.

Parameters

edgeId

The id of the edge to get

Returns

edge_t& A reference to the edge with the given id

edge() [3/3]

template<typename node_t, typename edge_t>

const auto & dsf::Network< node_t, edge_t >::edge ( Id const edgeId ) const

inline

Get an edge by id.

Parameters

edgeId

The id of the edge to get

Returns

const edge_t& A const reference to the edge with the given id

m_findEdge()

template<typename node_t, typename edge_t>
requires (std::is_base_of_v<Node, node_t> && std::is_base_of_v<Edge, edge_t>)

edge_t * dsf::Network< node_t, edge_t >::m_findEdge ( Id const source, Id const target ) const

protected

Find the edge going from source to target.

Only the source node's outgoing edges are scanned, instead of all edges

Returns

edge_t* A pointer to the edge, or nullptr if it does not exist

m_replaceNode()

template<typename node_t, typename edge_t>

template<typename TNode, typename... TArgs>
requires (std::is_base_of_v<node_t, TNode> && std::constructible_from<TNode, node_t const&, TArgs...>)

TNode & dsf::Network< node_t, edge_t >::m_replaceNode ( std::unique_ptr< node_t > & pNode, TArgs &&... args )

inlineprotected

Replace a node with a new object of type TNode, built from the old one.

The new node keeps the old node's edges, whose source/target node pointers are re-linked to it. Any other reference to the old node dangles. Safe to call concurrently for different nodes: for an edge u -> v, u only writes the edge's source node and v only its target node.

Parameters

pNode	The network's owning pointer to the node to replace
args	Extra arguments forwarded to TNode's constructor, after the old node

Returns

TNode& A reference to the new node

node() [1/3]

template<typename node_t, typename edge_t>

template<typename TNode>
requires (std::is_base_of_v<node_t, TNode>)

auto & dsf::Network< node_t, edge_t >::node ( Id const nodeId )

inline

Get a node by id and cast it to a derived type.

Template Parameters

TNode

The expected type of the node

Parameters

nodeId

The id of the node to get

Returns

TNode& A reference to the node with the given id, cast to the expected type

node() [2/3]

template<typename node_t, typename edge_t>

auto & dsf::Network< node_t, edge_t >::node ( Id const nodeId )

inline

Get a node by id.

Parameters

nodeId

The id of the node to get

Returns

node_t& A reference to the node with the given id

node() [3/3]

template<typename node_t, typename edge_t>

const auto & dsf::Network< node_t, edge_t >::node ( Id const nodeId ) const

inline

Get a node by id.

Parameters

nodeId

The id of the node to get

Returns

const node_t& A const reference to the node with the given id

setEdgeWeight()

template<typename node_t, typename edge_t>

virtual void dsf::Network< node_t, edge_t >::setEdgeWeight ( std::string_view const strv_weight, std::optional< double > const threshold = std::nullopt )

pure virtual

Implemented in dsf::mobility::RoadNetwork.

shortestPath()

template<typename node_t, typename edge_t>
requires (std::is_base_of_v<Node, node_t> && std::is_base_of_v<Edge, edge_t>)

PathCollection dsf::Network< node_t, edge_t >::shortestPath ( Id const sourceId, Id const targetId ) const

inline

Find the shortest path between two nodes using Dijkstra's algorithm.

Parameters

sourceId	The id of the source node
targetId	The id of the target node

Returns

A map where each key is a node id and the value is a vector of next hop node ids toward the target. Returns an empty map if no path exists

Exceptions

std::out_of_range

if the source or target node does not exist

Uses Dijkstra's algorithm to compute strict distances to target, then includes only transitions that both: (1) strictly decrease the target distance (acyclic), and (2) are consistent with shortest source-distance labels. The second constraint keeps the returned PathCollection sound when exploded, i.e. it avoids combining prefix-dependent hops into over-budget paths.

Member Data Documentation

m_weightFunction

template<typename node_t, typename edge_t>

std::function<double(edge_t const&)> dsf::Network< node_t, edge_t >::m_weightFunction

protected

Initial value:

                           =
[]([[maybe_unused]] edge_t const& edge) {
  return 1.0;  
}

---

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

• src/dsf/base/Network.hpp