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
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?
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.
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:
４—(2)→０—(3)→１—(2)→２—(1)→３ //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:
Then, we have the output:
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!
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.