Thread: Reset values

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    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
    Last edited by dpp; 01-24-2009 at 01:09 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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)
    {
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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
    Last edited by dpp; 01-24-2009 at 06:50 AM.

  4. #4
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    Code:
    while(t)
    {
         Graph s;
         s.Build_Network();
         t--;
    }
    you create new instance of Graph in every loop...
    is that what you really want?

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    Question

    well auralius is that cosing the prob

  7. #7
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    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!!!
    Last edited by auralius; 01-24-2009 at 08:34 AM.

  8. #8
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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

  9. #9
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    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....

  10. #10
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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
    Last edited by dpp; 01-24-2009 at 10:15 AM.

  11. #11
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91

    here...

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

  12. #12
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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

  13. #13
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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
    Last edited by dpp; 01-24-2009 at 11:42 AM.

  14. #14
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    sorry...
    but now i'm totally confused...
    i'll be back if i have time and idea...

  15. #15
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    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
    Last edited by dpp; 01-25-2009 at 12:17 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 12-30-2007, 10:08 AM
  2. Reset Combo Control VS C++ 6.0
    By WaterNut in forum Windows Programming
    Replies: 8
    Last Post: 12-26-2007, 10:37 AM
  3. Need help with project
    By chrisa777 in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2006, 05:01 PM
  4. Replies: 1
    Last Post: 02-03-2005, 03:33 AM
  5. How to read in empty values into array from input file
    By wpr101 in forum C++ Programming
    Replies: 5
    Last Post: 11-28-2002, 10:59 PM