From 2bfae41038b8b5c82eb8109ca59d556fff65fadd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Mon, 14 Nov 2016 07:06:13 +0100
Subject: Algorithms : complete 05-advanced_algorithms_and_complexity
 01-flows_in_networks

---
 .../01-evacuation/evacuation.cpp                   |  46 ++++++
 .../02-airline_crews/airline_crews.cpp             | 170 +++++++++++++++++++--
 .../03-stock_charts/stock_charts.cpp               | 154 +++++++++++++++----
 3 files changed, 335 insertions(+), 35 deletions(-)

diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp
index db0dfe8..f6b857b 100644
--- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp
+++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/01-evacuation/evacuation.cpp
@@ -1,7 +1,10 @@
 #include <iostream>
 #include <vector>
+#include <queue>
+#include <limits>
 
 using std::vector;
+using std::queue;
 
 /* This class implements a bit unusual scheme for storing edges of the graph,
  * in order to retrieve the backward edge for a given edge quickly. */
@@ -71,6 +74,49 @@ FlowGraph read_data() {
 
 int max_flow(FlowGraph& graph, int from, int to) {
     int flow = 0;
+
+    queue<int> q;
+
+    for (;;) {
+        vector<int> pred(graph.size(), -1);
+        q.push(from);
+        while(!q.empty()) {
+            int node = q.front();
+            q.pop();
+            auto edges = graph.get_ids(node);
+            for (int i = 0; i < edges.size(); i++) {
+                const FlowGraph::Edge& edge = graph.get_edge(edges[i]);
+                 if (pred[edge.to] == -1 && edge.to != from && edge.capacity > edge.flow) {
+                    pred[edge.to] = edges[i];
+                    q.push(edge.to);
+                 }
+            }
+        }
+        if (pred[to] == -1)
+            break;
+
+        /* std::cout << from << " -> " << to << std::endl; */
+        /* for (int i = 0; i < pred.size(); i++) */
+        /*     std::cout << pred[i] << " "; */
+        /* std::cout << std::endl; */
+        /* break; */
+
+        int df = std::numeric_limits<int>::max();
+        for (int e = pred[to]; e != -1; e = pred[e]) {
+            const FlowGraph::Edge& edge = graph.get_edge(e);
+            /* std::cout << edge.from << " -> " << edge.to << std::endl; */
+            df = std::min(df, edge.capacity - edge.flow);
+            e = edge.from;
+        }
+
+        for (int e = pred[to]; e != -1; e = pred[e]) {
+            const FlowGraph::Edge& edge = graph.get_edge(e);
+            graph.add_flow(e, df);
+            e = edge.from;
+        }
+
+        flow += df;
+    }
     return flow;
 }
 
diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp
index 46765ea..d81c09a 100644
--- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp
+++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/02-airline_crews/airline_crews.cpp
@@ -2,10 +2,96 @@
 #include <vector>
 #include <algorithm>
 #include <memory>
+#include <stack>
 
 using std::vector;
+using std::stack;
 using std::cin;
 using std::cout;
+using std::endl;
+
+/* #define DEBUG */
+
+class FlowGraph {
+public:
+    struct Edge {
+        int from, to;
+    };
+
+private:
+    vector<Edge> edges;
+    vector<bool> full;
+    vector<vector<size_t>> graph;
+    vector<bool> visited;
+
+public:
+    explicit FlowGraph(size_t n): graph(n) { }
+
+    void add_edge(int from, int to) {
+        Edge forward_edge = {from, to};
+        Edge backward_edge = {to, from};
+        graph[from].push_back(edges.size());
+        edges.push_back(forward_edge);
+        graph[to].push_back(edges.size());
+        edges.push_back(backward_edge);
+        full.push_back(false);
+        full.push_back(true);
+    }
+
+    size_t size() const {
+        return graph.size();
+    }
+
+    const vector<size_t>& get_ids(int from) const {
+        return graph[from];
+    }
+
+    const Edge& get_edge(size_t id) const {
+        return edges[id];
+    }
+
+    const bool isFull(size_t id) const {
+        return full[id];
+    }
+
+    void print_edge(size_t id) const {
+        const Edge& e = get_edge(id);
+        cout << " " << e.from << "->" << e.to << " " << full[id] << endl;
+    }
+
+    void use(size_t id) {
+        full[id] = !full[id];
+        full[id ^ 1] = !full[id ^ 1];
+    }
+
+    void dfs(int from, int to, vector<size_t>& path) {
+        path.clear();
+        visited.clear();
+        visited.resize(graph.size(), false);
+        _dfs(from, to, path);
+    }
+
+private:
+    bool _dfs(int from, int to, vector<size_t>& path) {
+        visited[from] = true;
+
+        if (from == to)
+            return true;
+
+        const vector<size_t>& ids = get_ids(from);
+        for (auto id : ids) {
+            if (!full[id]) {
+                int next = edges[id].to;
+                if (!visited[next] && _dfs(next, to, path)) {
+                    path.push_back(id);
+                    return true;
+                }
+            }
+        }
+
+        return false;
+    }
+};
 
 class MaxMatching {
  public:
@@ -41,19 +127,85 @@ class MaxMatching {
     cout << "\n";
   }
 
-  vector<int> FindMatching(const vector<vector<bool>>& adj_matrix) {
-    // Replace this code with an algorithm that finds the maximum
-    // matching correctly in all cases.
+  vector<int> FindMatching(const vector<vector<bool>>& adj_matrix)
+  {
     int num_left = adj_matrix.size();
     int num_right = adj_matrix[0].size();
+
+#ifdef DEBUG
+    cout << "matrix" << endl;
+    for (int i = 0; i < num_left; i++) {
+      for (int j = 0; j < num_right; j++)
+          cout << adj_matrix[i][j] << " ";
+      cout << endl;
+    }
+    cout << " ---" << endl;
+#endif
+
+    FlowGraph graph(num_left + num_right + 2);
+    int source = graph.size() - 2;
+    int sink = source + 1;
+
+    for (int i = 0; i < num_left; i++)
+        graph.add_edge(source, i);
+    for (int i = num_left; i < num_left + num_right; i++)
+        graph.add_edge(i, sink);
+
+    for (int i = 0; i < num_left; i++) {
+        for (int j = 0; j < num_right; j++) {
+            if (adj_matrix[i][j])
+                graph.add_edge(i, num_left + j);
+        }
+    }
+#ifdef DEBUG
+    cout << "graph : " << endl;
+    for (int i = 0; i < graph.size(); i++) {
+        const vector<size_t>& ids = graph.get_ids(i);
+        for (int j = 0; j < ids.size(); j++)
+            graph.print_edge(ids[j]);
+        cout << endl;
+    }
+#endif
+
+    vector<size_t> edges;
+    for(;;) {
+
+        graph.dfs(source, sink, edges);
+
+        if (edges.size() == 0)
+            break;
+#ifdef DEBUG
+        cout << "path : " << endl;
+        for (auto eid : edges)
+            graph.print_edge(eid);
+        cout << endl;
+#endif
+
+        for (auto e : edges)
+            graph.use(e);
+
+#ifdef DEBUG
+        cout << "graph : " << endl;
+        for (int i = 0; i < graph.size(); i++) {
+            const vector<size_t>& ids = graph.get_ids(i);
+            for (int j = 0; j < ids.size(); j++)
+                graph.print_edge(ids[j]);
+            cout << endl;
+        }
+#endif
+    }
+
     vector<int> matching(num_left, -1);
-    vector<bool> busy_right(num_right, false);
-    for (int i = 0; i < num_left; ++i)
-      for (int j = 0; j < num_right; ++j)
-        if (matching[i] == -1 && !busy_right[j] && adj_matrix[i][j]) {
-          matching[i] = j;
-          busy_right[j] = true;
+    for (int i = 0; i < num_left; i++) {
+        const vector<size_t>& ids = graph.get_ids(i);
+        for (auto& eid : ids) {
+            if (graph.isFull(eid)) {
+                const FlowGraph::Edge& edge = graph.get_edge(eid);
+                if (edge.to != source)
+                    matching[edge.from] = edge.to - num_left;
+            }
         }
+    }
     return matching;
   }
 };
diff --git a/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp b/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp
index 2a70c87..a6cca51 100644
--- a/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp
+++ b/05-advanced_algorithms_and_complexity/01-flows_in_networks/03-stock_charts/stock_charts.cpp
@@ -7,6 +7,97 @@ using std::vector;
 using std::cin;
 using std::cout;
 
+class FlowGraph {
+public:
+    struct Edge {
+        int from, to;
+    };
+
+private:
+    vector<Edge> edges;
+    vector<bool> full;
+    vector<vector<size_t>> graph;
+    vector<bool> visited;
+
+public:
+    explicit FlowGraph(size_t n): graph(n) { }
+
+    void add_edge(int from, int to) {
+        Edge forward_edge = {from, to};
+        Edge backward_edge = {to, from};
+        graph[from].push_back(edges.size());
+        edges.push_back(forward_edge);
+        graph[to].push_back(edges.size());
+        edges.push_back(backward_edge);
+        full.push_back(false);
+        full.push_back(true);
+    }
+
+    size_t size() const {
+        return graph.size();
+    }
+
+    const vector<size_t>& get_ids(int from) const {
+        return graph[from];
+    }
+
+    const Edge& get_edge(size_t id) const {
+        return edges[id];
+    }
+
+    const bool isFull(size_t id) const {
+        return full[id];
+    }
+
+    void print_edge(size_t id) const {
+        const Edge& e = get_edge(id);
+        cout << " " << e.from << "->" << e.to << " " << full[id] << "\n";
+    }
+
+    void print() {
+        cout << "graph : " << "\n";
+        for (int i = 0; i < size(); i++) {
+            const vector<size_t>& ids = get_ids(i);
+            for (int j = 0; j < ids.size(); j++)
+                print_edge(ids[j]);
+            cout << "\n";
+        }
+    }
+
+    void use(size_t id) {
+        full[id] = !full[id];
+        full[id ^ 1] = !full[id ^ 1];
+    }
+
+    void dfs(int from, int to, vector<size_t>& path) {
+        path.clear();
+        visited.clear();
+        visited.resize(graph.size(), false);
+        _dfs(from, to, path);
+    }
+
+private:
+    bool _dfs(int from, int to, vector<size_t>& path) {
+        visited[from] = true;
+
+        if (from == to)
+            return true;
+
+        const vector<size_t>& ids = get_ids(from);
+        for (auto id : ids) {
+            if (!full[id]) {
+                int next = edges[id].to;
+                if (!visited[next] && _dfs(next, to, path)) {
+                    path.push_back(id);
+                    return true;
+                }
+            }
+        }
+
+        return false;
+    }
+};
+
 class StockCharts {
  public:
   void Solve() {
@@ -32,35 +123,46 @@ class StockCharts {
   }
 
   int MinCharts(const vector<vector<int>>& stock_data) {
-    // Replace this incorrect greedy algorithm with an
-    // algorithm that correctly finds the minimum number
-    // of charts on which we can put all the stock data
-    // without intersections of graphs on one chart.
-
-    int num_stocks = stock_data.size();
-    // Vector of charts; each chart is a vector of indices of individual stocks.
-    vector<vector<int>> charts;
-    for (int i = 0; i < stock_data.size(); ++i) {
-      bool added = false;
-      for (auto& chart : charts) {
-        bool can_add = true;
-        for (int index : chart)
-          if (!compare(stock_data[i], stock_data[index]) &&
-              !compare(stock_data[index], stock_data[i])) {
-            can_add = false;
-            break;
+      int sz = stock_data.size();
+
+      FlowGraph graph(2 * sz + 2);
+      int source = graph.size() - 2;
+      int sink = source + 1;
+
+
+      for (int i = 0; i < sz; i++) {
+          for (int j = 0; j < sz; j++) {
+              // j is strictly above i
+              if (compare(stock_data[i], stock_data[j]))
+                  graph.add_edge(i, sz + j);
           }
-        if (can_add) {
-          chart.push_back(i);
-          added = true;
-          break;
-        }
       }
-      if (!added) {
-        charts.emplace_back(vector<int>{i});
+
+      for (int i = 0; i < sz; i++) {
+          graph.add_edge(source, i);
+          graph.add_edge(sz + i, sink);
       }
-    }
-    return charts.size();
+
+      /* graph.print(); */
+
+      vector<size_t> edges;
+      for(;;) {
+
+          graph.dfs(source, sink, edges);
+
+          if (edges.size() == 0)
+              break;
+
+          for (auto e : edges)
+              graph.use(e);
+      }
+
+      int ret = 0;
+      for (auto& eid : graph.get_ids(source)) {
+          if (!graph.isFull(eid))
+              ret += 1;
+      }
+      return ret;
   }
 
   bool compare(const vector<int>& stock1, const vector<int>& stock2) {
-- 
cgit v1.1-2-g2b99