Member_2_4213139
asked on
Kruskal Algorithm
I am trying to create the "Kruskal Function" for a longer program I have, but I can't seem to get passed a few things. Right now, I get errors from "union" having no tag and "find" being a local illegal function definition. Can somebody tell me what's wrong and how to fix it?
template <class vType, int size>
void msTreeType<vType, size>::kruskal(vType sVertex)
{
int i, x, y, max, num;
setofsets set(size);
int k, l, xx, yy;
int parent[size];
for(i=0; i<max; i++)
{
int find (int x)
{
y = x;
while (parent[y] != y)
y = parent[y];
parent[x] = y;
return y;
}
}
{
union (int x, int y)
xx = parent[x];
yy = parent[y];
parent[yy] = xx;
}
if (parent[k] == parent[l])
find (k,l);
else
union(k,l);
} //end kruskal
#endif
ASKER
Dear parnasso,
A typo... but it did nothing... as a matter of fact, it ADDED an error!
A typo... but it did nothing... as a matter of fact, it ADDED an error!
union is a keyword like class and struct. you may not use it for function name.
Sara
Sara
ASKER
Dear sarabande,
Thank you! Down to three errors now... (I should have realized that in VS when "union" was blue'd!) The function doesn't like the two embedded functions "find" and now "checkUnion" ... the error is "local function definitions are illegal" ... (one of the original problems) ...
Thank you! Down to three errors now... (I should have realized that in VS when "union" was blue'd!) The function doesn't like the two embedded functions "find" and now "checkUnion" ... the error is "local function definitions are illegal" ... (one of the original problems) ...
you can't define 'local embedded' functions in c++.
that means each function body (implementation) must not be within another function.
do you have some more calls like
function2(int x, int y);
?
Sara
that means each function body (implementation) must not be within another function.
do you have some more calls like
function2(int x, int y);
?
Sara
ASKER
Dear sarabande,
I only have the two ("find" and "checkUnion") which I have to locate outside the function? Can "C" define functions within functions?
I only have the two ("find" and "checkUnion") which I have to locate outside the function? Can "C" define functions within functions?
no, function in functions are not allowed. can you post the code and the error messages?
Sara
Sara
ASKER
template <class vType, int size>
void msTreeType<vType, size>::kruskal(vType sVertex)
{
int i, x, y, max, num;
setofsets set(size);
int k, l, xx, yy;
int parent[size];
for(i=0; i<max; i++)
{
// find (int x);
{
y = x;
while (parent[y] != y)
y = parent[y];
parent[x] = y; // to speed up future find(x) searches
// return y;
}
}
// Union (int x, int y);
{
xx = parent[x];
yy = parent[y];
parent[yy] = xx;
}
if (parent[k] == parent[l])
find (k,l,i);
else
union(k,l);
} //end kruskal
#endif
Errors:
error C2332: "union" missing tag name
error C2514 'msTreeType<vType,size>::k
you still use union as a function in line 35.
i think both errors are related to that.
Sara
i think both errors are related to that.
Sara
ASKER
Dear Sara,
That last "union" is supposed to merge the sets in which k and l are present. How would I do that otherwise? (I thought "union" was then an internal command, not a function...)
That last "union" is supposed to merge the sets in which k and l are present. How would I do that otherwise? (I thought "union" was then an internal command, not a function...)
you should know that union in c++ is of same quality as class and struct. so you got same kind of errors as you would try
class("abc", 12345);
first the compiler is missing the 'tag' what means the classname and second it doesn't know of a constructor.
what do you mean by 'merging sets'? k and l are integers which you can't merge.
also note that c++ is case sensitive and Union and union is different. you could use the first for a function though i would recommend against.
the 'union' is a struct where all members use the same storage. it is not a command.
Sara
Sara
class("abc", 12345);
first the compiler is missing the 'tag' what means the classname and second it doesn't know of a constructor.
what do you mean by 'merging sets'? k and l are integers which you can't merge.
also note that c++ is case sensitive and Union and union is different. you could use the first for a function though i would recommend against.
the 'union' is a struct where all members use the same storage. it is not a command.
Sara
Sara
the functions find and Union must be defined outside of function kruskal.
can you tell me what the functions should do?
Sara
can you tell me what the functions should do?
Sara
note, statements like
parent[x] = y;
are very dangerous cause the x and y must be a valid index in the range from 0 to size-1.
i can't see anything in your code which would make that sure. if you access the array parent out of boundaries the program would crash.
and if you have a function find that takes 1 int, you can't call it with
find(k, l, i);
Sara
parent[x] = y;
are very dangerous cause the x and y must be a valid index in the range from 0 to size-1.
i can't see anything in your code which would make that sure. if you access the array parent out of boundaries the program would crash.
and if you have a function find that takes 1 int, you can't call it with
find(k, l, i);
Sara
ASKER
Dear Sara,
This is a Kruskal Algorithm. I'm trying to first sort the edges in ascending order based on their weights, considering each edge in that order. Then, I want to include it in an MST solution if it does not result in cycle, and reject it otherwise.
I wanted the "union" to merge the sets in which k and l are present.
This is a Kruskal Algorithm. I'm trying to first sort the edges in ascending order based on their weights, considering each edge in that order. Then, I want to include it in an MST solution if it does not result in cycle, and reject it otherwise.
I wanted the "union" to merge the sets in which k and l are present.
i am now offline a few hours. i'll will find out about kruskal in the meantime. you could make a sample of a graph and tell what should happen.
Sara
Sara
ASKER
Dear Sara,
I understand! I had to leave for a few hours, myself! I was trying to tell you that, but the EE site started taking forever to load, so I had to abandon the comment! Sorry!!!
The data is fed to the program via a text file. If the algorithm is working properly, it should give data similar to the following:
******* Using Prim2 Algorithm *********
Source Vertex: 0
Edges Weight
(6, 1) 4.00
(0, 2) 5.00
(0, 3) 2.00
(1, 4) 2.00
(2, 5) 7.00
(2, 6) 5.00
Tree Weight: 25.00
******* Using Kruskal's Algorithm *********
Edges Weight
(3457600, 3679400) 0.00
(2682532, 1) 4.00
(0, 0) 5.00
(1, -1) 2.00
(3457592, 1748248731) 2.00
(2682344, 1747322550) 7.00
Tree Weight: 20.00
The Prim2 Algorithm is working perfectly. The Kruskal Algorithm is supposed to do something similar. THANK YOU!
I understand! I had to leave for a few hours, myself! I was trying to tell you that, but the EE site started taking forever to load, so I had to abandon the comment! Sorry!!!
The data is fed to the program via a text file. If the algorithm is working properly, it should give data similar to the following:
******* Using Prim2 Algorithm *********
Source Vertex: 0
Edges Weight
(6, 1) 4.00
(0, 2) 5.00
(0, 3) 2.00
(1, 4) 2.00
(2, 5) 7.00
(2, 6) 5.00
Tree Weight: 25.00
******* Using Kruskal's Algorithm *********
Edges Weight
(3457600, 3679400) 0.00
(2682532, 1) 4.00
(0, 0) 5.00
(1, -1) 2.00
(3457592, 1748248731) 2.00
(2682344, 1747322550) 7.00
Tree Weight: 20.00
The Prim2 Algorithm is working perfectly. The Kruskal Algorithm is supposed to do something similar. THANK YOU!
i know now what kruskal is.
i checked the code you posted and though there are a few unknowns like the msTreeType and the template type vType i found nothing which actually can be taken as a base to proceed on. for example you have an array parent[size] which is not initialised. but you do a loop on it like it was properly filled with vertex data.
also the results you posted for kruskal do not build a minimum spanning tree.
can you post the source of the prim2 algorithm which 'is working perfectly'?
can you also post the msTreeType header and the intented type for vType?
Sara
i checked the code you posted and though there are a few unknowns like the msTreeType and the template type vType i found nothing which actually can be taken as a base to proceed on. for example you have an array parent[size] which is not initialised. but you do a loop on it like it was properly filled with vertex data.
also the results you posted for kruskal do not build a minimum spanning tree.
can you post the source of the prim2 algorithm which 'is working perfectly'?
can you also post the msTreeType header and the intented type for vType?
Sara
ASKER
Dear Sara,
I was afraid of that! As I looked to other Kruskal examples, I noticed some other parts of my code were lacking, but each had the same inner core that mine had, so I thought I was good.
Here is the Prim2 Algorithm:
"vType" is from the Type Class. and its lengthy. Would you still need it?
I was afraid of that! As I looked to other Kruskal examples, I noticed some other parts of my code were lacking, but each had the same inner core that mine had, so I thought I was good.
Here is the Prim2 Algorithm:
template <class vType, int size>
void msTreeType<vType, size>::prim2(vType sVertex)
{
int i, j, k;
double minWeight;
source = sVertex;
bool visited[size];
for (j = 0; j < gSize; j++)
{
visited[j] = false;
edges[j] = source;
edgeWeights[j] = weights[source][j];
}
visited[source] = true;
edgeWeights[source] = 0;
for (i = 0; i < gSize; i++)
{
minWeight = infinity;
k = -1;
for (j = 0; j < gSize; j++)
if (!visited[j] && edgeWeights[j] < minWeight)
{
k = j;
minWeight = edgeWeights[j];
}
if (k != source && k != -1)
{
visited[k] = true;
for (j = 0; j < gSize; j++)
if (!visited[j])
if (weights[k][j] < edgeWeights[j])
{
edges[j] = k;
edgeWeights[j] = weights[k][j];
}
}
} //end for
} //end prim2
template<class vType, int size>
class msTreeType: public graphType<vType, size>
{
public:
void createSpanningGraph();
//Function to create the graph and the weight matrix.
void minimalSpanning(vType sVertex);
//Function to create the edges of the minimal
//spanning tree. The weight of the edges is also
//saved in the array edgeWeights.
void printTreeAndWeight();
//Function to output the edges and the weight of the
//minimal spanning tree.
void printKruskal();
//Function to output the edges and the weight of the
//minimal spanning tree for Kruskal algorithm.
void prim2(vType sVertex);
//This function creates the edges of the minimal
//spanning tree. The weight of the edges is also
//saved in the array edgeWeights
void kruskal(vType sVertex);
//This function finds the minimal spanning tree by
//finding smallest weights. The weight of the edges is
//also saved in the array edgeWeights
protected:
vType source;
double weights[size][size];
int edges[size];
double edgeWeights[size];
edgeContainer eList[size*size];
int arrayX[size];
int arrayY[size];
};
"vType" is from the Type Class. and its lengthy. Would you still need it?
ASKER
Dear Sara,
What I actually figured was that I would take what I have in the Prim2 and put the code that I have for Kruskal on it, as then Prim2 would then act as Kruskal. Thoughts?
What I actually figured was that I would take what I have in the Prim2 and put the code that I have for Kruskal on it, as then Prim2 would then act as Kruskal. Thoughts?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Dear Sara,
THANK YOU! I know that ee is to help and not do the work! I am both grateful and appreciative for (well, most of) the help I get here!!! (YOU are included in the gratefulness and appreciation!!!)
You're the BEST!
THANK YOU! I know that ee is to help and not do the work! I am both grateful and appreciative for (well, most of) the help I get here!!! (YOU are included in the gratefulness and appreciation!!!)
You're the BEST!
ASKER
Sara's the BEST!
when you want to procede with new questions you always can ask what to do next here in that thread.
much luck.
Sara
much luck.
Sara
22: {
23: union (int x, int y)
put this instead:
22: union (int x, int y)
23: {