|
Size: 1962
Comment:
|
Size: 2034
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
== Predicates == * '''Input''': edge/2, query/2 * '''Output''': reaches/2 |
|
| Line 16: | Line 10: |
| 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) . |
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)}}} . |
| Line 21: | Line 14: |
| == Predicates == * '''Input''': {{{edge/2, query/2}}} * '''Output''': {{{reaches/2}}} |
|
| Line 23: | Line 22: |
| 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: | 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: {{{ |
| Line 30: | Line 29: |
| }}} | |
| Line 31: | Line 31: |
| 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'. | 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'. |
| Line 35: | Line 35: |
| 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). | 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). |
| Line 40: | Line 40: |
| edge(1,3). edge(3,4). edge(3,5). edge(4,2). edge(2,5). query(1,2). | {{{edge(1,3). edge(3,4). edge(3,5). edge(4,2). edge(2,5). query(1,2).}}} |
| Line 42: | Line 42: |
| reaches(1,3). reaches(1,4). reaches(1,2). | {{{reaches(1,3). reaches(1,4). reaches(1,2).}}} |
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 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