Thread: Sefmentation Fault

Yes, the code. As moderators on this board would say, post the smallest complete program that demonstrates the problem.

i will post the necessary lines of code in the enxt post

Not so much confusing, as crappily indented and overly long.

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<iostream>
#include<stdio.h>
#include <list>
#include<string.h>
using namespace std;

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

#include<map>
#define maxedges 999999

# define maxnodes  100009
# define max 100

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();     
    //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()
{
    // long long int maxedges=10000;
    ListNode *newNode;  //This is the new vertex
    ListNode *nodePtr;   //Traversing pointer
    ListNode *downPtr;  //Edge/Adjacent Vertex Traversing pointer
    multiset<int> myset;
    multiset<int>::iterator it,itlow,itup;
    long long int  num_Nodes,vertex,flag=0;
    static long long int i,j,alt;
    static long long int altnum_Edges[maxnodes];
    static long long int d[maxnodes],count,k;
    long long int  V_Name[maxnodes],p[maxnodes],t,vertex1,vertex2; 
    static long long  int  state[maxnodes],sum,v,a,b,top,big,num_Edges,altnum_Nodes;
    string str2[maxnodes];
    string s1,s2;
    std::map<long long int, long long int> elements,v1,v2;

    scanf("%I64d" ,&t);
    
    while(t)    //mainwhilet
    {
        scanf("%I64d",&num_Nodes);
        altnum_Nodes = num_Nodes;

        j=0;
        while(altnum_Nodes)
        {
            //  cout<<"\n CITY\n";
            cin>>str2[j];
            scanf("%I64d",&altnum_Edges[j]);
            num_Edges+=altnum_Edges[j];
            for(i=0;i<altnum_Edges[j];i++)
            {
                v1[k]=j+1;
                scanf("%I64d",&v2[k]);
                scanf("%I64d",&alt);
                elements[v1[k]+v2[k]+v1[k]*v2[k]]=alt;
                k++;
            }
            altnum_Nodes--;
            j++;
        }

        for( i = 0; i<num_Nodes; i++) //ifor 
        {
            V_Name[i]=i+1;  
            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

        j=0;
        while(nodePtr)
        {
            //ut<<"\n node--"<<nodePtr->name;
            nodePtr=nodePtr->next;
        }

        for( j=0; j<num_Edges; j++) //jfor   
        {
            ListNode *nodePtr;
            ListNode *downPtr;
            nodePtr = head;
            
            while(nodePtr)  //continue through all vertices
            {
                vertex=nodePtr->name;
                //  cout<<"\nall vertex"<<vertex;
                if(nodePtr->name==v1[j])
                    break;
                else
                    nodePtr=nodePtr->next;
            }
            

            ListNode *downNode;
            down_head =nodePtr->down;
            downNode = new ListNode;
            downNode->name=v2[j];
            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;
            }
        }

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

        while(final)
        {
            cin>>s1>>s2;
            //  scanf("%s",s1);
            //scanf("%s",s2);
            
            for(i=0;i<num_Nodes;i++)
            {
                if(s1.compare(str2[i])==0)
                    a=i+1;
                if(s2.compare(str2[i])==0)
                    b=i+1;
            }
            
            myset.clear();
            
            count=0;
            flag=0;        
            
            for(i=0;i<num_Nodes;i++)
            {
                d[i+1]=maxedges;
                d[a]=0;
                state[i+1]=0;
                myset.insert(d[i+1]);
                
            }
            
            while(myset.size())
            {
                count++;
                
                it=myset.begin();
                top=*it;

                if(myset.size()==1)
                {
                    goto s10;
                }

                for(i=0;i<num_Nodes;i++)
                {
                    if(d[i+1]==top)
                    {
                        vertex1=i+1;
                        goto s11;
                    }
                }

s11: 
                if(vertex1==b)
                    goto s10;

                state[vertex1]=1;
                
                nodePtr=head;
                while(nodePtr)
                {
                    if(nodePtr->name==vertex1)
                    break;
                    else         
                    nodePtr=nodePtr->next;            
                }
                downPtr=nodePtr->down;

                while(downPtr)
                {
                    //cout<<"\n adjacent of"<<vertex1<<"are"<<downPtr->name;
                    // cout<<"\n and its state is"<<state[downPtr->name];
                    if(state[downPtr->name]==0)
                    {
                        vertex2= downPtr->name;
                        // cout<<"\n--before == d["<<vertex2<<"] is--"<<d[vertex2];
                        // cout<<"\n before---enmame=="<<E_Name[vertex2+vertex1+vertex2*vertex1];
                        if(d[vertex2]>d[vertex1]+elements[vertex2+vertex1+vertex2*vertex1])
                        {
                            it=myset.find(d[vertex2]);
                            myset.erase(it);
                            d[vertex2]=d[vertex1]+elements[vertex2+vertex1+vertex2*vertex1];
                            // cout<<"\n d["<<vertex2<<"] is--"<<d[vertex2];
                            myset.insert(d[vertex2]);
                            // sum+=d[vertex2];
                            // state[vertex2]=1;
                        }
                    }
                    downPtr=downPtr->down;
                }
                it=myset.begin();
                myset.erase(it);
                d[vertex1]=-1;
            }//q
s10:        
            //cout<<d[b]<<"\n";   
            printf("%I64d",d[b]);
            printf("\n");
            final--;
        }//whilefinal        
        t--;
        printf("\n");
    }

    //delete [] position,E_Name,color,v1,v2,altnum_Edges;
    delete nodePtr,downPtr,newNode,head,down_head;
}

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

