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

weakly_connected_component(directed_network, vert: vert_type, size_hint: int = 0) component[vert_type]
template<directed_static_network_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<directed_static_network_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 [12, 13].

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<directed_static_network_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<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

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<directed_static_network_edge EdgeT>
component<typename EdgeT::VertexType> in_component(const network<EdgeT> &dir, const typename EdgeT::VertexType &root, std::size_t size_hint = 0)
template<directed_static_network_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<directed_static_network_edge EdgeT>
std::vector<std::pair<typename EdgeT::VertexType, component<typename EdgeT::VertexType>>> in_components(const network<EdgeT> &dir)
template<directed_static_network_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<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

connected_component(undirected_network, vert: vert_type, size_hint: int = 0) component[vert_type]
template<undirected_static_network_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<undirected_static_network_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<undirected_static_network_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<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
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.

Static Component types

class component[vert_type](vertices: list[vert_type] = [], size_hint: int = 0)
insert(vertex: vert_type)
insert(vertices: list[vert_type])
merge(other: component[vert_type])
__eq__(other: component[vert_type])
__iter__()
__len__()
__contains__(vertex: vert_type)
static vertex_type() type
template<network_vertex VertT>
class component
type VertexType
type IteratorType
void insert(const VertT &vert)
template<ranges::input_range Range>
requires std::convertible_to<ranges::range_value_t<Range>, VertT>
void insert(Range &&verts)
void merge(const component<VertT> &other)
bool operator==(const component<VertT> &other) const
std::size_t size() const
bool contains(const VertT &vert) const
IteratorType begin() const
IteratorType end() const

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]
size() int
static vertex_type() type
template<network_vertex VertT>
class component_size
type VertexType
std::size_t size() const
class component_size_estimate[vert_type]
size_estimate() float
static vertex_type() type
template<network_vertex VertT>
class component_size_estimate
type VertexType
double size_estimate() const