/*******************************************************************************
+
+  LEDA 3.5
+
+  _sugiyama.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
//------------------------------------------------------------------------
// SUGIYAMA EMBEDDING
//
// D. Ambras (1996/97)
//------------------------------------------------------------------------


#include <stdio.h>
#include <LEDA/array.h>
#include <LEDA/p_queue.h>
#include <LEDA/stream.h>
#include <LEDA/graph.h>
#include <LEDA/graph_alg.h>

#ifdef _DRAW_SUGI
 #include <LEDA/panel.h>
#endif


typedef int  bitarray;

#define SORT_LOWER 1
#define SORT_UPPER 2
#define SORT_BOTH  3
#define PERMUTE    4
#define IMPROVE    8

#define HIGH    1
#define LOW     0
#define UP      1
#define DOWN    0

#ifdef _DRAW_SUGI
window  W;
#endif
double  aspect_ratio=3;
int     ps_count=1;
int     perm_max=10, sort_max=6;
int     max_level;
bool    do_debug=true;





void write_to_ps(const graph &G, array<list<node> > &Level, node_array<int>
                  &x_coord, node_array<int> &nlabel, int width, int height,
                  char *headline, file_ostream &out)
{
 int    x_off, y_off, x_gap, y_gap, radius, i;
  x_off  = y_off= x_gap= 20;
  y_gap  = int(x_gap * aspect_ratio + 0.5);
  radius = 3;

 node   v, s, t;
 edge   e;

 out << "%!PS\n";
 out << "%%Creator: SUGIYAMA_EMBEDDING v1.0\n";
 out << "%%Pages: 1\n";
 out << "%%PageOrder: Ascend\n";
 out << "%%BoundingBox: " << 0 << " " << 0 << " ";
 out << x_gap*width + 2*x_off << " " << y_gap*height + 2*y_off << "\n";
 out << "%%EndComments\n\n%%Page: 1 1\n\n";

 out << "% " << headline << endl << endl;




 out << "% drawing the nodes\n\n";
 i=-1;
 while ((++i) <= max_level)
  forall(v, Level[i]) if (nlabel[v] != 0)
  { out << "newpath ";
    out << x_gap *x_coord[v] +x_off << " " << y_gap *i +y_off;
    out << " " << radius << " 0 360 arc fill\n";
  }

 out << "\n% drawing the edges\n\nnewpath\n";
 i=0;
 while ((++i) <= max_level)                             // drawing the edges
  forall(v, Level[i-1])  forall_out_edges(e, v)
  { s= G.source(e);  t= G.target(e);
    out << x_gap *x_coord[s] +x_off << " " << y_gap*(i-1) +y_off
        << " moveto  ";
    out << x_gap *x_coord[t] +x_off << " " << y_gap*i +y_off
        << " lineto\n";
  }

 out << "stroke\nshowpage\n\n%%EOF" << endl << flush;
}






#ifdef _DRAW_SUGI

void user_exit(void)
{
 cout << "Aborted." << endl << flush;
 exit(1);
}





bool draw_hierarchy(const graph &G, array<list<node> > &Level,
                     node_array<int> &x_coord, node_array<int> &nlabel,
                     char *headline, const bool &draw_virtual_nodes)
{
 int    i, x_min=100, x_max=-100, xv, b=NO_BUTTON;
 int    width=0, height;
 double W_size;
 color  bkg_color=white, node_color, edge_color=blue;
 color  rnode_color=green, vnode_color=white;
 node   v, w;
 edge   e;
 char   filename[200];

 forall_nodes(v, G)
 { i=x_coord[v];
   if (x_min > i) x_min= i;
   if (x_max < i) x_max= i;
 }

 width= x_max -x_min +1;
 height=max_level + 1;

 W_size=(width > height*aspect_ratio ? width: height*aspect_ratio);
 W.init(-1, W_size, -1);
 W.clear(bkg_color);  W.set_frame_label(headline);




#ifdef _DEBUG_SUGI
  if (do_debug)
  { W.message("writing graph to disk ...");
    sprintf(filename, "figure%d.ps", ps_count);
    file_ostream  ps_out(filename);
    write_to_ps(G, Level, x_coord, nlabel, width,
                 height, filename, ps_out);
    ps_count++;
  }
#elif _DEBUG2_SUGI
  if (do_debug)
  { W.message("writing graph to disk ...");
    sprintf(filename, "figure%d.ps", ps_count);
    file_ostream  ps_out(filename);
    write_to_ps(G, Level, x_coord, nlabel, width,
                 height, filename, ps_out);
    ps_count++;
  }
#endif




 i=0;  forall(v, Level[i])
 W.draw_int_node(x_coord[v]-x_min, i*aspect_ratio, nlabel[v], rnode_color);

 do
 { if (i == max_level)                          // no more levels
   { W.message(
     "press left mouse button to proceed, other button to abort");
     while (b == NO_BUTTON) b= W.get_button();
     W.del_messages();
     if (b==MOUSE_BUTTON(1))
     { W.message("continue calculations, please wait ...");
       return true;
     }
     return false;
   }

   forall(v, Level[i])                                  // drawing the edges
   { xv=x_coord[v]-x_min;
     forall_out_edges(e, v)
      if (draw_virtual_nodes || (nlabel[v] > 0 && nlabel[G.target(e)] > 0) )
       W.draw_edge(xv, i*aspect_ratio, x_coord[G.target(e)]-x_min,
                    (i+1)*aspect_ratio, edge_color);
      else
       W.draw_segment(xv, i*aspect_ratio, x_coord[G.target(e)]-x_min,
                       (i+1)*aspect_ratio, edge_color);
   }

   forall(v, Level[i+1])                                // drawing the nodes
   { if (nlabel[v]==0) node_color=vnode_color;
      else node_color=rnode_color;
     if (draw_virtual_nodes || nlabel[v] > 0)
      W.draw_int_node(x_coord[v]-x_min, (i+1)*aspect_ratio,
                       nlabel[v], node_color);
   }
   i++;
 } while (0<1);
}






#endif


bool slide_node(const graph &G, const node &v, const int &priority,
         const int &best_pos, node_array<int> &x_coord, node_array<int> &x_prio,
         array<bool> &x_set, array<node> &x_owner)
{
 int    cur_pos=x_coord[v], N=G.number_of_nodes();




 while (cur_pos < best_pos)
 { if (cur_pos > N-1) return false;

   if (x_set[cur_pos+1])
   { if (x_prio[ x_owner[cur_pos+1]] > priority)
       return false;

     if ( !slide_node(G, x_owner[cur_pos+1],
                        priority, cur_pos+2,
                        x_coord, x_prio,
                        x_set, x_owner))  return false;
                                        // owner was move-able, but others not
   }

   x_set[cur_pos++]=false;
   x_set[cur_pos]=true;                 // move node one step
   x_owner[cur_pos]=v;
   x_coord[v]=cur_pos;
 }




 while (cur_pos > best_pos)
 { if (cur_pos < -N+1) return false;

   if (x_set[cur_pos-1])
   { if (x_prio[ x_owner[cur_pos-1]] >= priority)
       return false;

     if ( !slide_node(G, x_owner[cur_pos-1],
                        priority, cur_pos-2,
                        x_coord, x_prio,
                        x_set, x_owner))  return false;
   }
   x_set[cur_pos--]=false;
   x_set[cur_pos]=true;
   x_owner[cur_pos]=v;
   x_coord[v]=cur_pos;
 }



 return true;                           // successful move
}




bool two_level(const graph &G, array<list<node> > &Level, const int &upper, 
             node_array<int> &x_coord, node_array<int> &x_prio,
             const bitarray &what_to_do)
{
 bool           changes=false;
 int            lower=upper+1, N=G.number_of_nodes();
 int            x, count, pcount, hprio_count;
 node           nu, nl;
 node           u, v;
 edge           e;
 double         bary, old_bary, hprio_bary;

 list<node>             equal_bary;
 p_queue<double, node>  Su, Sl;
 pq_item                pit;

 array<bool>            x_set(-N, N);
 array<node>            x_owner(-N, N);
 node_array<int>        p_bary(G);




 if (what_to_do & SORT_UPPER)
 { forall(nu, Level[upper])
   { bary=0;
     hprio_count=0;
     hprio_bary=0;

     forall_out_edges(e, nu)
     { x=x_coord[ G.target(e) ];  bary+=x;
       if (x_prio[ G.target(e) ] == N)          // a long edge
       { hprio_count++;
         hprio_bary+=x;
       }
     }

     if (count=G.outdeg(nu))  bary =bary/count;
       else bary=x_coord[nu];                   // no in- edges

     if (what_to_do & IMPROVE)
     { Su.insert(-x_prio[nu], nu);              // sort by priority
       p_bary[nu]=(int)(bary+0.5);
       if (hprio_count)
         p_bary[nu]=(int)(hprio_bary/ hprio_count +0.5);
                                                // we ignore short edges
     }
     else  Su.insert(bary, nu);
   }

   if (what_to_do & IMPROVE)
   { for(x=-N; x<= N; x++)  x_set[x]=false;
     forall(v, Level[upper])
     { x_owner[ x_coord[v]]=v;
       x_set[   x_coord[v]]=true;
     }
   }



   count=0;  old_bary=-1;  pcount=-2;

   while(Su.size())
   { pit=Su.find_min();
     v=Su.inf(pit);
     bary=Su.prio(pit);
     Su.del_item(pit);

     if (what_to_do & IMPROVE)                  // set real x_coordinates
       slide_node(G, v,
                   x_prio[v], p_bary[v],
                   x_coord, x_prio,
                   x_set, x_owner);

     else if (x_coord[v] != count)              // set consecutive x_coordinates
     { changes=true;
       x_coord[v] = count;
     }

     if (what_to_do & PERMUTE)                  // we shall permute
      if (bary==old_bary)
      { equal_bary.append(u);
        pcount=count;
      }
      else
      { if (pcount == count-1) equal_bary.append(u);
        while (!equal_bary.empty())
        { changes=true;
          x_coord[equal_bary.pop()]= pcount--;
        }
      }
     count++;
     old_bary=bary;
     u=v;
   }
   if (pcount == count-1) equal_bary.append(u);

   while (!equal_bary.empty())                  // flush equal_bary
   { changes=true;
     x_coord[equal_bary.pop()]= pcount--;
   }
 }



 if (what_to_do & SORT_LOWER)
 { forall(nl, Level[lower])
   { bary=0;
     hprio_count=0;
     hprio_bary=0;

     forall_in_edges(e, nl)
     { x=x_coord[ G.source(e) ];  bary+=x;
       if (x_prio[ G.source(e) ] == N)          // a long edge
       { hprio_count++;
         hprio_bary+=x;
       }
     }
     if (count=G.indeg(nl))  bary =bary/count;
      else bary=x_coord[nl];

     if (what_to_do & IMPROVE)                  // set real x_coordinates
     { Sl.insert(-x_prio[nl], nl);
       p_bary[nl]=(int)(bary +0.5);
       if (hprio_count)
         p_bary[nl]=(int)(hprio_bary/ hprio_count +0.5);
                                                // ignore short edges
     }
     else  Sl.insert(bary, nl);
   }

   if (what_to_do & IMPROVE)
   { for(x=-N; x<= N; x++)  x_set[x]=false;
     forall(v, Level[lower])
     { x_owner[ x_coord[v]]= v;
       x_set[   x_coord[v]]= true;
     }
   }



   count=0;  old_bary=-1;  pcount=-2;

   while(Sl.size())
   { pit=Sl.find_min();
     v=Sl.inf(pit);
     bary=Sl.prio(pit);
     Sl.del_item(pit);

     if (what_to_do & IMPROVE)
       slide_node(G, v,
                   x_prio[v], p_bary[v],
                   x_coord, x_prio,
                   x_set, x_owner);

     else if (x_coord[v] != count)
     { changes=true;
       x_coord[v] = count;
     }
     if (what_to_do & PERMUTE)
      if (bary==old_bary)
      { equal_bary.append(u);
        pcount=count;
      }
      else
      { if (pcount == count-1) equal_bary.append(u);
        while (!equal_bary.empty())
        { changes=true;
          x_coord[equal_bary.pop()]=pcount--;
        }
      }
     count++;
     old_bary=bary;
     u=v;
   }
   if (pcount == count-1) equal_bary.append(u);

   while (!equal_bary.empty())                  // flush equal_bary
   { changes=true;
     x_coord[equal_bary.pop()]=pcount--;
   }
 }



#ifdef _DEBUG2_SUGI
 char    headline[200], dir[10], text_p[10], text_i[10];

 if (( upper > 10) && do_debug)
 { if (what_to_do & SORT_LOWER) sprintf(dir, "[down]");
     else sprintf(dir, "[up]");
// ( supposed SORT_BOTH is not selected )

   if (what_to_do & PERMUTE) sprintf(text_p, " + permute");
     else sprintf(text_p, " ");

   if (what_to_do & IMPROVE) sprintf(text_i, " + improve");
     else sprintf(text_i, " ");

   sprintf(headline, "after two_level for u-level %d, sort %swards%s%s",
         upper, dir, text_p, text_i);

   if (!draw_hierarchy(G, Level, x_coord, x_coord, headline, true)) user_exit();
 }
#endif


 return changes;
}



list<edge> sort_edges(const graph &G, array<list<node> > &Level,
                        const int &column, const int &height,
                        node_array<int> &x_coord, list<edge> &edges)
{
 int         i=0;
 node        v;
 edge        e;
 list<edge>  result;

 array< list<edge> >    nlist( Level[column].size() );

 forall(e, edges)
 { if (height == LOW)  v=G.target(e);
    else v=G.source(e);
   nlist[ x_coord[v] ].append(e);
 }

 while (i < Level[column].size() )
  result.conc(nlist[i++]);

 return result;
}



static bool cross(const graph &G, node_array<int> &x_coord,
                   edge_array<int> &current_pos, const edge &e, const edge &f)
{
 int   xu1, xu2, xl1, xl2;

 xu1=current_pos[e];
 xu2=current_pos[f];
 xl1=x_coord[ G.target(e) ];
 xl2=x_coord[ G.target(f) ];

 return ( xu1 < xu2 && xl1 > xl2) || ( xu1 > xu2 && xl1 < xl2 );

}




int number_of_crossings(const graph &G, array<list<node> > &Level,
                         const int &upper, node_array<int> &x_coord)
{
 int            lower=upper+1, result=0, i;
 node           vu;
 edge           e, f, g, h;
 list<edge>     edges, work_list;
 list_item      lit;

 forall(vu, Level[upper])
  forall_adj_edges(e, vu) edges.append(e);

 edges= sort_edges(G, Level, lower, LOW , x_coord, edges);
 edges= sort_edges(G, Level, upper, HIGH, x_coord, edges);




 array<edge>             current_order(edges.size() );
 edge_array<int>         current_pos(G);
 edge_array<list_item>   worklist_it(G, nil);

 i=0;
 forall(e, edges)
 { current_order[i]=e;
   current_pos[e]=i++;
 }

 for (i=0; i < edges.size()-1; i++)
 { e=current_order[i];
   f=current_order[i+1];
   if ( cross(G, x_coord, current_pos, e, f) )
     worklist_it[e] = work_list.append(e);
 }




 while (!work_list.empty() )
 { e=work_list.pop();
   worklist_it[e]= nil;
   i=current_pos[e];
   result++;

   if (i < edges.size()-1)
   { f=current_order[i+1];
     current_order[i]=f;
     current_order[i+1]=e;
     current_pos[e]++;
     current_pos[f]--;

     if (lit=worklist_it[f])
     { work_list.del_item(lit);
       worklist_it[f]= nil;
     }

// Test, whether e or f cross their new neighbor:

     if (i>0)
     { g=current_order[i-1];
       if (cross(G, x_coord, current_pos, g, f) )
       { if (!worklist_it[g])
           worklist_it[g]= work_list.append(g);
       }
       else
       if (lit=worklist_it[g])
       { work_list.del_item(lit);
         worklist_it[g]= nil;
       }
     }

     if (i < edges.size()-2)
     { h=current_order[i+2];
       if (cross(G, x_coord, current_pos, e, h) )
         worklist_it[e]=work_list.append(e);
     }
   }
 }


 return result;
}



void init_positions(graph &G, array<list<node> > &Level,
                    node_array<int> &x_coord, node_array<int> &nlabel,
                    node_array<int> &x_prio, bool first)
{
 node   v;
 int    i=-1, label=1, x, N=G.number_of_nodes();

 while ( (++i) <= max_level)
 { x=0;
   forall(v, Level[i])
   { if (first)  x_coord[v]=x++;
     if (x_prio[v] == -1)
     { x_prio[v]= N;                    // dummy node = highest priority
       nlabel[v]= 0;
     }
     else
     { x_prio[v]= G.degree(v);
       nlabel[v]= label++;
     }
   }
 }
}




bool make_hierarchy(graph &G, node_array<int> &the_level, array<list<node> >
                     &Level, list<node> &dummy_nodes, bool first)
{
 int    i=0;
 node   v;

 forall_nodes(v, G)
   Level[ the_level[v] ].append(v);

 if (!first) return false;




 bool   lost_edge=false;
 int    j;
 node   w, a, b;
 edge   e;
 list<edge> remove, split, turn;

 Make_Simple(G);

 forall_nodes(v, G)
 { i=the_level[v];
   forall_out_edges(e, v)
   { j=the_level[ G.target(e) ];
     if (i>j)   turn.append(e);
     if (i==j)  remove.append(e);
     if (i+1<j) split.append(e);
   }
 }

 forall(e, turn)
 { 
   a=G.source(e);   b=G.target(e);

   e=G.rev_edge(e);

   if (the_level[b]+1 < the_level[a]) split.append(e);
 }

 if (!remove.empty()) 
 { error_handler(1,"input is not a hierarchical graph."); 
   lost_edge=true;
   forall(e, remove)  G.del_edge(e);
  }




 dummy_nodes.clear();

 forall(e,split)
 {
   a = G.source(e);   
   b = G.target(e);

   i = the_level[a] + 1;  
   j = the_level[b];

   w = G.new_node();
   Level[i].append(w);
   dummy_nodes.append(w);
   G.move_edge(e,a,w);
   a = w;
   i++;

   while (i<j)
   { w=G.new_node();
     Level[i].append(w);
     dummy_nodes.append(w);
     G.new_edge(a,w);
     a = w;
     i++;
    }

   G.new_edge(a,b);
 }


 if (split.empty() )  return lost_edge;

 the_level.init(G);                     // there are more nodes now
 i=-1;
 while( (++i) <= max_level)
   forall(v, Level[i]) the_level[v]=i;

 return lost_edge;
}







inline int all_crossings(const graph &G, array<list<node> > &Level,
                   node_array<int> &x_coord, array<int> &L_crosses)
{
 int    i=0, crosses=0, c;

 while(i < max_level)
 { c= L_crosses[i]= number_of_crossings(G, Level, i++, x_coord);
   crosses+=c;
 }

 return crosses;
}



inline void copy_all_xcoord(const graph &G, array<list<node> >& /* Level */,
                            node_array<int> &x_coord, node_array<int> &x_new,
                            array<int> &L_crosses, array<int> &L_crosses_new)
{
 int  i=0;
 node v;

  while(i < max_level)
  { L_crosses_new[i]= L_crosses[i];
    i++;
  }
  forall_nodes(v, G)  x_new[v]=x_coord[v];
}




bool update_best(const graph &G, array<list<node> > &Level,
                    node_array<int> &x_coord, node_array<int> &x_new,
                    array<int> &L_crosses, const int &i,
                    int &crosses, const bitarray &what_to_do)

{ bool update, process_next;
  int  rcn1, rcn2=0, next_level, cr_sum, work_level;
  // int make_worse= 1.2;
  node v;

  two_level(G, Level, i, x_coord, x_coord, what_to_do);
                                // makes the requested change

  if (what_to_do & SORT_LOWER)
  { next_level=i+1;
    work_level=i+1;
  }
  else
  { next_level=i-1;
    work_level=i;
  }

  process_next=((what_to_do & SORT_LOWER) && (next_level < max_level));
  if ((what_to_do & SORT_UPPER) && (next_level > -1))  process_next=true;
                                // what level is neighbor to the changed if any

  rcn1= number_of_crossings(G, Level, i, x_coord);
  if (process_next)
   rcn2= number_of_crossings(G, Level, next_level, x_coord);

  cr_sum= L_crosses[i];
  if (process_next) cr_sum+= L_crosses[next_level];

  update= ((rcn1+rcn2) <= cr_sum);
//  update= ((rcn1+rcn2) <= cr_sum* make_worse);




  if (update)
  { crosses= crosses- L_crosses[i]+ rcn1;
    L_crosses[i]= rcn1;
    forall(v, Level[work_level])  x_new[v]=x_coord[v];

    if (process_next)
    {  crosses= crosses- L_crosses[next_level]+ rcn2;
       L_crosses[next_level]= rcn2;
    }
  }
  else
   forall(v, Level[work_level])  x_coord[v]=x_new[v];

 return update;
}







bool down_up_sort(graph &G, array<list<node> > &Level, node_array<int>& x_coord,
                  array<int> &L_crosses, int &crosses, 
                  node_array<int>& /* nlabel */,
                  int how_often, int first, int begin)
{
 int     i=0, j=0;
 int     best_crosses, orig_crosses;
 char    headline[200];
 bool    ch, u_changes=false, l_changes=false;
 bool    result=false;

 node_array<int>   x_new(G);
 node_array<int>   x_old(G);
 array<int>  L_crosses_new(max_level);
 array<int>  L_crosses_old(max_level);
 copy_all_xcoord(G, Level, x_coord, x_old, L_crosses, L_crosses_old);

 array<bool> Lu_changes(max_level);
 array<bool> Ll_changes(max_level);
 for(i=0; i < max_level; i++)
   Lu_changes[i]=Ll_changes[i]=false;

 best_crosses= orig_crosses= crosses;




 j=how_often;
 while (j--)
 { if (best_crosses==0) break;
   if (first==DOWN)
   { for (i=begin; i< max_level; i++)
     { ch=two_level(G, Level, i, x_coord, x_coord, SORT_LOWER);
       if (ch && !Ll_changes[i]) l_changes=true;
       Ll_changes[i]=ch;
       if (ch)
       { crosses-= L_crosses[i];
         L_crosses[i]= number_of_crossings(G, Level, i, x_coord);
         crosses+= L_crosses[i];
         if (i< max_level-1)
         { crosses-= L_crosses[i+1];
           L_crosses[i+1]= number_of_crossings(G, Level, i+1, x_coord);
           crosses+= L_crosses[i+1];
         }
         if (crosses < best_crosses)
         { copy_all_xcoord(G, Level, x_coord, x_new,
              L_crosses, L_crosses_new);
           best_crosses=crosses;                // new high score
         }
       }
     }
     begin=max_level-1;                         // set 'begin' for up-sort new
   }
   if (best_crosses==0) break;




   for (i=begin; i>=0; i--)
   { ch=two_level(G, Level, i, x_coord, x_coord, SORT_UPPER);
     if (ch && !Lu_changes[i]) u_changes=true;
     Lu_changes[i]=ch;
     if (ch)
     { crosses-= L_crosses[i];
       L_crosses[i]= number_of_crossings(G, Level, i, x_coord);
       crosses+= L_crosses[i];
       if (i>0) 
       { crosses-= L_crosses[i-1];
         L_crosses[i-1]= number_of_crossings(G, Level, i-1, x_coord);
         crosses+= L_crosses[i-1];
       }
       if (crosses < best_crosses)
       { copy_all_xcoord(G, Level, x_coord, x_new, L_crosses, L_crosses_new);
         best_crosses=crosses;
       }
     }
   }

   first=DOWN;
   begin=0;

   if ( !(u_changes || l_changes) )  break;  else result=true;

   u_changes= l_changes= false;
 }




 if (best_crosses < orig_crosses)
 { copy_all_xcoord(G, Level, x_new, x_coord, L_crosses_new, L_crosses);
   crosses=best_crosses;
 }
 if (crosses > orig_crosses)
 { copy_all_xcoord(G, Level, x_old, x_coord, L_crosses_old, L_crosses);
   crosses=orig_crosses;
 }
 return result;
}







int down_up_change(graph &G, array<list<node> > &Level, node_array<int>
                      &x_coord, node_array<int> &nlabel, bool first)
{
 bool    skip_sort=true;
 int     i=0, j=0;
 int     crosses, prev_crosses, pprev_crosses, orig_crosses;
 char    headline[200];

 node_array<int>   x_new(G);
 node_array<int>   x_old(G);
 array<int>     L_crosses(max_level);
 array<int>     L_crosses_new(max_level);
 array<int>     L_crosses_old(max_level);

 prev_crosses= orig_crosses= crosses=
   all_crossings(G, Level, x_coord, L_crosses);
 pprev_crosses= prev_crosses+1;

 if (first)
 { down_up_sort(G, Level, x_coord, L_crosses,
                 crosses, nlabel, sort_max, DOWN, 0);

#ifdef _DEBUG_SUGI
   sprintf(headline, "hierarchy after normal sort: %d crossings", crosses);
   if (!draw_hierarchy(G, Level, x_coord, nlabel, headline, true)) user_exit();
#endif
 }

 if (crosses==0) return 0;

 copy_all_xcoord(G, Level, x_coord, x_old, L_crosses, L_crosses_old);
 copy_all_xcoord(G, Level, x_coord, x_new, L_crosses, L_crosses_new);




 j=perm_max;
 while (j--)
 { if (!skip_sort)
   { down_up_sort(G, Level, x_coord, L_crosses,
                        crosses, nlabel, 1, DOWN, 0);
     copy_all_xcoord(G, Level, x_coord, x_new,
                        L_crosses, L_crosses_new);      // update x_new
   }

   i=0;  skip_sort=false;
   while (i < max_level)                                // down loop
   { update_best(G, Level, x_coord, x_new,
        L_crosses, i, crosses, SORT_LOWER | PERMUTE);
     update_best(G, Level, x_coord, x_new,
        L_crosses, i, crosses, SORT_LOWER);
     if (crosses==0) return 0;
     i++;
   }

#ifdef _DEBUG_SUGI
   sprintf(headline, "hierarchy after down-permute, pass %d: %d crossings",
   perm_max-j, crosses);
   if (!draw_hierarchy(G, Level, x_coord, nlabel, headline, true)) user_exit();
#endif

   i= max_level-1;
   while (i>=0)                                         // up loop
   { update_best(G, Level, x_coord, x_new,
        L_crosses, i, crosses, SORT_UPPER | PERMUTE);
     update_best(G, Level, x_coord, x_new,
        L_crosses, i, crosses, SORT_UPPER);
     if (crosses==0) return 0;
     i--;
   }
#ifdef _DEBUG_SUGI
   sprintf(headline, "hierarchy after up-permute, pass %d: %d crossings",
   perm_max-j, crosses);
   if (!draw_hierarchy(G, Level, x_coord, nlabel, headline, true)) user_exit();
#endif

   if ((pprev_crosses== crosses) && (prev_crosses== crosses))
     break;

   pprev_crosses= prev_crosses;  prev_crosses= crosses;

 }  // outer loop




// do_debug=true;

 down_up_sort(G, Level, x_coord, L_crosses,
                        crosses, nlabel, 2, DOWN, 0);
 if (crosses > orig_crosses)
 { copy_all_xcoord(G, Level, x_old, x_coord, L_crosses_old, L_crosses);
   return orig_crosses;
 }

 return crosses;
}








int improve_coord(graph &G, node_array<int> &the_level, array<list<node> >
                    &Level, node_array<int> &x_coord, node_array<int> &x_prio,
                    node_array<int>& /*nlabel */)
{
 int    i, x_min=100, x_max=-100, width=0, wl=0;
 int    xv, xw, cpos, lpos, rpos, y_prev;
 node   v, w;
 edge   e;
 list_item              lit;
 node_array<list_item>  LIT(G);

 G.sort_nodes(x_coord);
 i=0;
 while (i <= max_level)  Level[i++].clear();
 forall_nodes(v, G)  LIT[v]=Level[ the_level[v] ].append(v);

 i=0;
 while (i < max_level)
  two_level(G, Level, i++, x_coord, x_prio, SORT_LOWER | IMPROVE);

#ifdef _DEBUG_SUGI
 if (!draw_hierarchy(G, Level, x_coord, nlabel, "1st down improving", true))
     user_exit();
#endif


 while (i > 0)
  two_level(G, Level, --i, x_coord, x_prio, SORT_UPPER | IMPROVE);

#ifdef _DEBUG_SUGI
 if (!draw_hierarchy(G, Level, x_coord, nlabel, "1st up improving", true))
     user_exit();
#endif




 i=-1;
 while ((++i) <= max_level)
 { if (Level[i].size() > width)
   { width=Level[i].size();  wl=i; }
 }

 while (wl < max_level)
  two_level(G, Level, wl++, x_coord, x_prio, SORT_LOWER | IMPROVE);

#ifdef _DEBUG_SUGI
 if (!draw_hierarchy(G, Level, x_coord, nlabel, "2nd down improving", true))
     user_exit();
#endif




 forall_nodes(v, G)
 { cpos= lpos= rpos= 0;

   forall_out_edges(e, v)
   { w=G.target(e);
     xv=x_coord[v];  xw=x_coord[w];
     if (xv   == xw) cpos++;
     if (xv+1 == xw) rpos++;            // an edge right slanting
     if (xv-1 == xw) lpos++;
   }

   forall_in_edges(e, v)
   { w=G.source(e);
     xv=x_coord[v];  xw=x_coord[w];
     if (xv   == xw) cpos++;
     if (xv+1 == xw) rpos++;
     if (xv-1 == xw) lpos++;
   }

   if ((cpos>=rpos) && (cpos>=lpos)) continue;
   lit=LIT[v];  i=the_level[v];
   if (lpos> rpos)
   { lit=Level[i].pred(lit);
     if (lit) xw=x_coord[ Level[i].inf(lit) ];
     if (!lit || (xw != xv-1)) x_coord[v]--;
   }
   else
   { lit=Level[i].succ(lit);
     if (lit) xw=x_coord[ Level[i].inf(lit) ];
     if (!lit || (xw != xv+1)) x_coord[v]++;
   }
 }




 G.sort_nodes(x_coord);
 i=0;  y_prev=x_coord[G.first_node()];

 forall_nodes(v, G)
  if (x_coord[v] == y_prev)
  { y_prev= x_coord[v];  x_coord[v]=i; }
  else
  { y_prev= x_coord[v];  x_coord[v]=++i; }

 return i+1;
}







