[1]:
import networkit as nk
[2]:
# Read a graph
G = nk.readGraph("../input/foodweb-baydry.konect", nk.Format.KONECT)
GDir = G
source = 0
target = 27
This algorithm computes all existing simple paths from a source node to a target node.
The AllSimplePaths(G, source, target, cutoff=none) constructor expects an unweighted graph, the source node and the target node as mandatory parameters. The maximum length of the paths can be fixed through cutoff parameter. This algorithm could take a lot of time on large networks (many edges), especially if the cutoff value is high or not specified.
The algorithm is implemented only for unweighted graphs, so we shall convert G to an unweighted graph.
[3]:
GUnweighted = nk.graphtools.toUnweighted(GDir)
# Initialize algorithm
asp = nk.reachability.AllSimplePaths(GUnweighted, source, target, 5).run()
[4]:
# The number of simple paths in the graph
print(asp.numberOfSimplePaths())
# The list of all paths
paths = asp.getAllSimplePaths()
# Print first simple path node 0
print(paths[0])
5582
[0, 1, 96, 92, 29, 27]
This algorithm computes/estimates the number of reachable nodes from each node in the graph
It takes as input a graph and a boolean value exact to determine (in directed graphs) whether to compute the exact number of reachable nodes (set to True), or an estimation (set to False). The estimation is only done in directed graphs where to compute the number of reachable nodes is expensive. In undirected graphs the number of reachable nodes is always computed exactly in linear time.
[5]:
# Exact computation
rn = nk.reachability.ReachableNodes(G).run()
u = 27
print("Number of nodes reachable from {:d}: {:d}".format(u, rn.numberOfReachableNodes(u)))
Number of nodes reachable from 27: 105
[6]:
# Estimate
rn = nk.reachability.ReachableNodes(G, False).run()
u = 55
print("Number of nodes reachable from {:d} is at least {:d} and at most {:d}".format(u, rn.numberOfReachableNodesLB(u), rn.numberOfReachableNodesUB(u)))
Number of nodes reachable from 55 is at least 106 and at most 107