= 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) and a couple of nodes of V, the solution to the Reachability problem reachable(a,b) determines whether node b is reachable from node a through a 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 a set of facts for the binary predicate reaches(n1,n2) containing (at least) all nodes of some path from a to b (witnessing that b is actually reachable from a). == 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(s) == Author: Giorgio Terracina <
> Affiliation: University of Calabria, Italy