networkit.reachability¶

class networkit.reachability.AllSimplePaths(G, source, target, cutoff=None)¶

Bases: Algorithm

Algorithm to compute all existing simple paths from a source node to a target node. The maximum length of the paths can be fixed through ‘cutoff’.

Note

CAUTION: This algorithm could take a lot of time on large networks (many edges), especially if the cutoff value is high or not specified.

Parameters:

• G (networkit.Graph) – The input graph.

• source (int) – The source node.

• target (int) – The target node.

• cutoff (int, optional) – The maximum length of the simple paths. Default: None

forAllSimplePaths(callback)¶

More efficient path iterator. Iterates over all the simple paths.

Parameters:

callback (object) – Any callable object that takes the parameter path

getAllSimplePaths()¶

Returns all the simple paths from source to target.

Returns:

A list containing all simple paths (each represented by a list of nodes).

Return type:

list(list(int))

numberOfSimplePaths()¶

Returns the number of simple paths.

Returns:

The number of simple paths.

Return type:

int

class networkit.reachability.ReachableNodes(G, exact)¶

Bases: Algorithm

Determines or estimates the number of reachable nodes from each node in the graph.

Parameters:

• G (networkit.Graph) – The input graph.

• exact (bool) – Whether or not to compute the number of reachable nodes exactly. Only used for directed graphs, on undirected graphs the number of reachable nodes from every node can be computed in linear time.

exact¶

numberOfReachableNodes(u)¶

Returns the number of reachable nodes from the given node ‘u’. Only available if ‘exact’ is true.

Parameters:

u (int) – A node.

Returns:

The number of nodes reachable from ‘u’.

Return type:

int

numberOfReachableNodesLB(u)¶

Returns a lower bound of the number of reachable nodes from the given node ‘u’.

Parameters:

u (int) – A node.

Returns:

Lower bound of number of nodes reachable from ‘u’.

Return type:

int

numberOfReachableNodesUB(u)¶

Returns an upper bound of the number of reachable nodes from the given node ‘u’.

Parameters:

u (int) – A node.

Returns:

Upper bound of number of nodes reachable from ‘u’.

Return type:

int