Avatar of ssami81
ssami81

asked on 

how to run this program

Hi;
I have this code from internet and I am trying to run it.
what would be the running format
I tried
filename <input.txt
also
filename input.txt
I don't know what line FILE* input = fopen("mf.in","r"); means
please help  the code is


// The Ford-Fulkerson Algorithm in C

#include <stdio.h>

// Basic Definitions

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000

// Declarations

int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search              
int pred[MAX_NODES];  // array to store augmenting path

int min (int x, int y) {
    return x<y ? x : y;  // returns minimum of x and y
}

// A Queue for Breadth-First Search

int head,tail;
int q[MAX_NODES+2];

void enqueue (int x) {
    q[tail] = x;
    tail++;
    color[x] = GRAY;
}

int dequeue () {
    int x = q[head];
    head++;
    color[x] = BLACK;
    return x;
}

// Breadth-First Search for an augmenting path

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;
}

// Ford-Fulkerson Algorithm

int max_flow (int source, int sink) {
    int i,j,u;
    // Initialize empty flow.
    int max_flow = 0;
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            flow[i][j] = 0;
        }
    }
    // While there exists an augmenting path,
    // increment the flow along this path.
    while (bfs(source,sink)) {
        // Determine the amount by which we can increment the flow.
        int increment = oo;
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
        }
        // Now increment the flow.
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            flow[pred[u]][u] += increment;
            flow[u][pred[u]] -= increment;  // Reverse in residual
        }
        // Path trace
        for (u=sink; pred[u]!=(-1); u=pred[u]) {
            printf("%d<-",u);
        }
        printf("%d adds %d incremental flow\n",source,increment);
        max_flow += increment;
    }
    // No augmenting path anymore. We are done.
    return max_flow;
}

// Reading the input file and the main program

void read_input_file() {
    int a,b,c,i,j;
    FILE* input = fopen("mf.in","r");
    // read number of nodes and edges
    fscanf(input,"%d %d",&n,&e);
    // initialize empty capacity matrix
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            capacity[i][j] = 0;
        }
    }
    // read edge capacities
    for (i=0; i<e; i++) {
        fscanf(input,"%d %d %d",&a,&b,&c);
        capacity[a][b] += c; // Could have parallel edges
    }
    fclose(input);
}

int main () {
    int i,j;
    read_input_file();
    printf("total flow is %d\n",max_flow(0,n-1));
    printf("flows along edges:\n");
    for (i=0; i<n; i++)
      for (j=0; j<n; j++)
        if (flow[i][j]>0)
          printf("%d->%d has %d\n",i,j,flow[i][j]);
    return 0;
}

System ProgrammingC

Avatar of undefined
Last Comment
AndyAinscow
ASKER CERTIFIED SOLUTION
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

Blurred text
THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
Avatar of ssami81
ssami81

ASKER

so does that mean I can give a input.txt here instead of mf.in and it would read it
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

Assuming that input.txt contains the information it requires in the correct format - yes.

Simplest would be to just try it and see what happens
Avatar of ssami81
ssami81

ASKER

and how would I run it then
filename input.txt
or
filename <input.txt
i tried both not working
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

replace
fopen("mf.in", "r")
with
fopen("input.txt", "r")
Avatar of ssami81
ssami81

ASKER

I have and if you see the output still not working
Avatar of ssami81
ssami81

ASKER

I think you should try for youreself and see what the error is
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

Check your input.txt is the correct format/information.
Try single stepping in the debugger as it is read in and see if the values read are what you want.
Avatar of ssami81
ssami81

ASKER

Input is ok it is in this format
7 11
1 2 9
1 4 7
1 3 8
2 3 2
2 5 6
4 6 6
3 5 1
3 7 5
3 6 2
5 7 7
6 7 11
Avatar of AndyAinscow
AndyAinscow
Flag of Switzerland image

I don't know what the algorithm should do.

If I understand the situation:
You can read the data from the file into the program.  
The data read in is correct.  
The output isn't.

That makes me think either the function to manipulate the data or the outputting of the results isn't coded correctly.
System Programming
System Programming

Kernel and system programming is the process of creating the software necessary for a computer or device to function and operate other programs. Some operating systems (such as Microsoft Windows) are proprietary, but others, such as the various Linux distributions, are open source.

41K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts
Ask the experts
Read over 600 more reviews

TRUSTED BY

IBM logoIntel logoMicrosoft logoUbisoft logoSAP logo
Qualcomm logoCitrix Systems logoWorkday logoErnst & Young logo
High performer badgeUsers love us badge
LinkedIn logoFacebook logoX logoInstagram logoTikTok logoYouTube logo