[BL!TZ]

okay I'm tired of trying to get this right it needs some tweaking this is my final proyect for a class this is suppose to be a group work but guest what I'm alone doing this. anyway here is the code

#include<iostream.h>
#include<process.h>
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999


struct node  {
  int predecessor;
  int dist;  int status;  };
struct edge  {      int u;       int v;  };
  int create_graph();
     void display();
  int maketree(edge [],int *); 
  int all_perm(node [] );
  int adj[MAX][MAX];
  int n;    void main() {      int i,j;
  int path[MAX];
  int wt_tree,count;
struct edge tree[MAX];
   create_graph();
   cout<<"Adjacency matrix is :\n";

   count = maketree(tree,&wt_tree);
   cout<<"Weight of spanning tree is : "<<wt_tree;
   cout<<"Edges to be included in spanning tree are : \n";
     for(i=1;i<=count;i++)
{  cout<<tree[i].u<<" -> \n";
   cout<<tree[i].v<<"\n";       } }
   int create_graph() {
   int i,max_edges,origin,destin,wt;
   cout<<" Prism minimun spamming tree algorithm";
   cout<< endl;

   cout<<"Enter number of vertices : ";
    cin>>n;      max_edges=n*(n-1)/2;
        for(i=1;i<=max_edges;i++)
{  cout<<"Enter edge "<< i <<" (0 0 to quit) : ";
   cin>>origin;
   cout<<"\t";
   cin>>destin;
         if((origin==0) && (destin==0))             break;
   cout<<"Enter weight for this edge : ";
   cin>>wt;
         if( origin > n || destin > n || origin<=0 || destin<=0)         {
   cout<<"Invalid edge!\n";            i--;         }
else         {            adj[origin][destin]=wt;   adj[destin][origin]=wt;   }    }
         if(i<n-1)      {
          cout<<"Spanning tree is not possible\n"; exit(1);  } }   void display()
 {      int i,j;       for(i=1;i<=n;i++)      
{        for(j=1;j<=n;j++)         cout<<"\t"<<adj[i][j];    cout<<"\n";       } }
    int maketree(edge tree[MAX],int *weight) {      node state[MAX];
    int i,k,min,count,current,newdist;
    int m;
    int u1,v1;      *weight=0;           for(i=1;i<=n;i++)
 {    state[i].predecessor=0;    state[i].dist = infinity;   state[i].status = TEMP;       }
      state[1].predecessor=0;       state[1].dist = 0;       state[1].status = PERM;
      current=1;       count=0;
      while( all_perm(state) != TRUE )

 {  for(i=1;i<=n;i++)          {
 if ( adj[current][i] > 0 && state[i].status == TEMP )             {
 if( adj[current][i] < state[i].dist )
 {       state[i].predecessor = current;         state[i].dist = adj[current][i];    }
 }      } min=infinity;
 for(i=1;i<=n;i++)      {         if(state[i].status == TEMP && state[i].dist < min)
 {             min = state[i].dist;             current=i;          }
 }        state[current].status=PERM;             u1=state[current].predecessor;
 v1=current;
 count++;       tree[count].u=u1;       tree[count].v=v1;   *weight=*weight+adj[u1][v1];       }
 return (count); }  int all_perm(node state[MAX] ) {      int i;      for(i=1;i<=n;i++)
 if( state[i].status == TEMP )

    return FALSE;
 else
return TRUE;
cout<< " Press e to exit";
cin>>"e";

}

This is been coded in borland C++ I dont know if it works in V++

[eker676]

What's wrong with it? Does it compile? Is the output not what you expected?

Give us a little more information so we can help you diagnose the program.

[BL!TZ]

yes it compiles just I think the result is not right. Anyway please run it if you can and help me get it right

[eker676]

I don't know how to run your program or what to input. I don't know what is happening either.

I indented your code. Go through your code line by line in a debugger and see if everything is working correctly.

#include<iostream>
#include<process.h>
using namespace std;
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999


struct node  {
  int predecessor;
  int dist;
  int status;  
};

struct edge  {
	int u;       
	int v;  
};

void create_graph();
void display();
int maketree(edge [],int *); 
int all_perm(node [] );
int adj[MAX][MAX];
int n;    

int main()
{
	int i = 0, j = 0;
	int path[MAX] = {0};
	int wt_tree = 0, count = 0;

	struct edge tree[MAX];
	create_graph();
	cout<<"Adjacency matrix is :\n";

	count = maketree(tree,&wt_tree);
	cout<<"Weight of spanning tree is : "<<wt_tree;
	cout<<"Edges to be included in spanning tree are : \n";
    for(i=1;i<=count;i++)
	{
		cout<<tree[i].u<<" -> \n";
		cout<<tree[i].v<<"\n";       
	} 
}

