template<class T>
vector<Vertex<T> *> Graph<T>::calculateFordFulkerson(T source) {
    Graph<T> gr = this->clone();
    Graph<T> gf = this->clone();
    gf.resetEdgeFlow();

    Vertex<T>* src = gr.getVertex(source);
    if (src==NULL) throw -1;

    while(true)
    {
        vector<Vertex<T>*> visited;
        visited.push_back(src);

        float res = this->calculateFordFulkerson(src, NULL, 99999, &gf, &gr, visited);
        if (res < 0)
        {
            //*** All paths were searched. Terminating!
            break;
        }
    }

    return gf.vertexSet;
}

template<class T>
float Graph<T>::calculateFordFulkerson(Vertex<T>* current, Vertex<T>* parent, float min, Graph<T>* gf, Graph<T>* gr, vector<Vertex<T> *> visited) {

    vector<Edge<T> > edges = current->adj;

    for (unsigned int i = 0; i < edges.size(); i++)
    {
        Edge<T> edg = edges[i];

        //*** Searching edge to vertex edg.dest->info

        Vertex<T>* dest = edges[i].dest;
        Vertex<T>* destInGraph = this->getVertex(edges[i].dest->info);

        bool beenVisited = false;
        for (unsigned int j = 0; j < visited.size(); j++)
        {
            if (dest->info == visited[j]->info)
            {
                //*** Detected that dest->info was already visited. Will now continue with the next one!
                beenVisited = true;
                break;
            }
        }

        if (beenVisited)
            continue;

        if (edg.flow < min)
        {
            min = edg.flow;
            //*** Minimum flow updated to: min
        }

        visited.push_back(dest);

        if (destInGraph->adj.size() == 0)
        {
            //*** Reached a destination: dest->info

            //Upon the return, update the edges with the min value
            float newValue = edg.flow - min;
            if (newValue == 0)
            {
                //*** Deleting edge from current->info to dest->info since the val is 0!
                gr->removeEdge(current->info, dest->info);
            }
            else
                current->updateEdgeFlow(i, edg.flow - min);


            //Check to see if this edge already exists
            bool exists = false;
            unsigned int k = 0;
            for (k = 0; k < dest->adj.size(); k++)
            {
                if (dest->adj[k].dest->info == current->info)
                {
                    exists = true;
                    break;
                }
            }

            if (!exists)
            {
                gr->addEdge(dest->info, current->info, edg.weight, min);
                //*** Edge from dest->info to current->info does not exist in Gr... Adding with min
            }
            else
            {
                dest->updateEdgeFlow(k, dest->adj[k].flow + min);
                //*** Edge from dest->info to current->info already exists in Gr... Updating to: dest->adj[k].flow + min
            }

            //Search for the correct edge on Gf since both graphs may be unsynchronized
            Vertex<T>* updatedVertex = gf->getVertex(current->info);
            for (k = 0; k < current->adj.size(); k++)
            {
                if (current->adj[k].dest->info == dest->info)
                    break;
            }
            float oldValue = updatedVertex->adj[k].flow;

            updatedVertex->updateEdgeFlow(k, oldValue + min);
            Edge<T> updatedEdge = updatedVertex->adj[k];

            //*** Setting k new edge flow value to the final graph from updatedVertex->info to updatedEdge.dest->info with k flow value of updatedEdge.flow

            //****** Returning minimum value of : min
            return min;
        }
        else
        {
            //*** Will enter recursion with new current: dest->info
            float newmin = this->calculateFordFulkerson(dest, current, min, gf, gr, visited);

            //*** Returned from recursion where new current was: dest->info
            //*** New minimum value is: newmin

            if (newmin < 0)
            {
                //*** There are no more paths to the destination. Exiting with new minimum: newmin
                continue;
            }

            //Upon the return, update the edges with the min value
            float newValue = edg.flow - newmin;
            if (newValue == 0)
            {
                //*** Deleting edge from current->info to dest->info since the val is 0!
                gr->removeEdge(current->info, dest->info);
            }
            else
                current->updateEdgeFlow(i, edg.flow - newmin);

            //Check to see if this edge already exists
            bool exists = false;
            unsigned int k = 0;
            for (k = 0; k < dest->adj.size(); k++)
            {
                if (dest->adj[k].dest->info == current->info)
                {
                    exists = true;
                    break;
                }
            }

            if (!exists)
            {
                gr->addEdge(dest->info, current->info, edg.weight, newmin);
                //*** Edge from dest->info to current->info does not exist in Gr... Adding with newmin
            }
            else
            {
                float newValue = dest->adj[k].flow + newmin;
                dest->updateEdgeFlow(k, newValue);
                //*** Edge from dest->info to current->info already exists in Gr... Updating to: newValue
            }

            //Search for the correct edge on Gf since both graphs may be unsynchronized
            Vertex<T>* updatedVertex = gf->getVertex(current->info);
            for (k = 0; k < updatedVertex->adj.size(); k++)
            {
                if (updatedVertex->adj[k].dest->info == dest->info)
                    break;
            }
            if (k < updatedVertex->adj.size())
            {
                float oldValue = updatedVertex->adj[k].flow;

                updatedVertex->updateEdgeFlow(k, oldValue + newmin);
                Edge<T> updatedEdge = updatedVertex->adj[k];

                //*** Setting k new edge flow value to the final graph from updatedVertex->info to updatedEdge.dest->info with k flow value of updatedEdge.flow
            }
            else {
                //*** Didn't find the edge on Gf. Probably this was a REVERSE EDGE created in Gr. Find corresponding in Gf...
                Vertex<T>* reverseVertex = gf->getVertex(dest->info);
                for (k = 0; k < reverseVertex->adj.size(); k++)
                {
                    if (reverseVertex->adj[k].dest->info == current->info)
                        break;
                }
                if (k < reverseVertex->adj.size())
                {
                    float oldValue = reverseVertex->adj[k].flow;

                    reverseVertex->updateEdgeFlow(k, oldValue - newmin);
                    Edge<T> reverseEdge = reverseVertex->adj[k];

                    //*** ADJUSTING edge flow value to the final graph from reverseVertex->info to reverseEdge.dest->info with k flow value of reverseEdge.flow
                }

            }

            //*** Returning new minimum value of newmin after recursion!
            return newmin;
        }

    }

    return -1;
}