networkit.reachability

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

Bases: networkit.base.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: networkit.base.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