Dinik Edmonds Clark Algorythm in C++ by Shane Zentz
/* * * * * * * * * * * * * * * * * * * * * * * * *
* Shane Zentz *
* C455 Homework # 6 *
* 4.29.2009 *
* Queue.h *
* This file implements a simple priority queue, *
* that will be used to implement the Dinic *
* Edmond Clark agorithm for finding the maximum *
* flow in a directed graph. Specificaly it is *
* used in the breadth first search. *
* * * * * * * * * * * * * * * * * * * * * * * * */
#ifndef QUEUE_H
#define QUEUE_H
// A node for the queue.
class queueNode{
public:
int data;
queueNode *next;
};
class Queue
{
protected:
// The first and last nodes in queue.
queueNode *first, *last;
public:
// constructor
Queue();
// destructor.
~Queue();
// insert into queue.
void insert(int data);
// remove from queue.
int remove();
// find out if the queue is empty or not.
bool isEmpty();
// delete the entire queue.
void makeEmpty();
// Print the queue (to test).
void print();
};
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * *
* Shane Zentz *
* C455 Homework # 6 *
* 4.29.2009 *
* Graph.h *
* This file defines a class which creates a *
* graph for the Dinic Edmonds Karp maximum flow *
* algorithm. *
* * * * * * * * * * * * * * * * * * * * * * * * */
#ifndef GRAPH_H
#define GRAPH_H
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFINITY 1000000
//#include "Queue.h"
//#include
//#incldue
class Graph
{
protected:
int totalVertices, totalEdges;
int ** capacity;
int ** flow;
int * color;
int * augment;
public:
// Default constructor.
Graph();
// Destructor.
~Graph();
// Read the input file.
int readFile(char *filename);
// Breadth First Search
int bfs(int start, int target);
// Dinic Edmonds Karp algorithm.
int dek(int source, int sink);
// Print the flow matrix.
void printFlow();
};
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * *
* Shane Zentz *
* C455 Homework # 6 *
* 4.29.2009 *
* Queue.cc *
* This file implements a simple queue that will *
* be used in an implementation of Dinic Edmonds *
* Karp algorithm to find the maximum flow in a *
* directed graph... *
* * * * * * * * * * * * * * * * * * * * * * * * */
#include
#include "Queue.h"
using namespace std;
Queue::Queue()
{
first = last = NULL;
}
// The destructor.
Queue::~Queue()
{
delete first;
delete last;
}
// Insert a node into the queue.
void Queue::insert(int data)
{
queueNode *temp = new queueNode;
temp->data = data;
temp->next = NULL;
// If the queue is empty, make first = last
if (isEmpty())
first = last = temp;
else
last = last->next = temp;
}
// Remove the top node from queue.
int Queue::remove()
{
// Make sure not to remove from empty queue.
if (isEmpty())
return -1;
int value;
queueNode *temp = new queueNode;
temp = first;
value = temp->data;
first = first->next;
return value;
}
// See if the queue is empty or not.
bool Queue::isEmpty() { return first==NULL; }
// Print the queue.
void Queue::print()
{
if (isEmpty())
cout << "The queue is empty." << endl;
queueNode *temp = first;
while (temp)
{
cout << temp->data << endl;
temp = temp->next;
}
}
// Delete the entire queue.
void Queue::makeEmpty()
{
while(!isEmpty()) remove();
}
/* * * * * * * * * * * * * * * * * * * * * * * *
* Shane Zentz *
* C455 *
* Graph.cc *
* 4.29.2009 *
* This file implements the Dinic Edmonds Karp *
* algorithm for finding the maximum flow in a *
* directed graph. *
* * * * * * * * * * * * * * * * * * * * * * * **/
#include "Graph.h"
#include "Queue.h"
#include
#include
using namespace std;
// Constructor
Graph::Graph() {}
// Destructor
Graph::~Graph() {}
// Breadth First Search returns the shortest path
// from start to target.
int Graph::bfs(int start, int target)
{
int u, v;
// stores the augmented path.
augment = new int[totalVertices];
// stores the color (visited status for queue) for bfs.
color = new int[totalVertices];
// inititally all vertices are unvisited.
for (u=0; u
// Create a queue, and insert start.
Queue que;
que.insert(start);
// when start is on the queue set it to waiting.
color[start] = GRAY;
augment[start] = -1;
// while que is not empty find all paths
while (!que.isEmpty())
{
u = que.remove();
color[u] = BLACK;
for (v=0; v < totalVertices; v++)
{
if (color[v] == WHITE && capacity[u][v] - flow[u][v] > 0)
{
que.insert(v);
color[v] = GRAY;
augment[v] = u;
}
}
}
// delete the queue.
que.makeEmpty();
// if the color of target is black then it was reached.
return color[target]==BLACK;
}
// The implementation of the Dinic Edmonds Karp
// algorithm for finding the maximum flow in a
// directed graph.
int Graph::dek(int source, int sink)
{
int i,j,u;
// initialize the flows to zero
int maxFlow = 0;
flow = new int * [totalVertices];
for (int h=0; h
flow[h] = new int [totalVertices];
if (!flow[h]) { cout << "Memory problem. " << endl; }
}
for (i=0; i
flow[i][j] = 0; }
}
// While bfs returns a path increase the flow
// on that path.
while (bfs(source,sink))
{
int increment = INFINITY;
for (u = totalVertices - 1; augment[u] >= 0; u = augment[u])
{
increment = min(increment, capacity[augment[u]][u] -
flow[augment[u]][u]);
}
// increment the flow.
for (u= totalVertices - 1; augment[u] >= 0; u = augment[u])
{
flow[augment[u]][u] += increment;
flow[u][augment[u]] -= increment;
}
maxFlow += increment;
}
// now there are no more augment paths
// so return the maximum flow.
return maxFlow;
}
// Read the input file, call dek, and return maxFlow.
int Graph::readFile(char *filename)
{
int a,b;
ifstream inFile(filename);
if (! inFile.is_open() )
cout << "Can't open file: " << filename << endl;
// First get the total number of vertices and edges.
inFile >> totalVertices;
inFile >> totalEdges;
// Now get capacities for all edges
capacity = new int * [totalVertices];
if (!capacity) { cout << "Not enough Memory." << endl; }
for (int o=0; o < totalVertices; o++)
{
capacity[o] = new int [totalVertices];
if(!capacity[o]) { cout << "Memory problem." << endl; }
}
// Set all capacities to zero.......
for (int x=0; x
}}
/*
// TESTING, print out cap matrix..
cout << "Printing initial capacity matrix." << endl;
for (int row = 0; row < totalVertices; row++){
for (int col = 0; col < totalVertices; col++)
cout << capacity[row][col] << "\t";
cout << endl; }
*/
for (int i=0; i
inFile >> a;
inFile >> b;
inFile >> capacity[a][b];
}
// TESTING, print out updated capacity matrix.
cout << endl;
cout << "The capacity matrix:" << endl;
for (int rows=0; rows
cout << endl; }
// Close the file...
inFile.close();
// Return the maxFlow to caller.
return dek(0, totalVertices - 1);
}
// Print the flow matrix.
void Graph::printFlow()
{
cout << endl;
cout << "Printing the flow matrix..." << endl;
for(int row=0; row < totalVertices; row++){
for(int col=0; col < totalVertices; col++)
cout << flow[row][col] << "\t";
cout << endl; }
}
/* * * * * * * * * * * * * * * * * * * * * * * * *
* Shane Zentz *
* C455 Homework # 6 *
* 4.29.2009 *
* DEC.cc *
* This file implements the Dinic Edmonds Clark *
* algorithm using the graph and queue classes. *
* The timing in milliseconds resolution is also *
* calculated and printed.... *
* * * * * * * * * * * * * * * * * * * * * * * * */
/************ g++ Version *******************/
#include
#include
#include
#include
#include "Graph.h"
using namespace std;
int main(int argc, char *argv[])
{
// If the user did not enter a file, exit.
if (argc != 2)
{
cout << "Try: " << argv[0] << " filename \n";
return 1;
}
// call graph to construct graph with filename arg.
else
{
// Timing variables.
struct timeval before1, after1;
// Timing stuff aqui.
gettimeofday(&before1,0);
Graph g;
int x = g.readFile( argv[1] );
g.printFlow();
cout << endl;
cout << "Max flow is: "<< x << endl;
cout << endl;
gettimeofday(&after1,0);
cout << "function elapsed time (seconds): " <<
(after1.tv_sec+after1.tv_usec/1000000.f)-
(before1.tv_sec+before1.tv_usec/1000000.f)
<< endl;
cout << endl;
}// end of else
} // end of main
/*********************************************************
EXAMPLE OF RUNNING PROGRAM:
file: graph.txt
7
11
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9
>g++ Graph.cc Queue.cc DEC.cc -o dek
>dek graph.txt
The capacity matrix:
0 3 0 3 0 0 0
0 0 4 0 0 0 0
3 0 0 1 2 0 0
0 0 0 0 2 6 0
0 1 0 0 0 0 1
0 0 0 0 0 0 9
0 0 0 0 0 0 0
Printing the flow matrix...
0 2 0 3 0 0 0
-2 0 2 0 0 0 0
0 -2 0 1 1 0 0
-3 0 -1 0 0 4 0
0 0 -1 0 0 0 1
0 0 0 -4 0 0 4
0 0 0 0 -1 -4 0
Max flow is: 5
function elapsed time (seconds): 0.001254
*********************************************************/
****************** README **************************
This program requires a text file as input. The text file should be in
the following form:
the first line should conatin the total number of vertices in the graph,
The second line should contain the total number of edges in the graph,
Finally, each edge should be listed in the following form:
the source vertex(int) the destination vertex(int) capacity(int)
*The program will not run correctly or give correct results if the
file argument given to the program is not in the correct form.
**See the graph.txt file for an example file in the correct form.
To compile the program use the following:
g++ Graph.cc Queue.cc DEK.cc -o dek
Then, to run the program with your text file:
dek yourfile
*yourfile must exactly match your file name (including any extensions).
/***************************** FIN ************************************/
