|
Size: 2036
Comment:
|
← Revision 13 as of 2011-02-01 09:23:36 ⇥
Size: 2993
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| 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. |
Reachability is one of the best studied problems in computer science. Instances of the reachability problem occur{, directly or indirectly, in a lot of relevant real world applications, ranging from databases to product configurations and networks. In database terms, determining all pairs of reachable nodes in a graph G amounts to computing the transitive closure of the relation storing the edges. The version of the problem for this competition comes in terms of queries to the transitive closure of G. |
| Line 10: | 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 {{{{G}}}, the truth of the atom {{{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 query of the form {{{reaches(a,b)?}}}. |
| Line 12: | Line 12: |
| In database terms, determining all pairs of reachable nodes in G amounts to computing the transitive closure of the relation storing the edges. | |
| Line 16: | Line 15: |
| * '''Input''': {{{edge/2, query/2}}} | * '''Input''': {{{edge/2}}} * '''Query''': {{{reaches/2}}} |
| Line 22: | Line 23: |
| 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 31: | Line 32: |
| 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 expressed as a ground atom of the binary predicate {{{reaches}}}: e.g. {{{reaches(a,b)?}}} asks whether node 'b' is reachable from node 'a'. Only ground queries are provided. |
| Line 35: | Line 36: |
| 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, {{{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), according the Competition Input and Output specification. |
| Line 37: | Line 39: |
| == Example == | == Notes and differences with previous versions of this problem == With respect to the Second ASP Competition, the goal query is herein made explicit by means of the {{{reaches(a,b)?}}} which shall be found in input instances. == Example(s) == |
| Line 40: | Line 46: |
| {{{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). reaches(1,2)?}}} |
| Line 43: | Line 49: |
| {{{reaches(1,3). reaches(1,4). reaches(1,2).}}} | {{{reaches(1,2).}}} == Problem Peculiarities == '''Type''': Polynomial/Query '''Competition''': both Model & Solve and System competition Reachability can be considered a classic polynomial problem, not to be considered too trivial. The instance graphs will be indeed quite large: rather than modelling abilities (we expect all competitors will adopt a pretty standard encoding in the M&S track also), this problem will stress memory usage and the ability of tailoring the search space at hand to what is needed for answering the goal query only. |
| Line 46: | Line 60: |
| Author: Giorgio Terracina <<BR>> Affiliation: University of Calabria, Italy |
* 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 occur{, directly or indirectly, in a lot of relevant real world applications, ranging from databases to product configurations and networks. In database terms, determining all pairs of reachable nodes in a graph G amounts to computing the transitive closure of the relation storing the edges. The version of the problem for this competition comes in terms of queries to the transitive closure of G.
Given a directed graph G=(V,E) and a couple <a,b> of nodes of {G, the truth of the atom 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 query of the form reaches(a,b)?.
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 expressed as a ground atom of the binary predicate reaches: e.g. reaches(a,b)? asks 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), according the Competition Input and Output specification.
Notes and differences with previous versions of this problem
With respect to the Second ASP Competition, the goal query is herein made explicit by means of the reaches(a,b)? which shall be found in input instances.
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).
Problem Peculiarities
Type: Polynomial/Query Competition: both Model & Solve and System competition
Reachability can be considered a classic polynomial problem, not to be considered too trivial. The instance graphs will be indeed quite large: rather than modelling abilities (we expect all competitors will adopt a pretty standard encoding in the M&S track also), this problem will stress memory usage and the ability of tailoring the search space at hand to what is needed for answering the goal query only.
Author(s)
- Author: Giorgio Terracina
- Affiliation: University of Calabria, Italy