Flight School

/* Summary:
 *		All of the edges and verteces are consecutive so I
 *		can use an array to store them.
 *
 *		The graph will be initialized with a dyn allocated
 *		array of
*/
 
struct nodeEdge {
	// Summary:
	//		Each node actually only needs to be identified
	//		by index.  This is meant to pair it with an edge
	//		weight in the graph.
	nodeEdge(int v, int w);
	nodeEdge* next;
	int weight;
	int vertex;
};
 
class Graph	{
	// Summary:
	//		The graph has a dyn allocated array of size nV.
	//		Each index is the vertex it represents, and out of
	//		it is a pointer to a list of nodes with their weight
	//		in that adj list.
	public:
		int nV, nE, s, t;
		nodeEdge **nodes;
		Graph(int nV,int nE);
		Graph(const Graph* other);
		Graph* bottleneckGraph(int b);
		~Graph();
		void setSourceSink(int s,int t);
		void addEdge(int u, nodeEdge* v);
		void removeEdge(int u, nodeEdge* v);
		int updateEdgeWeight(int u, int v, int w);
		void toString();
	private:
		int updateWeight(nodeEdge* u, int v, int w);
		void insertEdge(nodeEdge* u, nodeEdge* v);
		void extractEdge(nodeEdge* u, nodeEdge* v);
		void deleteNodes(nodeEdge *n);
};

#include <cstddef>
#include <iostream>
#include "Graph.h"
using namespace std;
 
nodeEdge::nodeEdge(int v,int w){
	weight = w;
	vertex = v;
	next = NULL;
};
 
Graph::Graph(int nV,int nE){
	this->nV = nV+1; // Offsetting by 1 b/c node index starts at 1
	this->nE = nE;
 
	nodes = new nodeEdge*[this->nV];
	nodeEdge* edge = new nodeEdge(nE, 0);
	for (int i=0; i<this->nV; i++) {
		nodes[i] = i==0 ? edge : NULL;
		//cout << "Initializing: " << i << " val: " << nodes[i] << endl;
	}
};
 
Graph::Graph(const Graph* other){
	nV = other->nV;
	nE = other->nE;
	s = other->s;
	t = other->t;
	nodes = new nodeEdge*[nV];
	for (int i = 0; i < nV; i++) {
		nodeEdge* n = other->nodes[i];
		if (n!=NULL) {
			nodeEdge* o = nodes[i] = new nodeEdge(n->vertex, n->weight);
			while (n->next!=NULL) {
				o->next = new nodeEdge(n->next->vertex, n->next->weight);
				o = o->next;
				n = n->next;
			}
		} else {
			nodes[i]=NULL;
		}
	}
}
 
Graph* Graph::bottleneckGraph(int b){
	Graph* g = new Graph(nV-1,nE);
	g->s = s;
	g->t = t;
	for (int i=0; i<nV; i++) {
		nodeEdge* n = nodes[i];
		if (n!=NULL) {
			// Only copy nodes with high enough weight
			while (n!=NULL && n->weight<b) {
				n = n->next;
			}
			g->nodes[i] = n==NULL ? NULL : new nodeEdge(n->vertex, n->weight);
			nodeEdge* o = g->nodes[i];
			while (n!=NULL && n->next!=NULL) {
				if (n->next->weight>=b) {
					o->next = new nodeEdge(n->next->vertex, n->next->weight);
					o = o->next;
					n = n->next;
				} else {
					// Skip this one, not high enough weight
					n = n->next;
				}
			}
		} else {
			g->nodes[i] = NULL;
		}
	}
	return g;
}
 
Graph::~Graph(){
	for (int i=0; i < nV; i++) {
		// Go through nodes and tear down linked
		// list (each node should be from the heap)
		if(nodes[i]!=NULL) deleteNodes(nodes[i]);
	}
	delete(nodes);
};
 
void Graph::deleteNodes(nodeEdge *n){
	if (n->next!=NULL) {
		deleteNodes(n->next);
	};
	delete n;
};
 
void Graph::setSourceSink(int s,int t){
	if (1 > s || nV <= s || 1 > t || nV <= t) {
		cout << "Attempting to set a source or sink node that is outside the node range" << endl;
		exit(1);
	}
	this->s = s;
	this->t = t;
};
 
void Graph::addEdge(int u, nodeEdge* v){
	// summary:
	//		This takes an edge and tries to insert it.
	//		If there is no linked list, this starts it,
	//		otherwise it finds the end with insertEdge
	//
	//		Currently there is no check for double edges
	//		as this was not a requirements
	if(1 > u || nV <= u){
		cout << "Attempting to add an edge with a non-existant vertex" << endl;
		exit(1);
	}
	if(nodes[u]==NULL){
		// This is the first in the list
		nodes[u] = v;
	} else {
		insertEdge(nodes[u], v);
	}
}
 
