= 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 {{{reaches(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/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 by a single fact for the binary predicate "query", where {{{query(a,b)}}} asks whether node 'b' is reachable starting from node 'e'.

== 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