GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 23-Jan-2009, 09:57
prem prem is offline
New Member
 
Join Date: Jan 2009
Posts: 5
prem has a little shameless behaviour in the past

Dijkstra's algorithm: segmentation fault


hi i ve just implemented dijkstra's algorithm.... used queue... for space constraints i used maps.... but stll getting segmentation fault... can u help
CPP / C++ / C Code:
#include <list>
#include<string.h>
using namespace std;
#include <queue>
  std::queue<int> q; 

# define maxedges 10009
# define maxnodes  10009
# define max 10009
class Graph

{
   private:
  

     struct ListNode

     {

      long long int name;
      long long int pos;
      long long int w;

        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();     
         void display2(long long,long long);     //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()

{

   ListNode *newNode;  //This is the new vertex

   ListNode *nodePtr;   //Traversing pointer

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


   long long int  num_Nodes,vertex;
   static long long int    i,j,position[100],color[maxnodes],d[maxnodes],count;

   long long int  V_Name[maxnodes],p[maxnodes],t; 
      long long int  E_Name[maxedges+maxedges],v1[maxedges],v2[maxedges];
      static long long  int  state[maxnodes],sum,v,a,b,top,big;
      char str[10];
      



   
       
       //cin>>t;
       scanf("%I64d" ,&t);
       printf("\n");
      while(t)
  //mainwhilet
  {
          
   
    //cin>>num_Nodes;
    scanf("%I64d" ,&num_Nodes);
    long long  int num_Edges;


            
            num_Edges=num_Nodes-1;


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

    //ifor 
     {

         V_Name[i]=i+1;
         color[i+1]=0;
         d[i+1]=max;
         p[i+1]=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   
      {
               
        
           
           cin>>v1[j]>>v2[j]>>E_Name[v1[j]+v2[j]+v1[j]*v2[j]];
          // scanf("%I64d %I64d %I64d" ,&v1[j],&v2[j],&E_Name[v1[j]+v2[j]+v1[j]*v2[j]]);
           
            

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

    {
          vertex=nodePtr->name;
         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=E_Name[j];
            downNode->pos=j+1;
            
          
        

            downNode->down = NULL;

            if(!down_head)

            {

               nodePtr->down = downNode;

               down_head = downNode;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode;

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

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

            ListNode *downNode1;

            down_head =nodePtr->down;

            downNode1 = new ListNode;
            
            
          
          
            downNode1->name = v1[j];
            downNode1->w=E_Name[j];
            downNode1->pos=j+1;

            downNode1->down = NULL;



            if(!down_head)

            {

               nodePtr->down = downNode1;

               down_head = downNode1;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode1;

            }
         }

      
              
     while(1)
    {              
   //cin>>str;
   scanf("%s",&str);
  while(!q.empty())
  q.pop();
   if(strcmp(str,"DONE")==0)break;
   for(i=0;i<num_Nodes;i++)
   {
                           color[i+1]=0;
         d[i+1]=max;
         p[i+1]=0;
         }
   if(strcmp(str,"CHANGE")==0)
          {
                             // cin>>a>>b;
                             scanf("%I64d %I64d" ,&a,&b);
                             
                              E_Name[v1[a-1]+v2[a-1]+v1[a-1]*v2[a-1]]=b;
                             
          }
   
          if(strcmp(str,"QUERY")==0)
          {
               a=0,b=0;                    
             //cin>>a>>b;
              scanf("%I64d %I64d" ,&a,&b);
             nodePtr = head; 
             color[a]=11;
             d[a]=0;
             p[a]=0;
             q.push(a);
             while(!q.empty())
             {
                              top=q.front();
                            // cout<<"\n topt os "<<top<<"\n";
                              nodePtr=head;
                              while(nodePtr)
                              {
                                   if(nodePtr->name==top)
                                   break;
                                   else         
                                nodePtr=nodePtr->next;            
                              }
                           
                              downPtr=nodePtr->down;
                              while(downPtr)
                              {
                                           vertex= downPtr->name;
                                         //  cout<<"\n adjacent down--vertex"<<downPtr->name;
                                         //  cout<<"\n colrvertex"<<color[vertex];
                                          if(color[vertex]==0)
                                          {
                                          //    cout<<"\ncolr =0";
                                              color[vertex]=11;
                                              p[vertex]=top;
                                             // cout<<"\n d--top"<<d[top];
                                             //  cout<<"\n E--vertex"<<E_Name[vertex+top];
                                              d[vertex]=d[top]+E_Name[vertex+top+vertex*top];
                                              if(d[vertex]>big) big=d[vertex];
                                              q.push(vertex);
                                            
                                           }
                                            
                                            if(vertex==b) 
                                            goto s20;
                                            downPtr= downPtr->down;        
                              }
                              q.pop();
                              color[top]=2;
             }
                              
                              
             
             


                  
                        
                                     
                  

                                  
          
          
        s20:  
                         cout<<d[vertex]<<"\n";
          
          
          } //endif  
          
          }//big while                   
                   
               
t--;
}
}





int main()
{
  
    Graph s;
    s.Build_Network();
 
   
    return 0;
}
and the input output follows the pattern.
Quote:
no.of testcases(bound 10)
no.of nodess (bound 10,000)

node name

no.of adjacent nodes

adjacent node and its weight


no.of paths to find -(bound 100)


source 1 dest 1
.
.
.


plz help
Last edited by LuciWiz : 23-Jan-2009 at 10:52. Reason: Please insert your C++ code between [cpp] & [/cpp] tags
  #2  
Old 24-Jan-2009, 07:01
Mexican Bob's Avatar
Mexican Bob Mexican Bob is offline
Member
 
Join Date: Mar 2008
Location: Chicxulub, Yucatán
Posts: 226
Mexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the rough

Re: Dijkstra's algorithm: segmentation fault


Since you obviously did not read the guidelines for posting code, go back and read them and then rewrite your post.

Most likely you are chasing an uninitialized pointer or trying to dereference a null pointer.


MxB
  #3  
Old 25-Jan-2009, 02:46
prem prem is offline
New Member
 
Join Date: Jan 2009
Posts: 5
prem has a little shameless behaviour in the past

Re: Dijkstra's algorithm: segmentation fault


thanks mexicanBob for reply
Quote:
Originally Posted by Mexican Bob
Since you obviously did not read the www.gidforums.com for posting code, go back and read them and then rewrite your post.

well i ve used code tags and have explained about the prob..the problem must be in linnes of code...but i had to post the entire code cos i am not sure where the error is....but still i ve modidied the graph construction part
Quote:
Most likely you are chasing an uninitialized pointer or trying to dereference a null pointer.



can u elabrate on thsi please.... that ll solve the problem..i am stuck with it for a long long time


more over am not able to edit the first post...the option is disabled.....
  #4  
Old 25-Jan-2009, 02:58
prem prem is offline
New Member
 
Join Date: Jan 2009
Posts: 5
prem has a little shameless behaviour in the past

Re: Dijkstra's algorithm: segmentation fault


i have done the following changes in the build function

at the start of build function
i initialised NULL..(first i dint)
CPP / C++ / C Code:
ListNode *newNode = NULL;  //This is the new vertex

   ListNode *nodePtr = NULL;   //Traversing pointer

   ListNode *downPtr = NULL;  //Edge/Adjacent Vertex Traversing pointer[/code]
and i also did downnode->next=NULL in 
[code]while(nodePtr)  //continue through all vertices

    {

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

            ListNode *downNode1 = NULL;

            down_head =nodePtr->down;

            downNode1 = new ListNode;

            downNode1->name = v1[j];

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

i will be greatful if u help me with it.
thanks
Last edited by admin : 25-Jan-2009 at 03:12. Reason: Please insert your example C/C++ codes between [CPP] and [/CPP] tags
  #5  
Old 25-Jan-2009, 11:45
prem prem is offline
New Member
 
Join Date: Jan 2009
Posts: 5
prem has a little shameless behaviour in the past

Re: Dijkstra's algorithm: segmentation fault


is my way of graph construction and traversals not the ebst ones...its exceeding the time limit....
can i better it anyways...
please help
 
 

Recent GIDBlogProblems with the Navy (Chiefs) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
I have a segmentation fault in my project takachi C++ Forum 6 09-Mar-2008 23:30
Find the Segmentation Fault jlwelch C Programming Language 3 10-Oct-2006 11:16
My Bane - The Segmentation Fault DCOM C Programming Language 6 08-Feb-2005 23:58
segmentation fault in c++ rushman8282 C++ Forum 2 26-Jan-2005 04:38
child pid xxx exit signal Segmentation fault (11) bezak Apache Web Server Forum 1 24-Nov-2003 10:18

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 15:01.


vBulletin, Copyright © 2000 - 2009, Jelsoft Enterprises Ltd.