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


void make_acyclic(graph& G)
{
  node_array<int> dfsnum(G);
  node_array<int> compnum(G);
  DFS_NUM(G,dfsnum,compnum);

  list<edge> back;
  edge e;

  forall_edges(e,G)
  { node v = source(e);
    node w = target(e);
    if (v == w || (dfsnum[v] > dfsnum[w] && compnum[v] < compnum[w]))
    { back.append(e);
      }
  }

  forall(e, back) G.del_edge(e);

}


int compute_depth(graph& G, node_array<int>& depth)
{
  // reverse all edges and compute longest paths in topological order
  // starting in nodes with indegree 0
  // PRECONDITION: G is acyclic or the edges causing cycles are marked 'hidden'
 
  node_array<int>  degree(G);
  list<node>       zero_deg;
  node v;
  edge e;

  int count = 0;
  int max_depth = 0;
 
  forall_nodes(v,G)
  { depth[v] = 0;
    degree[v] = G.indeg(v);
    if (G.indeg(v) == 0) zero_deg.append(v);
  }
 
  while(! zero_deg.empty())
  { count++;
    v = zero_deg.pop();
    forall_out_edges(e, v)
    { int  d = depth[v]+1;
      node w = G.target(e);
      if (depth[w] < d) 
      { depth[w] = d;
        if (max_depth < d) max_depth = d;
      }
      if (--degree[w] == 0) zero_deg.append(w);
    }
  }

  if (count < G.number_of_nodes()) 
  { cerr << "Error: cyclic graph\n";
    exit(1);
  }

  return max_depth;
}



int main(int argc, char *argv[])
{
  GraphWin GW("Sugiyama Demo");

/* funktioniert wohl erst nach W.display() richtig ??????
  GW.set_node_shape(rectangle_node);
  GW.set_node_width(18);
  GW.set_node_height(18);
  GW.set_flush(false);
*/

  GW.display();

  GW.set_node_shape(circle_node);
  GW.set_node_width(10);
  GW.set_node_height(10);
  GW.set_node_label_type(no_label);
  GW.set_directed(true);
  GW.set_flush(false);

  GW.message("Construct a graph and press done.");

  while (GW.edit()) 
  {
    graph& G= GW.get_graph();

    node_array<int>        level(G);
    node_array<int>        xcoord(G);
    edge_array<list<int> > xpoly(G);

    make_acyclic(G);
    GW.update_graph();

    compute_depth(G, level);

    float T = used_time();

    int crossings = SUGIYAMA_EMBEDDING(G, xcoord, level, xpoly);

    T = used_time() - T;

    GW.update_graph();

    node v;
    forall_nodes(v, G)
       GW.set_position(v,point(xcoord[v],level[v]));

    edge e;
    forall_edges(e,G) 
    { list<int>& X = xpoly[e];
      if (!X.empty())
      { list<point> poly;
        int y = level[source(e)]; 
        int x;
        forall(x,X)
           poly.append(point(x,++y));
        GW.set_polygon(e,poly);
       }
     }
        
   GW.fill_window();
   GW.message(string("%d crossings     time: %.2f sec", crossings,T));

  }

 return 0;
}