void create_graph() {
	int i,max_edges,origin,destin,wt;
	
	cout<<" Prism minimun spamming tree algorithm";
	cout<< endl;

	cout<<"Enter number of vertices : ";
    cin>>n;
	max_edges=n*(n-1)/2;
    for(i=1;i<=max_edges;i++)
	{
		cout<<"Enter edge "<< i <<" (0 0 to quit) : ";
		cin>>origin;
		cout<<"\t";
		cin>>destin;

        if((origin==0) && (destin==0))
			break;

		cout<<"Enter weight for this edge : ";
		cin>>wt;

        if( origin > n || destin > n || origin<=0 || destin<=0)         
		{
			cout<<"Invalid edge!\n"; 
			i--;
		}
		else
		{
			adj[origin][destin]=wt;
			adj[destin][origin]=wt;
		}
	}
    if(i<n-1)
	{
		cout<<"Spanning tree is not possible\n";
		exit(1);
	}
}

void display()
{
	int i,j;
	
	for(i=1;i<=n;i++)      
	{
		for(j=1;j<=n;j++)
			cout<<"\t"<<adj[i][j];
		cout<<"\n";
	}
}

int maketree(edge tree[MAX],int *weight)
{
	node state[MAX];
    int i = 0,k = 0,min  = 0,count = 0,current = 0,newdist = 0;
    int m = 0;
    int u1 = 0, v1 = 0;
	*weight=0;
	
	for(i=1;i<=n;i++)
	{
		state[i].predecessor=0;
		state[i].dist = infinity;
		state[i].status = TEMP;
	}
    
	state[1].predecessor=0;
	state[1].dist = 0; 
	state[1].status = PERM;
      
	current=1;
	count=0;
    
	while( all_perm(state) != TRUE )
	{
		for(i=1;i<=n;i++)
		{
			if ( adj[current][i] > 0 && state[i].status == TEMP )
			{
				if( adj[current][i] < state[i].dist )
				{
					state[i].predecessor = current;
					state[i].dist = adj[current][i]; 
				}
			}
		}
		
		min=infinity;
		
		for(i=1;i<=n;i++)
		{
			if(state[i].status == TEMP && state[i].dist < min)
			{
				min = state[i].dist;
				current=i;
			}
		}
		
		state[current].status=PERM;
		u1=state[current].predecessor;
		v1=current;
		
		count++;
		tree[count].u=u1;
		tree[count].v=v1;
		
		*weight=*weight+adj[u1][v1];
	}

	return (count);
}

int all_perm(node state[MAX] )
{
	int i;
	
	for(i=1;i<=n;i++)
		if( state[i].status == TEMP )
			return FALSE;
		else
			return TRUE;

	cout<< " Press e to exit";
	char c;
	cin>>c;

	return FALSE;
}

[BL!TZ]

thanks for indenting the program. Look what the prism algorithm does and that will help you understand what my program should do

[eker676]

Here's the problem with that. A google on "prism algorithm" gives me a hundred different algorithms. Then even if I find the correct one, I don't want to look through ten pages of text trying to understand it.

You are the one you wrote the program. You should know what it does and what it doesn't. I have no clue what is does or how it works so I can't run a quick test to see if it's working properly.

Point out a specific block of code that is giving you problems, then explain those problems. Is the output wrong? Does the input work incorrectly? If it's a question about the algorithm then you are going to have to explain what is supposed to happen.

That program is 170 lines with no comments whatsoever. We cannot help you unless you tell us specifically what is wrong. Saying it doesn't work isn't going to cut it.

This post has been edited by eker676: 12 May 2010 - 08:20 PM

[BL!TZ]

okay mister Eker added notes just for you. and MAIN PROBLEM IS OUTPUT DOESN'T STAY ENOUGH TIME TO SEE IT.

#include<iostream>
#include<process.h>
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999


struct node  {
  int predecessor;
  int dist; /*Distance from predecessor */
  int status;
};

struct edge  {
        int u;       
        int v;  
};

void create_graph();
void display();
int maketree(edge [],int *); 
int all_perm(node [] );
int adj[MAX][MAX];
int n;    

int main()
{
        int i = 0, j = 0;
        int path[MAX] = {0};
        int wt_tree = 0, count = 0;

        struct edge tree[MAX];
        create_graph();
        cout<<"Adjacency matrix is :\n";

        count = maketree(tree,&wt_tree);
        cout<<"Weight of spanning tree is : "<<wt_tree;
        cout<<"Edges to be included in spanning tree are : \n";
    for(i=1;i<=count;i++)
        {
                cout<<tree[i].u<<" -> \n";  /*End of main()*/
                cout<<tree[i].v<<"\n";       
        } 
}

