Just a simple question...

This is a discussion on Just a simple question... within the C Programming forums, part of the General Programming Boards category; Im trying to do a quite simple thing,read a file which as values displayed like this: 1 2 3 3 ...

  1. #1
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82

    Just a simple question...

    Im 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 im doing this:
    Code:
    while(fscanf(fp,"%d %d %d",&noi,&nof,&peso)!=EOF)
    	{
    	capacidade[noi][nof] = peso;
    	
        }
    But the problem is that it keeps reading the same line over and over...I tried a file like this:
    John 12
    Mary 15
    ...
    and then
    Code:
    while(fscanf(fp,"%s %d",Name,&age)!=EOF)
    printf("%s %d", Name,age);
    and its working...Can someone explain to me the difference?

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    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?

  4. #4
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    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...Ive found one,but it had some limitations that my program cant have:for example,i the edges dont have to be ordered (1 2 3, 1 4 5, 4 5 6...) and the capacity of a path can be 0 or negative...

  5. #5
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    well,already solved the fscanf problem...thnks anyway.Now i realized that my program doesnt work correctly...This algorithm is a bit weird...

  6. #6
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    ok,so i managed to write my program,but now im having another problem:its always returning 0...Heres the code:
    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("Impossvel 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));
    		}
    }
    This is an implementation of the ford fulkerson algorhitm for the maximum flow problem along an directed graph. The imput file looks like this:
    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).

  7. #7
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    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.im sorry if im 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...

  8. #8
    Registered User
    Join Date
    Mar 2003
    Location
    UK
    Posts
    169
    >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

  9. #9
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    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 isdiscover 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;
    }
    Last edited by Lost__Soul; 04-17-2003 at 10:06 AM.

  10. #10
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    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:

    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]
    help ,please!
    Last edited by Lost__Soul; 04-17-2003 at 04:12 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple question regarding variables
    By Flakster in forum C++ Programming
    Replies: 10
    Last Post: 05-18-2005, 09:10 PM
  2. Simple class question
    By 99atlantic in forum C++ Programming
    Replies: 6
    Last Post: 04-21-2005, 12:41 AM
  3. Simple question about pausing program
    By Noid in forum C Programming
    Replies: 14
    Last Post: 04-02-2005, 09:46 AM
  4. simple question.
    By InvariantLoop in forum Windows Programming
    Replies: 4
    Last Post: 01-31-2005, 12:15 PM
  5. simple fgets question
    By theweirdo in forum C Programming
    Replies: 7
    Last Post: 01-27-2002, 06:58 PM

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