# Find spanning tree with maximum edges with the same weight

For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer.

I have tested the code on my local machine and it gives correct outputs on different data sets. However, when I upload the solution to the evaluation system, I see that the program completion time is up to 3 times longer than the reference time.

Here are two files that are in the project. I added detailed comments, of course:

//struct for subsets used in MST Kruskal algoritm
typedef struct subset {
int parent;
int rank;
} subset_t, *subset_p;

//struct for storing graph edges
typedef struct edges {
int src;
int dest;
int weight;
} edges_t, *edges_p;

//struct for storing weights and number of their occuriences
typedef struct weights {
int weight;
int occurCount;
} weights_t, *weights_p;

//struct to store all built trees
typedef struct trees {

int totalWeight; // total tree weight
int mostOccurNumber; // highest number of repeated edges for a tree
} trees_t, *trees_p;

//find and union function prototypes
int find(struct subset subsets[], int i);
void Union(struct subset subsets[], int x, int y);


Source Code.cpp

#include <stdio.h>
#include <stdlib.h>

//find function used in Kruskals algorithm
int find(subset_p subsets, int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}

//union function used in Kruskals algorithm
void Union(subset_p subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
//compare function used in qsort(). Sorts all edges by ascending weight
int myComp1 (const void *a, const void *b)
{
const edges_t * ptr_a = (const edges_t *)a;
const edges_t * ptr_b = (const edges_t *)b;
if (ptr_a->weight < ptr_b->weight) return -1;
if (ptr_a->weight > ptr_b->weight) return 1;
return 0;
}
//Sorts all present weights by descending number of occuriences in the MST
int myComp2 (const void *a, const void *b)
{
const weights_t * ptr_a = (const weights_t *)a;
const weights_t * ptr_b = (const weights_t *)b;
if (ptr_a->occurCount > ptr_b->occurCount) return -1;
if (ptr_a->occurCount < ptr_b->occurCount) return 1;
return 0;
}
//Sorts all present MSTs primarily by descending number of same-weight occuriences
//Secondly by ascending weights
int myComp3 (const void *a, const void *b)
{
const weights_t * ptr_a = (const weights_t *)a;
const weights_t * ptr_b = (const weights_t *)b;
int diff = ptr_b->occurCount - ptr_a->occurCount;
if (diff == 0) {
if (ptr_a->weight < ptr_b->weight) {
diff = -1;
} else if (ptr_a->weight > ptr_b->weight) {
diff =  1;
} else diff = 0;
}
return diff;
}

int main() {
//number of vertices and edges for a graph
int num_vertices, num_edges;
scanf("%d%d", &num_vertices, &num_edges);

// struct to keep all graph edges
edges_p allEdges = (edges_p)malloc(num_edges*sizeof(edges_t));

//input variables for source vertex, destanation vertex and weight of the edge
int curr_src, curr_dest, curr_weight;

//array to store all present (different!) weight values
int * weights = (int *)malloc(num_edges*sizeof(int));

//a variable to store number of elements in 'weights' array - number of different weight values in a graph
int newWeightIndex = 0;

//inputing data about graph edges: source vertex, destination vertex, weight
for (int i = 0; i < num_edges; i++) {
scanf("%d%d%d", &curr_src, &curr_dest, &curr_weight);

//filling array of structs with input info
allEdges[i].src = curr_src - 1;
allEdges[i].dest = curr_dest - 1;
allEdges[i].weight = curr_weight;

//'Weights' array contains all weights that are present in a graph.
//Here we decide whether we should put current weight value into an array.
for (int j = 0; j < i; j++) {
if (weights[j] == curr_weight) {
break;
}
}
weights[newWeightIndex] = curr_weight;
newWeightIndex++;
}
}
// end of data input

//an array of structs to store info about build MSTs (the weight of MST and maximum number of edges with same weights)
trees_p myTrees = (trees_p)malloc(newWeightIndex * sizeof(trees_t));

//Kruscal Algoritm lopp to find an MST for all present weights.
//We take each weight in 'weights' and change the weight of every edge in a graph that has weight equal to 'weights[i]' to -1
for (int i = 0; i < newWeightIndex; i++) {
int minimizedWeight = weights[i];

//array to store subsets of vertices
subset_p subsets = (subset_p)malloc(num_vertices * sizeof(subset_t));

//array to store MST Edges
edges_p mstEdges = (edges_p)malloc(num_vertices*sizeof(edges_t));

//array to store current edge
edges_p currentEdge = (edges_p)malloc(sizeof(edges_t));

//variable to keep the amount of weight that was subtracted (when setting some weights to -1)
//this is done in order to restore default weights after MST build finishes
int subtractedWeight = 0;

//variable to keep the number of edges which weight was changed to -1
int infEdgesTotal = 0;

//variable to keep the number of edges which weight was changed to -1 included to MST
int infEdgesTaken = 0;

//setting minimum weights
for (int i = 0; i < num_edges; i++) {
if (allEdges[i].weight == minimizedWeight) {
allEdges[i].weight = -1;
subtractedWeight += minimizedWeight+1;
infEdgesTotal++;
}
}

//sorting all graph edges in ascending order
qsort(allEdges, num_edges, sizeof(edges_t), myComp1);

//the kruskal algoritm itself - BEGINNING
for (int v = 0; v < num_vertices; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}

int e = 0;
int currentIndex = 0;
int mstWeight = 0;
int mstEdgesCount = 0;
while (e < num_vertices - 1) {

currentEdge.src = allEdges[currentIndex].src;
currentEdge.dest = allEdges[currentIndex].dest;
currentEdge.weight = allEdges[currentIndex].weight;

int x = find(subsets, currentEdge.src);
int y = find(subsets, currentEdge.dest);
currentIndex++;

if (x != y) {
mstEdges[e].src = currentEdge.src;
mstEdges[e].dest = currentEdge.dest;
mstEdges[e].weight = currentEdge.weight;
mstWeight += mstEdges[e].weight;
mstEdgesCount++;
if (mstEdges[e].weight == -1) {
infEdgesTaken++;
}
e++;
Union(subsets, x, y);
}

}
free(subsets);
//the kruskal algoritm itself - END

//Restoring default weights
for (int i = 0; i < num_edges; i++) {
if (allEdges[i].weight == -1) {
allEdges[i].weight += minimizedWeight+1;
}
}

//Calculating built MST weight
mstWeight += subtractedWeight/infEdgesTotal*infEdgesTaken;

//an array to store all weight values in MST and a number of edges in MST with that weight
weights_p myWeights = (weights_p)malloc(mstEdgesCount*sizeof(weights_t));

//a variable to store the number of different weight values in MST
int num_weights = 0;

//filling 'myWeights' array
for(int i = 0; i < mstEdgesCount; i++) {
myWeights[i].weight = -100;
}
for (int i = 0; i < mstEdgesCount; i++) {
for (int j = 0; j < i + 1; j++) {
if (myWeights[j].weight == -100) {
myWeights[j].weight = mstEdges[i].weight;
myWeights[j].occurCount = 1;
num_weights++;
break;
} else if (myWeights[j].weight != mstEdges[i].weight){
continue;
} else {
myWeights[j].occurCount++;
break;
}
}
}

free(currentEdge);

//sorting all present weights by descending number of edges with that weight
qsort(myWeights, num_weights, sizeof(weights_t), myComp2);

//a variable to store a maximum number of weight occuriences in MST
int mostOccs = myWeights.occurCount;

free(myWeights);
free(mstEdges);

myTrees[i].totalWeight = mstWeight;
myTrees[i].mostOccurNumber = mostOccs;
}
// End of Krushkal Algorithm iteration

free(weights);
free(allEdges);

//sorting 'myTrees' array to get an MST with maximum number of same-edge occuriences
//and lowest weight in the top
qsort(myTrees, newWeightIndex, sizeof(trees_t), myComp3);

//outputing the result
printf ("%d",myTrees.totalWeight);

free(myTrees);
system("pause");
return 0;
}


Now there seems to be too many loops, but honestly, I don't know how I can simplify the algorithm even more.

I really need some suggestions about how to enhance the performance of this solution. May be there are some obvious things I can't see.

• Is your file also called "Source Code.cpp"? Keep in mind that some compilers will assume that it's C++ code then and interpret the code slightly different. – Zeta Oct 22 '17 at 14:21