LINK ERROR

[arush]

Hello ,
I have a code to compute maximum flow . It works fine when the number
of nodes in the graph are around 5000.
I want to use the code to compute the maximum flow of around 110K
nodes. It gives me a link error : Image size exceeded. I think this is
because the size of the executable file is exceeded. Is it possible to
modify the code (given below) to find the maximum flow for a 100K
nodes. Could someone recommend what changes should i make.

Note : i am using visual studio 6.0 to compile the program.

#include <stdio.h>
#include <stdlib.h>
#include<fstream.h>

//Basic Definitions
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 20000
#define NODES 10000
#define oo 10000

//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 = 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[v]-flow[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[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=n-1; pred>=0; u=pred) {
// increment = min(increment,capacity[pred]-flow[pred]
);
increment = increment<capacity[pred]-flow[pred] ?
increment : capacity[pred]-flow[pred];

}
// Now increment the flow.
for (u=n-1; pred>=0; u=pred) {
flow[pred] += increment;
flow[pred] -= 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("input.dat","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[j] = 0;
}
}
// read edge capacities
for (i=0; i<e; i++) {
fscanf(input,"%d %d %d",&a,&b,&c);
capacity[a] = c;
}
fclose(input);
}
int main()
{
FILE *cptr;
int inindex = 0;
if((cptr = fopen("input.dat","w")) ==NULL)
{
cout<<"File Could not opened "<<endl;
}
int totalnodes = NODES;
int totalarcs = NODES - 1;
fprintf(cptr,"%d %d \n",totalnodes,totalarcs);

for(int ptr = 0 ; ptr < NODES- 1 ; ptr++)
{
fprintf(cptr,"%d %d %d \n",inindex,inindex+1,1);
inindex++;
}
fclose(cptr);
read_input_file();
cout<<" Max Flow : "<<max_flow (0,n-1)<<endl;
return 0;
}

 

[arush]

Hello ,
I have a code to compute maximum flow . It works fine when the number
of nodes in the graph are around 5000.
I want to use the code to compute the maximum flow of around 110K
nodes. It gives me a link error : Image size exceeded. I think this is
because the size of the executable file is exceeded. Is it possible to
modify the code (given below) to find the maximum flow for a 100K
nodes. Could someone recommend what changes should i make.

Note : i am using visual studio 6.0 to compile the program. [...]
#define MAX_NODES 20000 [...]
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix

[...]

Consider this:  If MAX_NODES is defined as 100000, then you will need
to have the capacity[][] and flow[][] arrays hold 10,000,000,000 ints
each.  If you have 32-bit ints, this means 80GB of storage just for
these two arrays, which simply isn't possible with 32-bit addresses.

It may be possible on a 64-bit Windows system, it the compiler and the
system fully support the 48-bit(?) addresses available there, in which
case I would recommend allocating the storage at runtime with malloc()
or new, rather than fixed at compile time.

Hello Kenneth,
Thanks for your advice. I had a quick question regarding bit
representation... this may sound a little dumb ... but i will ask
anyways...

to check if your system is 32 or 64 bit .... i did the following

int a = 5 ;
cout<<&a<<endl;

which gives output : 0x0013FF7C now since there are 8 digits after x
does this mean the system uses a 32 bit allocation.
Is this the correct way to check... or is there any other way.
Thanks,
Arush.

 

[red floyd]

to check if your system is 32 or 64 bit .... i did the following

int a = 5 ;
cout<<&a<<endl;

which gives output : 0x0013FF7C now since there are 8 digits after x
does this mean the system uses a 32 bit allocation.
Is this the correct way to check... or is there any other way.

#include <iostream>
#include <ostream>
#include <cstdlib>
int main()
{
std::cout << sizeof(void*) << std::endl;
return EXIT_SUCCESS;
}

 

[James Kanze]

#include <iostream>
#include <ostream>
#include <cstdlib>
int main()
{
std::cout << sizeof(void*) << std::endl;

This should be:

std::cout << CHAR_BITS * sizeof( void* ) << std::endl ;

if you want the number of *bits* in a pointer.

(On most modern general purpose machines, CHAR_BITS will be 8.
There are exceptions, though.)

 

[red floyd]

This should be:

std::cout << CHAR_BITS * sizeof( void* ) << std::endl ;

if you want the number of *bits* in a pointer.

(On most modern general purpose machines, CHAR_BITS will be 8.
There are exceptions, though.)

Picky, picky, picky, James.

In that case, I also need to #include <climits>