Thread: Segmentation Fault

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

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

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...

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;

}

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.

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.

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.

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...

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.

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...