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.

Component types#

class component[vert_type]#
template<network_vertex VertT>
class component#

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__.

class component_size[vert_type]#
template<network_vertex VertT>
class component_size#
class component_size_estimate[vert_type]#
template<network_vertex VertT>
class component_estimate#

Weak-connectivity#

weakly_connected_component(directed_network, vert: vert_type, size_hint: int = 0) component[vert_type]#
template<static_directed_edge EdgeT>
component<typename EdgeT::VertexType> weakly_connected_component(const network<EdgeT> &dir, const typename EdgeT::VertexType &vert, std::size_t size_hint = 0)#

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.

weakly_connected_components(directed_network, singletons: bool = True) Iterable[component[vert_type]]#
template<static_directed_edge EdgeT>
std::vector<component<typename EdgeT::VertexType>> weakly_connected_components(const network<EdgeT> &dir, bool singletons = true)#

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.

largest_weakly_connected_component(directed_network) component[vert_type]#
template<static_directed_edge EdgeT>
component<typename EdgeT::VertexType> largest_weakly_connected_component(const network<EdgeT> &dir)#

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<static_directed_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#

in_component(directed_network, vert: vert_type, size_hint: int = 0) component[vert_type]#
out_component(directed_network, vert: vert_type, size_hint: int = 0) component[vert_type]#
template<static_directed_edge EdgeT>
component<typename EdgeT::VertexType> in_component(const network<EdgeT> &dir, const typename EdgeT::VertexType &root, std::size_t size_hint = 0)#
template<static_directed_edge EdgeT>
component<typename EdgeT::VertexType> out_component(const network<EdgeT> &dir, const typename EdgeT::VertexType &root, std::size_t size_hint = 0)#

Calculate the in- or out-component of a vertex in a static directed network.

From all vertices#

in_components(directed_network) iterable[pair[vert_type, component[vert_type]]]#
out_components(directed_network) iterable[pair[vert_type, component[vert_type]]]#
template<static_directed_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component<typename EdgeT::VertexType>>> in_components(const network<EdgeT> &dir)#
template<static_directed_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component<typename EdgeT::VertexType>>> out_components(const network<EdgeT> &dir)#

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<static_directed_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component_size<typename EdgeT::VertexType>>> in_component_sizes(const network<EdgeT> &dir)#
template<static_directed_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<static_directed_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<static_directed_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#

connected_component(undirected_network, vert: vert_type, size_hint: int = 0) component[vert_type]#
template<static_undirected_edge EdgeT>
component<typename EdgeT::VertexType> connected_component(const network<EdgeT> &net, const typename EdgeT::VertexType &vert, std::size_t size_hint = 0)#

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]]#
template<static_undirected_edge EdgeT>
std::vector<component<typename EdgeT::VertexType>> connected_components(const network<EdgeT> &net, bool singletons = true)#

Returns all connected components of the static undirected network.

largest_connected_component(undirected_network) component[vert_type]#
template<static_undirected_edge EdgeT>
component<typename EdgeT::VertexType> largest_connected_component(const network<EdgeT> &net)#

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<static_undirected_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#
template<static_edge EdgeT>
bool is_reachable(const network<EdgeT> &net, const typename EdgeT::VertexType &source, const typename EdgeT::VertexType &destination)#

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)#
template<static_edge EdgeT>
std::unordered_map<typename EdgeT::VertexType, std::size_t, hash<typename EdgeT::VertexType>> shortest_path_lengths_from(const network<EdgeT> &net, const typename EdgeT::VertexType &vert)#

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)#
template<static_edge EdgeT>
std::unordered_map<typename EdgeT::VertexType, std::size_t, hash<typename EdgeT::VertexType>> shortest_path_lengths_to(const network<EdgeT> &net, const typename EdgeT::VertexType &vert)#

Returns a dictionary (an unordered map) mapping all vertices that can reach the destination vertex to their shortest path length to the destination vertex.