/**************************************************************************
*
*
* Nathan Balon
* CIS 350
* Data Structures and Algorithms
* Univeristy of Michigan Dearborn
*
* Program #3: Minimum Cut
*
* The program will read in a number of graphs from the standard input.
* The the program will compute the minimum cut for each graph. The program
* will display to the user the cost of the cut and one of the sets will be
* displayed. The output will also be written to a file "out.txt".
*
* Input:
*
* The input to the program will consist of:
* # of vertices
* "degree of vertex_1", "vertices connected to vertex_1"
* "degree of vertex_2", "vertices connected to vertex_2"
* ...
* "degree of vertex_n", "vertices connected to vertex_n"
*
* The program will continue to read in graphs until a line is found starting
* with 0.
*
* Sample of valid input:
*
* 6
* 3 3 6 5
* 2 3 5
* 4 4 4 2 1
* 2 3 3
* 3 1 2 6
* 2 1 5
* 0 To indicate the end of the program
*
* Output:
*
* The program will display the cost of the cut and on of the sets in the cut.
*
* Sample output:
*
* "The min cost is 2 with the cut 1 5 6"
*
*
******************************************************************************/
#include
#include
#include
#include
#include
using namespace std;
/* Global constants */
const string FILE_NAME = "out.txt"; // file to store graphs containing the minimum cut.
/* Global functions used by main */
void displayHelp(); // displays help to the user
int getNumberOfVertices(); // get the number of vertices contained in a graph
// from the user before creating the graph.
/*****************************************************************************
*
* Class Vertex is used to store one vertex in a graph and to list the
* vertices that it is connected to.
*
*****************************************************************************/
class Vertex{
public:
Vertex(int number);
~Vertex();
int getDegree() const;
friend ostream& operator<<(ostream & out, const Vertex & vertex);
private:
int number_; // number used to a identify a vertex
int outDegree_; // the out degree of a vertex
int inDegree_; // the in degree of a vertex
bool locked_; // locked to indicate the vertex was swapped
vector * edges_; // the edges contained in the graph
friend class Graph;
};
/**
* Vertex: creates an instance of a Vertex object.
* param: number is a number used to identify the vertex.
* param: edges is a vector containing the number to identify the
* vertices that the vertex is connected to.
* Precondition: Sufficient resources are available to create the
* object.
* Postcondition: A vertex is created.
*/
Vertex::Vertex(int number){
locked_ = false;
outDegree_ = 0;
inDegree_ = 0;
number_ = number;
edges_ = new vector;
}
Vertex::~Vertex(){
delete edges_;
}
/**
* getDegree: gets the degree of a vertex.
* Precondition: None
* Postcondition: The degree of the vertex is returned.
*/
int Vertex::getDegree()const{
return outDegree_ - inDegree_;
}
/**
* operator<<: returns a stream of the contents of a vertex.
* Precondition: A vertex object must be properly initialized.
* Postcondition: Returns the stream representation of a vertex.
*/
ostream & operator<<(ostream & out, const Vertex & vertex){
out << vertex.number_ << ": ";
for(int i = 0; i < vertex.edges_->size(); i++){
out << vertex.edges_->at(i)->number_ << " ";
}
out << endl;
return out;
}
/***********************************************************************
*
* Class Graph is used to store all the vertices and edges in a
* graph using a adacency list. The main purpose of the class is to
* store a graph and the compute the minimum cut on the graph.
*
* ********************************************************************/
class Graph{
public:
Graph(int numberOfVertices);
~Graph();
void addEdge(int source, int dest);
vector getVertexNumbers();
string cut();
friend ostream & operator<<(ostream & out, const Graph & graph);
private:
void displayTable(vector vertices);
int cost(vector & vertices);
bool isPositiveDegree(vector & vertices) const;
void swapLargestVertices(vector & lowerGraph,
vector & upperGraph);
void updateDegrees(Vertex * vertex, vector & setBelongTo,
vector & otherSet);
void calculateDegree(vector & vertices);
Vertex * getVertex(const int & number);
vector *vertices_; // the vertices contained in the graph
};
/**
* Graph: creates an instance of a graph.
* Precondition: Resources are available to creates the object and
* the vertex objects contain in the vector have been
* properly initialized.
* Postcondition: A graph object is created. The graph will be created with the
* number of vertices specified by the numberOfVertices argument.
*/
Graph::Graph(int numberOfVertices){
vertices_ = new vector;
for(int i = 0; i < numberOfVertices; i++){
Vertex * ver = new Vertex(i + 1);
vertices_->push_back(ver);
}
}
/**
* ~Graph frees up resources that were used by a graph object.
* Precondition: A graph must have been instantiated.
* Postcondition: Resources that were used by a graph object are deallocated.
*/
Graph::~Graph(){
delete vertices_;
}
/**
* addEgde: adds an edge to the between two vertices in the graph.
* Precondition: A graph must exist and the source and destination are vertices
* that already exist in the graph.
* Postcondition: An edge will be created between two vertices in the graph.
*/
void Graph::addEdge(int source, int destination){
Vertex *sour = getVertex(source);
Vertex *dest = getVertex(destination);
sour->edges_->push_back(dest);
}
/**
* getVertex: returns a vertex for based on the numrical identifier given.
* Precondition: The graph contains a vertex with the numerical identifier.
* Postconidtion: A vertex will be returned, if a vertex with the number does
* not exist in the graph NULL will be returned.
*/
Vertex * Graph::getVertex(const int & number){
for(int i = 0; i < vertices_->size(); i++){
if(vertices_->at(i)->number_ == number){
return vertices_->at(i);
}
}
return NULL;
}
/**
* isPositiveDegree: returns a bool to indicate that the graph has vertices with
* a positive degree.
* Precondition: None.
* Postcondition: Returns true if the graph contain vertices with a positive degree.
*/
bool Graph::isPositiveDegree(vector & vertices)const{
bool positiveDegree = false;
for(int i = 0; i < vertices.size(); i++){
if((vertices.at(i)->getDegree() > 0) && !vertices.at(i)->locked_){
positiveDegree = true;
break;
}
}
return positiveDegree;
}
/**
* cut: determines what the minimum cut is for a graph.
* The member function creates two graphs by cutting the graph in
* half. Then determines what the degree is for each vertex in
* each graph. Cut then swaps the largest degree vertex in each graph
* until the one of the graphs contain no positive degree vertices.
* Precondition: A graph object is properly initialized and the graph
* contains an even number of vertices.
* Postcondition: The minimum cut for the graph will be determined and
* the graph with the minimum cut will be returned.
*/
string Graph::cut(){
vector lowerGraphVertices; // the vertices contained in the lower graph
// after the cut
vector upperGraphVertices; // the vertices contained in the upper graph
// after the cut
int sizeOfGraph = vertices_->size(); // the size of the graph to cut
string cut; // a string to hold one of the min cuts
stringstream ss; // used to convert ints to strings
// split the graph into half
for(int i = 0; i < sizeOfGraph/2; i++){
lowerGraphVertices.push_back(this->vertices_->at(i));
}
for(int i = sizeOfGraph/2; i < sizeOfGraph; i++){
upperGraphVertices.push_back(this->vertices_->at(i));
}
// calculate the degree of each vertice in the graphs
calculateDegree(lowerGraphVertices);
calculateDegree(upperGraphVertices);
// swap the two vertices with the largest out degrees
// and continue till the min cut is found
while(isPositiveDegree(lowerGraphVertices) && isPositiveDegree(upperGraphVertices)){
swapLargestVertices(lowerGraphVertices, upperGraphVertices);
}
// display the minimum cut and return the cut to the user
cout << "The min cost is " << cost(lowerGraphVertices) << " with the cut ";
for(int i = 0; i < upperGraphVertices.size(); i++){
cout << upperGraphVertices.at(i)->number_ << " ";
int vertNum = upperGraphVertices.at(i)->number_;
ss << vertNum << " ";
}
cout << endl;
cut = ss.str();
return cut;
}
/**
* calculateDegree: calculates the degree of each vertex that is contained
* in the graph. The method determines the outDegree - inDegree for each
* vertex. The degree is used to determine if the edges are connected to
* vertices in the same graph or in another graph. The results are then
* store in the Vertex objects degree_ data member.
* Precondition: A graph object is properly initialized.
* Postcondition: Each vertex in the graph will have its degree determined
* and stored in the vertex's data member degree_.
*/
void Graph::calculateDegree(vector & vertices){
int inDegree = 0; // the in degree of the vertex
int outDegree = 0; // the out degree of the vertex
int degree = 0; // the degree of the vertex
// determine the degree of the vertex
for(int i = 0; i < vertices.size(); i++){
inDegree = 0;
Vertex * vertex = vertices.at(i);
for(int j = 0; j < vertex->edges_->size(); j++){
for(int k = 0; k < vertices.size(); k++){
if(vertex->edges_->at(j)->number_ == vertices.at(k)->number_){
inDegree++;
}
}
}
outDegree = vertex->edges_->size() - inDegree;
degree = outDegree - inDegree;
// set the degree for the vertex
vertices.at(i)->inDegree_ = inDegree;
vertices.at(i)->outDegree_ = outDegree;
}
}
/**
* SwapLargestVertices: swaps the largest positive degree vertex in
* each graph.
* Precondition: Two graph must exist that have vertices of a
* postive degree for degree = outDegree - inDegree.
* Postcondition: The vertex with the largest positive degree from
* each graph is removed from their graph and inserted
* into the other graph.
*/
void Graph::swapLargestVertices(vector & lowerGraph,
vector & upperGraph ){
Vertex * vertexToRemove; // the vertex to remove from lowerGraph
Vertex * otherVertexToRemove; // the vertex to remove from upperGraph
int lowerIndex = 0; // the index location to remove a vertex from lowerGraph
int upperIndex = 0; // the index location to remove a vertex from upperGraph
int nodeToRemoveDegree = 0; // the degree of the vertex to remove from lowerGraph
int otherNodeToRemoveDegree = 0; // the degree of the vertex to remove from upperGraph
// bool foundEqualDegree = false; // found equal degrees for vertices
// find the location of the largest degree to remove from the lower portion of the graph
for(int i = 0; i < lowerGraph.size(); i++){
if((lowerGraph.at(i)->getDegree() >= nodeToRemoveDegree) && !lowerGraph.at(i)->locked_){
// the degrees are equal and previous read vertexToRemove has a smaller number
if((vertexToRemove != NULL)
&& (lowerGraph.at(i)->getDegree() == nodeToRemoveDegree)
&& (vertexToRemove->number_ < lowerGraph.at(i)->number_)){
// do nothing, keep the previous read vertex since it has a smaller number
}else{
lowerIndex = i;
nodeToRemoveDegree = lowerGraph.at(i)->getDegree();
vertexToRemove = lowerGraph.at(i);
}
}
}
// find the location of the largest degree to remove from the upper portion of the graph
for(int i = 0; i < upperGraph.size(); i++){
if((lowerGraph.at(i)->getDegree() >= otherNodeToRemoveDegree) && !upperGraph.at(i)->locked_){
// the degrees are equal and the previous read otherVertexToRemove has a smaller number
if((otherVertexToRemove != NULL)
&& (upperGraph.at(i)->getDegree() == otherNodeToRemoveDegree)
&& (otherVertexToRemove->number_ < upperGraph.at(i)->number_ )){
// do nothing keep the previous read otherVertexToRemove since it is smaller
} else {
upperIndex = i;
otherNodeToRemoveDegree = lowerGraph.at(i)->getDegree();
otherVertexToRemove = upperGraph.at(i);
}
}
}
// swap the vertices
lowerGraph[lowerIndex] = otherVertexToRemove;
upperGraph[upperIndex] = vertexToRemove;
// lock the vertices
vertexToRemove->locked_ = true;
otherVertexToRemove->locked_ = true;
// update the degree of the vertices connected to the vertex that was swapped
updateDegrees(vertexToRemove, upperGraph, lowerGraph);
updateDegrees(otherVertexToRemove, lowerGraph, upperGraph);
}
/**
* UpdateDegrees: updates the inDegree and outDegree for all the edges of a
* vertex and then updates the degree of the vertex.
* Precondition: The member function calculateDegree must be called before
* updateDegrees, so that the degrees contained in the vertices
* are correct.
* Postconditon: The degrees of all vertices connected to the vertex will be
* updated.
*/
void Graph::updateDegrees(Vertex * vertex, vector & setBelongTo,
vector & otherSet){
int inDegree = 0; // the inDegree of the vertex
// update the degrees for the set the vertex was added to
for(int i = 0; i < vertex->edges_->size(); i++){
for(int j = 0; j < setBelongTo.size(); j++){
if(vertex->edges_->at(i)->number_ == setBelongTo.at(j)->number_){
inDegree++;
setBelongTo.at(j)->inDegree_++;
setBelongTo.at(j)->outDegree_--;
}
}
}
// update the degrees for the vertex that is swapped
vertex->inDegree_ = inDegree;
vertex->outDegree_ = vertex->edges_->size() - inDegree;
// update the degrees for the set the vertex is remove from
for(int i = 0; i < vertex->edges_->size(); i++){
for(int j = 0; j < otherSet.size(); j++){
if(vertex->edges_->at(i)->number_ == otherSet.at(j)->number_){
otherSet.at(j)->outDegree_++;
other