Reset values

my scenario is this

Code:

class Graph

{



   private:
  

     struct ListNode

     {

      long long int name;

        struct ListNode *next;      //This creates the same ListNode structure for the next and down pointers each one will have a name, a next, and a down.

        struct ListNode *down;

      };



       ListNode *head;

       ListNode *down_head;



    public:


      Graph() //Constructor

      {

         head = NULL;     //in-line initializations of head and down_head

         down_head = NULL;

      }



         void build() ;

};

and in build function i make the list as below(here 1,2,3,4 are nodes and -> shows its adjacency list)


1->2->4
2_>3
3->NULL
4->NULL

it works fine in all cases

but in main function i call the build for some iterations say

Code:

while(t)
{
s.build();
t--;
}

now each time i want my adj lists and nodes to be reset...but the old values of prev iteration also exists...
In the new iteration i construct entirely new nodes and new adj lists... but old values existing... any help
thanks

Originally Posted by dpp

now each time i want my adj lists and nodes to be reset...but the old values of prev iteration also exists...
In the new iteration i construct entirely new nodes and new adj lists... but old values existing... any help

Create a new Graph object on each iteration.

THat said, your build() member function looks like it should either be in the default constructor or be a non-member function. It makes more sense for the default constructor to create an empty Graph, so I would suggest turning build() into a non-member function. This also means that Graph should provide a proper interface for accessing and manipulating a graph.

Incidentally, std::list can be used when you need a linked list, though it is a doubly linked list. If not, you will probably be manually managing memory, so you should implement the copy constructor, copy assignment operator and destructor.

Also, if you want to initialise the member variables instead of assigning to them (even though that assignment gives the member variables initial values), you should use an initialisation list:

Code:

Graph() : head(NULL), down_head(NULL)
{
}

thanks laserlight...i am thru with it.
well am getting runtime error...(its not seg fault.. so says an online judge system )
http://www.spoj.pl/forum/viewtopic.p...af7bef1a4#p103
i had "other" runtime error. this is for spanning tree prim's algo

Code:

                                                                     
                                                                     
                                                                     
                                             
#ifndef GRAPH_H  //This checks the preprocessor to see if GRAPH_H has been defined and if it hasnt then it defines it as follows.
#define GRAPH_H


#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include<map>

using namespace std;




# define maxedges 300000
# define maxnodes  10009


class Graph

{



   private:
  

     struct ListNode

     {

      long long int name;

        struct ListNode *next;      //This creates the same ListNode structure for the next and down pointers each one will have a name, a next, and a down.

        struct ListNode *down;

      };



       ListNode *head;

       ListNode *down_head;



    public:


      Graph() //Constructor

      {

         head = NULL;     //in-line initializations of head and down_head

         down_head = NULL;

      }



         void Build_Network(); //This function will prompt the user for all of the information, as well as perform the necessary linked list operations

         void Display();          //This function will print out the linked list in a manner that is easily read.



};



#endif //Ends the definition of GRAPH_H



void Graph::Build_Network()

