/*******************************************************************************
+
+  LEDA 3.5
+
+  graph_draw.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.
+ 
*******************************************************************************/
#ifndef LEDA_GRAPH_DRAW_H
#define LEDA_GRAPH_DRAW_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350052
#include <LEDA/REDEFINE_NAMES.h>
#endif

#include <LEDA/graph.h>


/*{\Manpage {graph_draw} {} {Graph Drawing Algorithms}}*/

/*{\Mtext
\bigskip
This section gives a summary of the graph drawing algorithms contained in 
LEDA. Before using them the header file {\tt <}LEDA/graph\_draw.h{\tt >} 
has to be included.
\bigskip
}*/


int STRAIGHT_LINE_EMBEDDING(graph& G, node_array<int>& xcoord, 
                                      node_array<int>& ycoord);

/*{\Mfuncl
STRAIGHT\_LINE\_EMBEDDING takes as argument a directed graph $G$ representing
a planar map. It computes a straight line embedding of $G$ by assigning 
non-negative integer coordinates ($xcoord$ and $ycoord$) in the range 
$0..2(n-1)$ to the nodes. STRAIGHT\_LINE\_EMBEDDING returns the maximal 
coordinate.
The algorithm (\cite{Fa48}) has running time $O(\Labs{V}^2)$.
\bigskip
}*/

void STRAIGHT_LINE_EMBEDDING(graph& G,node_array<double>& xcoord,
                                      node_array<double>& ycoord);


int STRAIGHT_LINE_EMBEDDING2(graph& G, node_array<int>& xcoord,
                                       node_array<int>& ycoord);

void STRAIGHT_LINE_EMBEDDING2(graph& G,node_array<double>& xcoord,
                                       node_array<double>& ycoord);



bool TUTTE_EMBEDDING(const graph& G, const list<node>& fixed_nodes,
                                         node_array<double>& xpos, 
                                         node_array<double>& ypos);
/*{\Mfuncl
   computes a convex drawing of the graph $G$ if possible. The list
   |fixed_nodes| contains nodes with prescribed coordinates already
   given in |xpos| and |ypos|. The computed node positions of the other 
   nodes are stored in |xpos| and |ypos|, too. If the operation is 
   successful, true is returned. }*/
 

                                                           
void SPRING_EMBEDDING(const graph& G, node_array<double>& xpos,
                                                node_array<double>& ypos,
                                                double xleft,   double xright,
                                                double ybottom, double ytop,
                                                int iterations=250);
/*{\Mfuncl ...}*/

void SPRING_EMBEDDING(const graph& G, const list<node>& fixed,
                                                node_array<double>& xpos,
                                                node_array<double>& ypos,
                                                double xleft,   double xright,
                                                double ybottom, double ytop,
                                                int iterations=250);
/*{\Mfuncl ...}*/



int ORTHO_EMBEDDING(const graph&,node_array<int>&,
                                           node_array<int>&,
                                           edge_array<list<int> >&,
                                           edge_array<list<int> >&,
                                           bool= false);
/*{\Mfuncl orthoganal embedding with bend minimization implementation by 
           G. Klau (MPI Saarbr\"ucken), the final version will be part of the
           AGD Graph Drawing Library.}*/


int TAMASSIA_EMBEDDING(const graph&, node_array<double>&, 
                                               node_array<double>&,
                                               edge_array<list<double> >&,  
                                               edge_array<list<double> >&,  
                                               bool = false);
/*{\Mfuncl  ... }*/




int SUGIYAMA_EMBEDDING(graph &G, node_array<int>& xcoord, 
                                           node_array<int>& level,
                                           edge_array<list<int> >& xpoly);
/*{\Mfuncl ... }*/


#endif

