/*******************************************************************************
+
+  LEDA 3.5
+
+  graph_misc.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_MISC_H
#define LEDA_GRAPH_MISC_H

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




//-----------------------------------------------------------------------------
// miscellaneous  (should be members or constructors)
//-----------------------------------------------------------------------------

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

/*{\Manpage {graph_misc} {} {Miscellaneous Graph Functions} }*/

/*{\Moperations 2 5}*/

extern bool Is_Simple(const graph& G);
/*{\Mfunc  returns true if $G$ is simple, i.e., has no parallel
           edges, false otherwise. }*/

inline bool Is_Bidirected(const graph& G) { return G.is_bidirected(); }
/*{\Mfuncl  	returns true if every edge has a reversal and 
                false otherwise. }*/

extern bool Is_Bidirected(const graph& G, edge_array<edge>& rev);
/*{\Mfuncl  	computes for every edge $e = (v,w)$ in $G$ its
		reversal $rev[e] = (w,v)$ in $G$ (nil if
		not present). Returns true if every edge has a
		reversal and false otherwise. }*/

extern bool Is_Map(const graph& G);
/*{\Mfuncl      tests whether $G$ is a map. }*/	

extern bool Is_Planar_Map(const graph& G);
/*{\Mfuncl      tests whether $G$ is a planar map. }*/	
  
extern bool Is_Acyclic(const graph& G);
/*{\Mfunc  returns true if the directed $G$ is acyclic
           and false otherwise. }*/

extern bool Is_Acyclic(const graph& G, list<edge>& L);
/*{\Mfunc  as above; in addition, constructs a list of edges $L$ 
           whose deletion makes $G$ acyclic. }*/

extern void Make_Acyclic(const graph& G);
/*{\Mfunc  makes $G$ acyclic by removing all DFS back edges. }*/ 



extern bool Is_Connected(const graph& G);
/*{\Mfunc  returns true if the undirected graph underlying $G$ is connected
           and false otherwise. }*/


extern bool Is_Biconnected(const graph& G);
/*{\Mfunc  returns true if the undirected graph underlying $G$ is biconnected
           and false otherwise. }*/


bool Is_Bipartite(const graph& G);
/*{\Mfuncl returns true if $G$ is bipartite and false otherwise. }*/

bool Is_Bipartite(const graph& G, list<node>& A, list<node>& B);
/*{\Mfuncl returns true if $G$ is bipartite and false otherwise. 
           If $G$ is bipartite the two sides are returned in $A$ and $B$,
           respectively. }*/

bool Is_Planar(const graph& G);
/*{\Mfuncl returns true if $G$ is planar and false otherwise. }*/



extern list<edge> Make_Simple(graph& G);
/*{\Mfunc  makes $G$ simple by removing all but one from each set of
           parallel edges. Returns the list of remaining edges with 
           parallel edges in the original graph. }*/



extern void Make_Bidirected(graph& G,list<edge>& L);
/*{\Mfuncl 	makes $G$ bidirected by inserting missing reversal
                edges. Appends all inserted edges to list $L$. }*/

extern list<edge> Make_Bidirected(graph& G);
/*{\Mfuncl 	makes $G$ bidirected by inserting missing reversal
                edges. Returns the list of inserted edges. }*/


extern void Make_Connected(graph& G,list<edge>& L);
/*{\Mfuncl  makes $G$ connected; appends all inserted 
            edges to list $L$. }*/

extern list<edge> Make_Connected(graph& G);
/*{\Mfuncl  makes $G$ connected; returns the list of inserted edges. }*/



extern void Make_Biconnected(graph& G,list<edge>& L);
/*{\Mfuncl  makes $G$ biconnected; appends all inserted 
            edges to list $L$. }*/

extern list<edge> Make_Biconnected(graph& G);
/*{\Mfuncl  makes $G$ biconnected; returns the list of inserted edges. }*/



extern list<node> Delete_Loops(graph& G);
/*{\Mfunc returns the list of nodes with self-loops and deletes 
           all self-loops. }*/


extern int Genus(const graph& G);
/*{\Mfunc computes the genus of $G$. \precond $G$ must be a map. }*/


// for historical reasons:

inline bool compute_correspondence(const graph& G, edge_array<edge>& rev)
{ return Is_Bidirected(G,rev); }

inline void eliminate_parallel_edges(graph& G) { Make_Simple(G); }



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

#endif