void create_graph() {
        int i,max_edges,origin,destin,wt;
        
        cout<<" Prism minimun spamming tree algorithm";
        cout<< endl;

        cout<<"Enter number of vertices : ";
    cin>>n;
        max_edges=n*(n-1)/2;
    for(i=1;i<=max_edges;i++)
        {
                cout<<"Enter edge "<< i <<" (0 0 to quit) : ";
                cin>>origin;
                cout<<"\t";
                cin>>destin;

        if((origin==0) && (destin==0))
                        break;

                cout<<"Enter weight for this edge : ";
                cin>>wt;

        if( origin > n || destin > n || origin<=0 || destin<=0)         
                {
                        cout<<"Invalid edge!\n"; 
                        i--;
                }
                else
                {
                        adj[origin][destin]=wt;
                        adj[destin][origin]=wt;
                }
        }
    if(i<n-1)
        {
                cout<<"Spanning tree is not possible\n";
                exit(1);  /*End of create_graph()*/
        }
}

void display()    /*End of display()*/
{
        int i,j;
        
        for(i=1;i<=n;i++)      
        {
                for(j=1;j<=n;j++)
                        cout<<"\t"<<adj[i][j];
                cout<<"\n";
        }
}

int maketree(edge tree[MAX],int *weight)
{
        node state[MAX];
    int i = 0,k = 0,min  = 0,count = 0,current = 0,newdist = 0;
    int m = 0;
    int u1 = 0, v1 = 0;
        *weight=0;
         /*Make all nodes temporary*/
         /*Make first node permanent*/
         /*Start from first node*/
         /*count represents number of nodes in tree */
         /*Loop till all the nodes become PERM*/

        for(i=1;i<=n;i++)
        {
                state[i].predecessor=0;
                state[i].dist = infinity;
                state[i].status = TEMP;
        }
    
        state[1].predecessor=0;
        state[1].dist = 0; 
        state[1].status = PERM;
      
        current=1;
        count=0;
    
        while( all_perm(state) != TRUE )
        {
                for(i=1;i<=n;i++)
                {
                        if ( adj[current][i] > 0 && state[i].status == TEMP )
                        {
                                if( adj[current][i] < state[i].dist )
                                {
                                        state[i].predecessor = current;
                                        state[i].dist = adj[current][i];
                                }
                        }
                }
                
                min=infinity;    /*Search for temporary node with minimum distance and make it current node*/
                
                for(i=1;i<=n;i++)
                {
                        if(state[i].status == TEMP && state[i].dist < min)
                        {
                                min = state[i].dist;
                                current=i;
                        }
                }
                
                state[current].status=PERM;  /*Insert this edge(u1,v1) into the tree */
                u1=state[current].predecessor;
                v1=current;
                
                count++;
                tree[count].u=u1;
                tree[count].v=v1;
                 /*Add wt on this edge to weight of tree */
                *weight=*weight+adj[u1][v1];
        }         /*End of while*/

          /*End of maketree()*/
        return (count);
}

int all_perm(node state[MAX] )    /*This function returns TRUE if all nodes are permanent*/
{
        int i;
        
        for(i=1;i<=n;i++)
                if( state[i].status == TEMP )
                        return FALSE;
                else
                        return TRUE;  /*End of all_perm()*/

        cout<< " Press e to exit";
        char c;
        cin>>c;

        return FALSE;
}

[BL!TZ]

bump!

[janotte]

BL!TZ, on 13 May 2010 - 12:56 PM, said:

okay mister Eker added notes just for you. and MAIN PROBLEM IS OUTPUT DOESN'T STAY ENOUGH TIME TO SEE IT.

Keep up the childish attitude and the shouting and you'll find no-one prepared to help you.

Here's what may be your last help here if you don't sort your attitude problem out.

Add "cin.get();" and "return 0;" to the end of the main() function.
As below:

int main()
{
   // your existing code here

   cin.get();
   return 0;
}

http://www.gidnetwork.com/b-61.html

[divinespirit9671]

First of all the algorithm to find minimum spanning tree is called Prim's algorithm and NOT prism algorithm.

Secondly no need to shout unnecessarily;
If you post your errors and add description of what you program is supposed to do with proper examples;you will find more people willing to help you.

This post has been edited by divinespirit9671: 13 May 2010 - 03:46 AM

[BL!TZ]

thanks janotte that resolved part of my problem still need to check some things out. sorry for my actitude but I'm kind of desperated this is due for today and is 50% of my final grade

[JackOfAllTrades]

Actually, looks like that code is just ripped right from here. You'd better hope your teacher doesn't check for plagiarism...it was very easy to find, you just stripped out the comments.