Class ReachableNodes¶

Inheritance Relationships¶

Class Documentation¶

class ReachableNodes : public NetworKit::Algorithm¶

Public Functions

ReachableNodes(const Graph &G, bool exact = true)¶

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

Parameters:

• G – The graph.

• exact – 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.

virtual void run() override¶

Runs the algorithm.

inline count numberOfReachableNodes(node u) const¶

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

Parameters:

u – A node.

Returns:

The number of nodes reachable from u.

inline count numberOfReachableNodesLB(node u) const¶

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

Parameters:

u – A node.

Returns:

Lower bound of number of nodes reachable from u.

inline count numberOfReachableNodesUB(node u) const¶

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

Parameters:

u – A node.

Returns:

Upper bound of number of nodes reachable from u.

Public Members

bool exact¶