Reachability problem
 

Given a directed graph G=(V,E), compute all pairs of nodes (a,b) such that b is reachable from a through a sequence of edges in E. In database terms, the problem amounts to computing the transitive closure of the relation containing the edges.

INPUT: Relation "edge/2". A fact "edge(a,b)" means that there is an edge from a to b in G (we assume that the set of vertices in G is {1,2,...,n}).

OUTPUT: The "reachable/2" relation containing all facts of the form reachable(a,b) such that b is reachable from a through the edges of the input graph G.

DATA SETS: The following relations (graphs) where generated with the help of the Stanford GraphBase system. The whole collection, six graphs: B30, R-150-11000-804, R-250-9000-74, R-350-5000-101, R-400-3500-8 and  R-500-3000-138, is available in the following tarred and gzipped file:

reachability_data.tar.gz
 

NOTES: