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
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
what else you have added?
check here:
nodePtr = head, while head could be NULLCode: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]; : : }
the you did: down_head =nodePtr->down
this is a culprit...
may be you check first,
i runned in debug, and always crash here!Code:if (nodePtr) down_head =nodePtr->down; //!!!!!!!!!!!!!!!!!!!!
see part with "//!!!!!!!!!!!!!!!!!!!!!!!!"
Last edited by auralius; 01-25-2009 at 10:41 PM.
well aurilus u say that nodePtr will be null at that point...
but i dont think
becauseeven if v1[j] is the last element in the list then i will break ,.... i dint increment nodePtr=nodePtr->next;Code:while(nodePtr) //continue through all vertices { if(nodePtr->name==v1[j]) break; else 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
What if none of the vertices have name == v1[j]? If that condition is logically possible, you should write something like this:Originally Posted by dpp
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; } 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. }
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.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]; // ...
Oh, and you need to break up your function into smaller ones.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
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....
Yes...
See below
i think i can conclude that your common problem is due to a careless pointer assignment...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
how if i ask: what will happen if nodePtr is NULL...Code:nodePtr->down = downNode
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
thanks ...u mean to say
fine... but i am puzzled with one big thing...when will i have my nodePtr null...Code:if(nodePtr) { nodePtr->down = downNode; //!!!!!!!!!!!!!!!!!!!!! crash here! why...?? down_head = downNode; }
assume that the user i/p's are all safe....how will my nodeptr point to null...or where is it pointing to null
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
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.Originally Posted by dpp
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
but laserlight my question is ..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.Originally Posted by dpp
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
well, that's the fact.. i entered random number every time it asks...