//////////////////////////////////////////////////////////////////////////////
/// @file       NetworkFlow.h
/// @author     Benjamin Fedder Jensen (bfje@itu.dk)
/// @brief      Flow Behind Enemy Lines
//              Implements the Ford-Fulkerson Algorithm
//////////////////////////////////////////////////////////////////////////////
#ifndef NETWORKFLOW_H
#define NETWORKFLOW_H

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <list>
#include <vector>
#include <limits>
#include <queue>
#include <set>
#include <unordered_map>

namespace algorithms {

    enum EdgeType { FORWARD, BACKWARD };
    struct Node;    // forward declaration

    struct Edge {
    public:
        Node&           u;  // source
        Node&           v;  // destination
        int             c;  // capacity
        int             f;  // flow
        Edge(Node& u, Node& v, int c) : u(u), v(v), c(c), f(0) {};
    };

    struct ResidualEdge {   // residual edge - derives all from its edge parent e
        Edge&           e;  // edge it belongs to
        EdgeType        t;  // type of edge - determines capacity & direction in graph
        int capacity(void)      { return (t == FORWARD) ? e.c - e.f : e.f; }    // residual capacity
        Node&           u(void) { return (t == FORWARD) ? e.u : e.v; }          // source
        Node&           v(void) { return (t == FORWARD) ? e.v : e.u; }          // destination
        ResidualEdge(Edge& e, EdgeType t) : e(e), t(t) {};
    };

    struct Node {
        std::wstring     n;         // name
        std::list<Edge>  o;         // outgoing edges
        std::list<ResidualEdge> r;  // residual edges
        Node(std::wstring n) : n(n) {};
    };

    typedef std::list<ResidualEdge*> path;

    class NetworkFlow {
        // Append result set to output stream
        friend std::wostream& operator<<(std::wostream& os, NetworkFlow& a);
    private:
        std::vector<Node>   graph; // Both graph & residual graph
    public:
        NetworkFlow&    Load(const std::wstring&);          // Load data set
        int             Execute(void);                      // Execute algorithm
    private:
        void            Augment(path&);                     // Augmenting path
        int             BottleNeck(path&);                  // Bottleneck
        path            BreadthFirstSearch(Node&, Node&, std::set<Edge*>* = NULL);  // BFS search, returns layer
    };

    NetworkFlow& NetworkFlow::Load(const std::wstring& data) {
        std::wcout << L"algorithms::NetworkFlow::Load : Opening file \"" << data << L"\"." << std::endl;
        std::wifstream file;
        file.open(data, std::wifstream::in);
        if (!file.is_open()) throw std::exception("algorithms::NetworkFlow::Load : Could not open file.");
        std::wstring ILine;
        std::getline(file, ILine);
        int n = _wtoi(ILine.c_str());
        for (int i = 0; i < n && std::getline(file, ILine); i++) graph.push_back(Node(ILine));
        std::getline(file, ILine);
        int m = _wtoi(ILine.c_str());
        for (int i = 0; i < m && std::getline(file, ILine); i++) {
            std::wistringstream IStream(ILine);
            int u, v, c;
            IStream >> u >> v >> c;
            if (c < 0) c = std::numeric_limits<int>::max();
            graph[u].o.push_back(Edge(graph[u], graph[v], c));
            graph[u].r.push_back(ResidualEdge(graph[u].o.back(), FORWARD));
            graph[v].r.push_back(ResidualEdge(graph[u].o.back(), BACKWARD));
            graph[v].o.push_back(Edge(graph[v], graph[u], c));
            graph[v].r.push_back(ResidualEdge(graph[v].o.back(), FORWARD));
            graph[u].r.push_back(ResidualEdge(graph[v].o.back(), BACKWARD));
        }
        file.close();
        return *this;
    }

    int NetworkFlow::Execute(void) {
        Node& s = graph.front();    // source
        Node& t = graph.back();     // sink
        path p;                     // path to sink
        int sum = 0;
        while(!(p = BreadthFirstSearch(s, t)).empty()) Augment(p);
        std::list<Edge>::iterator i;
        for (i = graph.front().o.begin(); i != graph.front().o.end(); i++) sum += (*i).f;
        return sum;
    }

    void NetworkFlow::Augment(path& p) {
        int b = BottleNeck(p);
        for (path::iterator i = p.begin(); i != p.end(); i++) {
            if ((*i)->t == FORWARD) (*i)->e.f += b;
            else                    (*i)->e.f -= b;
        }
    }

    int NetworkFlow::BottleNeck(path& p) {
        int b = std::numeric_limits<int>::max();
        for (path::iterator i = p.begin(); i != p.end(); i++) if ((*i)->capacity() <= b) b = (*i)->capacity();
        return b;
    }

    path NetworkFlow::BreadthFirstSearch(Node& s, Node& t, std::set<Edge*>* bottleneck) {
        std::queue<Node*> queue;    // FIFO
        std::set<Node*> closed;     // closed set - visited nodes
        path p;                     // found path as a list
        std::unordered_map<Node*, ResidualEdge*> prev;  // previous nodes - encodes path
        queue.push(&s);
        closed.insert(&s);
        while (!queue.empty()) {
            Node* n = queue.front();
            queue.pop();
            if (n == &t) break;
            std::list<ResidualEdge>::iterator i;
            for (i = n->r.begin(); i != n->r.end(); i++) {
                if (closed.find(&(i->v())) != closed.end()) continue; // is in closed set
                if (i->capacity() < 1) {
                    if (bottleneck) bottleneck->insert(&(*i).e);
                    continue; // has no capacity
                }
                queue.push(&(i->v()));
                closed.insert(&(i->v()));
                prev[&(i->v())] = &(*i);
            }
        }
        if (prev.find(&t) == prev.end()) return p; // t was not reached
        for(Node* n = &t; n != &s; n = &(prev[n]->u())) p.push_front(prev[n]);
        return p; // t was reached - return path
    }

    inline std::wostream& operator<<(std::wostream& os, NetworkFlow& a) {
        Node& s = a.graph.front();  // source
        Node& t = a.graph.back();   // sink
        std::set<Edge*> bottleneck; // bottleneck edges
        a.BreadthFirstSearch(s, t, &bottleneck);
        std::set<Edge*>::iterator i;
        for (i = bottleneck.begin(); i != bottleneck.end(); i++) {
            if ((*i)->f == (*i)->c) // only show those leading from A to B - for each edge there is an edge from B to A with 0 flow
                os << (*i)->u.n << L" --> " << (*i)->v.n << ", flow: " << (*i)->f << ", capacity: " << (*i)->c << "\n";
        }
        return os ;
    }

}

#endif