/**************************************************************************
*
*
*   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 <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>

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 <Vertex *> * 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::~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<int> getVertexNumbers();
        string cut();
        friend ostream & operator<<(ostream & out, const Graph & graph);	

    private:
        void displayTable(vector<Vertex *> vertices);  
        int cost(vector <Vertex *> & vertices);    
        bool isPositiveDegree(vector<Vertex *> & vertices) const;
        void swapLargestVertices(vector <Vertex *> & lowerGraph, 
                                 vector <Vertex *> & upperGraph);
        void updateDegrees(Vertex * vertex, vector <Vertex *> & setBelongTo, 
                                                vector <Vertex *> & otherSet);
        void calculateDegree(vector <Vertex*> & vertices);
        Vertex * getVertex(const int & number);

        vector<Vertex *> *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<Vertex*>;	
    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<Vertex *> & 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<Vertex*> lowerGraphVertices;      // the vertices contained in the lower graph
                                             // after the cut
    vector<Vertex*> 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 <Vertex*> & 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<Vertex *> & lowerGraph, 
                                          vector <Vertex *> & 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 <Vertex *> & setBelongTo, 
                                               vector <Vertex *> & 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