Weighted Graphs, Minimum spanning tree and cluster analysis.

Introduction
create a C++ program that receives in input a weighted
graph and groups its nodes in the required number of clusters.
Input and Output
The input is a single text file containing:
• The graph, in adjacent list format
• The weight matrix
• The required number of clusters
Example 1 of input
1
2
3
4
5
6
7
8
9
10
11
12
13
1 2 3 4
0 2 3
0 1 3
0 1 2
0
0 3 4 5	2
3 0 2 4	-999
4 2 0 1	-999
5 4 1 0	-999
2 -999 -999 -999 0
2

// -999 = no connections between 2 nodes. 


1
2
3
Example	1 of output	
0 4
1 2 3


So I'm still going about trying to understand this thing, my main concern being the clustering part. Does anyone have any idea how on what approach i should take to cut down the graph and separate it into the number of clusters required?

// Btw I am not allowed to use STL or Vectors.
Last edited on
how are you defining clusters, within N distance from a node? Or by weight total? Or something else?

The output program should be a text file containing the clusters, represented as list of nodes on different rows. As a convention, nodes should appear in numerical order. Clusters should be sorted by numerical order of their first node.
I echo @jonnin's question. How are you defining clusters? You told us how to print them out, but nothing tells us how to determine what a cluster is.
Since I have the same assignment as they do, I'll help clarify the question. First, we need to find the shortest path that connect each nodes without causing the cycle. Therefore, the graph for this input will look like this:

4—(2)→0—(3)→1—(2)→2—(1)→3 //number in () means the weight of the edge

For the last line of the input '2' means that we need to group its nodes in 2 clusters by cutting the highest edge, which is (3), so the graph will become like this:

1
2
4—(2)→0
1—(2)→2—(1)→3


Then, we have the output:
1
2
0 4
1 2 3


Since I'm still working on this too, I really hope someone can help us with method that does the job. Thanks!
Last edited on
yeah exactly what fraC19 said, i forgot to check the forum and just left it.


The cluster is specified by the number given to us, and we basically find the Minimal Span of the Graph and cut all the highest weights. And keep checking the loop until the desire number of clusters is achieved.
Registered users can post here. Sign in or register to post.