Thread: Segmentation Fault

I tried another version of my program(post "memory problem") with lists.But now i´m having a segmentation fault problem.
here´s the code:

Code:

#include <stdio.h>
#define MAX 1000  /* Array limit */

int percurso[MAX]; /* must be dinamic */
int cara=0,coroa=0;
int maxpeso=-1000000000; /* another infinite */
int in;
int ja_ta=0;
int somei=0;

typedef struct as_adjacencias
{
	int vertice;
	int peso;
	struct as_adjacencias *proximo;
} ADJACENCIAS;

typedef ADJACENCIAS* adjacencias;

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);
}
adjacencias proximo_elemento (int elemento, adjacencias* Adjacencias)
{
     if (elemento == (*Adjacencias) -> vertice)
          return (**Adjacencias).proximo;

     return proximo_elemento (elemento, &(**Adjacencias).proximo);
}

adjacencias lista[7001]; /*must be dinamic */

void poe_na_fila(int x) 
{
	percurso[coroa]=x;
	coroa++;
}
int peso_elemento(adjacencias *Adjacencias, int b)
{
     if (b== (*Adjacencias) -> vertice)
          return (*Adjacencias) -> peso;

     return peso_elemento (&(**Adjacencias).proximo,b);
}


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;
}
		
void max_peso(int source, int sink, int nodes, adjacencias proximo)
{
    int u = 0, n = 0;
    if ( ja_ta ) return;
    if (proximo==NULL && source == in) 
    {
        ja_ta = 1;
        return;
    }
    else
    {
        if (source == sink) {
            poe_na_fila(source);
        }
        else
        {
            if (proximo==NULL)
            {
                percurso[coroa] = 0;
                coroa -= 1;
                max_peso(percurso[coroa], sink, nodes,proximo_elemento(source, &(*(lista+percurso[coroa]))));
            }
            else
            {
                	
                    poe_na_fila(source);
                    max_peso(proximo->vertice, sink, nodes, lista[proximo->vertice]);
                
            }
        }
        if ( ja_ta ) return;
        else
        {
        n = somador(percurso, nodes);
        if (n > maxpeso)
            maxpeso = n;
        coroa = coroa - 1;
        percurso[coroa] = 0;
        coroa = coroa - 1;
         max_peso(percurso[coroa], sink, nodes, proximo_elemento(source, &(*(lista+percurso[coroa]))));
        }
    }
}

main (int argc, char *argv[])
{
	int noi,nof,peso,i,u,j,arcos,nos,inicio,fim;
	inicio=fim=noi=nof=i=j=peso=arcos=nos=u=0;
	FILE *fp;
	fp=fopen(argv[1],"r");
	if (fp==NULL)
		printf("Impossível abrir o ficheiro %s", argv[1]);
	else
		{
			fscanf(fp,"%d",&nos);
			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);
			in=inicio;
			max_peso(inicio,fim,nos,lista[inicio]);
			if(somei)
			printf("%d\n",maxpeso);
			else
			printf("NA\n");
		}
		

}

As I said in previous posts,the idea is to calculate max flow along a directed graph.The path is stored in the array percurso.For example:
7
9
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
1 3 4
3 5 8
5 7 12
1 7
the first path stored is 1-2-3-4-5-6-7(since we want to compute the max flow between nodes 1 and 7).Then there´s somador that calculates the flow,which is correct,21.Then the program start "moving backwards",trying to look for other paths. To do that,i have to look at the next element of the adjency list of each node. For example 6 only has a transition to 7,so proximo will be NULL. This works fine until it gets to five.Since it already used the 6 transition, it discovers the 7 one, the path becomes 1-2-3-4-5-7,but the calculated flow results in 14,and not 22,as it should be.This is my first problem.
The second is when it begins moving backwards again. Its going to search for alternative paths in 5,which sould be NULL,since there arent any others,but its not,and i get segmentation fault...
Can anyone help me?this is probably one of those small errors so hard to find...

Try adding returns shown in the following functions that I described in my last post. With this change I still get 24.

Code:

adjacencias proximo_elemento (int elemento, adjacencias* Adjacencias)
{
     if (elemento == (*Adjacencias) -> vertice)
          return (**Adjacencias).proximo;

     return proximo_elemento (elemento, &(**Adjacencias).proximo);
}

int peso_elemento(adjacencias *Adjacencias, int b)
{
     if (b== (*Adjacencias) -> vertice)
          return (*Adjacencias) -> peso;

     return peso_elemento (&(**Adjacencias).proximo,b);
}

I'm compiling with MS Visual Studio C++ v6

Or, it could be that the stack size on your comple is to small for the level of recursion. The MS VC6 that I'm using may default to a higher stack size than yours. Try increasing the stack size.

It depends on your compiler/linker. In VC6 I add a link option /stack: If for example, setting the stack to 15 mb I use the following link option:

/stack:0xe4e1c0

Which may be different on your compiler.

Just tried running using t5.in and I'm getting a stack overflow.

I set the stack to 40 mb and still getting stack overflow. I added a counter to count the levels of recursion which gets to 345085 levels before overflow which is not suprising.

I set then set the stack to 100 mb and overflowed at recursion level 862026.

200mb stack = recursion level 1724166 before overflow. This will never work until the recursion problem is sorted out.