troubleshooting Question

how to run this program

Avatar of ssami81
ssami81 asked on
System ProgrammingC
10 Comments1 Solution434 ViewsLast Modified:
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;
}

ASKER CERTIFIED SOLUTION
AndyAinscow
Freelance programmer / Consultant

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Log in to continue reading
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform for $9.99/mo
View membership options
Unlock 1 Answer and 10 Comments.
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
See how we're fighting big data
The Value of Experts Exchange in My Daily IT Life

Experts Exchange (EE) has become my company's go-to resource to get answers. I've used EE to make decisions, solve problems and even save customers. OutagesIO has been a challenging project and... Keep reading >>

Mike

Owner of Outages.IO
Phoenix, Arizona, United States
Member Since 2016
Join a full scale community that combines the best parts of other tools into one platform.
Unlock 1 Answer and 10 Comments.
View membership options
“All of life is about relationships, and EE has made a virtual community a real community. It lifts everyone's boat.”
William Peck

Member since 2004