#include <LEDA/graphics/graphwin.h>
#include <LEDA/graph/graph.h>
#include <LEDA/core/queue.h>
#include <LEDA/core/list.h>

using namespace leda;

// 0 unvisited, 1 visiting, 2 visited in status
void DFS(const graph& G, node s, node_array<int>& status, list<edge>& cycle_edges){
    if (status[s] == 2) return;
    status[s] = 1;
    edge e;
    forall_out_edges(e, s){
        node v = G.target(e);
        if ( status[v] == 0){
            DFS(G, v, status, cycle_edges);
        } else if ( status[v] == 1){
            //Rückwärtskante gefunden
            cycle_edges.append(e);
            node next_node = v;
            edge f;
            while (next_node != s){
                // Kreiskanten finden
                forall_out_edges(f,next_node){
                    node w = G.target(f);
                    if (status[w] == 1){
                        next_node = w;
                        cycle_edges.append(f);
                        break;
                    }
                }
            }
        }
        if (!cycle_edges.empty()) return;
    }
    status[s] = 2;
}    


list<edge> findCycleEdges(const graph& G) {
    node s;
    node_array<int> status(G, 0);
    list<edge> cycle_edges;
    forall_nodes(s, G){
        if (status[s] == 0){
            DFS(G, s, status, cycle_edges);
            if (!cycle_edges.empty()){
                return cycle_edges;
            }
        }
    }
    return cycle_edges;
}


bool TOPSORT(const graph& G, node_array<int>& ord)
{ 
  int n = G.number_of_nodes();

  node_array<int> INDEG(G,0);

  queue<node> ZEROINDEG;

  int count = 0;

  node v;
  forall_nodes(v,G) 
  { int d = G.indeg(v); 
    INDEG[v] = d;
    if (d == 0) ZEROINDEG.append(v); 
   }

  while (!ZEROINDEG.empty())
   { node u = ZEROINDEG.pop();
     ord[u] = ++count;
     edge e;
     forall_out_edges(e,u)
     { node v = G.target(e);
       if (--INDEG[v]==0) ZEROINDEG.append(v);
      }
   }
  
  return count == n; 
}

void redrawing(GraphWin& gw, node_array<int>& ord)
{ 
    const graph& G = gw.get_graph();
    //Anordnung der Kanten
    if (TOPSORT(G, ord)){
        bool flush0 = gw.set_flush(false);
        node v;
        double y = 10;
        forall_nodes(v,G){
            double x = ord[v] * 20;
            gw.set_position(v,point(x,y));
                y += 20;
        }
        gw.redraw();
        gw.set_flush(flush0); 
    }
    else{
        //Faerbung des Kreises
        bool flush0 = gw.set_flush(false);
        list<edge> cycle_edge = findCycleEdges(G);
        edge e;
        forall(e, cycle_edge){
            gw.set_color(e,red);
            node source_node = G.source(e);
            node target_node = G.target(e);
            gw.set_color(source_node,red);
            gw.set_color(target_node,red);
        }    

        
        gw.redraw();
        gw.set_flush(flush0);
    }
}


int main() 
{
    GraphWin gw;
    graph& G = gw.get_graph();
    gw.display(window::center,window::center);
    
    while (gw.edit()){
        node_array<int> ord(G,0);
        if (TOPSORT(G,ord))  {
            gw.save_all_attributes();
            node_array<int> ord(G,0);
            redrawing(gw, ord);
            gw.wait("This Graph is acyclic.");
            gw.restore_all_attributes();
        }
        else {
            gw.save_all_attributes();
            node_array<int> ord(G,0);
            redrawing(gw, ord);
            gw.wait("This Graph is cyclic, here is a Cycle.");
            gw.restore_all_attributes();
        }
    }    
   return 0;
}