void Graph::removeEdge(int u, nodeEdge* v){
	// summary:
	//		We have a node pointer to remove from list
	//		of vertex v.  Easy if it's the end of the list
	//		rewire if it's not.  If it's the only one...
	nodeEdge* tmp = NULL;
 
	if (nodes[u]->vertex == v->vertex) {
		// This is if it's the first one
		tmp = nodes[u]->next != NULL ? nodes[u]->next : NULL;
		delete nodes[u];
		nodes[u] = tmp;
		return;
	}
	extractEdge(nodes[u], v);
}
 
int Graph::updateEdgeWeight(int u, int v, int w){
	// Returns 0 if it needed to create an edge, 1 if it updates
 
	nodeEdge* nu = nodes[u];
	if (nu == NULL){
		// No edge yet, create it!
		nodes[u] = new nodeEdge(v, w);
		return 0;
	} else if (nu->vertex == v) {
		nu->weight += w;
		if (nu->weight == 0) {
			// Remove me!
			removeEdge(u, nu);
		}
		return 1;
	} else {
		return updateWeight(nu, v, w);
	}
}
 
void Graph::toString(){
	cout << "====Graph Details====" << endl;
	cout << "Source: " << s << " Sink: " << t << endl;
	cout << "----Adj List---------" << endl;
	for (int i=1; i < nV; i++) {
		cout << "Node " << i << ": " << endl;
		nodeEdge* n = nodes[i];
		if(n==NULL){
			cout << "NULL" << endl;
		} else {
			while(n!=NULL) {
				// Verify something first
				cout << "v: " << n->vertex << " w: " << n->weight << endl;
				n = n->next;
			};
		}
	}
}
 
int Graph::updateWeight(nodeEdge* u, int v, int w){
	if (u->next==NULL) {
		// I'm next
		u->next = new nodeEdge(v, w);
		return 0;
	} else {
		if (u->next->vertex == v) {
			u->next->weight += w;
			if (u->next->weight == 0) {
				// Remove me!
				extractEdge(u, u->next);
			}
			return 1;
		} else {
			return updateWeight(u->next, v, w);
		}
	}
}
 
void Graph::insertEdge(nodeEdge* u, nodeEdge* v){
	// summary:
	//		This takes a node, already inserted, and sees
	//		if it's the last in the linked list.  If not
	//		it will call this recursively with the next
	if(u->next == NULL){
		// Insert me here
		u->next = v;
	} else {
		// Look at the next one
		insertEdge(u->next, v);
	}
}
 
void Graph::extractEdge(nodeEdge* u, nodeEdge* v){
	if (u->next == NULL) {
		cout << "Error, didn't find the node" << endl;
		exit(1);
	}
	if (u->next->vertex == v->vertex) {
		nodeEdge *tmp = u->next->next;
		delete u->next;
		u->next = tmp;
	} else {
		u = u->next;
		extractEdge(u, v);
	}
}

#include "Graph.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <queue>
using namespace std;
 
 
/** Summary:
 *		A special version of BFS which returns useful
 *		information for maxFlow: path with associated
 *		weights.  If minCut is set to true, BFS will
 *		instead return the set of nodes it can reach
 */
 
int* BFS(Graph *g, int s, int t, bool minCut){
	int nV = g->nV;
	queue<int> visit;
	bool found = false;
 
	// Initialize values to be used in the search
	// keeping track of parent and whether node has
	// been visited or not.
	int* visited = new int[nV];
	int* parent = new int[nV*2]; // This is a horrible hack of making a 2D array
	int* path = new int[nV*2];
	for (int i=0; i<nV; i++) {
		// Visited: 0 hasn't been visited, 1 is on the frontier, 2 is done
		visited[i] = 0;
		parent[i] = 0; //Only worry about 0 - keys, if a key is set I set the weight
		path[i] = 0;
	}
 
	// Enqueue the entry node, s, and search for t
	visit.push(s);
	visited[s] = 1;
	while (!visit.empty()) {
		// Search
		int u = visit.front();
		visit.pop();
 
		if(u==t){
			// Found it - build path array.
			found = true;
			int c = t;
			int p = parent[t];
			do {
				path[c] = p;
				path[c+nV] = parent[c+nV];
				c = p;
				p = parent[c];
			} while (p!=0);
			break;
		} else {
			// Color me, enqueue my children and color them
			visited[u] = 2;
			nodeEdge* adjList = g->nodes[u];
			while (adjList!=NULL) {
				// Get adj node, see if it's been visited and
				// if not it's my child
				int v = adjList->vertex;
				if(visited[v]==0){
					visit.push(v);
					parent[v] = u;
					parent[v+nV] = adjList->weight;
					visited[v] = 1;
				}
				adjList = adjList->next;
			}
		}		
	}
 
	!found && (path = NULL);
	minCut ? delete path : delete visited;
	delete parent;
 
	return minCut ? visited : path;
}
/** Summary:
 *		This finds the minimum edge weight along
 *		a path and returns it, since the flow cannot
 *		exceed that.
 */
