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

Public Member Functions
	Network ()=default
	Construct a new empty Network object.
auto const &	nodes () const noexcept
	Get the nodes as an unordered map.
auto const &	edges () const noexcept
	Get the edges as an unordered map.
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... TArgs> requires (std::is_base_of_v<edge_t, TEdge> && std::constructible_from<TEdge, TArgs...>)
void	addEdge (TArgs &&... args)
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
constexpr auto	m_cantorHash (Id u, Id v) const
constexpr auto	m_cantorHash (std::pair< Id, Id > const &idPair) const

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

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

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