int main()
{
    Graph s;
    s.Build_Network();
    return 0;
}

Your function is over 200 lines long.
You're trying to do WAY too much work in one place, split it up.

Also, all that static data in the function is bad design. It should be part of the class.

That is far from complete.

Why do you want Salem to remove the code that you posted to Salem and me? If it's secret, don't give it out. If you want help, you have to post enough code for us to understand what you are doing [and I doubt that anyone would want to "rip off" your code - it doesn't appear like it's working, and it's not exactly a work of art - I'm sorry to say].

Code:

    long long int  V_Name[maxnodes],p[maxnodes],t,vertex1,vertex2; 
 ... 
    string str2[maxnodes];

That uses up (at least - exact amount depends on sizeof(std::string)) 24 * 100009 bytes of stack-space, which is a relatively large amount. It is probably OK, but be aware that using large amounts of stackspace can cause problems.

Code:

            cin>>str2[j];
            scanf("%I64d",&altnum_Edges[j]);

Decide if you are going to use C or C++ I/O functions. Mixing them is very likely to cause problems.

Code:

        j=0;
        while(nodePtr)
        {
            //ut<<"\n node--"<<nodePtr->name;
            nodePtr=nodePtr->next;
        }

        for( j=0; j<num_Edges; j++) //jfor   
        {
            ListNode *nodePtr;
            ListNode *downPtr;
            nodePtr = head;

Given the green bit of code, the red bit does absolutely nothing.

--
Mats

Originally Posted by dpp

wat do u mean by


and i used scanf at various places since cin wud consume a lot of time

My "that is far from complete" was referring to your post #22 above.

scanf() isn't exactly fast (considering that it parses a string and goes through all sorts of layers to actually do the translation from string to decimal etc), so I doubt there will be much difference between operator>> and scanf(). Sounds like premature optimization [and if you REALLY want to save time on I/O, it's probably best to read a large block and then translate small portions of the large block, as small I/O tends to have much more overhead than the translation of text to binary form]. But the main point is that you should decide if you use C or C++ style I/O - not mix and match as you feel like - that will almost certainly break on some architecture or another.

--
Mats

Originally Posted by dpp

do u mean to say that i have to choose completely someother method to identify the unique index may be randomize fns..

but i tot this wud do
will it not?

No, we want you to post a complete piece of code that shows the problem, that is smaller than 200 lines - particularly if you don't want to show your ACTUAL CODE, you need to post a complete problem that shows the REAL PROBLEM - not just a few lines cut out of the 200 lines. This is because our experience is that quite often, the failures of code is NOT in the bit of code that is posted, but in some of the "other" code.

Also, if you have a calculation like this:

Code:

cin>>e[v1[i]+v2[i]+v1[i]*v2[i]];

and v1, v2 are in the range 0..maxnodes, you will need maxnodes * maxnodes number of elements in e[], or you will get some sort of "out of bounds" reaction - go far enough out of bounds, and you get a page-fault (segmentation fault or whatever the OS calls it).

--
Mats

v1, v2 are in the range 0..maxnodes, you will need maxnodes * maxnodes number of elements in e[], or you will get some sort of "out of bounds" reaction - go far enough out of bounds, and you get a page-fault (segmentation fault or whatever the OS calls it).

well yes i am getting segmentation fault...but tat is the reason i used maps..but stll i am not through with it


the complete code is already found in #19