int bottleNeck(int *path, int t, int nV){
	if(path==NULL) return 0;
	int m = 0, p = path[t], last=t;
	do {
		m = m==0 ? path[last+nV] : min(path[last+nV], m);
		last = p;
		p = path[last];
	} while (p!=0);
	//cout << "Bottleneck: " << m << endl;
	return m;
}
 
/** Summary:
 *		Capacity scaling implementation of Ford-
 *		Fulkerson algorithm.
 */
int maxFlow(Graph *g){
	ofstream output("output.txt", ios::out);
	if (!output) {
		cout << "Error: failed create output file" << endl;
		return -1;
	}
	// First create the residual graph by copying the original
	Graph *bG, *rG = new Graph(g);
	// C-capacity from source, mC-max capacity from A={s}, delta-nearest power of 2, rC-residual capacity
	int C=0, mC=0, delta=1, rC=0, s=g->s, t=g->t, nV=g->nV;
 
	// Get an upper bound on the flow by summing the
	// capacity coming out of the source node
	nodeEdge *src = rG->nodes[s];
	while (src!=NULL) {
		int tmp = src->weight;
		mC=max(tmp,mC);
		C+=tmp;
		src = src->next;
	}
 
	//cout << "Capacity: " << C << endl;
	if(mC>1){
		// Technically should also check for an upper bound which
		// depends on architecture, 32/64 bit.
		while (delta<mC) {
			delta<<=1;
		}
		if (delta>mC) {
			// Shift it back one so it's less than or equal to C
			delta>>=1;
		}
	}else if(mC==1){
		delta = 1;
		cout << "Edge weight is 1 so setting delta as 1 since lower power of 2 is 0" << endl;
	} else {
		cout << "There is no positive capacity, no positive flow exists" << endl;
		exit(1);
	}
 
	bG = rG->bottleneckGraph(delta);
	// Now find an aug path
	int* augPath = BFS(bG, s, t, false);
	while (delta>=1) {
		// Keep getting augPaths until down on delta
		output << "With DELTA=" << delta << ", ";
		while (augPath!=NULL) {
			// Get all augmenting paths for current delta	
			int p, c, b;
			if (augPath==NULL) {
				c = b = p = 0;
			} else {
				b = bottleNeck(augPath, t, nV);
				c = t;
				p = augPath[t];
			}
 
			while (p!=0){
				// I have an edge.  First reduce the weight on all edges we sent flow
				// through of the form p->c.  
				int success = rG->updateEdgeWeight(p, c, -b);
				if(success==0){
					// Means we created an edge, shouldn't have happened throw error
					cout << "Error, didn't find edge in adj list" << endl;
					exit(1);
				}
 
				// Now update the residual graph by either creating a c->p edge, or 
				// adding weight
				rG->updateEdgeWeight(c, p, b);
 
				c = p;
				p = augPath[c];
			}
			// Destroy my last bottleneck graph and make a new one
			delete bG;
			bG = rG->bottleneckGraph(delta);
			augPath = BFS(bG, s, t, false);
		}
		// I want to see my new graph for each augmentation
		//rG->toString();
 
		rC = 0;
		src = rG->nodes[s];
		while (src!=NULL) {
			rC+=src->weight;
			src = src->next;
		}
		output << "Flow value=" << C-rC << endl;
		// My residual graph has been updated with my last flow, find a new
		// augmenting path and try it again.
		delta =  delta/2;
		bG = rG->bottleneckGraph(delta);
		augPath = BFS(bG, s, t, false);
	}
 
	output << "Max-flow value=" << C-rC << endl;
 
	output << "The max-flow:" << endl;
	// Print the max flow by going through the edges in the original
	// graph and subtracting the
	for (int i=1; i<g->nV; i++) {
		nodeEdge *r, *n = g->nodes[i];
		while (n!=NULL) {
			r = rG->nodes[i]; // Start at the beginning each time since edges could be gone
			while (r!=NULL && r->vertex!=n->vertex) {
				r = r->next;
			}
			int wt = r==NULL ? n->weight : n->weight - r->weight;
			if(wt>0) output << i << " " << n->vertex << " " << wt << endl;
 
			n = n->next;
		}
	}
 
	// Now find and print the min-cut
	output << endl << "Min-cut capacity=" << C-rC << endl;
	output << "The min-cut:" << endl;
 
	// This assumes a connected graph
	int* minCut = BFS(rG, rG->s, rG->t, true);
	vector<int> S, T;
	for (int i=1; i<rG->nV; i++) {
		minCut[i]>0 ? S.push_back(i) : T.push_back(i);
	}
 
	output << "The set S:" << endl;	
	for (size_t i=0; i<S.size(); i++) {
		output << S[i] << ", ";
	}
	output << endl << "The set T:" << endl;
	for (size_t i=0; i<T.size(); i++) {
		output << T[i] << ", ";
	}
	output << endl;
	output.close();
	delete rG;
	return C-rC;
};
 
