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

using namespace leda;

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

bool acyclic(const graph& G, node_array<double>& topsort, node_array<bool>& node_deleted, edge_array<bool>& edge_deleted) {
  list<node> zeroindeg;
  node_array<int> indeg(G);
  int pointer = 0;
  node v;
  edge e;

  // Initialize indeg array and zeroindeg list
  cout << "Initializing" << endl;
  forall_nodes(v, G) {
    indeg[v] = G.indeg(v);
    if (indeg[v] == 0) zeroindeg.append(v);
  }

  // successively remove nodes of indegree zero
  cout << "Running topsort algorithm" << endl;
  while(pointer < zeroindeg.length()) {
    v = zeroindeg.contents(zeroindeg[pointer]);
    cout << "Removing node " << v << endl;
    forall_out_edges(e, v) {
      edge_deleted[e] = true;
      if (--indeg[target(e)] == 0) zeroindeg.append(target(e));
    }
    node_deleted[v] = true;

    topsort[v] = pointer++;
  }

  // return true if all nodes were removed
  bool acyclic = zeroindeg.length() == G.number_of_nodes();
  return acyclic;
}

bool acyclic(GraphWin& gw)
{
  node v;
  node u;
  edge e;
  
  const graph& G = gw.get_graph();
  node_array<int> indeg(G);
  node_array<double> topsort(G);
  node_array<bool> node_deleted(G);
  edge_array<bool> edge_deleted(G);
  bool acyc = acyclic(G, topsort, node_deleted, edge_deleted);

  if (acyc) {
    // visualize acyclic graph
    node_array<double> ycoord(G);
    gw.save_all_attributes();
    gw.set_flush(false);
    gw.message("Graph ist azyklisch.");
    point new_pos;
    forall_nodes(v, G) {
      int i = 0;
      forall_inout_edges(e, v) {
        u = opposite(v, e);
        ycoord[u] = gw.get_position(u).ycoord() + i++;
      }

      gw.set_label_type(v, no_label);
      gw.set_width(v, 8);
      gw.set_height(v, 8);
    }
    gw.set_position(topsort, ycoord);
    gw.redraw();
    gw.set_flush(true);
    gw.place_into_win();

    // wait until user clicks done, then restore graph
    gw.edit();
    gw.restore_all_attributes();
    gw.message("");
  }
  else {
    // successively remove nodes of outdegree 0: init
    queue<node> zerooutdeg;
    node_array<int> outdeg(G);
    forall_nodes (v, G) {
      outdeg[v] = G.outdeg(v);
      if (outdeg[v] == 0 && !node_deleted[v]) zerooutdeg.push(v);
    }

    // remove nodes
    while(!zerooutdeg.empty()) {
      v = zerooutdeg.pop();
      cout << "Removing node " << v << endl;
      forall_in_edges(e, v) {
        if (!edge_deleted[e]){
          edge_deleted[e] = true;
          if (--outdeg[source(e)] == 0) zerooutdeg.append(source(e));
        }
      }
      node_deleted[v] = true;
    }

    // find cycle
    // first find a node that has not been deleted
    node_array<bool> visited(G, false);
    list<node> visitOrder;
    forall_nodes(v, G) {
      if (!node_deleted[v]) break;
    }
    visited[v] = true;
    visitOrder.append(v);

    // run along random edges until reaching an already visited node
    while (true) {
      // find not deleted out edge of v
      forall_out_edges(e, v) {
        if (!edge_deleted[e]) break;
      }

      // check if opposite node is already visited
      v = opposite(v, e);
      if (visited[v]) {
        // remove all nodes visited before the one we found
        while (visitOrder.head() != v) visitOrder.pop();
        break;
      }
      else {
        // Mark node as visited
        visited[v] = true;
        visitOrder.append(v);
      }
    }

    // visualize result
    gw.save_all_attributes();
    gw.message("Graph ist zyklisch.");
    while (!visitOrder.empty()) {
      v = visitOrder.pop();
      gw.set_color(v, green);
    }
    gw.edit();
    gw.restore_all_attributes();
    gw.message("");
  }

  return acyc;
}


int main()
{
  GraphWin gw("Test auf azyklische Graphen");

  gw.display();

  while(gw.edit()) {
    bool isAcyclic = acyclic(gw);
    cout << (isAcyclic ? "Graph is acyclic." : "Graph is cyclic.") << endl;
  }

  return 0;
}