Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1460
  • Last Modified:

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) :
 
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 ;    
}

Open in new window

and here ( in Prim_sparse.cpp)
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
}


#endif

Open in new window

Please dear experts, could you pls inspect all the code written and tried to help me address the issue.


HeapPrim.cpp
Prim-Sparse.cpp
wgraph1.txt
0
ozzyfanta
Asked:
ozzyfanta
  • 15
  • 8
  • 2
  • +1
1 Solution
 
TommySzalapskiCommented:
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.
0
 
ozzyfantaAuthor Commented:
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
0
 
ozzyfantaAuthor Commented:
Thanks...
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
phoffricCommented:
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] ] )     )
0
 
ozzyfantaAuthor Commented:
Thanks phoffric...
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 ;    
}

Open in new window


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

0
 
ozzyfantaAuthor Commented:
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...
0
 
phoffricCommented:
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.
0
 
phoffricCommented:
>>  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).
0
 
ozzyfantaAuthor Commented:
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->&
0
 
phoffricCommented:
Graph::MST_Prim
            u =t->wgt;  // u is a weight
            if (t->wgt < dist[u]) 

Open in new window

so how can u be an index into dist? If a weight is large enough, then your out-of-bounds index can even cause a crash.

>> 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

Open in new window

0
 
phoffricCommented:
Here is the pseudo-code for Prim's Algorithm: Prim's Algorithm Pseudo-CodeHere is the graph of the above example: Graph MST ExampleHere is the final result:  Graph MST Final Result
0
 
ozzyfantaAuthor Commented:
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?
0
 
phoffricCommented:
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/
0
 
phoffricCommented:
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.
0
 
ozzyfantaAuthor Commented:
Please check my code, hope you will discover the errors. Will wait for your answer
0
 
phoffricCommented:
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.
0
 
phoffricCommented:
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
0
 
phoffricCommented:
>> 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).
    http://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 http:#35454185 .

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.
0
 
phoffricCommented:
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:
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 child

Open in new window

I didn't do timing tests, but I believe that a good optimizing compiler will result in as efficient code as the original less readable version. But, if you are concerned about this, then you can add the more readable variables, and then, after you have the program working, you can substitute their original expressions back into the code.

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.
  # 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

Open in new window

Below is the output for the 8 V - 10 E example corresponding to the above figures. I see that I made a mistake in writing down the MST for this case in an earlier post. 6 -> 7 (with a weight of 14) of course should not have been in the list. The program below produces better results than what I posted earlier. The total MST weight of 53 is consistent with the bottom figure in http:#35455791
# 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

Open in new window

0
 
phoffricCommented:
>> 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.
0
 
ozzyfantaAuthor Commented:
Hello guys...I have made a lot of research ...this is the way i have changed my siftDown function
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);
	}
}

Open in new window


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...
0
 
phoffricCommented:
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 http:#35500324 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.
0
 
phoffricCommented:
Here is a methodology to get a working program. Your graph class uses the heap class, so it is imperative that you have a working heap class.

To this end, create a project called HeapTest. It includes only the heap class and a main test driver. Good OO design would have the test driver knowing little about the heap class. For example, it should not have to set keys to 10000. You could have a constructor that builds the heap with this initialization. The driver can change the key using a decrease_key function (yet to be implemented). If you do not implement this function, then your driver will know too much about your implementation of your priority queue. Your heap test driver should test every high level function. The sift functions should be made private; they can be exercised thoroughly via the public functions.

Note that a priority queue could have been implemented with a simple vector (although inefficient). I'm not suggesting that you abstract your heap to do better OO; I'm suggesting that you form the abstraction so that you can properly test and correct your heap class.

During debug, every time the heap changes, the heap class should display the new heap in the manner in which I showed you in my debug output in http:#35500324. Then it will be easy for you to spot incorrect heaps. If you run into a problem with a bad heap, then I will try to show you how to debug it. -- What OS and debugger are you using? If none, then I will suggest extra debug statements - again, see my debug output for suggestions.

If you post your new heap class and test driver with the correct results, then I will try to break it with further testing. If I fail to break it, then you go onto the next step, which will be a slightly simpler Graph class implementation than what you have.
0
 
phoffricCommented:
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.
0
 
TommySzalapskiCommented:
I agree. phoffric provided much more than was required to answer the original question.
0
 
mlmccCommented:
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

  • 15
  • 8
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now