Segmentation Fault

This is a discussion on Segmentation Fault within the C Programming forums, part of the General Programming Boards category; That level of recursion is normal,since there are 2000 nodes and 39894 edges,so thousands of possible combinations.For example, in the ...

  1. #16
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    That level of recursion is normal,since there are 2000 nodes and 39894 edges,so thousands of possible combinations.For example, in the 16 mb file,there are 7000 nodes and 1225213 edges...

  2. #17
    Registered User
    Join Date
    Mar 2003
    Location
    UK
    Posts
    169
    500mb stack = recursion level 4,310,578 before stack overflow. Is this level normal? If it is then you're going to need to reduce the amount of memory that's used on the stack on each recursion. i.e. pass less parameters to max_peso, make more globals etc...

    Also MAX needs to be upped to 2000 for t5.in
    Last edited by Scarlet7; 04-20-2003 at 11:27 AM.

  3. #18
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Not sure,like i said 2000 nodes and 39894 edges...There are a variable j which is not used anymore,it was the first version of the program,but all the others are necessary...Updated the code in the first post
    Last edited by Lost__Soul; 04-20-2003 at 11:32 AM.

  4. #19
    Registered User
    Join Date
    Mar 2003
    Location
    UK
    Posts
    169
    The max number of recursion levels using a function call with no parameters, return codes or local variables and 500 mb stack size is 5,952,618 before a stack overflow. You're not going to get any better than this.

    You're going to have look at performing the calculations with no recursive calls.

  5. #20
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    There´s no way of doing those calculations without recursion...Thnks anyway...
    Hope anyone has an idea of solving that stack thing.I also have to make all the arrays dinamic,already asked that in a previous post.both percurso and lista should have only the number of nodes.This stack thing is driving me nuts...
    Last edited by Lost__Soul; 04-20-2003 at 01:45 PM.

  6. #21
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Well,yesterday i managed to implement the program with almost no recursion.The stack overflow problem is solved.But now, when i run the program with t4.in, i get an infinite cycle.Since this is quite odd,i tried the debug in eclipse,saw the program compute sucessive flows correctly until it just closed eclipse!no error,no infinite cycle, just closed!Can anyone understand this?i believe there´s only one or 2 details more in order to make the program work perfectly.Here´s the new code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    int *percurso; /* stores the path */
    int coroa=0; /* just a variable, could have another name */
    int maxpeso=-1000000000; /* infinite, because flow can be negative*/
    int in; /* represents always the first node */
    int ja_ta=0; /* indicates if all the flows have been computed */
    int somei=0; /*indicates if any flow has been made */
    
    typedef struct as_adjacencias
    {
    	int vertice;
    	int peso;
    	struct as_adjacencias *proximo;
    } ADJACENCIAS;
    
    typedef ADJACENCIAS* adjacencias;
    
    /*adds a new element to the adjacency list */
    void insere (adjacencias* Adjacencias, int nof, int peso) 
    {
    	if(*Adjacencias == NULL)
    		{
     			*Adjacencias=(adjacencias)malloc(sizeof(ADJACENCIAS));
    			if(*Adjacencias == NULL)
    				return;
    				(*Adjacencias) -> vertice=nof;
    				(*Adjacencias) -> peso=peso;
    				(**Adjacencias).proximo = NULL;
    		}
    		else
    			insere (&(**Adjacencias).proximo, nof, peso);
    }
    /* gives the next edge of node "elemento". For example, if we
     * have 2 paths from node 5 to node 7, one from node 5 to 6 and
     * then to 7,and another directly from 5 to 7:after we computed
     * the path which involves the 3 nodes, we want to compute the
     * one that involves only 5 and 7.In this case, proximo would
     * be the transition with 7.*/
    adjacencias proximo_elemento (int elemento, adjacencias* Adjacencias)
    {
         while (elemento != (*Adjacencias) -> vertice)
        	Adjacencias = &(**Adjacencias).proximo;
    
         return (**Adjacencias).proximo;
    
    }
    
    /* stores the edges, and the capacities of each path*/
    adjacencias *lista;
    
    /* puts a node in the percurso array which corresponds to the path */
    void poe_na_fila(int x)
    {
    	percurso[coroa]=x;
    	coroa++;
    }
    /* searches the list of one node, for the capacitie of
     * node b */
    int peso_elemento(adjacencias *Adjacencias, int b)
    {
         while (b!= (*Adjacencias) -> vertice)
         	Adjacencias = &(**Adjacencias).proximo;
    
         return (*Adjacencias) -> peso;
    }
    
    /* after each path has been calculated, this function
     * computes the flow of the path by adding the peso from
     * each transition */
    int somador(int percurso[],int nos)
    {
    	int i=0,soma=0;
    	somei=1;
    	for(i=0; i< coroa-1;i++)
    		soma += peso_elemento(&lista[percurso[i]],percurso[i+1]);
    	return soma;
    }
    
    /* searches for paths
     * if ja_ta is 1, it means that all flows have been calculated
     * after that, the maximum flow is maxpeso*/
    void max_peso(int source, int sink, int nodes, adjacencias proximo)
    {
        int  n = 0;
       	while(ja_ta==0)
       	{
        if (proximo==NULL && source == in) /* if all paths have been calculated */
        {
            ja_ta = 1;
            return;
        }
        else
        {
            if (source == sink) { /* if we found a complete path */
                poe_na_fila(source);
                 n = somador(percurso, nodes);
            if (n > maxpeso)
                maxpeso = n;
            coroa = coroa - 1;
            percurso[coroa] = 0;
            coroa = coroa - 1;
            proximo=proximo_elemento(source, &(*(lista+percurso[coroa])));
            source=percurso[coroa];
    
            }
            else
            {
                if (proximo==NULL)
                {
                    percurso[coroa] = 0;
                    coroa -= 1;
                    proximo=proximo_elemento(source, &(*(lista+percurso[coroa])));
                     source=percurso[coroa];
                }
                else
                {
    
                        poe_na_fila(source);
                        source=proximo->vertice;
                        proximo=lista[proximo->vertice];
    
                }
            }
    
       	}
       	}
    
    }
    int main (int argc, char *argv[])
    {
    	int noi,nof,peso,i,u,j,arcos,nos,inicio,fim;
    	FILE *fp;
    	inicio=fim=noi=nof=i=j=peso=arcos=nos=u=0;
    	fp=fopen(argv[1],"r");
    	if (fp==NULL)
    		printf("Impossivel abrir o ficheiro %s\n", argv[1]);
    	else
    		{
    			fscanf(fp,"%d",&nos);
    			percurso=(int *)malloc((sizeof(int)*(nos+1))); /* number of nodes */
    			lista=(adjacencias *)malloc((sizeof(ADJACENCIAS)*(nos+1)));
    			fscanf(fp,"%d",&arcos);
    			for(u=0;u<=nos;u++)
    			{
    				percurso[u]=0;
    			}
    			for(j=0; j<=nos;j++)
    				lista[j]=NULL;
    			for(i=0;i<arcos;i++)
    			{
    
    				fscanf(fp,"%d %d %d", &noi,&nof,&peso);
    				insere(&lista[noi],nof,peso);
    			}
    			fscanf(fp,"%d %d", &inicio, &fim);
    			fclose(fp);
    			in=inicio;
    			max_peso(inicio,fim,nos,lista[inicio]);
    			if(somei) /* if no sum has been made, then theres no maxpeso */
    			printf("%d\n",maxpeso);
    			else
    			printf("NA\n");
    			free(lista);
    			free(percurso);
    		}
    		return 0;
    
    }
    Last edited by Lost__Soul; 04-23-2003 at 01:00 PM.

  7. #22
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    You should be checking the return codes from your your fscanf() functions. There may be other problems, I haven't read all of your code.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  8. #23
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    The return codes?you mean if i´m "fecthing" the right parameters?Already confirmed that, the last thing fscanf catches is the inicio and fim nodes, 1 and 300.Must be another problem

  9. #24
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Originally posted by Lost__Soul
    The return codes?you mean if i´m "fecthing" the right parameters?Already confirmed that, the last thing fscanf catches is the inicio and fim nodes, 1 and 300.Must be another problem
    Observe
    Code:
      if (fscanf(fp, "%d", &myint) != 1)
      {
        /* Handle error */
      }
      
      OR
      
      if (fscanf(fp, "%d %d", &myint1, &myint2) != 2)
      {
        /* Handle error */
      }
    This might not be related to your problem, but you should be doing it anyway.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  10. #25
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Yes, i understood,but since the files that my program analyzes are supposed to be always in the same format,i guess there´s no need for that.Thnks for the advice,anyway.Must be another thing causing this strange error

  11. #26
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Lesson number one, never trust anything that is outside of your control. At least, that's in the "real world", I suppose a homework example is different, so it's up to you if you want to check the input or not.

    Now to the infinite loops. Read through your code, finding all the possible points at which the code could loop, then put some printf()'s within them. Run the prog, and see which printf()'s get output infinitely, then debug from there.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  12. #27
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    I´m a very trustfull person
    No,serious, it was said to me that the inputs will be all in the same format,no need to check them.
    As for the cycle thing,i tried the program with small inputs,like in the first post,and it worked. And, since eclipse has a good debug I added a breakpoint in the point where it computes a flow.In the "not so large" input file,t4.in, the flows are correctly computed but at random flow,because i made the debug 3 times,eclipse closes whithout gaving any error message...Also the flow could be always the same,which would be strange,but would mean that the program entered an infinite cycle,but no,they´re all different and are correct.

    Now i tried to run the program with t6.in , the 16Mb input file, and got exactly the same thing: that strange "infinite cycle".Run the debug with the file,the flows are also correctly computed(even saw the final flow),but ,as for t4.in,eclipse closes at a random flow.Odd...
    Last edited by Lost__Soul; 04-22-2003 at 11:00 AM.

  13. #28
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Updated the code. Now all the arrays are dinamic.Still the infinite cycle problem...

  14. #29
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Originally posted by Lost__Soul
    Still the infinite cycle problem...
    Maybe this never becomes true:
    >>if (proximo == NULL && source == in)

    Understanding your code is difficult for me, as most of the text isn't in English All I can suggest is you determine when YOU think that test should become true, and do some debugging to determine why your prog never appears to come to the same conclusion.

    Also, get rid of the unnecessary global variables, especially percurso, which conflicts with a local variable in the somador function.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  15. #30
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Well,i guess u really arent understanding my code,since there´s no conflict what so ever...I´ll try to write more commentarys.And,please, try to be more attentive to the other replys to my post:The stop condition IS verified in other inputs, like the one i gave in the first place;and i already did the debug!like i said,after a lot of flows computed,at a random place,the program just closes!I cant do more than this!

    Ok,i updated the code again, if u cant understand it this way, please just try to run the code in debug with the example from the first post and then with t4.in,try to find the differences,because, apart from being a bigger file,i cant see any others...

    Oh,and let me try to explain the stop condition once more...
    So the program calculates paths, for example we have the path:
    1-2-5-6-8,which are the number of nodes in percurso.
    After computing the flow in this path, it would be good to return to node 6 and see if there were any alternative paths from 6 to 8.If there arent any,we just go to node 5 and repeat the same analysis.When it founds an alternative path it stores the nodes in percurso until it reaches node 8 again.When during the backwards movement we have reached the first node,the "in",and there´s no alternative path in node in,so proximo=NULL, then it means that all paths have been analyzed and the max flow is maxpeso.Hope i was clear enough...
    Last edited by Lost__Soul; 04-23-2003 at 01:52 AM.

Page 2 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault problem
    By odedbobi in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2008, 02:36 AM
  2. Segmentation fault
    By bennyandthejets in forum C++ Programming
    Replies: 7
    Last Post: 09-07-2005, 05:04 PM
  3. Segmentation fault
    By NoUse in forum C Programming
    Replies: 4
    Last Post: 03-26-2005, 02:29 PM
  4. Locating A Segmentation Fault
    By Stack Overflow in forum C Programming
    Replies: 12
    Last Post: 12-14-2004, 12:33 PM
  5. Segmentation fault...
    By alvifarooq in forum C++ Programming
    Replies: 14
    Last Post: 09-26-2004, 12:53 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21