ozzyfanta
asked on
Prim's implementation
Hello dear experts...
I am trying for sometimes now to implement prim's algorithm, it is partially working but i believe someone with good knowledge could help me get it fully functional. I have written three files: HeapPrim.cpp ,Prim_sparse.cpp and wgraph1.txt . I have tried in vain to find any coding error algorithm's wise, but failed. I presumed that i have a problem in here ( in HeapPrim.cpp) :
i
HeapPrim.cpp
Prim-Sparse.cpp
wgraph1.txt
I am trying for sometimes now to implement prim's algorithm, it is partially working but i believe someone with good knowledge could help me get it fully functional. I have written three files: HeapPrim.cpp ,Prim_sparse.cpp and wgraph1.txt . I have tried in vain to find any coding error algorithm's wise, but failed. I presumed that i have a problem in here ( in HeapPrim.cpp) :
void Heap::siftDown( int k)
{
int v, j;
v = h[k];
while (k<=N/2)
{
if((j<N && dist[h[j+1]]) < dist[h[j]])
++j;
if(dist[v] < h[j])
break;
h[k] = h[j];
hPos[h[k]] =k ;
k=j;
}
h[k]=v;
hPos[v] =k ;
}i
nt * Graph::MST_Prim( Vertex s)
{
Vertex v, u;
int wgt;
int * dist, * parent, * heapPos;
Node * t;
dist = new int[V+1];
parent = new int[V+1];
heapPos = new int[V+1];
for(v=0; v<=V; ++v)
{
dist[v] =10000;
parent[v] = 0;
heapPos[v] =0;
}
dist[s] = 0;
Heap pq(V, dist, heapPos);
pq.insert(s);
while(!pq.isEmpty())
{
v=pq.remove();
dist[v]=-dist[v];
for(Node *t=adj[v];t!=z; t=t->next)
{
u =t->wgt;
if (t->wgt < dist[u])
{
dist[u] = t->wgt;
parent[u] = v;
if(heapPos[u] == 0)
{
pq.insert(u);
}
else
{
pq.siftDown( heapPos[u]);
}
}
}
}
free( dist);
free (heapPos);
return parent; // return pointer to MST
}
#endifHeapPrim.cpp
Prim-Sparse.cpp
wgraph1.txt
TommySzalapski
It would help if you told us what it was doing that it shouldn't do and what it needed to do. Also, if you hit 'Request Attention' and ask that the C and C++ zones be added, you're bound to get a solution faster.
ASKER
Thanks Tommy...
Actually it is not implementing the prim's algo correctly. For example, when you input the name of the file and the starting vertex (first of all, only starting at vertex 1 is at least giving me the wrong implementation, starting at other vertices is making the program to crash)...it gives me the following:
The minimum spanning tree is:
A ->&
B ->A
C ->&
D ->B
E ->&
F->A
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
NB :Where it is & needs to be sorted
thanks guys
Actually it is not implementing the prim's algo correctly. For example, when you input the name of the file and the starting vertex (first of all, only starting at vertex 1 is at least giving me the wrong implementation, starting at other vertices is making the program to crash)...it gives me the following:
The minimum spanning tree is:
A ->&
B ->A
C ->&
D ->B
E ->&
F->A
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
NB :Where it is & needs to be sorted
thanks guys
ASKER
Thanks...
Couple of problems with Line 8: if( (j<N && dist[ h[j+1] ] ) < dist[ h[j] ] )
(1) j is not initialized
(2) Do you want to perform this comparison: dist[ h[j+1] ] ) < dist[ h[j] ] ?
If so, then probably need to change line to:
if( j<N && ( dist[ h[j+1] ] < dist[ h[j] ] ) )
(1) j is not initialized
(2) Do you want to perform this comparison: dist[ h[j+1] ] ) < dist[ h[j] ] ?
If so, then probably need to change line to:
if( j<N && ( dist[ h[j+1] ] < dist[ h[j] ] ) )
ASKER
Thanks phoffric...
Your suggestions has helped a little bit with the problem...I have rewritten the siftDown function like this:
Now starting at any vertex doesnt crash the program, but it still give me wrong implemetation. If I input for example starting at vertex 6 gives the following answer:
The minimum spanning tree is:
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
NB :Where it is & needs to be sorted
thanks guys
Your suggestions has helped a little bit with the problem...I have rewritten the siftDown function like this:
void Heap::siftDown( int k)
{
int v, j=0;
v = h[k];
while (k<=N/2)
{
if((j<N && (dist[h[j+1]]) < dist[h[j]]))
++j;
if(dist[v] < h[j])
break;
h[k] = h[j];
hPos[h[k]] =k ;
k=j;
}
h[k]=v;
hPos[v] =k ;
}Now starting at any vertex doesnt crash the program, but it still give me wrong implemetation. If I input for example starting at vertex 6 gives the following answer:
The minimum spanning tree is:
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
NB :Where it is & needs to be sorted
thanks guys
ASKER
forgot to mention that whenever i deliberately input the wrong file name, it outputs the correct message( could not find the file) then crashes....I can not figure out the errors...
Debugging with a smaller set may be easier. Have you gotten it to work with a very small set? And then just add one entity to make it fail? How about posting the file contents with the smallest set that works and the smallest set that does not work.
>> i deliberately input the wrong file name ... I can not figure out the errors...
If you keep file operations separate from the graph class, you may have an easier time. The graph constructor detects the error and simply returns. But there is no indication in main that there was a problem. No surprise that when you continue processing, that you have a bug (or, in your case, a crash).
If you keep file operations separate from the graph class, you may have an easier time. The graph constructor detects the error and simply returns. But there is no indication in main that there was a problem. No surprise that when you continue processing, that you have a bug (or, in your case, a crash).
ASKER
Thanks phoffric...It is working with a small set...I could only suggest that i have a problem in one of the for loop in the program , probably in line 31. because first it could only run when you start at vertex 1 to 6( from 7 it doesnt do anything) and second because when i get it implemented, vertex E to M has unknown values like in:
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
Graph::MST_Prim
u =t->wgt; // u is a weight
if (t->wgt < dist[u]) >> It is working with a small set
Please post the contents of the file for which it worked.
It may prove useful if you add judicious debug statements showing the intermediate steps in this algorithm. Compare these results with your own hand-written version.
Let's use this as a guide, since I have this problem worked out in class notes.
08 10
1 3 9
2 4 15
3 4 7
3 7 5
3 8 12
4 5 10
5 6 3
5 7 8
6 7 14
7 8 6
Here is the pseudo-code for Prim's Algorithm: 
Here is the graph of the above example: 
Here is the final result: 
Here is the graph of the above example: Here is the final result:
ASKER
Thanks phoffric...I think we are heading well. I know now where lies the errors...u=t->wgt , it is to initialise the weight before the if statement...it turns out to be a very stupid mistake. Could you pls help me initialise the weight cos i tried u=o , it is not giving me the right...so my question is how to initialise a weight?
Please download this video for review. Between the first graph and the last is essentially an animation showing the steps in initializing and updating the keys. But it wouldn't hurt to watch the graph review, and the proofs associated with MST to get familiar with the shop talk.
There is a full transcript on this page as well for you to review.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/
There is a full transcript on this page as well for you to review.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/
That was theory. On a practical note (and I'll check your code tomorrow), your heap should be independent of the application. (Well, if you are not familiar with templating, you can hold that off - so the heap can store the data type that includes the key.
Using STL in a future enhancement will be a plus from a programming perspective.
Using STL in a future enhancement will be a plus from a programming perspective.
ASKER
Please check my code, hope you will discover the errors. Will wait for your answer
Setting the index to the weight was a serious programming error since it can cause you program to crash. However, this error is indicative of a design issue. Do you understand completely how the Prim Algorithm works? If not, then I urge you to watch the video; if you have any questions on it, then you can ask questions on it.
After understanding how it works, please explain the salient points here, with special emphasis on the key. Then you have to turn this understanding into a design that you can post here.
If you need immediate attention on understanding the algorithm or the design (since I'm not here 24x7), feel free to ask a question just in the Algorithm zone, so as to get a timely response. Otherwise, feel free to ask it here if you can wait.
If you need more references to understand the Prim Algorithm, let me know, and I'll see if I can find them for you.
After understanding how it works, please explain the salient points here, with special emphasis on the key. Then you have to turn this understanding into a design that you can post here.
If you need immediate attention on understanding the algorithm or the design (since I'm not here 24x7), feel free to ask a question just in the Algorithm zone, so as to get a timely response. Otherwise, feel free to ask it here if you can wait.
If you need more references to understand the Prim Algorithm, let me know, and I'll see if I can find them for you.
Part of the problem is that you are not mixing up vertices with dist. You also made this mixup in siftDown:
if(dist[v] < h[j]) // comparing apples and oranges ??
I mentioned earlier that you were using j without setting it. You revised your code to initialize j to 0. You should draw the PQ structure, and set j appropriately in the loop.
When working with graphs, it is valuable to have multiple copies and show how the code modifies them. The video and slides have a good exmple of that.
For the example in the slide, I get:
Minimum Spanning tree is:
1 -> 3
2 -> 4
3 -> 4
4 -> 0
5 -> 6
6 -> 7
7 -> 3
8 -> 7
(I didn't see any reason to change node names from numbers to letters.)
PrimEx-2.PNG
if(dist[v] < h[j]) // comparing apples and oranges ??
I mentioned earlier that you were using j without setting it. You revised your code to initialize j to 0. You should draw the PQ structure, and set j appropriately in the loop.
When working with graphs, it is valuable to have multiple copies and show how the code modifies them. The video and slides have a good exmple of that.
For the example in the slide, I get:
Minimum Spanning tree is:
1 -> 3
2 -> 4
3 -> 4
4 -> 0
5 -> 6
6 -> 7
7 -> 3
8 -> 7
(I didn't see any reason to change node names from numbers to letters.)
PrimEx-2.PNG
>> Please check my code, hope you will discover the errors. Will wait for your answer
Given that your question is academic in nature, I am bound by EE policy on academic questions (including self-study).
https://www.experts-exchange.com/help.jsp?hi=21
So, I am happy to provide you with guidance if you need further assistance, but I am not permitted to provide a full coding solution.
If you are still having trouble, then here is a hint to help you along with this assignment. With regards to your siftDown function, take a look at:
http://en.wikipedia.org/wiki/Binary_heap#Deleting_the_root_from_the_heap
paying particular attention to the left and right child relationship to the parent when using a heap array. That is definitely part of your problem and has a direct bearing to your initialization of j that I mentioned in https:#a35454185 .
If you can describe to me how you want to remove the top of your PQ, then we can analyze it and try to get a working implementation.
Given that your question is academic in nature, I am bound by EE policy on academic questions (including self-study).
https://www.experts-exchange.com/help.jsp?hi=21
So, I am happy to provide you with guidance if you need further assistance, but I am not permitted to provide a full coding solution.
If you are still having trouble, then here is a hint to help you along with this assignment. With regards to your siftDown function, take a look at:
http://en.wikipedia.org/wiki/Binary_heap#Deleting_the_root_from_the_heap
paying particular attention to the left and right child relationship to the parent when using a heap array. That is definitely part of your problem and has a direct bearing to your initialization of j that I mentioned in https:#a35454185 .
If you can describe to me how you want to remove the top of your PQ, then we can analyze it and try to get a working implementation.
As you already noticed, sometimes you get good results for certaint values of the initial node (and sometimes you can even crash for other values). For this reason, in order to test your classes more thoroughly, I modified the main driver to loop through all the possible starting nodes.
One error you have is for the case where you change the dist of an element already in the heap. The resultant change in the heap is incorrect. To see this (and other heap errors), display the heap every time it changes (i.e., for Extract-Min, or Insert, or Change Existing Key).
In siftDown, regarding the initialization of j, I suggest that you define some extra variables to help clarify the model. Here's how I started when I debugged your siftDown function:
Here is the output for your 13 V - 22 E graph. The loop goes from 1 to 13 for the starting vertex. The first run has the maximum debug; a little less for the 2nd run; and only results for the remaining runs.
Notice that the selected edges differ amongst the runs. For example, you will find 4 -> 5 (2) for s=5, but it does not appear in the s=13 run. And the s=13 run includes 6 -> 12 (2), which was not selected in the s=5 run.
For this reason, it is important to show the weights and the total sum of the weights. The Min Weight Sum for all the runs is 16.
One error you have is for the case where you change the dist of an element already in the heap. The resultant change in the heap is incorrect. To see this (and other heap errors), display the heap every time it changes (i.e., for Extract-Min, or Insert, or Change Existing Key).
In siftDown, regarding the initialization of j, I suggest that you define some extra variables to help clarify the model. Here's how I started when I debugged your siftDown function:
void Heap::siftDown( int k)
{
int v = h[k];
int key_v = key[v];
int parent_idx = k;
int child_idx = 2*parent_idx; // intially, left childHere is the output for your 13 V - 22 E graph. The loop goes from 1 to 13 for the starting vertex. The first run has the maximum debug; a little less for the 2nd run; and only results for the remaining runs.
Notice that the selected edges differ amongst the runs. For example, you will find 4 -> 5 (2) for s=5, but it does not appear in the s=13 run. And the s=13 run includes 6 -> 12 (2), which was not selected in the s=5 run.
For this reason, it is important to show the weights and the total sum of the weights. The Min Weight Sum for all the runs is 16.
# Vertices = 13 # Edges = 22
1-->2 (1)
1-->6 (2)
1-->7 (6)
2-->3 (1)
2-->4 (2)
2-->5 (4)
3-->5 (4)
4-->5 (2)
4-->6 (1)
5-->6 (2)
5-->7 (1)
5-->12 (4)
6-->12 (2)
7-->8 (3)
7-->10 (1)
7-->12 (5)
8-->9 (2)
9-->11 (1)
10-->11 (1)
10-->12 (3)
10-->13 (2)
12-->13 (1)
=======================
First Vertex, s = 1
Extract MIN: 1(0)
HEAP EMPTY
adj_v=7
decreaseKey Node 7: 10000 --> 6
HEAP
07(06)
adj_v=6
decreaseKey Node 6: 10000 --> 2
HEAP
06(02)
07(06)
adj_v=2
decreaseKey Node 2: 10000 --> 1
HEAP
02(01)
07(06) 06(02)
Extract MIN: 2(1)
HEAP
06(02)
07(06)
adj_v=5
decreaseKey Node 5: 10000 --> 4
HEAP
06(02)
07(06) 05(04)
adj_v=4
decreaseKey Node 4: 10000 --> 2
HEAP
06(02)
04(02) 05(04)
07(06)
adj_v=3
decreaseKey Node 3: 10000 --> 1
HEAP
03(01)
06(02) 05(04)
07(06) 04(02)
adj_v=1
Extract MIN: 3(1)
HEAP
04(02)
06(02) 05(04)
07(06)
adj_v=5
adj_v=2
Extract MIN: 4(2)
HEAP
06(02)
07(06) 05(04)
adj_v=6
decreaseKey Node 6: 2 --> 1
HEAP
06(01)
07(06) 05(04)
adj_v=5
decreaseKey Node 5: 4 --> 2
HEAP
06(01)
07(06) 05(02)
adj_v=2
Extract MIN: 6(1)
HEAP
05(02)
07(06)
adj_v=12
decreaseKey Node 12: 10000 --> 2
HEAP
05(02)
07(06) 12(02)
adj_v=5
adj_v=4
adj_v=1
Extract MIN: 5(2)
HEAP
12(02)
07(06)
adj_v=12
adj_v=7
decreaseKey Node 7: 6 --> 1
HEAP
07(01)
12(02)
adj_v=6
adj_v=4
adj_v=3
adj_v=2
Extract MIN: 7(1)
HEAP
12(02)
adj_v=12
adj_v=10
decreaseKey Node 10: 10000 --> 1
HEAP
10(01)
12(02)
adj_v=8
decreaseKey Node 8: 10000 --> 3
HEAP
10(01)
12(02) 08(03)
adj_v=5
adj_v=1
Extract MIN: 10(1)
HEAP
12(02)
08(03)
adj_v=13
decreaseKey Node 13: 10000 --> 2
HEAP
12(02)
08(03) 13(02)
adj_v=12
adj_v=11
decreaseKey Node 11: 10000 --> 1
HEAP
11(01)
12(02) 13(02)
08(03)
adj_v=7
Extract MIN: 11(1)
HEAP
12(02)
08(03) 13(02)
adj_v=10
adj_v=9
decreaseKey Node 9: 10000 --> 1
HEAP
09(01)
12(02) 13(02)
08(03)
Extract MIN: 9(1)
HEAP
12(02)
08(03) 13(02)
adj_v=11
adj_v=8
decreaseKey Node 8: 3 --> 2
HEAP
12(02)
08(02) 13(02)
Extract MIN: 12(2)
HEAP
13(02)
08(02)
adj_v=13
decreaseKey Node 13: 2 --> 1
HEAP
13(01)
08(02)
adj_v=10
adj_v=7
adj_v=6
adj_v=5
Extract MIN: 13(1)
HEAP
08(02)
adj_v=12
adj_v=10
Extract MIN: 8(2)
HEAP EMPTY
adj_v=9
adj_v=7
Minimum Spanning tree is:
2 -> 1 (1)
3 -> 2 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 2
Extract MIN: 2(0)
HEAP EMPTY
HEAP
05(04)
HEAP
04(02)
05(04)
HEAP
03(01)
05(04) 04(02)
HEAP
03(01)
01(01) 04(02)
05(04)
Extract MIN: 3(1)
HEAP
01(01)
05(04) 04(02)
Extract MIN: 1(1)
HEAP
04(02)
05(04)
HEAP
04(02)
05(04) 07(06)
HEAP
04(02)
06(02) 07(06)
05(04)
Extract MIN: 4(2)
HEAP
06(02)
05(04) 07(06)
HEAP
06(01)
05(04) 07(06)
HEAP
06(01)
05(02) 07(06)
Extract MIN: 6(1)
HEAP
05(02)
07(06)
HEAP
05(02)
07(06) 12(02)
Extract MIN: 5(2)
HEAP
12(02)
07(06)
HEAP
07(01)
12(02)
Extract MIN: 7(1)
HEAP
12(02)
HEAP
10(01)
12(02)
HEAP
10(01)
12(02) 08(03)
Extract MIN: 10(1)
HEAP
12(02)
08(03)
HEAP
12(02)
08(03) 13(02)
HEAP
11(01)
12(02) 13(02)
08(03)
Extract MIN: 11(1)
HEAP
12(02)
08(03) 13(02)
HEAP
09(01)
12(02) 13(02)
08(03)
Extract MIN: 9(1)
HEAP
12(02)
08(03) 13(02)
HEAP
12(02)
08(02) 13(02)
Extract MIN: 12(2)
HEAP
13(02)
08(02)
HEAP
13(01)
08(02)
Extract MIN: 13(1)
HEAP
08(02)
Extract MIN: 8(2)
HEAP EMPTY
Minimum Spanning tree is:
1 -> 2 (1)
3 -> 2 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 3
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 3 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 4
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 5
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 5 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 6
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 6 (2)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 7
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 5 (2)
5 -> 7 (1)
6 -> 4 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 8
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
9 -> 8 (2)
10 -> 11 (1)
11 -> 9 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 9
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
8 -> 9 (2)
10 -> 11 (1)
11 -> 9 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 10
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 11
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 5 (2)
5 -> 7 (1)
6 -> 4 (1)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 11 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 12
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 12 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 13 (2)
11 -> 10 (1)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 13
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 12 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 13 (2)
11 -> 10 (1)
12 -> 13 (1)
Min Weight Sum = 16# Vertices = 8 # Edges = 10
1-->3 (9)
2-->4 (15)
3-->4 (7)
3-->7 (5)
3-->8 (12)
4-->5 (10)
5-->6 (3)
5-->7 (8)
6-->7 (14)
7-->8 (6)
=======================
First Vertex, s = 1
Extract MIN: 1(0)
HEAP EMPTY
adj_v=3
decreaseKey Node 3: 10000 --> 9
HEAP
03(09)
Extract MIN: 3(9)
HEAP EMPTY
adj_v=8
decreaseKey Node 8: 10000 --> 12
HEAP
08(12)
adj_v=7
decreaseKey Node 7: 10000 --> 5
HEAP
07(05)
08(12)
adj_v=4
decreaseKey Node 4: 10000 --> 7
HEAP
07(05)
08(12) 04(07)
adj_v=1
Extract MIN: 7(5)
HEAP
04(07)
08(12)
adj_v=8
decreaseKey Node 8: 12 --> 6
HEAP
08(06)
04(07)
adj_v=6
decreaseKey Node 6: 10000 --> 14
HEAP
08(06)
04(07) 06(14)
adj_v=5
decreaseKey Node 5: 10000 --> 8
HEAP
08(06)
04(07) 06(14)
05(08)
adj_v=3
Extract MIN: 8(6)
HEAP
04(07)
05(08) 06(14)
adj_v=7
adj_v=3
Extract MIN: 4(7)
HEAP
05(08)
06(14)
adj_v=5
adj_v=3
adj_v=2
decreaseKey Node 2: 10000 --> 15
HEAP
05(08)
06(14) 02(15)
Extract MIN: 5(8)
HEAP
06(14)
02(15)
adj_v=7
adj_v=6
decreaseKey Node 6: 14 --> 3
HEAP
06(03)
02(15)
adj_v=4
Extract MIN: 6(3)
HEAP
02(15)
adj_v=7
adj_v=5
Extract MIN: 2(15)
HEAP EMPTY
adj_v=4
Minimum Spanning tree is:
2 -> 4 (15)
3 -> 1 (9)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 2
Extract MIN: 2(0)
HEAP EMPTY
HEAP
04(15)
Extract MIN: 4(15)
HEAP EMPTY
HEAP
05(10)
HEAP
03(07)
05(10)
Extract MIN: 3(7)
HEAP
05(10)
HEAP
05(10)
08(12)
HEAP
07(05)
08(12) 05(10)
HEAP
07(05)
01(09) 05(10)
08(12)
Extract MIN: 7(5)
HEAP
01(09)
08(12) 05(10)
HEAP
08(06)
01(09) 05(10)
HEAP
08(06)
01(09) 05(10)
06(14)
HEAP
08(06)
01(09) 05(08)
06(14)
Extract MIN: 8(6)
HEAP
05(08)
01(09) 06(14)
Extract MIN: 5(8)
HEAP
01(09)
06(14)
HEAP
06(03)
01(09)
Extract MIN: 6(3)
HEAP
01(09)
Extract MIN: 1(9)
HEAP EMPTY
Minimum Spanning tree is:
1 -> 3 (9)
3 -> 4 (7)
4 -> 2 (15)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 3
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 4
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 4 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 5
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
6 -> 5 (3)
7 -> 5 (8)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 6
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 6 (3)
7 -> 5 (8)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 7
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 8
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 8 (6)
Min Weight Sum = 53
>> One error you have is for the case where you change the dist of an element already in the heap. The resultant change in the heap is incorrect.
Did you notice that whenever you change the dist , you are always lowering the value. That is why you will see the PRIM Algorithm as having a DECREASE-KEY function. When this occurs for an existing element in the MIN-HEAP, then it may either remain where it is or rise up the heap. This point should help you figure out what is wrong with the implementation for this scenario.
Did you notice that whenever you change the dist , you are always lowering the value. That is why you will see the PRIM Algorithm as having a DECREASE-KEY function. When this occurs for an existing element in the MIN-HEAP, then it may either remain where it is or rise up the heap. This point should help you figure out what is wrong with the implementation for this scenario.
ASKER
Hello guys...I have made a lot of research ...this is the way i have changed my siftDown function
I think (100% sure) that the problem remains with my int * Graph::MST_Prim( Vertex s)...Could you pls advice because i am still having the same result like;
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
Would be grateful if you could really help...
void Heap::siftDown(int k)
{
int v, j = k;
v = h[k];
int l = 2 * k, r = l + 1;
if (l <= N && dist[h[l]] < dist[h[j]]) j = l;
if (r <= N && dist[h[r]] < dist[h[j]]) j = r;
if (j != k)
{
h[k] = h[j];
h[j] = v;
hPos[h[k]] = k;
hPos[h[j]] = j;
siftDown(j);
}
}I think (100% sure) that the problem remains with my int * Graph::MST_Prim( Vertex s)...Could you pls advice because i am still having the same result like;
A ->F
B ->F
C ->&
D ->B
E ->&
F->&
G->&
H ->&
I->&
J->&
K->&
L->&
M->&
Would be grateful if you could really help...
I am glad you are making progress. :)
I'll be back this evening. IMO, the most important next step is to begin isolating problems in the intermediate steps. I believe I have identified all the problem areas in your code. Your output is your end result. It would be beneficial to you if you produce intermediate debug output. (See my output for a very useful format) and produce this output evey time the heap changes. Whenever you see a heap that doesn't satisfy the heap properties, then walk through your code with the GUI debugger. (I used VS 2010 C++ debugger; but ddd or Netbeans should also be good.)
Now, one important piece of advice. Your MST_Prim function should not know about the particular implementation of your priority queue (which you chose to implement as a MIN-HEAP). That is why I recommended defining a function called DECREASE-KEY. You should not have sift-related functions in MST_Prim since those are just techniques to maintain the heap. The DECREASE-KEY function is also part of the heap class - sometimes it will insert; sometimes it will have to decrease the key of an existing element.
The main problem that I see in your methodology is that you are testing everything all at once. Instead, think about testing one class at a time by testing the individual functions in that class. BTW, your implementation of the equivalence of DECREASE-KEY is incorrect.
Try to produce an output like I showed in https:#a35500324 and then try to figure out one small problem at a time instead of trying to tackle the entire problem at once.
One more thing for our discussion. Your input file talks about node numbers and weights; but your output talks about node letters. I guess A corresponds to 1, but why not just make them the same. I switched to using just node numbers; and recommend that at least until you complete the problem, that you do the same.
I'll be back this evening. IMO, the most important next step is to begin isolating problems in the intermediate steps. I believe I have identified all the problem areas in your code. Your output is your end result. It would be beneficial to you if you produce intermediate debug output. (See my output for a very useful format) and produce this output evey time the heap changes. Whenever you see a heap that doesn't satisfy the heap properties, then walk through your code with the GUI debugger. (I used VS 2010 C++ debugger; but ddd or Netbeans should also be good.)
Now, one important piece of advice. Your MST_Prim function should not know about the particular implementation of your priority queue (which you chose to implement as a MIN-HEAP). That is why I recommended defining a function called DECREASE-KEY. You should not have sift-related functions in MST_Prim since those are just techniques to maintain the heap. The DECREASE-KEY function is also part of the heap class - sometimes it will insert; sometimes it will have to decrease the key of an existing element.
The main problem that I see in your methodology is that you are testing everything all at once. Instead, think about testing one class at a time by testing the individual functions in that class. BTW, your implementation of the equivalence of DECREASE-KEY is incorrect.
Try to produce an output like I showed in https:#a35500324 and then try to figure out one small problem at a time instead of trying to tackle the entire problem at once.
One more thing for our discussion. Your input file talks about node numbers and weights; but your output talks about node letters. I guess A corresponds to 1, but why not just make them the same. I switched to using just node numbers; and recommend that at least until you complete the problem, that you do the same.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Author acknowledged making progress in http:#35457266 and in http:#35705251.
I helped identify many errors in his OP and subsequent posts. For example, in http:#35500324 I point out an error, and explain how he can see it for himself. I also recommended the debug output so that he could see what information is important to use to understand his program better.
I helped identify many errors in his OP and subsequent posts. For example, in http:#35500324 I point out an error, and explain how he can see it for himself. I also recommended the debug output so that he could see what information is important to use to understand his program better.
I agree. phoffric provided much more than was required to answer the original question.
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.