= Reachability =

<<TableOfContents>>

== 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 <a,b> 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.

== Predicates ==

 * '''Input''': {{{edge/2}}}

 * '''Query''': {{{reaches/2}}}

 * '''Output''': {{{reaches/2}}}

== 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 in the facts for the binary predicate reaches, as {{{reaches(a,b)?}}} asking whether node 'b' is reachable from node 'a'. Only ground queries are provided.

== Output format ==

If the answer to the input query, say, {{{reaches(a,b)}}}, is positive (i.e., b is reachable from a), then the output should be a single fact representing the query itself;
if the query is false, the output is nothing (thus resulting in an empty row).

== Example(s) ==

Input:
{{{edge(1,3). edge(3,4). edge(3,5). edge(4,2). edge(2,5). reaches(1,2)?}}}

Possible Output:
{{{reaches(1,2).}}}

== Author(s) ==
 * Author: Giorgio Terracina
   * Affiliation: University of Calabria, Italy