» ASP Competition


Hierarchical Clustering

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).

Graphical representation of the given graph:

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). parentdge(5,3). parentedge(5,1).

The hierarchial clustering of the graph:

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky