/*******************************************************************************
+
+  LEDA 3.5
+
+  sugiyama.h
+
+  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.
+ 
*******************************************************************************/
#include <LEDA/array.h>
#include <LEDA/stream.h>
#include <LEDA/graph.h>

//------------------------------------------------------------------------
// SUGIYAMA EMBEDDING
//
// D. Ambras (1997)
//
//------------------------------------------------------------------------

/*{\Manpage {sugiyama} {I,E} {Sugiyama Embedding}}*/


bool make_hierarchy(graph &G, node_array<int> &the_level,
                                       array<list<node> > &Level, 
                                       list<node> &dummy_nodes, bool first);
/*{\Mfuncl
This procedure gets the raw input graph $G$ and information about to which 
level a node belongs to $the_level$ and makes a proper hierarchy as mentioned 
in [1]. That means, it turns wrong directed edges, splits long edges and 
deletes edges who are parallel. The data structures $Level$ and $G$ contains 
this hierarchy after termination. In the unlucky event that horizontal edges 
exists they will be deleted and the procedure terminates with $true$ to 
indicate it.
\precond The arguments $G$ and $the_level$ contains appropriate data, array 
Level is suitable for all levels of $G$.  }*/


extern int SUGIYAMA_EMBED(graph &G, node_array<int>& xcoord,
                                    node_array<int>& level,
                                    list<node>& dummy_nodes);
/*{\Mfuncl
This function computes an initial Sugiyama embedding of the graph $G$.
\precond $G$ and $the_level$ contains appropriate data. The arguments
$dummy_nodes$ and $xcoord$ must contain relyable data too, maybe from a
former call and additional changes. Entries of $xcoord$ are delimited to
the range (0 \dots G.number\_of\_nodes()). }*/


int SUGIYAMA_iterate(graph &G, node_array<int> &x_coord, node_array<int> &the_level, list<node> &dummy_nodes);
/*{\Mfuncl
This function can be used to iterate the Sugiyama embedding.
\precond See $SUGIYAMA\_EMBED$.  }*/


int SUGIYAMA_simple(const graph &G, const node_array<int>& level);
/*{\Mfuncl
computes for the graph $G$ and the node levels determined in $level$ the number of crossings. The node\_array must be valid for all nodes of G and have to contain the number of the level starting from zero a node belongs to. The output is a file named sugi\_out.ps containing the embeded graph as a postscript image. This procedure returns -1 if horizontal edges occured in the original graph, the number of crossings otherwise. }*/