int SUGIYAMA_and_info(graph &G, node_array<int> &x_coord,
                         node_array<int> &the_level, list<node> &dummy_nodes,
                         bool first= true)
{

 if (G.number_of_nodes() == 0)                  // paranoia setting
   return 0;

 int   crosses;
 node  v;

  max_level= 0;
  forall_nodes(v, G)
    if (the_level[v] > max_level)  max_level= the_level[v];

 array<list<node> > Level(max_level+1);

  if (make_hierarchy(G, the_level, Level, dummy_nodes, first) )
     return -1;
  if (first)  x_coord.init(G);


 node_array<int>   nlabel(G);
 node_array<int>   x_prio(G, 0);

  forall(v, dummy_nodes)  x_prio[v]= -1;
  init_positions(G, Level, x_coord, nlabel, x_prio, first);

#ifdef _DEBUG_SUGI
 int    i;
 char   head[200];

   i=crosses=0;
   while(i < max_level)
    crosses+= number_of_crossings(G, Level, i++, x_coord);
   sprintf(head, "original hierarchy: %d crossings", crosses);
   if (!draw_hierarchy(G, Level, x_coord, nlabel, head, true)) user_exit();
#endif




 crosses= down_up_change(G, Level, x_coord, nlabel, first);

#ifdef _DEBUG_SUGI
 sprintf(head, "Sort/permute finished with %d crossings", crosses);
 if (!draw_hierarchy(G, Level, x_coord, nlabel, head, true)) user_exit();
#endif

 int width= improve_coord(G, the_level, Level, x_coord, x_prio, nlabel);

#ifdef _DEBUG_SUGI
 if (!draw_hierarchy(G, Level, x_coord, nlabel, "final embedding", true))
     user_exit();
#endif




 return crosses;
}



