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

Python

weakly_connected_component(directed_network, vert: vert_type, size_hint: int = 0) → component[vert_type]

C++

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.

Python

weakly_connected_components(directed_network, singletons: bool = True) → Iterable[component[vert_type]]

C++

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.

Python

largest_weakly_connected_component(directed_network) → component[vert_type]

C++

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.

Python

is_weakly_connected(directed_network) → bool

C++

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

Python

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]

C++

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

Python

in_components(directed_network) → iterable[pair[vert_type, component[vert_type]]]

out_components(directed_network) → iterable[pair[vert_type, component[vert_type]]]

C++

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

Python

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

C++

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

Python

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

C++

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

Python

connected_component(undirected_network, vert: vert_type, size_hint: int = 0) → component[vert_type]

C++

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

Python

connected_components(undirected_network, singletons: bool = True) → Iterable[components[vert_type]]

C++

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.

Python

largest_connected_component(undirected_network) → component[vert_type]

C++

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.

Python

is_connected(undirected_network) → bool

C++

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

Python

is_reachable(network, source, destination) → bool

C++

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

Python

shortest_path_lengths_from(network, source)

C++

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.

Python

shortest_path_lengths_to(network, destination)

C++

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

Python

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

C++

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

Python

class component_size[vert_type]

size() → int

static vertex_type() → type

C++

template<network_vertex VertT>
class component_size

type VertexType

std::size_t size() const

Python

class component_size_estimate[vert_type]

size_estimate() → float

static vertex_type() → type

C++

template<network_vertex VertT>
class component_size_estimate

type VertexType

double size_estimate() const