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

using namespace leda;

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

void my_BFS(const graph& G, node s, node_array<int>& level) {
  queue<node> bfsqueue;
  node v;
  node u;
  edge e;
  
  // Initialize
  forall_nodes (v, G) level[v] = MAXINT;
  bfsqueue.push(s);
  level[s] = 0;

  // Main loop
  while (!bfsqueue.empty()) {
      v = bfsqueue.pop();
      forall_inout_edges(e, v) {
        u = opposite(v, e);
        if (level[u] == MAXINT) {
          level[u] = level[v] + 1;
          bfsqueue.append(u);
        }
      }
    }
}

int main()
{
  GraphWin gw("BFS-Algorithmus");

  gw.display();

  while(gw.edit()) {
    graph G = gw.get_graph();
    node s = G.all_nodes().head();
    node_array<int> level(G);

    my_BFS(G, s, level);

    node v;
    node_array<double> xcoord(G, 0);
    node_array<double> ycoord(G);

    // 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
    gw.save_all_attributes();
    // gw.set_flush(false);
    // gw.set_position(xcoord, ycoord);
    forall_nodes(v, G) {
      point p = point(xcoord[v], ycoord[v]);
      gw.set_position(v, p);
    }
    gw.place_into_win();
    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.redraw();

    gw.edit();
    //gw.set_flush(true);
    gw.restore_all_attributes();
  }

  return 0;
}