Seminar7

// ListGraph как в прошлом семинаре.

#include <iostream>
#include <queue>
#include <memory>
#include <unordered_set>
#include <vector>

#include "ListGraph.hpp"

void BFS(const IGraph& graph, int start) {
  std::vector<bool> visited(graph.VerticesCount());
  std::queue<int> to_go;
  to_go.push(start);
  to_go.push(-1);
  visited[start] = true;
//  int last_in_layer = start;
  while (!to_go.empty()) {
    int u = to_go.front(); to_go.pop();
    if (u == -1) {
      std::cout << "\n";
      if (!to_go.empty()) to_go.push(-1);
      continue;
    }
    std::cout << u << " ";
    for (int v : graph.FindAllAdjacentOut(u)) {
      if (!visited[v]) {
        to_go.push(v);
        visited[v] = true;
      }
    }
//    if (last_in_layer == u) {
//      if (!to_go.empty()) last_in_layer = to_go.back();
//      std::cout << "\n";
//    }
  }
}

int main1() {
  ListGraph lg(10);
  lg.AddEdge(6, 0);
  lg.AddEdge(3, 2);
  lg.AddEdge(2, 1);
  lg.AddEdge(2, 5);
  lg.AddEdge(1, 5);
  lg.AddEdge(3, 4);
  lg.AddEdge(4, 7);
  lg.AddEdge(7, 8);
  lg.AddEdge(8, 4);
  lg.AddEdge(5, 7);
  lg.AddEdge(1, 9);
  lg.AddEdge(9, 3);

  lg.AddEdge(0, 6);
  lg.AddEdge(2, 3);
  lg.AddEdge(1, 2);
  lg.AddEdge(5, 2);
  lg.AddEdge(5, 1);
  lg.AddEdge(4, 3);
  lg.AddEdge(7, 4);
  lg.AddEdge(8, 7);
  lg.AddEdge(4, 8);
  lg.AddEdge(7, 5);
  lg.AddEdge(9, 1);
  lg.AddEdge(3, 9);

  BFS(lg, 3);

  return 0;
}

void DFS(size_t u, const IGraph& graph, std::vector<int8_t>& colors, std::vector<size_t>& parents) {
  colors[u] = 1;  // Grey
  for (size_t v : graph.FindAllAdjacentOut(u)) {
    std::cout << u << " " << v << std::endl;
    if (colors[v] == 0) {
      parents[v] = u;
      DFS(v, graph, colors, parents);
    }
    if (colors[v] == 1) {  // Нашли цикл
      std::cout << "Success!\n";
      std::cout << v << " ";
      for (size_t w = u; w != v; w = parents[w]) {
        std::cout << w << " ";
      }
      std::cout << "\n";
    }
  }
  colors[u] = 2;  // Black
}

void MainDFS(const IGraph& graph) {
  std::vector<int8_t> colors(graph.VerticesCount()/*, false*/);
  std::vector<size_t> parents(graph.VerticesCount(), -1);
  for (size_t v = 0; v < graph.VerticesCount(); ++v) {
    if (colors[v] == 0) DFS(v, graph, colors, parents);
  }
}

int main2() {
  ListGraph lg(7);
  lg.AddEdge(0, 1);
  lg.AddEdge(1, 2);
  lg.AddEdge(2, 3);
  lg.AddEdge(6, 2);
  lg.AddEdge(6, 5);
  lg.AddEdge(6, 4);
  lg.AddEdge(3, 6);
  lg.AddEdge(4, 2);
  lg.AddEdge(5, 1);

  MainDFS(lg);

  return 0;
}

bool BFSForDualCheck(const IGraph& graph, size_t start, std::unordered_set<size_t>& left,
                     std::unordered_set<size_t>& right) {
  std::queue<size_t> to_go;
  to_go.push(start);
  while (!to_go.empty()) {
    size_t u = to_go.front(); to_go.pop();
    bool is_left = left.contains(u);
    for (size_t v : graph.FindAllAdjacentOut(u)) {
      if (left.contains(v)) {
        if (is_left) return false;
      } else if (right.contains(v)) {
        if (!is_left) return false;
      } else {
        to_go.push(v);
        (is_left ? right : left).insert(v);
      }
    }
  }
  return true;
}

bool IsDual(const IGraph& graph) {
  std::unordered_set<size_t> left, right;
  for (size_t i = 0; i < graph.VerticesCount(); ++i) {
    if (!left.contains(i) && !right.contains(i)) {
      left.insert(i);
      if (!BFSForDualCheck(graph, i, left, right)) return false;
    }
  }
  return true;
}

int main3() {
  ListGraph lg(7);
  lg.AddEdge(0, 1);
  lg.AddEdge(1, 2);
  lg.AddEdge(2, 3);
  lg.AddEdge(6, 2);
  lg.AddEdge(6, 5);
  lg.AddEdge(6, 4);
  lg.AddEdge(3, 6);
  lg.AddEdge(4, 2);
  lg.AddEdge(5, 1);

  std::cout << IsDual(lg);

  return 0;
}

void DFSReverseRecursive(size_t u, const IGraph& graph,
                         std::vector<bool>& visited, std::vector<size_t>& to_go) {
  visited[u] = true;
  for (size_t v : graph.FindAllAdjacentIn(u)) {
    if (!visited[v]) DFSReverseRecursive(v, graph, visited, to_go);
  }
  to_go.push_back(u);
}

std::vector<size_t> DFSReverse(const IGraph& graph) {
  std::vector<size_t> to_go;
  std::vector<bool> visited(graph.VerticesCount());
  for (size_t s = 0; s < graph.VerticesCount(); ++s) {
    if (!visited[s]) DFSReverseRecursive(s, graph, visited, to_go);
  }
  return to_go;
}

std::unique_ptr<IGraph> Condense(const IGraph& graph) {
  std::vector<size_t> to_go = DFSReverse(graph);
//  for (int i = to_go.size() - 1; i >= 0; --i) {
//    if (!visited[to_go[i]]) {
//      ++current;
//      DFSCondense(to_go[i], graph, visited, component, current);
//    }
//  }

  std::unique_ptr<IGraph> condense = std::make_unique<ListGraph>(4);

  return condense;
}

int main() {
  ListGraph lg(10);
  lg.AddEdge(6, 0);
  lg.AddEdge(3, 2);
  lg.AddEdge(2, 1);
  lg.AddEdge(2, 5);
  lg.AddEdge(1, 5);
  lg.AddEdge(3, 4);
  lg.AddEdge(4, 7);
  lg.AddEdge(7, 8);
  lg.AddEdge(8, 4);
  lg.AddEdge(5, 7);
  lg.AddEdge(1, 9);
  lg.AddEdge(9, 3);

  auto condense = Condense(lg);
  return 0;
}