Thread: Reset values

  1. #16
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    solved it....now its exceeding the time limit...
    is my way of graph construction and traversal not the best one..... can it be bettered some way...please help

  2. #17
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    what else you have added?
    check here:

    Code:
    void Graph::Build_Network()
    
    {
            :
            :
    	ListNode *nodePtr = NULL;
    	ListNode *downPtr = NULL;
    	nodePtr = head;
    
    	while(nodePtr)  //continue through all vertices
    	{
    		if(nodePtr->name==v1[j])
    		break;
    	else
    		nodePtr=nodePtr->next; //!!!!!!!!!!!!!!!!!!!! this is will be OK because you check first with while (nodePtr)
    	}
    
    	ListNode *downNode = NULL;
    	down_head =nodePtr->down;  //!!!!!!!!!!!!!!!!!!!!!!!!!!what about here????
    	downNode = new ListNode;
    	downNode->name = v2[j];
    	// downNode->w=elements[j];
           :
           :
    }
    nodePtr = head, while head could be NULL
    the you did: down_head =nodePtr->down
    this is a culprit...

    may be you check first,
    Code:
    if (nodePtr)
        down_head =nodePtr->down; //!!!!!!!!!!!!!!!!!!!!
    i runned in debug, and always crash here!


    see part with "//!!!!!!!!!!!!!!!!!!!!!!!!"
    Last edited by auralius; 01-25-2009 at 10:41 PM.

  3. #18
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    well aurilus u say that nodePtr will be null at that point...
    but i dont think
    because
    Code:
     while(nodePtr)  //continue through all vertices
    
               {
    
             if(nodePtr->name==v1[j])
             break;
              else
              nodePtr=nodePtr->next;
              }
    even if v1[j] is the last element in the list then i will break ,.... i dint increment nodePtr=nodePtr->next;
    so it wont be null....
    but whwre s it breaking...i am still puzzled
    i may be wrong
    well i have not solved the issue til now

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by dpp
    even if v1[j] is the last element in the list then i will break ,.... i dint increment nodePtr=nodePtr->next;
    so it wont be null....
    What if none of the vertices have name == v1[j]? If that condition is logically possible, you should write something like this:
    Code:
    while (nodePtr && nodePtr->name != v1[j])
    {
        nodePtr = nodePtr->next;
    }
    
    if (nodePtr)
    {
        ListNode *downNode = NULL;
        down_head =nodePtr->down;
        downNode = new ListNode;
        downNode->name = v2[j];
    
        // ...
    }
    else
    {
        // v1[j] is not in the list.
        // Print a message to inform the user, throw an exception, etc.
    }
    If that condition is logically impossible, use an assertion to document the fact, e.g.,
    Code:
    while (nodePtr && nodePtr->name != v1[j])
    {
        nodePtr = nodePtr->next;
    }
    
    assert(nodePtr && "No vertex has the given name!");
    
    ListNode *downNode = NULL;
    down_head =nodePtr->down;
    downNode = new ListNode;
    downNode->name = v2[j];
    
    // ...
    In this case it does seem possible, even probable, that the user could provide a name that does not correspond to any vertex, so I would choose the former.

    Oh, and you need to break up your function into smaller ones.
    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

  5. #20
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    well i need not take care of tat case...its with the assumption that v1 belongs to one of the nodes in nodeptr....

    it can never violate it

  6. #21
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    well auralius can u check with this please ...if its crashing wen u run..
    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>
    #include<map>
    
    using namespace std;
    
    
    //template < class Key, class Compare = less<Key>,
         //      class Allocator = allocator<Key> > class multiset;
    
    # define maxedges 300009
    # define maxnodes  2059
    long long int price=0;
    
    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
    
            
                 //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;
       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]; 
        
         std::map<long long int, long long int> v1,v2;
        
          static long long int  state[maxnodes],sum=0,v=0;
          static long long count=0,flag=0;
          
    
     
          
    
         if(!myset.empty())
          myset.clear();
           
      
        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;
            
    
            
            
            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;
               if (nodePtr)
        down_head =nodePtr->down;
                //down_head =nodePtr->down;
    
                downNode = new ListNode;
    
                downNode->name = v2[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;
                if (nodePtr)
        down_head =nodePtr->down;
                //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;
                           
                            while(nodePtr)  
                            {
                                            ////////////////
                                  
                                     
                                     //////////////  
                                  if(nodePtr->name==v)
                                  {
                                               
                               
                                     downPtr = nodePtr->down; 
                                     
                                       while(downPtr) // continue through all Adjacent edges/vertices
    
                                         {
                                                      
                                          
                                      
                                         
    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<<price*sum<<"\n";
                           
                    
                    delete nodePtr,downPtr,newNode,head,down_head;     
            
    
    }
    
    ///////////////
    
    
    ////////////////
    
    
    
    int main()
    {
      long long int t,n;
      
        cin>>t;
        while(t)
        {
                
        cin>>price;
         Graph s;
        s.Build_Network();
       
        t--;
      
        }
    
     
        return 0;
    }

    i dint use the dsestroy fns given by u...instread i use delete operation...guess this will do... wen i used destroy i was able to see it crashing....

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

    Thumbs up

    Yes...
    See below
    Code:
    while(nodePtr)  //continue through all vertices
    {
    
             if(nodePtr->name==v1[j])
                 break;
             else
                 nodePtr=nodePtr->next;
    }
              
                 
    ListNode *downNode = NULL;
    
    if (nodePtr)                  //!!!!!!!!!!!! You added this as per my first suggestion, right?
           down_head =nodePtr->down; //!!!!! Now, it's safe, but........
    
    //down_head =nodePtr->down;
    
    downNode = new ListNode;
    
    downNode->name = v2[j];
              
    downNode->down = NULL;
    
    
    downNode->next = NULL;
    
    //Building the Adjacent Vertex List
    
    if(!down_head)
    {
    
           nodePtr->down = downNode; //!!!!!!!!!!!!!!!!!!!!! crash here! why...??
           down_head = downNode;
    
     }
    
     else
    i think i can conclude that your common problem is due to a careless pointer assignment...
    Code:
    nodePtr->down = downNode
    how if i ask: what will happen if nodePtr is NULL...
    well, easy, its nodePtr->down will be pointing to invalid location on memory...
    see...!!!
    but you then assign downNode to it...

    my suggestion, go through all your function...
    be careful when you assigned to or from
    blabla->down or blabla->from
    because if blabla is NULL then its blabla->down or blabla->from will be pointing to invalid location on memory...(as i said before)...

    cheers

  8. #23
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    thanks ...u mean to say
    Code:
    if(nodePtr)
    {
      nodePtr->down = downNode; //!!!!!!!!!!!!!!!!!!!!! crash here! why...??
           down_head = downNode;
    }
    fine... but i am puzzled with one big thing...when will i have my nodePtr null...

    assume that the user i/p's are all safe....how will my nodeptr point to null...or where is it pointing to null

  9. #24
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by dpp View Post
    how will my nodeptr point to null...or where is it pointing to null
    Code:
    while(nodePtr)  //continue through all vertices
    {
    
             if(nodePtr->name==v1[j])
                 break;
             else
                 nodePtr=nodePtr->next;
    }
    when you leave the while loop without entering if even once - what is the value of nodePtr?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #25
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    i know that ...but it wont exit the while loop without entering if

  11. #26
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by dpp
    i know that ...but it wont exit the while loop without entering if
    It might. Even if you claim that the input is guaranteed to be correct, you should still check for it. At the very least you should use an assertion to document your assumption, as I stated, but an assertion is not really the best tool for that since it means that invalid user input in a release build would result in undefined behaviour whereas invalid user input in a debug build will trigger an assertion failure.
    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

  12. #27
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    but laserlight my question is ..Is it only because of user's bad i/p tat crash will occur???

  13. #28
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by dpp
    Is it only because of user's bad i/p tat crash will occur?
    In that particular case, I am inclined to say yes, but it would help if you indented your code more consistently and separated it into smaller functions. However, you apparently have other problems lurking in your code.
    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

  14. #29
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by dpp View Post
    but laserlight my question is ..Is it only because of user's bad i/p tat crash will occur???
    There is no such ting as bad user input - user could enter anything.

    There is bad verification of received data.

    So it is your bug, not user's...
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  15. #30
    a newbie :p
    Join Date
    Aug 2008
    Location
    Zurich, Switzerland, Switzerland
    Posts
    91
    well, that's the fact.. i entered random number every time it asks...

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