COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3 Requirements
• Due date: October 6, 2023 at 11:55PM. This is an individual assignment. This assign- ment is weighted 15% of the course grade.
• Each student submits three files: assignment1.pdf, spiders.lp, and spidershortlegs.lp. The file assignment1.pdf should contain the answers to questions 1.1, 1.2, 1.3, 2.1, 2.2,
and 3.1, including any snippets of code necessary.
Spanning Spiders
Let G = (V,E) be a graph. A spanning tree T is a subgraph of G with the following properties:
• T is a tree (i.e. it contains no cycles and is connected).
• T contains all of the vertices of G.
A spider S is a tree with at most one vertex in S whose degree is 3 or more. Such a vertex is called the centre of the spider. If S consists of no vertices with degree 3 or more, then any vertex can act as the centre of the spider. Finally, a leg of a spider is a path from the centre to a vertex of degree 1.
To get a better understanding of the terminology, consider the following example graph.
Figure 1: An example graph.
A possible spider is highlighted. In fact, the highlighted spider is a spanning spider because
it is a spider and a spanning tree.
Figure 2: A spider that is also a spanning tree. 1 of 3
Code Help
COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3
Given an input graph, our goal is to write an Answer Set Program to return a list of distinct spanning spiders (i.e. each stable model of our program corresponds to a distinct spanning spider). Not every graph has a spanning spider; if an input graph does not admit any spanning spiders, the corresponding program should return unsatisfiable.
Input format. An input file contains predicate instances of vertex/1, indicating the vertices of the graph and predicate instances of edge/2, indicating the edges of the graph. The example graph above is modelled with the following predicates.
vertex(a).
vertex(b).
vertex(c).
vertex(d).
vertex(e).
vertex(x).
vertex(y).
vertex(z).
edge(a, d).
edge(a, x).
edge(b, d).
edge(b, y).
edge(c, d).
edge(c, z).
edge(d, e).
edge(e, x).
edge(x, z).
edge(y, z).
Output format. Your program should compute a model containing a predicate leg/2, indicating which edges are included in the spanning spider. Each model should also contain a predicate centre/1, indicating which vertex is the centre of the spider.
CS Help, Email: tutorcs@163.com
COMP4418: Knowledge Representation and Reasoning Assignment 1, 23T3 Part I: Understanding the Problem
[1.1] Consider the spanning spider from Figure 2. Indicate the centre vertex and the list of edges that is included in the spanning spider.
[1.2] Provide ASP rules to define the centre/1 predicate and ensure that in any model, exactly one vertex is selected as the centre.
[1.3] Provide a generator for the leg/2 predicate.
Part II: Refining the Models
Up until now, you should have a set of models that consists of exactly one vertex as the centre of the spider and a set of leg edges. Our goal is to now remove some of these models that can form a spanning spider.
[2.1] One property required of spanning spiders is that every vertex should be reachable from the centre through leg edges. Introduce a derived predicate reachable/1 that ranges over vertex names and is true when the corresponding vertex is reachable from the centre through leg edges. Use this predicate to define a constraint that ensures every vertex of the original graph is reachable from the centre through leg edges.
[2.2] The reachability of every vertex from the centre is a required property of spanning spiders, but it is not sufficient and we need to ensure other constraints are satisfied. Describe all the other constraints that need to be satisfied and write ASP rules to enforce these constraints.
We are now ready to write an ASP program that returns the set of spanning spiders, given an input graph.
Part III: Putting everything together
[3.1] Based on your answers to the above questions, write an ASP program spiders.lp that takes an input graph and outputs all the distinct spanning spiders of the graph. How many distinct spanning spiders does the graph in Figure 1 have?
[3.2] Write an ASP program spidershortlegs.lp that outputs a spanning spider with the shortest longest leg.
Computer Science Tutoring