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


int compute_depth(const graph& G, node s, node_array<int>& depth, int offset=0)
// computes the depth of each node v with respect to node s. The depth
// of v is the length of the longest path from s to v. The offset is added
// to all depths. The maximal depth is returned.
// PRECONDITION: s is the single source of the acyclic graph G.
{
  node_array<int>  degree(G);
  list<node>       zero_deg;
  node v;
  edge e;

  int max_depth = offset;
 
  forall_nodes(v,G)
  {
    depth[v] = offset;
    degree[v] = G.indeg(v);
  }

  zero_deg.append(s);
 
  while(!zero_deg.empty())
  {
    v = zero_deg.pop();
    forall_adj_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);
    }
  }

  return max_depth;
}



int VISIBILITY_REPRESENTATION(graph& G,
    node_array<int>& leftx, node_array<int>& rightx, node_array<int>& ypos,
    edge_array<int>& xpos, edge_array<int>& lowy, edge_array<int>& topy)
// computes a visibility representation of the graph G, that is, each node
// is represented by a horizontal segment (or box) and each edge is
// represented by a vertical segment. We store the left and right x-coordinate
// of the segments representing nodes in the arrays leftx and rightx.
// We store the y-coordinate of a node segment in ypos. We store the
// lower and upper y-coordinate of edges in lowy and topy. We store the
// the x-coordinate of an edge segment in xpos.
// Precondition: G is simple, biconnected, planar and contains at least
// three nodes.
{
  graph D;                           // dual graph
  node v,s,t;
  edge e;
  face f;

  face_map<node> corr_node(G);       // maps between primal faces
  node_map<face> corr_face(D);       // and dual nodes
  edge_map<edge> corr_dual(G);       // maps between primal and
  edge_map<edge> corr_primal(D);     // dual edges

  edge_map<face> edge_left_face(G);  // left face of a primal edge
  node_map<face> node_left_face(G);  // left face of a primal node
  node_map<face> node_right_face(G); // right face of a primal node
                // left and right are according to st-orientation

  // make graph bidirected
  list<edge> bd_edges = Make_Bidirected(G);
  edge_array<bool> is_bd_edge(G,false);
  forall(e,bd_edges) is_bd_edge[e] = true;

  // compute embedding and dual graph
  G.make_planar_map();
  forall_faces(f,G)
  {
    node d = D.new_node();
    corr_node[f] = d;
    corr_face[d] = f;
  }
  forall_edges(e,G)
  {
    face f1 = G.adj_face(e);
    face f2 = G.adj_face(G.reversal(e));
    if( (!is_bd_edge[e]) && (f1 != f2) )
    {
      edge d =
      D.new_edge(corr_node[f1],corr_node[f2]);
      corr_dual[e] = d;
      corr_primal[d] = e;
    }
    else corr_dual[e] = nil;   // e is a bridge
  }

  // compute primal ST-numbering
  node_array<int> st_num(G);
  list<node> st_list;
  ST_NUMBERING(G,st_num,st_list);

  // find s,t and (s,t)
  s = st_list.pop();
  t = st_list.Pop();
  edge st = is_bd_edge[G.first_adj_edge(t)] ?
              G.reversal(G.first_adj_edge(t)) : G.first_adj_edge(t);

  // compute edge_left_face, node_left_face, node_right_face
  forall_faces(f,G)
  {
    forall_face_edges(e,f)
    {
      edge succ = G.face_cycle_succ(e);
      int e_max = Max(st_num[source(e)],st_num[target(e)]);
      int e_min = Min(st_num[source(e)],st_num[target(e)]);
      int s_max = Max(st_num[source(succ)],st_num[target(succ)]);
      int s_min = Min(st_num[source(succ)],st_num[target(succ)]);
      if(e_max == s_min) node_left_face[target(e)] = f;
      if(e_min == s_max) node_right_face[target(e)] = f;

      if(!is_bd_edge[e] && (e_min == st_num[source(e)]))
        edge_left_face[e] = f;
      else
        edge_left_face[e] = G.adj_face(G.reversal(e));
    }
  }
  if(source(st) == t)
  {
    node_left_face[t] = node_left_face[s] = G.adj_face(G.reversal(st));
    node_right_face[t] = node_right_face[s] = G.adj_face(st);
  }
  else
  {
    node_right_face[t] = node_right_face[s] = G.adj_face(G.reversal(st));
    node_left_face[t] = node_left_face[s] = G.adj_face(st);
  }

  // remove auxiliary edges
  G.del_edges(bd_edges);

  // orient all edges according to the st-numbering
  forall_edges(e,G)
    if(st_num[target(e)] < st_num[source(e)]) G.rev_edge(e);

  // compute primal depths
  node_array<int> primal_depth(G);
  compute_depth(G,s,primal_depth);

  // orient dual edges
  forall_edges(e,D)
  {
    edge p = corr_primal[e];
    if(corr_node[edge_left_face[p]] != source(e)) D.rev_edge(e);
  }
  D.rev_edge(corr_dual[st]);

  // compute dual depths
  node_array<int> dual_depth(D);
  compute_depth(D,corr_node[node_right_face[s]],dual_depth);

  // compute left, right, top, bottom
  forall_edges(e,G)
  {
    xpos[e] = dual_depth[corr_node[edge_left_face[e]]];
    lowy[e] = primal_depth[source(e)];
    topy[e] = primal_depth[target(e)];
  }
  forall_nodes(v,G)
  {
    int xmin = D.number_of_nodes()+1;
    int xmax = -1;

    // search for leftmost and rightmost edge of v
    forall_inout_edges(e,v)
    {
      int eleft = dual_depth[corr_node[edge_left_face[e]]];
      if(eleft < xmin) xmin = eleft;
      if(eleft > xmax) xmax = eleft;
    }

    leftx[v] = xmin;
    rightx[v] = xmax;
    ypos[v] = primal_depth[v];
  }

  return Max(primal_depth[t],dual_depth[corr_node[node_left_face[s]]]);
}


