代写C++程序Minimum Spanning Tree and Optimal Clustering

日期：2018-04-17 04:37

CSE310 Project 2: Minimum Spanning Tree and Optimal Clustering

Posted: Thursday, 03/28/2018, Due: Thursday, 04/19/2018

In our first programming project, you have implemented the min-heap data structure and its

associated functions. In this programming project, you will make minor modifications to yourmin heap data structure (by expanding the fields of the array elements) and combine that with

the disjoint set data structure (to be implemented) in designing an algorithm that can compute

optimal clustering and minimum spanning tree of a given undirected graph. For this project, you

do not have to build the edge adjacency list to store the given graph in computer memory. You can

just use a list of nodes where each node corresponds to an edge in the graph. Specifically, the list

of nodes can be of type EDGE, which has three fields: v1 (of type int), v2 (of type int), and cost

of type int), where v1 and v2 are the two end vertices of the edge, and cost is the cost of the edge.

You may add more fields to EDGE to carry out your algorithm. I leave this to you to figure out.

Assume that the graph has nV vertices and nE edges. You should build a disjoint set data

structure for nV nodes, and a min-heap data structure for nE edges. The array elements in the

min-heap should be of type EDGE. For the disjoint set data structure, you should implement union

by rank and find with path compression.

Suppose that you are asked to compute an optimal K-clustering of a graph G with nV vertices

and nE edges (you can assume that 1 ≤ K < nV ). You will apply Kruskal’s minimum spanning tree

algorithm with the following minor modification. Instead of performing nV − 1 union operations,

you perform nV − K union operations. The result will be an optimal clustering of the given graph,

where each cluster is connected by a tree whose edges are selected in the process.

You program should read the input from an ASCII file named input.txt and write the output

to an ASCII file named output.txt. The first line of input.txt contains one positive integer

K, which denotes the number of clusters to compute. The second line of input.txt contains two

positive integers nV and nE, which denote the number of vertices and number of weighted edges,

respectively, in an undirected graph G. The next nE lines each contain three integers u, v, cost,

where u and v are the end vertices of the corresponding edge and cost is the cost of that edge.

The vertices are numbered from 1 to nV. The edges are numbered from 1 to nE. For example, the

following input file asks you to find K = 2 clusters of a graph with nV = 6 vertices and nE = 8

edges.

2

6 8

1 2 10

1 3 7

2 3 9

2 4 2

3 5 8

4 5 3

1

4 6 5

5 6 4

Your program should initialize nV disjoint sets (one for each vertex) and initialize a min-heap of

nE elements by performing nE insertions to the initially empty heap, one insertion per edge. When

this is done, your program will print out the set structure and the heap structure. Your algorithm

will then compute an optimal K-clustering of the given graph, using the modification to Kruskal’s

algorithm. Whenever an edge is deleted from the heap, you will print out the new heap structure.

Whenever an edge is selected, you need to print it out, perform the union, and will print out the

new set structure. Eventually, you will print out the vertices in each of the clusters. For the sample

input, your program should generate the following output.

Set Structure:

0, 0, 0, 0, 0, 0

Heap Structure:

2, 4, 3, 7, 8, 9, 5, 10

Heap Structure:

3, 4, 5, 7, 8, 9, 10

Selecting edge (2, 4)

Set Structure:

0, 4, 0, -1, 0, 0

Heap Structure:

4, 7, 5, 10, 8, 9

Selecting edge (4, 5)

Set Structure:

0, 4, 0, -1, 4, 0

Heap Structure:

5, 7, 9, 10, 8

Selecting edge (5, 6)

Set Structure:

2

0, 4, 0, -1, 4, 4

Heap Structure:

7, 8, 9, 10

Heap Structure:

8, 10, 9

Selecting edge (1, 3)

Set Structure:

3, 4, -1, -1, 4, 4

Vertices in the cluster with vertex 3:

1, 3

Vertices in the cluster with vertex 4:

2, 4, 5, 6

Grading Policies: Your program should be implemented using C++. Your program should be

working on general.asu.edu. No credit will be given for programs that do not work on

general.asu.edu. Therefore, you should start with something that works, and keep adding

functions to a working program.

(10 pts) Disjoint set operations: You should have a module for disjoint set that implements the disjoint

set data structure, where union is by rank and find is with path compression.

(10 pts) Heap operations: Modify your min-heap data structure for the purpose of this project.

(10 pts) Clustering algorithm: Using heap operations to select the next edge. Using set operations to

decide whether two nodes are already connected.

(10 pts) Input and output of graphs: Your output should match the sample output.

(10 pts) Modularity: one module for heap, one module for set, one module for the clustering algorithm.

Other modules may be added if necessary. You will also need to provide a Makefile. The

executable file should be named run.

(10 pts) Documentation: Provide a README file that describes your project.

(20 pts) Public test cases: Pass each of the test cases posted

(20 pts) Private test cases: Pass each of the test cases created after the projects are submitted.

3

You should use the C++ programming language, working on general.asu.edu. All programs

will be compiled and graded on general.asu.edu. You will need to submit it electronically

at the blackboard, in one zip file, named CSE310-P02-Lname-Fname, where Lname is your last

name and Fname is your first name. The zip file should contain a set of files that are absolutely

necessary to compile and execute your program. If you program does not compile and work

on general.asu.edu, you will receive 0 on this project.

4

The following are some helpful hints for those with difficulties in programming. You don’t have

to follow/use these.

• Data structures for edges of the graph:

typedef struct TAG_edge{

int v1; /* from vertex */

int v2; /* to vertex */

int cost; /* cost of edge */

}EDGE;

typedef EDGE *ElementT;

• Data structures for heap on the edges:

typedef struct TAG_HEAP{

int capacity; /* max size of the heap */

int size; /* current size of the heap */

ElementT *elements; /* array of pointers to elements */

}HEAP;

typedef HEAP *heap;