#include <LEDA/graphics/graphwin.h>
#include <LEDA/graph/graph_alg.h>

using namespace leda;

using std::cout;
using std::endl;
using std::to_string;

bool bipartite(const graph& G, node_array<int>& level, list<edge>& circle) {
  node s;
  node v;
  node u;
  edge e;
  edge critical_edge;
  bool is_bipartite = true;
  queue<node> bfsqueue;
  node_array<edge> pred(G);


  forall_nodes(s, G) {    
    // Initialize
    forall_nodes (v, G) level[v] = MAXINT;
    bfsqueue.append(s);
    level[s] = 0;
    pred[s] = nil;

    // Main loop
    while (!bfsqueue.empty()) {
      v = bfsqueue.pop();
      forall_inout_edges(e, v) {
        u = opposite(v, e);
        if (level[u] == MAXINT) {
          pred[u] = e;
          level[u] = level[v] + 1;
          bfsqueue.append(u);
        }
        else if(is_bipartite && (level[u]-level[v]) % 2 == 0) {
           is_bipartite = false;
           critical_edge = e;
        }
      }
    }
    if (!is_bipartite) break;
  }

  if (!is_bipartite) {
    // find odd circle
    circle.clear();
    circle.append(critical_edge);

    if (level[source(critical_edge)] > level[target(critical_edge)]) {
      u = source(critical_edge);
      v = target(critical_edge);
    }
    else {
      v = source(critical_edge);
      u = target(critical_edge);
    }

    while(level[u] > level[v]) {
      circle.append(pred[u]);
      u = opposite(u, pred[u]);
    }

    while(u != v) {
      circle.append(pred[u]);
      circle.append(pred[v]);
      u = opposite(u, pred[u]);
      v = opposite(v, pred[v]);
    }
  }

  return is_bipartite;
}

int main()
{
  GraphWin gw("Bipartite Graphen");
  node v;

  gw.display();

  while(gw.edit()) {
    graph G = gw.get_graph();
    node_array<int> level(G);
    list<edge> circle;
    node_array<double> xcoord(G, 0);
    node_array<double> ycoord(G);

    bool is_bipartite = bipartite(G, level, circle);
    cout << is_bipartite << endl;

    gw.save_all_attributes();
    if(is_bipartite) {
      int counter1 = 0;
      int counter2 = 0;

      forall_nodes(v, G) {
        xcoord[v] = level[v] % 2 == 0 ? 100.0 : 300.0;
        if (level[v] % 2 == 0) {
          ycoord[v] = counter1++ * 12.0;
        }
        else {
          ycoord[v] = counter2++ * 12.0;
        }
      }
      // visualize
      forall_nodes(v, G) {
        point p = point(xcoord[v], ycoord[v]);
        gw.set_position(v, p);
      }
      forall_nodes(v, G) {
        string label;
        if (level[v] == MAXINT) {
          label = string(":(");
        }
        else {
          label += (level[v] + 48);
        }
        gw.set_label(v, label, true);
      }
      gw.update_edges();
      gw.place_into_win();
      gw.update_edges();
      gw.place_into_win();

      gw.message("Graph ist bipartit.");
    }
    else {
      // Set y coordinate (y = level) and find maximum level
      int maxlevel = 0;
      forall_nodes(v, G) {
        if (level[v] != MAXINT) {
          ycoord[v] = static_cast<double>(level[v]);
          if (maxlevel < level[v]) maxlevel = level[v];
        }
        else {
          ycoord[v] = -1.0;
        }
      }

      cout << maxlevel << endl;
      array<int> levelCounters(maxlevel);
      for (int i = 0; i < maxlevel; i++)
      {
        levelCounters[i] = 0;
      }

      // Calculate x coordinates
      forall_nodes(v, G) {
        if (level[v] != MAXINT) {
          int i = level[v];
          if (i == 0) continue;
          xcoord[v] = levelCounters[i-1]++;
        }
      }
      // visualize
      forall_nodes(v, G) {
        point p = point(xcoord[v], ycoord[v]);
        gw.set_position(v, p);
      }
      forall_nodes(v, G) {
        string label;
        if (level[v] == MAXINT) {
          label = string(":(");
        }
        else {
          label += (level[v] + 48);
        }
        gw.set_label(v, label, true);
      }
      gw.update_edges();
      gw.place_into_win();
      gw.update_edges();
      gw.place_into_win();
      gw.set_edge_direction(gw_edge_dir::undirected_edge);
      forall_nodes(v, G) {
        string label;
        if (level[v] == MAXINT) {
          label = string(":(");
        }
        else {
          label += (level[v] + 48);
        }
        gw.set_label(v, label, true);
      }
      gw.set_color(circle, red);
      gw.set_thickness(circle, 3.0);
      gw.message("Graph ist nicht bipartit.");
    }
    
    gw.edit();
    gw.message("");
    gw.restore_all_attributes();
  }

  return 0;
}