Reachability
Problem description
Reachability is one of the best studied problems in computer science. Instances
of the reachability problem occurr, directly or indirectly, in a lot of relevant
real world applications, ranging from databases to product configurations and networks.
Given a directed graph G=(V,E), a couple of
nodes of V belongs to the Reachability relation (also called the transitive closure relation) if there is a -empty path from a to b through a non-empty sequence of edges in E. The input is provided by a relation
edge(X,Y) where a fact edge(i,j) states that node j is directly reachable by an edge in E from node i, and by one tuple (fact) of the form query(a,b) .
In database terms, determining all pairs of reachable nodes in G amounts to computing
the transitive closure of the relation storing the edges.
Input format
The input graph is represented by the set of its edges. The predicate used to define
edges is a binary predicate "edge" where edge(a,b) means that there is a directed
edge going from a to b:
edge(1,3). edge(3,4). edge(4,2). edge(3,5). edge(2,5).
The query is encoded by a single fact for the binary predicate "query", where query(a,b)
asks whether node 'b' is reachable starting from node 'a'.
Output format
If the answer to the input query, say, query(a,b), is positive (i.e., b
is reachable from a), then the output should be given by the predicate
reaches which is a subset of the reachability relation of the edge
relation such that for some path (a n1 ... nk b), the output includes at least all atoms reaches(a,n1), reaches(a,n2),..,reaches(a,nk), reaches(a,b).
Example
Input:
edge(1,3). edge(3,4). edge(3,5). edge(4,2). edge(2,5). query(1,2).
Possible Output:
reaches(1,3). reaches(1,4). reaches(1,2).
Author: Giorgio Terracina
|