Ok,so here´s the deal. I have to make a program to calculate the maximum flow along a directed acyclic graph. I managed to tho that,the program is working perfectly,but only with "small" inputs.My teachers are going to test it with 16mb(or more) inputs,so i have to make it ready for that.The input file looks like this:
4
6
1 2 -134
1 3 -74
1 4 -31
2 3 -170
2 4 -57
3 4 -174
1 4
Where the first line is the number of nodes,the second the number of edges,the others represent the edges(for example, from node 1 to 2 the flow is -134), and the last one represents the nodes between we wish to calculate the max flow.In this particular case,the result is -31, which is correct in my program.But, with inputs like http://mega.ist.utl.pt/~smcos/t4.in the program SEEMS to enter an infinite cycle.Tried the debugg in eclipse,and after a few minutes watching the program compute the flows along some paths,it just closed eclipse.No error, no infinite cycle,just closed.Tried again,closed at a different point.I have no idea why this happens.Hope someone can help me!
here´s my code:
Code:
#include <stdio.h>
#define MAX 1000 /* Array limit */
int percurso[MAX]; /* must be dinamic */
int cara=0,coroa=0;
int maxpeso=-1000000000; /* 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)
{
while (elemento != (*Adjacencias) -> vertice)
Adjacencias = &(**Adjacencias).proximo;
return (**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)
{
while (b!= (*Adjacencias) -> vertice)
Adjacencias = &(**Adjacencias).proximo;
return (*Adjacencias) -> peso;
}
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;
while(ja_ta==0)
{
if (proximo==NULL && source == in)
{
ja_ta = 1;
return;
}
else
{
if (source == sink) {
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];
}
}
}
}
}
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("%dn",maxpeso);
else
printf("NAn");
}
}
Sorry if it is in portuguese,hope u understand the funcions.HELP!