int main (int argc, char * const argv[]) {
	// Read in the data and construct the graph
	string line;
	ifstream myfile;
	myfile.open("input.txt");
	if(myfile.is_open()){
		int edgeCount, counter = 1;
		Graph* g = NULL;
 
		cout << "Successfully opened file" << endl;
		while (!myfile.eof()) {
			getline(myfile, line);
			vector<string> tokens;
			int a, b, c;
 
			if(line.empty()){
				// Skip me
			}else {
				stringstream iss(line);
				copy(istream_iterator<string>(iss), 
					istream_iterator<string>(), 
					back_inserter<vector<string> >(tokens));
 
				if(tokens.size()>3){
					cout << "Input error: too many values/line" << endl;
					myfile.close();
					return -1;
				}
				if(tokens.size()!=2 && counter<=2){
					cout << "Input error: only two values allowed in first two lines: nV and nE or s and t" << endl;
					return -1;
				}
				// Now that we have the vector, we need to make sure
				// the input is integer and then create our graph
				// Values here would be greater than 0
				a = atoi(tokens[0].c_str());
				b = atoi(tokens[1].c_str());
				c = tokens.size()>2 ? atoi(tokens[2].c_str()) : 0;
 
				if(a<1 || b<1 || (counter>2 && c<1)){
					// I asked professor XUE and he said throw an error for 0
					// edge weight as well as non integer.
					cout << "Input error: Non integer (or 0) input" << endl;
					myfile.close();
					return -1;
				}
 
				if(counter == 1){
					// Initialize graph
					edgeCount = b;
					g = new Graph(a,b);
				}	
				// Other setup
				if (counter == 2) g->setSourceSink(a,b);
 
				if(counter > 2){
					// Adding vertices and edges baby
					nodeEdge *n = new nodeEdge(b,c);
					g->addEdge(a,n);
				}
				counter++;
			}
			//cout << "Vector size: " << tokens.size() << " 1: " << a << " 2: " << b << " 3: " << c << endl;
 
		}
		myfile.close();
 
		// One last check, now that I've gone through the file does the
		// number of expected edges match with the number of actual edges given?
		if (edgeCount != counter-3) {
			cout << "Expected " << edgeCount << " edges but found " << counter-3 << endl;
			return -1;
		}
 
		// Begin max flow algorithm! -- I should do this from a function
		maxFlow(g);
		//cout << "Flow value: " << flow << endl;
 
	} else {
		// ELSE to opening file.  Major fail
		cout << "Error opening file" << endl;
		return -1;
	}
	return 0;
}

6 8
1 4
1 2 3
1 4 1
1 6 4
2 3 3
2 5 4
3 4 3
5 4 8
6 5 4

With DELTA=4, Flow Value=4
With DELTA=2, Flow Value=7
With DELTA=1, Flow Value=8
Max-flow value=8
The max-flow:
1 2 3
1 4 1
1 6 4
2 3 3
3 4 3
5 4 4
6 5 4
 
Min-cut capacity=8
The min-cut:
The set S:
1, 
The set T:
2, 3, 4, 5, 6,

CC=g++
CFLAGS=-c -Wall
LDFLAGS=
 
all: run
 
run: main.o Graph.o
		$(CC) main.o Graph.o -o run
 
main.o: main.cpp
		$(CC) $(CFLAGS) main.cpp
 
Graph.o: Graph.cpp Graph.h
		$(CC) $(CFLAGS) Graph.cpp
 
clean:
		rm -rf *o run