int SUGIYAMA_and_info(graph &G, node_array<int> &x_coord,
                         node_array<int> &the_level, list<node> &dummy_nodes,
                         bool first, char *headline, file_ostream &ps_out)
{

 if (G.number_of_nodes() == 0)                  // paranoia setting
   return 0;

 int   crosses;
 node  v;

  max_level= 0;
  forall_nodes(v, G)
    if (the_level[v] > max_level)  max_level= the_level[v];

 array<list<node> > Level(max_level+1);

  if (make_hierarchy(G, the_level, Level, dummy_nodes, first) )
     return -1;
  if (first)  x_coord.init(G);


 node_array<int>   nlabel(G);
 node_array<int>   x_prio(G, 0);

  forall(v, dummy_nodes)  x_prio[v]= -1;
  init_positions(G, Level, x_coord, nlabel, x_prio, first);

#ifdef _DEBUG_SUGI
 int    i;
 char   head[200];

   i=crosses=0;
   while(i < max_level)
    crosses+= number_of_crossings(G, Level, i++, x_coord);
   sprintf(head, "original hierarchy: %d crossings", crosses);
   if (!draw_hierarchy(G, Level, x_coord, nlabel, head, true)) user_exit();
#endif




 crosses= down_up_change(G, Level, x_coord, nlabel, first);

#ifdef _DEBUG_SUGI
 sprintf(head, "Sort/permute finished with %d crossings", crosses);
 if (!draw_hierarchy(G, Level, x_coord, nlabel, head, true)) user_exit();
#endif

 int width= improve_coord(G, the_level, Level, x_coord, x_prio, nlabel);

#ifdef _DEBUG_SUGI
 if (!draw_hierarchy(G, Level, x_coord, nlabel, "final embedding", true))
     user_exit();
#endif




  write_to_ps(G, Level, x_coord,
                 nlabel, width, max_level,
                 headline, ps_out);

 return crosses;
}


