welcome:
location: ProblemsDescription / Reachability

# 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 <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.

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

ASP Competition 2011: ProblemsDescription/Reachability (last edited 2011-01-10 10:29:40 by CarmenSantoro)