|
Size: 69
Comment:
|
Size: 1985
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| Inserire una descrizione per FinalProblemDescriptions/Reachability. | = 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 |
Reachability
Contents
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