Printable View
I´m trying to do a quite simple thing,read a file which as values displayed like this:
1 2 3
3 4 5
5 6 6
...
and then i´m doing this:
But the problem is that it keeps reading the same line over and over...I tried a file like this:Code:
while(fscanf(fp,"%d %d %d",&noi,&nof,&peso)!=EOF)
{
capacidade[noi][nof] = peso;
}
John 12
Mary 15
...
and then
and its working...Can someone explain to me the difference?Code:while(fscanf(fp,"%s %d",Name,&age)!=EOF)
printf("%s %d", Name,age);
>>while(fscanf(fp,"%d %d %d",&noi,&nof,&peso)!=EOF)
This should really be:
>>while(fscanf(fp,"%d %d %d",&noi,&nof,&peso) == 3)
Post some more code if you're still having trouble.
Now it only reads one line...For example:
0 1 16 // capacity from 0 to 1 is 16
0 2 13 // capacity from 0 to 2 is 13
1 2 10 // capacity from 1 to 2 is 10
2 1 4 // capacity from 2 to 1 is 4
3 2 9 // capacity from 3 to 2 is 9
1 3 12 // capacity from 1 to 3 is 12
2 4 14 // capacity from 2 to 4 is 14
4 3 7 // capacity from 4 to 3 is 7
3 5 20 // capacity from 3 to 5 is 20
4 5 4 // capacity from 4 to 5 is 4
it reads the first, noi=0,nof=1,peso=16 and stores them in the array,but then the next fscanf is not 3 anymore...why is this happening?
By the way,im looking for an implementation of the ford fulkerson algorithm for the maximum flow problem,i was wondering if anyone has it...I´ve found one,but it had some limitations that my program cant have:for example,i the edges don´´t have to be ordered (1 2 3, 1 4 5, 4 5 6...) and the capacity of a path can be 0 or negative...
well,already solved the fscanf problem...thnks anyway.Now i realized that my program doesnt work correctly...This algorithm is a bit weird...
ok,so i managed to write my program,but now i´m having another problem:its always returning 0...Here´s the code:
This is an implementation of the ford fulkerson algorhitm for the maximum flow problem along an directed graph. The imput file looks like this:Code:#include <stdio.h>
#define MAX 1000
#define BRANCO 0 /* por descobrir */
#define PRETO 2 /* descoberto e fim de caminho */
#define CINZENTO 1 /* descoberto */
#define oo 1000000000 /* era suposto representar infinito (um infinito daqueles pequenos) */
int capacidade[MAX][MAX]; /*guarda os arcos com as capacidades */
int percurso[MAX]; /* guarda o percurso */
int cores[MAX]; /* para a bfs */
int cara, coroa; /* nomes originais :) */
int flow[MAX][MAX];
int vector[MAX+2];
void poe_na_fila(int x) /* nos que vao sendo descobertos */
{
vector[coroa]=x;
coroa++;
cores[x]=CINZENTO;
}
int min(int x, int y)
{
return x<y ? x : y; /* devolve o menor entre x e y */
}
int tira_da_fila() /* caminho descoberto => no preto */
{
int x= vector[cara];
cara++;
cores[x]= PRETO;
return x;
}
int bfs (int fabrica_xoricos, int armazem_xoricos, int nos)
{
int u,v;
u=v=0;
for(u=0;u<nos;u++)
{
cores[u]= BRANCO;
}
cara=coroa=0;
poe_na_fila(fabrica_xoricos);
percurso[fabrica_xoricos]=-1;
while (cara != coroa)
{
u= tira_da_fila();
for(v=0; v<nos; v++)
{
if(cores[v] == BRANCO && capacidade[u][v]-flow[u][v]>0)
{
poe_na_fila(v);
percurso[v]=u;
}
}
}
return cores[armazem_xoricos]==PRETO;
}
int max_peso(int inicio, int fim, int nos)
{
int i,j,u;
i=j=u=0;
int maxpeso=0;
int peso=oo;
for (i=0; i<nos; i++)
{
for(j=0; j<nos;j++)
{
flow[i][j]=0;
}
}
/* Enquanto existir um caminho, calcula o peso desse caminho */
while(bfs(inicio, fim, nos))
{
for(u=nos-1; percurso[u]>0; u=percurso[u])
{
peso=min(peso, capacidade[percurso[u]][u]-flow[u][u]);
}
for(u=nos-1; percurso[u]>=0; u=percurso[u])
{
flow[percurso[u]][u] +=peso;
flow[u][percurso[u]] -=peso;
}
maxpeso +=peso;
}
/* ja nao existem mais caminhos */
return maxpeso;
}
main (int argc, char *argv[])
{
int noi,nof,peso,i,j,arcos,nos,inicio,fim;
inicio=fim=noi=nof=i=j=peso=arcos=nos=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(i=0; i<nos;i++)
{
for(j=0;j<nos;j++)
capacidade[i][j]=0;
}
for(i=0;i<arcos;i++)
{
fscanf(fp,"%d %d %d", &noi,&nof,&peso);
capacidade[noi][nof]=peso;
}
fscanf(fp,"%d %d", &inicio, &fim);
printf("%d\n",max_peso(inicio,fim,nos));
}
}
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
Where the first 2 lines represent the number of nodes and edges, the next lines represent the edges, and the last one represents the nodes between we wish to calculate the max flow. THe problem is my program is always returning 0. Can someone help me with this?(in this particular example it should return 24).
I was wondering if anyone can correct my code,if it isnt very clear,i can change the name of the functions and the commentarys to english. And i can explain the ford fulkerson and the bfs algortithm for those who dont know.i´m sorry if i´m asking too much,but im quite a begginer so i cant find the error which is causing the program to always return 0.I think its working ok with the algorithms,must be another problem...:(
>while(bfs(inicio, fim, nos))
bfs function returns 0 on the first call so the while loop is never run and returns from max_peso(). I don't really understand what bfs() is trying doing!
>return cores[armazem_xoricos]==PRETO;
armazem_xoricos = 7
cores[armazem_xoricos] = 0
bfs function is the breadth first search algorithm. the idea is, given a vertex s, find every vertex that is reachable from s.It also produces a tree, with the root s and all reachable vertices. i have the implentation of that function here and its very similar to what i did...here it is:(discover the differences :))
Code:int bfs (int start, int target) {
int u,v;
for (u=0; u<n; u++) {
color[u] = WHITE;
}
head = tail = 0;
enqueue(start);
pred[start] = -1;
while (head!=tail) {
u = dequeue();
// Search all adjacent white nodes v. If the capacity
// from u to v in the residual network is positive,
// enqueue v.
for (v=0; v<n; v++) {
if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
enqueue(v);
pred[v] = u;
}
}
}
// If the color of the target node is black now,
// it means that we reached it.
return color[target]==BLACK;
}
Humm...not getting much replies,starting to worry(just a little) :(
hope this helps, this is the page where i found a program,and i based my program in this one:
http://www.aduni.org/courses/algorit..._09.html#25629
the only problem with this program isnt ANSI C. and iLm not sure if the capacities can be negative values or zero,but in my program they can. ILm not even sure if iLm supposed to use this ford fulkerson algorhitm,but i was told that it was the only way of computing the maximum flow in a directed graph.oh,by the way,the graph in the program must be acyclic, i think it doesnt matter for the algorithm.A lot of info can be found in google about graph and maximum flow.this is what i found in a book(introduction to algorthims) i bought today:
help ,please!Quote:
26.2 The Ford-Fulkerson method
This section presents the Ford-Fulkerson method for solving the maximum-flow problem. We
call it a "method" rather than an "algorithm" because it encompasses several implementations
with differing running times. The Ford-Fulkerson method depends on three important ideas
that transcend the method and are relevant to many flow algorithms and problems: residual
networks, augmenting paths, and cuts. These ideas are essential to the important max-flow
min-cut theorem (Theorem 26.7), which characterizes the value of a maximum flow in terms
of cuts of the flow network. We end this section by presenting one specific implementation of
the Ford-Fulkerson method and analyzing its running time.
The Ford-Fulkerson method is iterative. We start with f(u, v) = 0 for all u, v V, giving an
initial flow of value 0. At each iteration, we increase the flow value by finding an
"augmenting path," which we can think of simply as a path from the source s to the sink t
along which we can send more flow, and then augmenting the flow along this path. We repeat
this process until no augmenting path can be found. The max-flow min-cut theorem will show
that upon termination, this process yields a maximum flow.
FORD-FULKERSON-METHOD(G, s, t)
1 initialize flow f to 0
2 while there exists an augmenting path p
3 do augment flow f along p
4 return f
The basic Ford-Fulkerson algorithm
In each iteration of the Ford-Fulkerson method, we find some augmenting path p and increase
the flow f on each edge of p by the residual capacity cf(p). The following implementation of
the method computes the maximum flow in a graph G = (V, E) by updating the flow f[u, v]
between each pair u, v of vertices that are connected by an edge.[1] If u and v are not
connected by an edge in either direction, we assume implicitly that f[u, v] = 0. The capacities
c(u, v) are assumed to be given along with the graph, and c(u, v) = 0 if (u, v) ∉ E. The
residual capacity cf(u, v) is computed in accordance with the formula (26.5). The expression
cf(p) in the code is actually just a temporary variable that stores the residual capacity of the
path p.
FORD-FULKERSON(G, s, t)
1 for each edge (u, v) E[G]
2 do f[u, v] © 0
3 f[v, u] © 0
4 while there exists a path p from s to t in the residual network Gf
5 do cf(p) © min {cf(u, v) : (u, v) is in p}
6 for each edge (u, v) in p
7 do f[u, v] © f[u, v] + cf(p)
8 f[v, u] © -f[u, v]