main()
{
  GraphWin GW;

  GW.display();

  GW.set_flush(false);

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

    if (!Is_Simple(G))
    { GW.message("Graph is not simple");
      continue;
     }

    if (!PLANAR(G))
    { GW.message("Graph is not planar");
      continue;
     }

/*
    if (!Is_Biconnected(G))
    { GW.message("Graph is not biconnected");
      continue;
     }
*/

    list<edge> bi_edges;
    Make_Biconnected(G,bi_edges);


    node_array<int> leftx(G);
    node_array<int> rightx(G);
    node_array<int> ypos(G);

    edge_array<int> lowy(G);
    edge_array<int> topy(G);
    edge_array<int> xpos(G);
  
    int max_c = VISIBILITY_REPRESENTATION(G,leftx,rightx,ypos,xpos,lowy,topy);

    G.del_edges(bi_edges);


    GW.update_graph();

    double xmin = GW.get_xmin();
    double xmax = GW.get_xmax();

    double ymin = GW.get_ymin();
    double ymax = GW.get_ymax();

    double fx = (xmax - xmin)/(1.2 * max_c);
    double fy = (ymax - ymin)/(1.2 * max_c);

    xmin += (xmax - xmin) * 0.1;
    ymin += (ymax - ymin) * 0.1;


    node v;
    forall_nodes(v,G)
    { double r = double(rightx[v] - leftx[v])/2;
      double x = double(rightx[v] + leftx[v])/2;
      GW.set_shape(v,rectangle_node);
      GW.set_radius1(v,fx*(r+0.4));
      GW.set_position(v,point(xmin+fx*x,ymin+fy*ypos[v]));
    }
  
    edge e;
    forall_edges(e,G)
    { point pv = GW.get_position(source(e));
      point pw = GW.get_position(target(e));
      double x = xmin + fx*xpos[e];
      double y = (pv.ycoord() + pw.ycoord())/2;
      GW.set_bends(e,point(x,y));
     }

    GW.set_ortho_mode(true);
    GW.set_directed(true);
    GW.redraw();
  }
  
  return 0;
}
