Class Tree
Description Problem description
=================

A hierarchical clustering of an undirected graph G=(V,E) where V is a set of vertices, E is a set of edges, is defined by an assignment to each vertex x of a level number l(x) – an integer from 1…k (topmost level is numbered 1), and by the assignment to each vertex x with l(x) > 1, of an edge that identifies a unique parent vertex for x, which must be a vertex with the level l(x)-1, so that:

1. all the vertices that are connected to the same parent vertex form a clique (the are all connected to each other by edges),
2. the vertices in level 1 form a single clique, and
3. the number of vertices in each cluster including the cluster at level 1 must be bounded by b.


Input format
=================

Input graphs are stored in plain text files, one file for each graph. The format of the file is as follows:

1. The file starts with lines that define vertices. Vertices are defined using predicate name "vtx". Vertices are represented as integers that always start from 1 and end at n, where n is the number of the vertices.
2. The definition of edges follows that of the vertices. The predicate name used to define edges is "edge". Predicate edge has two parameters. Intuitively, edge(x, y) means there is an undirected edge between vertex x and vertex y that is different from x.
3. The predicate name that provides a positive integer bound on the number of vertices in each cluster is “bound”. It is given following the specification of edges.
4. The predicate name that provides the number of levels in the hierarchy is "levels". Levels are represented as integer numbers that always start from 1 and end at l. It closes the file.


Output format
=================

The programmers must ensure that, in the answer-sets, predicate "levelvtx" is used to represent the level of each vertex , and a predicate “parentedge(x,y)” which is used to imply that the parent vertex of y is x and is connected by an edge. Predicate levelvtx takes two parameters: levelvtx(i,x), which means that the vertex x is in the ith level.


Example
=================

Input:

vtx(1). vtx(2). vtx(3). vtx(4). vtx(5). vtx(6). vtx(7). vtx(8). edge(8,3). edge(8,6). edge(8,5). edge(8,1). edge(3,5). edge(3,1). edge(7,6). edge(7,5). edge(7,4). edge(6,5). edge(6,1). edge(5,1). edge(5,2). edge(4,2). bound(2). levels(1). levels(2). levels(3).

Valid Output:

levelvtx(3,8). levelvtx(3,7). levelvtx(3,6). levelvtx(1,5). levelvtx(2,4). levelvtx(2,3). levelvtx(1,2). levelvtx(2,1). parentedge(1,8). parentedge(4,7). parentedge(1,6). parentedge(2,4). parentedge(5,3). parentedge(5,1).

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky
Encodings
1 - 1 of 1