int SUGIYAMA_EMBED(graph &G, node_array<int> &x_coord,
                         node_array<int> &the_level, list<node> &dummy_nodes)
{
 return SUGIYAMA_and_info(G, x_coord, the_level, dummy_nodes, true);
}
 


int SUGIYAMA_iterate(graph &G, node_array<int> &x_coord,
                         node_array<int> &the_level, list<node> &dummy_nodes)
{
 return SUGIYAMA_and_info(G, x_coord, the_level, dummy_nodes, false);
}



int SUGIYAMA_simple(const graph &G, const node_array<int> &the_level)
{
 if (G.number_of_nodes() == 0)                  // paranoia setting
   return 0;

 char   filename[200];
 node   v;
 edge   e;
 list<node>       dummy_nodes;
 graph            CG;
 node_array<node> Cnode(G);

  forall_nodes(v, G) Cnode[v]=CG.new_node();
  forall_edges(e, G) CG.new_edge(Cnode[G.source(e)], Cnode[G.target(e)] );

 node_array<int>  x_coord(CG);
 node_array<int>  CLevel(CG);
  forall_nodes(v, G) CLevel[Cnode[v]]=the_level[v];

  sprintf(filename, "sugi_out.ps");
  file_ostream  ps_out(filename);

 return SUGIYAMA_and_info(CG, x_coord, CLevel, dummy_nodes, true,
                           filename, ps_out);
}







int SUGIYAMA_EMBEDDING(graph &G, node_array<int>& xcoord, 
                                 node_array<int>& level,
                                 edge_array<list<int> >& xpoly) 
{
 list<node> dummy_nodes;

 int crossings = SUGIYAMA_and_info(G, xcoord, level, dummy_nodes, true);

 xpoly.init(G);

 node_array<bool> dummy(G,false);
 
 node v;
 forall(v,dummy_nodes) dummy[v] = true;
 
 forall_nodes(v,G)
 { if (dummy[v]) continue;
   edge e = G.first_adj_edge(v);
   while (e)
   { edge next = G.adj_succ(e);
     edge x = e;
     node u = target(x);
     while (dummy[u])
     { xpoly[e].append(xcoord[u]);
       x = G.first_adj_edge(u);
       u = target(x);
      }
     if (u != target(e))
          G.move_edge(e,source(e),u);
     e = next;
    }
 }

 forall(v,dummy_nodes) G.del_node(v);

 return crossings;
}