{
//multiset<int> myset;
 //multiset<int>::iterator it,itlow,itup;
multiset<int> myset;
multiset<int>::iterator it,itlow,itup;
   ListNode *newNode;  //This is the new vertex

   ListNode *nodePtr;   //Traversing pointer

   ListNode *downPtr;  //Edge/Adjacent Vertex Traversing pointer


   long long int num_Nodes,vertex,alt;
   long long int  i=0,j=0;

   long long int V_Name[maxnodes],key[maxnodes],p[maxnodes];
  static  long long int elements[maxnodes][maxnodes]; 
     static long long int v1[maxedges],v2[maxedges];
     //static  long long  E_Name[5*maxedges];
      static long long int  state[maxnodes],sum=0,v=0;
      static long long count=0,flag=0;
      // std::map<long long int, long long int> elements;

 
      


       myset.empty();
   // cout << "How many nodes in the graph?: ";

    scanf("%I64d",&num_Nodes); 
    //cin>>num_Nodes;
long long  int num_Edges;


            //cout << "How many Edges are connected to ";

           // cin >>num_Edges; 
           scanf("%I64d" ,&num_Edges);


     for( i = 0; i<num_Nodes; i++)

    //ifor 
     {

         V_Name[i]=i+1;
          
         
         if(i==0)
         key[V_Name[i]]=0;
         else
         key[V_Name[i]]=maxedges+maxedges+i;//1000000
         //q.push(key[V_Name[i]]);
         myset.insert(key[V_Name[i]]);
         p[V_Name[i]]=0;
         state[V_Name[i]]=0;
         newNode = new ListNode;

         newNode->name = V_Name[i];



         newNode->next = NULL;

         newNode->down = NULL;

// Building the Vertex List

         if(!head)

            head = newNode;

         else

         {

            nodePtr = head;

            while(nodePtr->next)

            nodePtr = nodePtr->next;

            nodePtr->next = newNode;

           }

}//endifor
           


        for( j=0; j<num_Edges; j++)

      //jfor   
      {
               
        
           // cout << "What is the name of edge "<< j+1 << "?: ";
            scanf("%I64d" ,&v1[j]);
            scanf("%I64d" ,&v2[j]);
            scanf("%I64d" ,&alt);
            //elements[v1[j]+v2[j]+v1[j]*v2[j]]=alt;
            elements[v1[j]][v2[j]]=0;
            elements[v2[j]][v1[j]]=0;
            
            elements[v1[j]][v2[j]]=alt;
              elements[v2[j]][v1[j]]=alt;
           // cin>>v1[j]>>v2[j]>>E_Name[v1[j]+v2[j]+(v1[j]*v2[j])];
          //  cout<<"\n e_name"<<E_Name[5];

        
        
        ListNode *nodePtr;
        ListNode *downPtr;
            nodePtr = head;
           
           while(nodePtr)  //continue through all vertices

    {

         if(nodePtr->name==v1[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode;

            down_head =nodePtr->down;

            downNode = new ListNode;

            downNode->name = v2[j];
           // downNode->w=elements[j];

            downNode->down = NULL;

//Building the Adjacent Vertex List

            if(!down_head)

            {

               nodePtr->down = downNode;

               down_head = downNode;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode;

            }
                 ///////// for undirected
                 nodePtr=head;
                    
          while(nodePtr)  //continue through all vertices

    {

         if(nodePtr->name==v2[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode1;

            down_head =nodePtr->down;

            downNode1 = new ListNode;

            downNode1->name = v1[j];

            downNode1->down = NULL;

//Building the Adjacent Vertex List

            if(!down_head)

            {

               nodePtr->down = downNode1;

               down_head = downNode1;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode1;

            }
            
             

         }

      // }
      
 
     
    long long int n;
    sum=0;
      while(myset.size())
      {
              
            nodePtr = head;
    
    
                      
                       it=myset.begin();
                       n=*it;
                       
                     sum+=n;
                     
                      if(myset.size()==1)
                      {
                       
                       goto s12;
                       }
                       
                       for(i=0;i<num_Nodes;i++)
                       {
                                               if(key[i+1]==n)
                                               {
                                               v=i+1;
                                               
                                               goto s11;
                                               }
                                            
                       }
                       s11:
                     
                       state[v]=1;//to know its not in queue
                    
                      
                     
                       myset.erase(it);
                       key[v]=-1;
                       s10:
                       nodePtr=head;
                       long  long    counter=0;
                       long long   altcounter=0;  
                        while(nodePtr)  
                        {
                                        ////////////////
                        counter=0;
                         altcounter=0;       
                                 
                                 //////////////  
                              if(nodePtr->name==v)
                              {
                                    counter=0;
                                     altcounter=0;       
                           
                                 downPtr = nodePtr->down; 
                                 
                                   while(downPtr) // continue through all Adjacent edges/vertices

                                     {
                                                  
                                        /*altcounter++;          
                                       cout<<"\n are :ADJ----"<<downPtr->name;
                                       cout<<"\nstate is "<<state[downPtr->name];
                                       if(state[downPtr->name]!=0)
                                       counter++;*/
                                  
                                       
                                       if((state[downPtr->name]==0)&&(elements[v][downPtr->name]<=key[downPtr->name]))
                                        {
                                         
                                                                                                                  
                                     //   
                                              p[downPtr->name]=v;
                                               it= myset.find(key[downPtr->name]);
                                               key[downPtr->name]=-1;
                                               myset.erase(it);
                                              key[downPtr->name]=elements[v][downPtr->name]; 
                                             
                                              myset.insert(key[downPtr->name]);
                                              
                                          
                                                                      
                                         }
                                        
                                           
                                        downPtr = downPtr->down; //Increment the Adjacency pointer

                                       } 
                                       
                                    
                                    it=myset.begin();
                                      
                                     
                                                                          
                                       
                                        
                                      
                                                         
                             }//if==n
                                        
                       
                  
                        nodePtr = nodePtr->next;
                          }//while nodeptr
                          
                       

               }//while q empty
              
               
                 s12: 
                       //cout<<"\nPRICE IS"<<price<<"\n";
                        printf("%I64d" ,sum);
                        printf("\n");
                // delete nodePtr,downPtr;      
        

}

///////////////


////////////////



int main()
{
  long long int t,n;
  
    cin>>t;
    while(t)
    {
            
 
     Graph s;
    s.Build_Network();
    t--;
    }

  
    return 0;
}

can u help me
thanks

i ve posted the entire code

Code:

while(t)
{
     Graph s;
     s.Build_Network();
     t--;
}

you create new instance of Graph in every loop...
is that what you really want?

tat s wat laserlight suggested since the previous iteration values were existing along with new iter values...
but i wanted to construct entirely new set of nodes and its adj list

well auralius is that cosing the prob

i see your code...
i looks like a binary tree, right?
a two-headed binary tree...
check here:
http://www.cprogramming.com/tutorial/lesson18.html

Here what I did:

Code:

void destroy(ListNode *node){
    if(node!=NULL)
    {
        destroy(node->next);
        destroy(node->down);
        delete node;
    }
}

void destroy_head(){
    destroy(head);
}

void destroy_down_head(){
    destroy(down_head);
}

then add this to your main to reset those two trees:

Code:

	s.destroy_down_head();
	s.destroy_head();

but it will CRASH!!! why...
run in debug, put break point after s.Build_Network(); watch instant s.
see...at the end of tree, some of your next and down are pointing to invalid memory location! you didn't NULL all the end of tree...
it's very RISKY!
so fix your Build_Network function, make sure all the ends are NULL-ed!!!

thanks for the reply auralius ... well i implemented an undirected graph in general.
well can u elabrate on where i am pointing to invalid location and wat shud i do to overcome please

thanks

well. your Build_Network() is very complicated... go through it slowly...make sure its ended with NULL... if i have time i'll try to look at it....

run in debug, put break point after s.Build_Network(); watch instant s.

well i am able to run it successfully for all the testcases without any interuption but the runtime error is stated by the judge system...(am not able to trace it)it must be cos of null prob as u said...but am unable to find it out...need ur help

here is my Build_Network()
i put exclamation mark (//!!!!!!!!) on place that i modify...
i also initiate every declaration of ListNode.
hope it doesn't change your code...

Code:

void Graph::Build_Network()

{
//multiset<int> myset;
 //multiset<int>::iterator it,itlow,itup;
multiset<int> myset;
multiset<int>::iterator it,itlow,itup;
   ListNode *newNode = NULL;  //This is the new vertex

   ListNode *nodePtr = NULL;   //Traversing pointer

   ListNode *downPtr = NULL;  //Edge/Adjacent Vertex Traversing pointer


   long long int num_Nodes,vertex,alt;
   long long int  i=0,j=0;

   long long int V_Name[maxnodes],key[maxnodes],p[maxnodes];
  static  long long int elements[maxnodes][maxnodes]; 
     static long long int v1[maxedges],v2[maxedges];
     //static  long long  E_Name[5*maxedges];
      static long long int  state[maxnodes],sum=0,v=0;
      static long long count=0,flag=0;
      // std::map<long long int, long long int> elements;

 
      


       myset.empty();
   // cout << "How many nodes in the graph?: ";

    scanf("%I64d",&num_Nodes); 
    //cin>>num_Nodes;
long long  int num_Edges;


            //cout << "How many Edges are connected to ";

           // cin >>num_Edges; 
           scanf("%I64d" ,&num_Edges);


     for( i = 0; i<num_Nodes; i++)

    //ifor 
     {

         V_Name[i]=i+1;
          
         
         if(i==0)
         key[V_Name[i]]=0;
         else
         key[V_Name[i]]=maxedges+maxedges+i;//1000000
         //q.push(key[V_Name[i]]);
         myset.insert(key[V_Name[i]]);
         p[V_Name[i]]=0;
         state[V_Name[i]]=0;
         newNode = new ListNode;

         newNode->name = V_Name[i];



         newNode->next = NULL;

         newNode->down = NULL;

// Building the Vertex List

         if(!head)

            head = newNode;

         else

         {

            nodePtr = head;

            while(nodePtr->next)

            nodePtr = nodePtr->next;

            nodePtr->next = newNode;

           }

}//endifor
           


        for( j=0; j<num_Edges; j++)

      //jfor   
      {
               
        
           // cout << "What is the name of edge "<< j+1 << "?: ";
            scanf("%I64d" ,&v1[j]);
            scanf("%I64d" ,&v2[j]);
            scanf("%I64d" ,&alt);
            //elements[v1[j]+v2[j]+v1[j]*v2[j]]=alt;
            elements[v1[j]][v2[j]]=0;
            elements[v2[j]][v1[j]]=0;
            
            elements[v1[j]][v2[j]]=alt;
              elements[v2[j]][v1[j]]=alt;
           // cin>>v1[j]>>v2[j]>>E_Name[v1[j]+v2[j]+(v1[j]*v2[j])];
          //  cout<<"\n e_name"<<E_Name[5];

        
        
        ListNode *nodePtr = NULL;
        ListNode *downPtr = NULL;
            nodePtr = head;
           
           while(nodePtr)  //continue through all vertices

    {

         if(nodePtr->name==v1[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode = NULL;

            down_head =nodePtr->down;

            downNode = new ListNode;

            downNode->name = v2[j];
           // downNode->w=elements[j];

            downNode->down = NULL;
			downNode->next = NULL; //!!!!!!!!!
//Building the Adjacent Vertex List

            if(!down_head)

            {

               nodePtr->down = downNode;

               down_head = downNode;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode;

            }
                 ///////// for undirected
                 nodePtr=head;
                    
          while(nodePtr)  //continue through all vertices

    {

         if(nodePtr->name==v2[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode1 = NULL;

            down_head =nodePtr->down;

            downNode1 = new ListNode;

            downNode1->name = v1[j];

            downNode1->down = NULL;
			downNode1->next = NULL; //!!!!!!!!!

//Building the Adjacent Vertex List

            if(!down_head)

            {

               nodePtr->down = downNode1;

               down_head = downNode1;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode1;

            }
            
             

         }

      // }
      
 
     
    long long int n;
    sum=0;
      while(myset.size())
      {
           s15:           
            nodePtr = head;
    
    
                      
                       it=myset.begin();
                       n=*it;
                       
                     sum+=n;
                     
                      if(myset.size()==1)
                      {
                       
                       goto s12;
                       }
                       
                       for(i=0;i<num_Nodes;i++)
                       {
                                               if(key[i+1]==n)
                                               {
                                               v=i+1;
                                               
                                               goto s11;
                                               }
                                            
                       }
                       s11:
                     
                       state[v]=1;//to know its not in queue
                    
                      
                     
                       myset.erase(it);
                       key[v]=-1;
                       s10:
                       nodePtr=head;
                       long  long    counter=0;
                       long long   altcounter=0;  
                        while(nodePtr)  
                        {
                                        ////////////////
                        counter=0;
                         altcounter=0;       
                                 
                                 //////////////  
                              if(nodePtr->name==v)
                              {
                                    counter=0;
                                     altcounter=0;       
                           
                                 downPtr = nodePtr->down; 
                                 
                                   while(downPtr) // continue through all Adjacent edges/vertices

                                     {
                                                  
                                        /*altcounter++;          
                                       cout<<"\n are :ADJ----"<<downPtr->name;
                                       cout<<"\nstate is "<<state[downPtr->name];
                                       if(state[downPtr->name]!=0)
                                       counter++;*/
                                  
                                       
                                       if((state[downPtr->name]==0)&&(elements[v][downPtr->name]<=key[downPtr->name]))
                                        {
                                         
                                                                                                                  
                                     //   
                                              p[downPtr->name]=v;
                                               it= myset.find(key[downPtr->name]);
                                               key[downPtr->name]=-1;
                                               myset.erase(it);
                                              key[downPtr->name]=elements[v][downPtr->name]; 
                                             
                                              myset.insert(key[downPtr->name]);
                                              
                                          
                                                                      
                                         }
                                        
                                           
                                        downPtr = downPtr->down; //Increment the Adjacency pointer

                                       } 
                                       
                                    
                                    it=myset.begin();
                                      
                                     
                                   if(counter==altcounter)
                                     {
                                                          
                                                           
                                                           goto s15;
                                                          
                                                           
                                     }
                                        
                                       
                                        
                                      
                                                         
                             }//if==n
                                        
                       
                  
                        nodePtr = nodePtr->next;
                          }//while nodeptr
                          
                       

               }//while q empty
              
               
                 s12: 
                       //cout<<"\nPRICE IS"<<price<<"\n";
                        printf("%I64d" ,sum);
                        printf("\n");
                // delete nodePtr,downPtr;      
        

}

thanks auralius...it agains says runtime error... i commented everything after long long int n.
ir after

Code:

long long int n;
    sum=0;
      while(myset.size())
      {

..
(ie i jsut let it scan i/p and construct node and its down)...i commented the algo itself) i changed wat ever u said....prob in the construction itself

auralius thanks. your NULL was a great help...well i got thru with runtime error...
when i comment my main algo ie after
long long int n....

i get wrong answer(as expected cos nothing i do with the inputs)...
but wen i uncomment it it gives me segmentation fault...(it must be from my implementation ie code after long long int n........


any suggestions on why do i get seg fault

sorry...
but now i'm totally confused...
i'll be back if i have time and idea...

fine. well i got the segmentation fault in the 6th second... i was not pretty sure of which part is produing me that...wheter the graph construction or the implenetation of the algo part.... so i added

Code:

 
for(i=0;i<=maxedges*maxedges;i++)
      {
      i++;
      i--;
      }

this for loops just to consume time...after the grapgh constructionand before the impleentation of algo....
the time did change ...so i guess its after the implenataion of algo
suggest me nythng if u have time
thanks