/*******************************************************************************
+
+  LEDA 3.5
+
+  graph_gen.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_GEN_H
#define LEDA_GRAPH_GEN_H

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


//-----------------------------------------------------------------------------
// graph generators
//-----------------------------------------------------------------------------

#include <LEDA/graph.h>
#include <LEDA/node_array.h>


/*{\Manpage {graph_gen} {} {Graph Generators} }*/

extern void complete_graph(graph& G, int n, bool dir);

inline void complete_graph(graph& G, int n) 
{ complete_graph(G,n,G.is_directed()); }
/*{\Mfuncl   creates a complete graph $G$ with $n$ nodes. }*/

inline void complete_ugraph(graph& G, int n) 
{ complete_graph(G,n,false); }
/*{\Mfuncl   creates a complete undirected graph $G$ with $n$ nodes. }*/


extern void random_graph(graph& G, int n, int m);
/*{\Mfuncl   creates a random graph $G$ with $n$ nodes and $m$ edges. }*/


extern void test_graph(graph& G);
/*{\Mfuncl   creates interactively a user defined graph $G$. }*/


extern void complete_bigraph(graph& G, int a, int b, list<node>& A, list<node>& B);
/*{\Mfuncl   creates a complete bipartite graph $G$ with $a$ nodes 
            on side $A$ and $b$ nodes on side $B$. All edges are 
            directed from $A$ to $B$. }*/

extern void random_bigraph(graph& G, int a, int b, int m, list<node>& A, list<node>& B);
/*{\Mfuncl   creates a random bipartite graph $G$ with $a$ nodes on 
            side $A$, $b$ nodes on side $B$, and $m$ edges. All 
            edges are directed from $A$ to $B$. }*/


extern void test_bigraph(graph& G, list<node>& A, list<node>& B);
/*{\Mfuncl   creates interactively a user defined bipartite
	    graph $G$ with sides $A$ and $B$. All edges are
	    directed from $A$ to $B$. }*/



extern void random_planar_graph(graph& G, int n);
/*{\Mfuncl   creates a random planar graph $G$ with $n$ nodes. }*/

extern void random_planar_graph(graph& G, node_array<double>& xcoord,                                                     node_array<double>& ycoord,                                                     int n);
/*{\Mfuncl   creates a random planar graph $G$ with $n$ nodes embedded into
            the unit sqare. The embedding is given by $xcoord[v]$ and
            $ycoord[v]$ for every node $v$ of $G$. }*/


extern void triangulated_planar_graph(graph& G, int n);
/*{\Mfuncl   creates a triangulated planar graph $G$ with $n$ nodes. }*/


extern void triangulated_planar_graph(graph& G, 
                                                node_array<double>& xcoord, 
                                                node_array<double>& ycoord, 
                                                int n);
/*{\Mfuncl  creates a triangulated planar graph $G$ with $n$ nodes embedded
            into the unit sqare. The embedding is given by $xcoord[v]$ and
            $ycoord[v]$ for every node $v$ of $G$. }*/

extern void triangulated_planar_graph(graph& G, 
                                                list<node>& outer_face,
                                                node_array<double>& xcoord, 
                                                node_array<double>& ycoord, 
                                                int n);
/*{\Mfuncl  as above, in addition the list of nodes of the outer face 
            convex hull) is returned in |outer_face|. }*/



extern void grid_graph(graph& G,int n);
/*{\Mfuncl   creates a grid graph $G$ of size $n\times n$ nodes. }*/


extern void grid_graph(graph& G, node_array<double>& xcoord, 
                                           node_array<double>& ycoord, int n);
/*{\Mfuncl   creates a grid graph $G$ of size $n\times n$ nodes embedded
            into the unit sqare. The embedding is given by $xcoord[v]$ and
            $ycoord[v]$ for every node $v$ of $G$. }*/



extern void cmdline_graph(graph& G, int argc, char** argv);
/*{\Mfuncl   builds graph $G$ as specified by the command line arguments:\\
prog \hbox to 1.5cm{\hfill}       $\longrightarrow$ test\_graph()\\
prog \hbox to 1.5cm{$n$\hfill}    $\longrightarrow$ complete\_graph($n$)\\
prog \hbox to 1.5cm{$n$ $m$\hfill} $\longrightarrow$ test\_graph($n,m$)\\
prog \hbox to 1.5cm{$file$\hfill} $\longrightarrow$ $G$.read\_graph($file$). 
}*/



#if LEDA_ROOT_INCL_ID == 350054
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif


#endif

