Static network reachability#
The algorithms described in this page deal with the topic of reachability in different network types. Reachability is the ability to get from one vertex to another, but only through edges of the network. If the network is directed, the path between two vertices should always be following the directions of the edges.
The functions presented here accept both static dyadic and hypernetworks.
Temporal reachability functions#
Weak-connectivity#
Finds the weakly-connected component for vertex vert. The parameter
size_hint can help reduce memory re-allocations if you already have a
rough estimate (or even better: a good upper-bound) on the weakly-connected
component size you expect to get. If not, you can rely on the default behaviour.
Returns all weakly-connected components of the parameter network. Implementation is based on consecutive unions on a disjoint-set data structure of vertices [11, 12].
If you are not interested in weakly-connected components with only a single
vertex, set the singletons to false.
Returns the largest weakly-connected component by number of vertices. If the network is empty, an empty component is returned. If multiple components of maximum size exist, one of them is arbitrarily returned.
- is_weakly_connected(directed_network) bool#
-
template<directed_static_network_edge EdgeT>
bool is_weakly_connected(const network<EdgeT> &dir)#
Returns true if the network is weakly-connected: if all pairs of vertices can be connected through the network edges, if we forget about the directions of those edges, i.e., there exists an undirected path between every pair of vertices.
In- and out-components#
From a single source#
Calculate the in- or out-component of a vertex in a static directed network.
From all vertices#
Calculates the in- or out-components of all vertices in a static directed network.
In- and out-component sizes#
- in_component_sizes(directed_network) iterable[pair[vert_type, component_size[vert_type]]]#
- out_component_sizes(directed_network) iterable[pair[vert_type, component_size[vert_type]]]#
-
template<directed_static_network_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component_size<typename EdgeT::VertexType>>> in_component_sizes(const network<EdgeT> &dir)#
-
template<directed_static_network_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component_size<typename EdgeT::VertexType>>> out_component_sizes(const network<EdgeT> &dir)#
Calculates the in- or out-component sizes of all vertices in a static directed network. Compared to calculating all in- or out-components, this uses less memory in some cases.
In- and out-component size estimates#
- in_component_size_estimates(directed_network) iterable[pair[vert_type, component_size_estimate[vert_type]]]#
- out_component_size_estimates(directed_network) iterable[pair[vert_type, component_size_estimate[vert_type]]]#
-
template<directed_static_network_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component_size_estimate<typename EdgeT::VertexType>>> in_component_size_estimates(const network<EdgeT> &dir, std::size_t seed = 0)#
-
template<directed_static_network_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component_size_estimate<typename EdgeT::VertexType>>> out_component_size_estimates(const network<EdgeT> &dir, std::size_t seed = 0)#
Estimates the in- or out-component sizes of all vertices in a static directed network. Compared to calculating all in- or out-components and in- and out-component sizes, this uses much less memory and is much faster to run in many cases.
Undirected static networks#
Connected component of a specific vertex#
Returns the connected component that vertex vert belongs to. A connected
component is a maximal subset of vertices of the network where all vertices can
reach all others.
All connected components#
- connected_components(undirected_network, singletons: bool = True) Iterable[components[vert_type]]#
Returns all connected components of the static undirected network.
Returns the largest connected component by number of vertices. If the network is empty, an empty component is returned. If multiple components of maximum size exist, one of them is arbitrarily returned.
- is_connected(undirected_network) bool#
-
template<undirected_static_network_edge EdgeT>
bool is_connected(const network<EdgeT> &net);#
Returns true if all vertices of the network are reachable from all other.
Source-destination reachability#
- is_reachable(network, source, destination) bool#
Returns true if the vertex destination is reachable from the
vertex source by following edges in the legal direction. This function
accepts all static network types.
Shortest path length#
- shortest_path_lengths_from(network, source)#
Returns a dictionary (an unordered map) mapping all vertices reachable from the source vertex to their shortest path length from the source vertex.
- shortest_path_lengths_to(network, destination)#
Returns a dictionary (an unordered map) mapping all vertices that can reach the destination vertex to their shortest path length to the destination vertex.
Static Component types#
-
template<network_vertex VertT>
class component# -
type VertexType#
-
type IteratorType#
-
template<ranges::input_range Range>
requires std::convertible_to<ranges::range_value_t<Range>, VertT>
void insert(Range &&verts)#
-
std::size_t size() const#
-
IteratorType begin() const#
-
IteratorType end() const#
-
type VertexType#
A component is a set of network vertices. Components are iterable both in C++,
through satisfying the std::ranges::forward_range and
std::ranges::sized_range concepts, and in Python by implementing
__iter__.
-
template<network_vertex VertT>
class component_size# -
type VertexType#
-
std::size_t size() const#
-
type VertexType#