/*******************************************************************************
+
+  LEDA 3.5
+
+  graph.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_H
#define LEDA_GRAPH_H

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


//------------------------------------------------------------------------------
// graph (base for all graph types)
//
// by S. Naeher (1995)
//------------------------------------------------------------------------------


#include <LEDA/basic.h>
#include <LEDA/list.h>
#include <LEDA/graph_objects.h>
#include <LEDA/graph_map.h>


/*{\Manpage {graph} {} {Graphs} }*/

class graph {

/*{\Mdefinition

An instance $G$ of the data type $graph$ consists of a list $V$  of nodes
and a list $E$  of edges ($node$ and $edge$ are item types). 
Distinct graphs have disjoint node and edge lists. 
The value of a variable of type node is either the node of some graph, or the
special value $nil$ (which is distinct from all nodes), or is undefined 
(before the first assignment to the variable). A corresponding statement is 
true for the variables of type edge.

A graph with empty node list is called {\em empty}.   
A pair of nodes $(v,w) \in V\times V$ is associated with every 
edge $e\in E$; $v$ is called the {\em source} of $e$ and $w$ is called the 
{\em target} of $e$, and $v$ and $w$ are called {\em endpoints} of $e$.  
The edge $e$ is said to be {\em incident} to its endpoints.

A graph is either {\em directed} or {\em undirected}. The difference between
directed and undirected graphs is the way the edges incident to a node 
are stored and how the concept {\em adjacent} is defined.

In directed graphs two lists of edges are associated with every node $v$: 
$adj\_edges(v) = \{\ e \in E\ \Lvert v = source(e)\ \}$, 
i.e., the list of edges starting in $v$, and 
$in\_edges(v) = \{\ e \in E\ \Lvert v = target(e)\ \}$, i.e., the list of
edges ending in $v$.  The list $adj\_edges(v)$ is called the adjacency list 
of node $v$ and the edges in $adj\_edges(v)$ are called the edges
{\em adjacent} to node $v$. For directed graphs we often use $out\_edges(v)$ 
as a synonym for $adj\_edges(v)$.

In undirected graphs only the list $adj\_edges(v)$ is defined
for every every node $v$. Here it contains all edges incident to $v$, i.e., 
$adj\_edges(v) = \{\ e \in E\ \Lvert v \in \{source(e),target(e)\ \}$.
An undirectect graph may not contain selfloops, i.e., it may not contain an 
edge whose source is equal to its target.

In a directed graph an edge is adjacent to its source and in an undirected 
graph it is adjacent to its source and target. In a directed graph a node $w$ 
is adjacent to a node $v$ if there is an edge $(v,w) \in E$; in an undirected 
graph $w$ is adjacent to $v$ if there is an edge $(v,w)$ or $(w,v)$ in the 
graph. 

A directed graph can be made undirected and vice versa:
$G$.make\_undirected() makes the directed graph $G$ undirected by 
appending for each node $v$ the list $in\_edges(v)$ to the list 
$adj\_edges(v)$ (removing selfloops).  Conversely, $G$.make\_directed() 
makes the undirected graph $G$ directed by splitting for
each node $v$ the list $adj\_edges(v)$ into the lists $out\_edges(v)$ and
$in\_edges(v)$. Note that these two operations are not exactly inverse to 
each other.
The data type $ugraph$ (cf. section \ref{Undirected Graphs})  can only
represent undirected graphs. 
 
{\bf Reversal Information, Maps and Faces}\\
The reversal information of an edge $e$ is accessed through |G.reversal(e)|, it has type |edge| and may or may not be defined (|=nil|). 
Assume that |G.reversal(e)| is defined and let
$e' = |G.reversal(e)|$. Then $e = (v,w)$ and $e' = (w,v)$ for some
nodes $v$ and $w$, $|G.reversal|(e')$ is defined and $e = |G.reversal|(e')$. In other words, |reversal| deserves its name.

We call a directed graph \emph{bidirected} if for every edge of $G$ the 
reversed edge also belongs to $G$ and we call a bidirected graph a \emph{map} 
if all edges have their reversal information defined. Maps are the data 
structure of choice for embedded graphs. For an edge $e$ of a map $G$ let 
|face_cycle_succ(e) = cyclic_adj_succ(reversal(e))| and consider the sequence 
$e$, |face_cycle_succ(e)|, |face_cycle_succ(face_cycle_succ(e))|, \ldots\ . The 
first edge to repeat in this sequence is $e$ (why?) and the set of edges 
appearing in this sequence is called the \emph{face cycle} containing $e$. 
Each edge is contained in some face cycle and face cycles are pairwise 
disjoint. Let $f$ be the number of face cycles, $n$ be the number of nodes, 
$m$ be the number of edges, and let $c$ be the number of connected components. 
Then $g = (m/2 - n - f)/2 + c$ is called the \emph{genus} of the map 
\cite{Whi73} (note that $m/2$ is the number of edges in the underlying 
undirected graph). The genus is zero if and only if the map is planar, i.e., 
there is an embedding of $G$ into the plane such that for every node $v$ the 
counter-clockwise ordering of the edges around $v$ agrees with the cyclic 
ordering of $v$'s adjacency list.

If a graph $G$ is a map the faces of $G$ can be constructed explicitely
by |G.compute_faces()|. Afterwards, the faces of $G$ can be traversed
by different iterators, e.g., |forall_faces(f,G)| iterates over
all faces , |forall_adj_faces(v)| iterates over all faces adjacent 
to node $v$. By using face maps or arrays (data types |face_map|
and |face_array|) additional information can be associated with
the faces of a graph. Note that any update operation performed on
$G$ invalidates the list of faces. See the section on face operations 
for a complete list of available operations for faces. 

}*/

friend class ugraph;
friend class planar_map;
friend class GraphWin;

graph_obj_list v_list;   // list of all nodes 
graph_obj_list v_free;   // list of free nodes

graph_obj_list e_list;   // list of all edges
graph_obj_list e_free;   // list of free edges
graph_obj_list h_list;   // list of hidden edges

graph_obj_list f_list;   // list of all faces
graph_obj_list f_free;   // list of free faces

list<node> v_list_tmp;  // temporary list of nodes
list<edge> e_list_tmp;  // temporary list of edges
list<face> f_list_tmp;  // temporary list of faces

int max_n_index;     // maximal node index 
int max_e_index;     // maximal edge index
int max_f_index;     // maximal face index

bool undirected;

list<graph_map*> map_list[3];  //list of registered node/edge/face maps
list<int>        free_data[3]; //list of unused node/edge/face data slots
int              data_sz[3];   //number of additional node/edge/face data slots

graph_map* adj_iterator;
graph_map* FaceOf;


int node_bytes() const 
{ return sizeof(node_struct) + data_sz[0]*sizeof(GenPtr); }

int edge_bytes() const 
{ return sizeof(edge_struct) + data_sz[1]*sizeof(GenPtr); } 

int face_bytes() const 
{ return sizeof(face_struct) + data_sz[2]*sizeof(GenPtr); }




node add_node(GenPtr);
edge add_edge(node,node,GenPtr);
face add_face(GenPtr);

void dealloc_node(node);
void dealloc_edge(edge);
void dealloc_face(face);

face new_face(GenPtr);
face new_face();

void del_face(face);

void ins_adj_edge(edge, node, edge, node, edge, int d1, int d2);  
void del_adj_edge(edge,node,node);
void copy_graph(const graph&);


// virtual functions defined in parameterized graphs (GRAPH<vtype,etype>)

virtual void init_node_entry(GenPtr&) const {}
virtual void init_edge_entry(GenPtr&) const {}
virtual void init_face_entry(GenPtr&) const {}

virtual void copy_node_entry(GenPtr&) const {}
virtual void copy_edge_entry(GenPtr&) const {}
virtual void copy_face_entry(GenPtr&) const {}

virtual void clear_node_entry(GenPtr&) const {}
virtual void clear_edge_entry(GenPtr&) const {}
virtual void clear_face_entry(GenPtr&) const {}

virtual void read_node_entry(istream&, GenPtr&) {}
virtual void read_edge_entry(istream&, GenPtr&) {}
virtual void read_face_entry(istream&, GenPtr&) {}

virtual void write_node_entry(ostream&, GenPtr&) const {}
virtual void write_edge_entry(ostream&, GenPtr&) const {}
virtual void write_face_entry(ostream&, GenPtr&) const {}

virtual void print_node_entry(ostream&, GenPtr&) const {}
virtual void print_edge_entry(ostream&, GenPtr&) const {}
virtual void print_face_entry(ostream&, GenPtr&) const {}


protected:

graph_map node_data();
graph_map edge_data();
graph_map face_data();


// virtual functions called before and after update operations
// (e.g. useful for graph editors)

// node handler                                // called
virtual void pre_new_node_handler() {}         // before inserting a node
virtual void post_new_node_handler(node) {}    // after inserting node v
virtual void pre_del_node_handler(node) {}     // before deleting node v 
virtual void post_del_node_handler() {}        // after deleting a node

 
// edge handler
virtual void pre_new_edge_handler(node, node) {}     // before creating (v,w)
virtual void post_new_edge_handler(edge) {}          // after insertion of e

virtual void pre_del_edge_handler(edge) {}           // before deleteing edge e
virtual void post_del_edge_handler(node, node) {}    // after deletion of (v,w)

virtual void pre_move_edge_handler(edge,node,node){} // before moving e to (v,w)
virtual void post_move_edge_handler(edge,node,node){}// after moved e from (v,w)

virtual void pre_hide_edge_handler(edge) {}          // before hiding edge e
virtual void post_hide_edge_handler(edge) {}         // after hiding edge e

virtual void pre_restore_edge_handler(edge) {}       // before restoring edge e
virtual void post_restore_edge_handler(edge) {}      // after restoring edge e


// global handler
virtual void pre_clear_handler()  {}                 // before deleting graph
virtual void post_clear_handler() {}                 // after deleting graph
 


graph* parent; // for subgraphs

void copy_all_entries() const;
void clear_all_entries() const;

public:

int  register_map(graph_map*);
void unregister_map(graph_map*);


virtual int cmp_node_entry(node, node) const { return 0; }
virtual int cmp_edge_entry(edge, edge) const { return 0; }


virtual char* node_type() const { return "void"; }
virtual char* edge_type() const { return "void"; }
virtual char* face_type() const { return "void"; }


string get_node_entry_string(node) const;
string get_edge_entry_string(edge) const;

void   set_node_entry(node, string);
void   set_edge_entry(edge, string);


/*{\Mcreation G }*/

graph();
/*{\Mcreate  creates an object $G$ of type $graph$ and initializes it to 
             the empty directed graph. }*/

graph(int,int);

graph(const graph&);

graph& operator=(const graph&); 

virtual ~graph();


//subgraph constructors

/*
graph(graph&, const list<node>&, const list<edge>&);
graph(graph&, const list<edge>&);
*/

   graph* super()        const;

   int max_node_index()  const;
   int max_edge_index()  const;
   int max_face_index()  const;

   int  space() const;


/*{\Moperations 1.9 4.8 }*/

/*{\Mtext       
\bigskip
{\bf a) Access operations} }*/

   int  outdeg(node v)    const;
/*{\Mop     returns the number of edges adjacent to node $v$ 
            (\Labs {adj\_edges(v)} ). }*/


   int  indeg(node v)     const;
/*{\Mop     returns the number of edges ending at $v$ (\Labs{in\_edges(v)}
            if |\Mvar| is directed and zero if |\Mvar| is undirected). }*/

   int  degree(node v)    const;
/*{\Mop     returns  $outdeg(v) + indeg(v)$. }*/


   node source(edge e)    const;
/*{\Mop     returns the source node of edge $e$.}*/

   node target(edge e)    const;
/*{\Mop     returns the target node of edge $e$.}*/

   node opposite(node v, edge e) const;
/*{\Mop     returns $target(e)$ if $v = source(e)$ and $source(e)$ 
            otherwise. }*/

   int  number_of_nodes() const;
/*{\Mop     returns the number of nodes in $G$. }*/

   int  number_of_edges() const;
/*{\Mop     returns the number of edges in $G$. }*/


const list<node>& all_nodes()  const;
/*{\Mop     returns the list $V$ of all nodes of $G$. }*/

/*{\Moptions nextwarning=no }*/
const list<edge>& all_edges()  const;
/*{\Mop     returns the list $E$ of all edges of $G$. }*/


  list<edge> adj_edges(node v) const;
/*{\Mop     returns $adj\_edges(v)$. }*/

   list<edge> out_edges(node v) const;
/*{\Mop     returns $adj\_edges(v)$ if |\Mvar| is directed and
            the empty list otherwise.}*/

   list<edge> in_edges(node v) const;
/*{\Mop     returns $in\_edges(v)$ if |\Mvar| is directed and
            the empty list otherwise.}*/


   list<node> adj_nodes(node v) const;
/*{\Mop     returns the list of all nodes adjacent to $v$. }*/

   node first_node()      const;
/*{\Mop       returns the first node in $V$. }*/

   node last_node()       const;
/*{\Mop       returns the last node in $V$. }*/

   node choose_node()     const;
/*{\Mop       returns a random node of $G$ (nil if $G$ is empty). }*/

   node succ_node(node v) const;
/*{\Mop       returns the successor of node $v$ in $V$\\
	      (nil if it does not exist). }*/

   node pred_node(node v) const;
/*{\Mop       returns the predecessor of node $v$ in $V$\\
	      (nil if it does not exist). }*/


   edge first_edge()      const;
/*{\Mop       returns the first edge in $E$. }*/

   edge last_edge()       const;
/*{\Mop       returns the last edge in $E$. }*/

   edge choose_edge()     const;
/*{\Mop       returns a random edge of $G$ (nil if $G$ is empty). }*/

   edge succ_edge(edge e) const;
/*{\Mop       returns the successor of edge $e$ in $E$\\
	      (nil if it does not exist). }*/

   edge pred_edge(edge e) const;
/*{\Mop       returns the predecessor of edge $e$ in $E$\\
	      (nil if it does not exist). }*/


   edge first_adj_edge(node v) const;
/*{\Mop       returns the first edge in the adjacency list of $v$\\
              (nil if this list is empty). }*/

   edge last_adj_edge(node v)  const;
/*{\Mop       returns the last edge in the adjacency list of $v$\\
              (nil if this list is empty). }*/

   edge adj_succ(edge e)  const;
/*{\Mop       returns the successor of edge $e$ in the adjacency list of 
              node $source(e)$ (nil if it does not exist). }*/

   edge adj_pred(edge e)  const;
/*{\Mop       returns the predecessor of edge $e$ in the adjacency list of 
              node $source(e)$ (nil if it does not exist). }*/

   edge cyclic_adj_succ(edge e) const;
/*{\Mop       returns the cyclic successor of edge $e$ in the adjacency list
              of node $source(e)$. }*/

   edge cyclic_adj_pred(edge e) const;
/*{\Mop       returns the cyclic predecessor of edge $e$ in the adjacency list
              of node $source(e)$. }*/


   edge first_in_edge(node v)  const;
/*{\Mop       returns the first edge of $in\_edges(v)$\\
              (nil if this list is empty). }*/

   edge last_in_edge(node v)   const;
/*{\Mop       returns the last edge of $in\_edges(v)$\\
              (nil if this list is empty). }*/

   edge in_succ(edge e)  const;
/*{\Mop       returns the successor of edge $e$ in $in\_edges(target(e))$
              (nil if it does not exist). }*/

   edge in_pred(edge e)  const;
/*{\Mop       returns the predecessor of edge $e$ in $in\_edges(target(e))$ 
              (nil if it does not exist). }*/

   edge cyclic_in_succ(edge e) const;
/*{\Mop       returns the cyclic successor of edge $e$ in 
              $in\_edges(target(e))$ (nil if it does not exist). }*/

   edge cyclic_in_pred(edge e) const;
/*{\Mop       returns the cyclic predecessor of edge $e$ in 
              $in\_edges(target(e))$ (nil if it does not exist). }*/


   bool is_directed() const { return !undirected; }
/*{\Mop       returns true iff $G$  is directed. }*/

   bool is_undirected() const { return undirected; }
/*{\Mop       returns true iff $G$  is undirected. }*/

   bool empty() const { return v_list.empty(); }
/*{\Mop       returns true iff $G$  is empty. }*/

protected:

   GenPtr& entry(node v) const;
   GenPtr& entry(edge e) const;
   GenPtr& entry(face f) const;


   GenPtr  inf(node v) const;
   GenPtr  inf(edge e) const;
   GenPtr  inf(face f) const;

   node new_node(GenPtr);
   edge new_edge(node, node, GenPtr);
   edge new_edge(edge, node, GenPtr, int d);
   edge new_edge(node, edge, GenPtr, int d);
   edge new_edge(edge, edge, GenPtr, int d1, int d2);

   // undirected graphs
   edge new_edge(node, edge, node, edge, GenPtr, int d1, int d2);  
   edge new_edge(node, edge, node, GenPtr, int d);  
   edge new_edge(node, node, edge, GenPtr, int d);  


   node split_edge(edge, GenPtr, edge&, edge&);

   void assign(node v,GenPtr x);
   void assign(edge e,GenPtr x);
   void assign(face f,GenPtr x);


//sort using the virtual cmp_node/edge_entry functions
void sort_nodes();
void sort_edges();


face& access_face(edge e)  const { return (face&)FaceOf->map_access(e); }


public:


/*{\Mtext       
\bigskip
{\bf b) Update operations} }*/


   node new_node();
/*{\Mop        adds a new node to $G$ and returns it. }*/



   edge new_edge(node v, node w) 
   { GenPtr x=0; init_edge_entry(x); return graph::new_edge(v,w,x);}

/*{\Mopl        adds a new edge $(v,w)$ to |\Mvar| by appending it to 
                $adj\_edges(v)$ and to $in\_edges(w)$ (if |\Mvar| is 
                directed) or $adj\_edges(w))$ (if |\Mvar| is undirected), 
                and returns it. }*/


   edge new_edge(edge e, node w, int dir=after) 
   { GenPtr x=0; init_edge_entry(x); return graph::new_edge(e,w,x,dir); }

/*{\Mopl       adds a new edge $x = (source(e),w)$ to |\Mvar|. $x$ is inserted
               before ($dir=before$) or after ($dir=after$) edge $e$ into 
               $adj\_edges(source(e))$ and appended to $in\_edges(w)$ (if
               |\Mvar| is directed) or $adj\_edges(w)$ (if |\Mvar| is undirected). 
               Here $before$ and $after$ are predefined integer constants. 
               The operation returns the new edge $x$.\\
               \precond $source(e) \ne w$ if |\Mvar| is undirected. }*/


   edge new_edge(node v, edge e, int dir=after) 
   { GenPtr x=0; init_edge_entry(x); return graph::new_edge(v,e,x,dir); }

/*{\Mopl       adds a new edge $x = (v,target(e))$ to |\Mvar|. $x$ is appended
               to $adj\_edges(v)$ and inserted before ($dir=before$) or after
               ($dir=after$) edge $e$ into $in\_edges(target(e))$ (if |\Mvar| 
               is directed) or $adj\_edges(target(e))$ (if |\Mvar| is undirected).
               Here $before$ and $after$ are predefined integer constants. 
               The operation returns the new edge $x$.\\
               \precond $target(e) \ne v$ if |\Mvar| is undirected. }*/


   edge new_edge(edge e1, edge e2, int d1=after, int d2=after) 
   { GenPtr x=0; init_edge_entry(x); return graph::new_edge(e1,e2,x,d1,d2); }

/*{\Mopl       adds a new edge $x = (source(e1),target(e2))$ to |\Mvar|. $x$ is 
               inserted before (if $d1=before$) or after (if $d1=after$) 
               edge $e1$ into $adj\_edges(source(e1))$ and before 
               (if $d2=before$) or after (if $d2=after$) edge $e2$ into 
               $in\_edges(target(e2))$ (if |\Mvar| is directed) or 
               $adj\_edges(target(e2))$, if |\Mvar| is undirected.
               The operation returns the new edge $x$.}*/


   node merge_nodes(node v1, node v2);
/*{\Mop   experimental. }*/


   node split_edge(edge e, edge& e1, edge& e2)
   { GenPtr x=0; init_node_entry(x);
     return split_edge(e,x,e1,e2); }
/*{\Mop   experimental }*/


   void hide_edge(edge e);
/*{\Mop        removes edge $e$ from $adj\_edges(source(e))$ and 
               from $in\_edges(target(e))$ (if |\Mvar| is directed) or
               from $adj\_edges(target(e)$ (if |\Mvar| is undirected), 
               but leaves it in the list of all edges $E$. }*/

   bool is_hidden(edge e) const;
/*{\Mop        returns |true| if |e| is hidden and |false| otherwise. }*/


   void restore_edge(edge e);
/*{\Mop        restores $e$ by appending it $adj\_edges(source(e))$
               and to $in\_edges(target(e))$ ($adj\_edges(taret(e))$ if
               |\Mvar| is undirected). \precond $e$ must be hidden. }*/


   void restore_all_edges();
/*{\Mop        restores all hidden edges. }*/


   void del_node(node v);
/*{\Mop       deletes $v$ and all edges incident to $v$ from $G$. }*/

   void del_edge(edge e);
/*{\Mop       deletes the edge $e$ from $G$. }*/

   void del_nodes(const list<node>& L);
/*{\Mop       deletes all nodes in |L| from $G$. }*/

   void del_edges(const list<edge>& L);
/*{\Mop       deletes all edges in |L| from $G$. }*/

   void del_all_nodes(); 
/*{\Mop       deletes all nodes from $G$.  }*/

   void del_all_edges(); 
/*{\Mop       deletes all edges from $G$.  }*/

   void del_all_faces(); 
/*{\Mop       deletes all faces from $G$.  }*/

   void move_edge(edge e, node v, node w);
/*{\Mop       moves edge $e$ to source $v$ and target $w$ by appending it to
              $adj\_edges(v)$ and to $in\_edges(w)$ (if |\Mvar| is directed)
              or $adj\_edges(w))$ (if |\Mvar| is undirected). }*/

   void move_edge(edge e, edge e1, node w, int d=after);
/*{\Mop       moves edge $e$ to source $source(e1)$ and target $w$ by 
              inserting it before (if $d=before$) or after (if $d=after$) 
              edge $e1$ into $adj\_edges(source(e1))$ and by appending
              it to $in\_edges(w)$ (if |\Mvar| is directed)
              or $adj\_edges(w))$ (if |\Mvar| is undirected). }*/

   void move_edge(edge e, edge e1, edge e2, int d1=after, int d2=after);
/*{\Mop       moves edge $e$ to source $source(e1)$ and target $target(e2)$ by 
              inserting it before (if $d1=before$) or after (if $d1=after$) 
              edge $e1$ into $adj\_edges(source(e1))$ and before 
              (if $d2=before$) or after (if $d2=after$) edge $e2$ into 
              $in\_edges(target(e2))$ (if |\Mvar| is directed) or 
              $adj\_edges(target(e2))$, if |\Mvar| is undirected. }*/


   edge rev_edge(edge e);
/*{\Mop       reverses $e$ (|move_edge(e,target(e),source(e))|). }*/

   void rev_all_edges();
/*{\Mop        reverses all edges of |\Mvar|. }*/

   graph& rev() { rev_all_edges(); return *this; }


void sort_nodes(int (*cmp)(const node&, const node&));
/*{\Mopl      the nodes of $G$ are sorted according to the
	      ordering defined by the comparing function
	      $cmp$. Subsequent executions of forall\_nodes
	      step through the nodes in this order.
	      (cf.~TOPSORT1 in section \ref{Graph and network algorithms}). }*/



void sort_edges(int (*cmp)(const edge&, const edge&));
/*{\Mopl      the edges of $G$ and all adjacency lists
              are sorted according to the
	      ordering defined by the comparing function
	      $cmp$. Subsequent executions of forall\_edges
	      step through the edges in this order.
              (cf.~TOPSORT1 in section \ref{Graph and network algorithms}). }*/


/*{\Moptions nextwarning=no }*/
void sort_nodes(const graph_map& A);
/*
void sort_nodes(const node_array<T>& A);
*/
/*{\Mopl      the nodes of $G$ are sorted according to the entries of
              node\_array $A$ (cf. section \ref{Node Arrays}).\\
	      \precond $T$ must be numerical. }*/


/*{\Moptions nextwarning=no }*/
void sort_edges(const graph_map& A);
/*
void sort_edges(const edge_array<T>& A);
*/
/*{\Mopl      the edges of $G$ are sorted according to the entries of 
              edge\_array $A$ (cf. section \ref{Edge Arrays}).\\
	      \precond $T$ must be numerical. }*/


void sort_nodes(const list<node>& vl);
/*{/Mopl the nodes of $G$ are sorted into the ordering given by $vl$. 
         \precond  $vl$ contains exactly the nodes of $G$. }*/

void sort_edges(const list<edge>& el);
/*{/Mopl the edges of $G$ are sorted into the ordering given by $el$.
         \precond  $el$ contains exactly the edges of $G$. }*/



void bucket_sort_nodes(int l, int h, int (*ord)(const node&));
/*{\Mopl      sorts the nodes of $G$ using {\em bucket sort}
              \precond  $l \le ord(v) \le h$ for all nodes $v$. }*/

void bucket_sort_edges(int l, int h, int (*ord)(const edge&));
/*{\Mopl      sorts the edges of $G$ using {\em bucket sort}
              \precond  $l \le ord(e) \le h$ for all edges $e$. }*/


void bucket_sort_nodes(int (*ord)(const node&));
/*{\Mopl      same as |\Mvar.bucket_sort_nodes(l,h,ord| with $l$ ($h$) 
              equal to the minimal (maximal) value of $ord(v)$. }*/

void bucket_sort_edges(int (*ord)(const edge&));
/*{\Mopl      same as |\Mvar.bucket_sort_edges(l,h,ord| with $l$ ($h$)
              equal to the minimal (maximal) value of $ord(e)$. }*/



/*{\Moptions nextwarning=no }*/
void bucket_sort_nodes(const graph_map& A);
/*
void bucket_sort_nodes(const node_array<int>& A);
*/
/*{\Mopl      same as |\Mvar.bucket_sort_nodes(ord)| with
              $ord(v) = A[v]$ for all nodes $v$ of |\Mvar|. }*/


/*{\Moptions nextwarning=no }*/
void bucket_sort_edges(const graph_map& A);
/*
void bucket_sort_edges(const edge_array<int>& A);
*/
/*{\Mopl      same as |\Mvar.bucket_sort_edges(ord)| with
              $ord(e) = A[e]$ for all edges $e$ of |\Mvar|. }*/





   list<edge> insert_reverse_edges();
/*{\Mop       for every edge $(v,w)$ in $G$ the reverse edge $(w,v)$ 
              is inserted into $G$. Returns the list of all inserted 
              edges. }*/


   void make_undirected();
/*{\Mop       makes $G$  undirected by appending $in\_edges(v)$ to 
              $adj\_edges(v)$ for all nodes $v$. }*/

   void make_directed();
/*{\Mop       makes  $G$  directed by splitting $adj\_edges(v)$ into
              $out\_edges(v)$ and $in\_edges(v)$. }*/


virtual void clear();
/*{\Mop       makes $G$ the empty graph. }*/

   void join(graph& H);
/*{\Mop       merges $H$ into $G$ by moving all objects (nodes,edges, and 
              faces) from $H$ to $G$. $H$ is empty afterwards. }*/


 
/*{\Mtext
\bigskip
{\bf c) Reversal Edges and Maps} 
}*/

void  make_bidirected(list<edge>& R);
/*{\Mop  makes $G$ bidirected by inserting missing reversal
         edges. Appends all inserted edges to list $R$. }*/

bool is_bidirected() const;
/*{\Mop  returns true if every edge has a reversal 
         and false otherwise. }*/

bool make_map();
/*{\Mop  turns |\Mvar| into a map by setting the reversals for all edges. 
         Returns |true| if |\Mvar| is bidirected and |false| otherwise. }*/

void make_map(list<edge>& R);
/*{\Mop  makes |\Mvar| bidirected by inserting missing reversal edges and
         then turns it into a map setting the reversals for all edges. 
         Appends all inserted edges to list $R$. }*/

bool is_map() const;
/*{\Mop  tests whether $G$ is a map. }*/	


edge reversal(edge e) const { return e->rev; }
/*{\Mop returns the reversal information of edge $e$ 
        (|nil| if not defined).}*/

void set_reversal(edge e, edge r);
/*{\Mop makes |r| the reversal of |e| and vice versa.\\
\precond $e = (v,w)$ and $|r| = (w,v)$ for some nodes $v$ and $w$.}*/


edge face_cycle_succ(edge e) const;
/*{\Mop returns the cyclic adjacency successor of |reversal(e)|.\\
        \precond |reversal(e)| is defined.}*/


edge face_cycle_pred(edge e) const;
/*{\Mop returns the reversal of the cyclic adjacency predecessor of $e$.\\
        \precond |reversal(e)| is defined.}*/
 
edge split_map_edge(edge e);
/*{\Mop     splits edge $e=(v,w)$ and its reversal $r=(w,v)$
	    into edges $(v,u)$, $(u,w)$, $(w,u)$, and $(u,v)$.
	    Returns the edge $(u,w)$. }*/

edge new_map_edge(edge e1, edge e2);
/*{\Mop     inserts a new edge $e=(source(e1),source(e2)$ after $e1$ 
            into the adjacency list of $source(e1)$ and an edge $r$
            reversal to $e$ after $e2$ into the adjacency list of 
            $source(e2)$. }*/

list<edge> triangulate_map();
/*{\Mop    triangulates the map $G$ by inserting additional edges. The list 
           of inserted edges is returned. \precond $G$ must be connected.
           The algorithm (\cite{HU89}) has running time $O(\Labs{V}+\Labs{E})$.
}*/


/*{\Mtext
{\bf For backward compatibility}
}*/

edge reverse(edge e) const { return e->rev; }
/*{\Mop returns |reversal(e)| (historical). }*/

edge succ_face_edge(edge e) const;
/*{\Mop returns |face_cycle_succ(e)| (historical). }*/

edge next_face_edge(edge e) const { return face_cycle_succ(e); }
/*{\Mop returns |face_cycle_succ(e)| (historical). }*/

edge pred_face_edge(edge e) const;
/*{\Mop returns |face_cycle_pred(e)| (historical). }*/

/*{\Mtext
\bigskip
{\bf d) Faces and Planar Maps}
}*/

void compute_faces();
/*{\Mop constructs the list of faces of |\Mvar|.\\
        \precond |\Mvar| is a map. }*/

void make_planar_map();
/*{\Mop  makes |\Mvar| a planar map by reordering the edges such that
         for every node $v$ the ordering of the edges in the adjacency list of 
         $v$ corresponds to the counter-clockwise ordering of these edges 
         around $v$ in a planar embedding of |\Mvar| and constructs the list 
         of faces.\\
         \precond |\Mvar| is a planar bidirected graph (map). }*/

face       face_of(edge e)  const { return access_face(e); }
/*{\Mop      returns the face of |\Mvar| to the left of edge $e$.}*/

face       adj_face(edge e)  const { return face_of(e); }
/*{\Mop      returns |\Mvar.face_of(e)|. }*/

void print_face(face f) const;
/*{\Mop     prints face $f$. }*/

int number_of_faces()       const { return f_list.length(); }
/*{\Mop      returns the number of faces of |\Mvar|.}*/

face first_face()      const;
/*{\Mop       returns the first face of $G$.\\
	      (nil if empty). }*/

face last_face()      const;
/*{\Mop       returns the last face of $G$. }*/

face choose_face()     const;
/*{\Mop       returns a random face of $G$ (nil if $G$ is empty). }*/


face succ_face(face f) const;
/*{\Mop       returns the successor of face $f$ in the face list of $G$\\
	      (nil if it does not exist). }*/

face pred_face(face f) const;
/*{\Mop       returns the predecessor of face $f$ in the face list of $G$\\
	      (nil if it does not exist). }*/

const list<face>& all_faces() const;
/*{\Mop      returns the list of all faces of |\Mvar|.}*/


list<face> adj_faces(node v)   const;
/*{\Mop      returns the list of all faces of |\Mvar| adjacent
	     to node $v$ in counter-clockwise order.}*/


list<node> adj_nodes(face f)   const;
/*{\Mop      returns the list of all nodes of |\Mvar| adjacent
             to face $f$ in counter-clockwise order.}*/


list<edge> adj_edges(face)   const;
/*{\Mop      returns the list of all edges of |\Mvar| bounding
	     face $f$ in counter-clockwise order.}*/

int        size(face f)  const { return f->sz; }
/*{\Mop      returns the number of edges bounding face $f$. }*/


edge first_face_edge(face f) const { return f->head; }
/*{\Mop      returns the first edge of face $f$ in |\Mvar|. }*/


edge split_face(edge e1, edge e2);
/*{\Mopl    inserts the edge $e=(source(e_1),source(e_2))$
	    and its reversal into $G$ and returns $e$.\\
            \precond $e_1$ and $e_2$ are bounding the same face $F$.
	    The operation splits $F$ into two new faces. }*/

face join_faces(edge e);
/*{\Mopl    deletes edge $e$ and its reversal and joins the two adjacent
            faces to a new face $F$ and returns it. }*/


list<edge> triangulate_planar_map()
{ list<edge> L = triangulate_map();
  compute_faces();
  return L;
 }
/*{\Mopl   triangulates planar map $G$ and 
           recomputes its list of faces }*/


// used by iterators

edge next_face_edge(edge e, face F)  const  
{ e = succ_face_edge(e);
  return (e == F->head) ? nil : e;
}




/*{\Mtext       
\bigskip
{\bf e) Operations for undirected graphs} }*/

edge new_edge(node v, edge e1, node w, edge e2, int d1=after, int d2=after)  
{ GenPtr x=0; init_edge_entry(x); return graph::new_edge(v,e1,w,e2,x,d1,d2); }

/*{\Mopl       adds a new edge $(v,w)$ to |\Mvar| by inserting it before 
               (if $d1=before$) or after (if $d1= after$) edge $e1$ into 
               $adj\_edges(v)$ and before (if $d2=before$) or after (if 
               $d2= after$) edge $e2$ into $adj\_edges(w)$, and returns it.\\ 
               \precond  $e1$ is incident to $v$ and $e2$ is incident to 
               $w$ and $v \ne w$. }*/


edge new_edge(node v, edge e, node w,int d=after)  
{ GenPtr x=0; init_edge_entry(x); return graph::new_edge(v,e,w,x,d); }

/*{\Mopl       adds a new edge $(v,w)$ to |\Mvar| by inserting it before 
               (if $d=before$) or after (if $d= after$) edge $e$ into 
               $adj\_edges(v)$ and appending it to $adj\_edges(w)$, and 
               returns it.\\ 
               \precond  $e$ is incident to $v$  and $v \ne w$. }*/

edge new_edge(node v, node w, edge e, int d=after)  
{ GenPtr x=0; init_edge_entry(x); return graph::new_edge(v,e,w,x,d); }

/*{\Mopl       adds a new edge $(v,w)$ to |\Mvar| by appending it to
               to $adj\_edges(v)$, and by inserting it before
               (if $d=before$) or after (if $d= after$) edge $e$ into 
               $adj\_edges(w)$, and returns it.\\ 
               \precond  $e$ is incident to $w$  and $v \ne w$. }*/




edge adj_succ(edge e, node v) const;
/*{\Mop        returns the successor of edge $e$ in the adjacency list of 
               $v$.\\  \precond  $e$ is incident to $v$. }*/


edge adj_pred(edge e, node v) const;
/*{\Mop        returns the predecessor of edge $e$ in the adjacency list of 
               $v$.\\ \precond  $e$ is incident to $v$. }*/


edge cyclic_adj_succ(edge e, node v)  const;
/*{\Mopl      returns the cyclic successor of edge $e$ in the adjacency
              list of $v$.\\ \precond  $e$ is incident to $v$. }*/


edge cyclic_adj_pred(edge e, node v) const;
/*{\Mopl       returns the cyclic predecessor of edge $e$ in the adjacency 
               list of $v$.\\ \precond  $e$ is incident to $v$. }*/



// Old Iterators (only for backward compatibility, should be avoided!)
void init_adj_iterator(node v)         const;
bool next_adj_edge(edge& e, node v)    const;
bool current_adj_edge(edge& e, node v) const;
bool next_adj_node(node& w, node v)    const;
bool current_adj_node(node& w, node v) const;
void reset() const;
void init_node_iterator() const {}
void init_edge_iterator() const {}



/*{\Mtext
\bigskip
{\bf f) I/O Operations} }*/

void write(ostream& O = cout) const;
/*{\Mopl      writes $G$ to the output stream $O$.}*/

void write(string s) const;
/*{\Mop       writes $G$ to the file with name $s$.}*/

int  read(istream& I = cin);
/*{\Mopl      reads a graph from the input stream $I$ and assigns
              it to |\Mvar|. }*/

int  read(string s);
/*{\Mop       reads a graph from the file with name $s$ and assigns
              it to |\Mvar|. }*/


bool write_gml(ostream& O = cout,
               void (*node_cb)(ostream&,const graph*,const node)=0,
               void (*edge_cb)(ostream&,const graph*,const edge)=0) const;
/*{\Mopl      writes $G$ to the output stream $O$ in GML format
              (\cite{GML-Referenz}).
              If |node_cb| is not equal to 0, it is called while writing
              a node $v$ with output stream |O|, the graph and |v| as parameters.
              It can be used to write additional user defined node data.
              The output should conform with GML format (see manual
              page |gml_graph|). |edge_cb| is called while writing edges.
              If the operation fails, $false$ is returned.}*/

bool write_gml(string s,
               void (*node_cb)(ostream&,const graph*,const node)=0,
               void (*edge_cb)(ostream&,const graph*,const edge)=0) const;
/*{\Mop       writes $G$ to the file with name $s$ in GML format. For a 
              description of |node_cb| and |edge_cb|, see above. If
              the operation fails, $false$ is returned.}*/

bool read_gml(string s);
/*{\Mop       reads a graph in GML format from the file with name $s$
              and assigns it to |\Mvar|. }*/

bool read_gml(istream& I = cin);
/*{\Mop       reads a graph in GML format from the input stream $I$
              and assigns it to |\Mvar|. }*/


void print_node(node v, ostream& O = cout)  const;
/*{\Mopl      prints node $v$ on the output stream $O$. }*/


virtual void print_edge(edge e, ostream& O = cout) const;
/*{\Mopl      prints  edge $e$ on the output stream $O$. If |\Mvar|
              is directed $e$ is represented by an arrow 
              pointing from source to target. If |\Mvar| is undirected
              $e$ is printed as an undirected line segment. }*/


void print(string s, ostream& O = cout) const;
/*{\Mopl      prints $G$ with header line $s$ on the output 
              stream $O$. }*/

void print(ostream& O = cout) const { print("",O); }
/*{\Mopl      prints $G$ on the output stream $O$. }*/



/*{\Mtext
\bigskip
{\bf g) Animation Support}

            The following operations have no effect by themselves, but they
            are used to provide insights into a graph algorithm or a
            graph data structure. This is useful for debugging, animation,
            tracing, and recording sequences of operations on graphs.
            See also class $msg\_graph$, class $graph\_recorder$ and
            class $graph\_animation$.

            These operations are implemented by virtual methods, so they
            can be adjusted to anything appropriate in derived classes.
            On the other hand there is nearly no overhead when using
            them with plain graphs.
}*/


/*{\Moptions nextwarning=no }*/
virtual void touch(node, string) const {}
/*
virtual void touch(node v, string s) const {}
*/
/*{\Mop        indicates that an algorithm is just visiting node $v$.
               $s$ can be used to provide additional information like
               DFS numbers, shortest path estimates or coordinates. }*/

/*{\Moptions nextwarning=no }*/
virtual void touch(edge, string) const {}
/*
void touch(edge e, string s) const {}
*/
/*{\Mop        indicates that an algorithm is just visiting edge $e$.
               $s$ can be used to provide additional information. }*/

/*{\Moptions nextwarning=no }*/
virtual void comment(string) const {}
/*
void comment(string s) const {}
*/
/*{\Mop        is a way to signal, e.g.,  beginning and termination of
               sub-algorithms, or major steps in an algorithm. }*/

virtual bool query() const { return true; }
/*{\Mop        indicates a global query in a dynamic graph data
               structure. }*/

/*{\Moptions nextwarning=no }*/
virtual bool query(node, node) const { return true; }
/*
bool query(node v, node w) const { return true; }
*/
/*{\Mop        indicates a query concerning two nodes. }*/

/*{\Moptions nextwarning=no }*/
virtual bool query(edge) const { return true; }
/*
bool query(edge) const { return true; }
*/
/*{\Mop        indicates a query concerning an edge. }*/



};


inline bool graph::is_hidden(edge e) const { return (e->id & 0x80000000) != 0; }

inline face face_of(edge e) { return graph_of(e)->face_of(e); }

inline int  graph::outdeg(node v) const { return v->adj_length[0]; }
inline int  graph::indeg(node v)  const { return v->adj_length[1]; }
inline int  graph::degree(node v) const { return outdeg(v) + indeg(v); }

inline node graph::source(edge e)    const   { return e->term[0]; }
inline node graph::target(edge e)    const   { return e->term[1]; }
inline node graph::opposite(node v,edge e) const 
{ return (v==source(e)) ? target(e) : source(e); }

inline graph* graph::super()       const   { return parent; }

inline int graph::max_node_index() const   { return max_n_index; }
inline int graph::max_edge_index() const   { return max_e_index; }
inline int graph::max_face_index() const   { return max_f_index; }

inline int  graph::number_of_nodes() const   { return v_list.length(); }
inline int  graph::number_of_edges() const   { return e_list.length(); }

inline GenPtr& graph::entry(node v) const  { return v->data[0]; }
inline GenPtr& graph::entry(edge e) const  { return e->data[0]; }
inline GenPtr& graph::entry(face f) const  { return f->data[0]; }

inline GenPtr  graph::inf(node v) const { return v->data[0]; }
inline GenPtr  graph::inf(edge e) const { return e->data[0]; }
inline GenPtr  graph::inf(face f) const { return f->data[0]; }

inline void graph::assign(node v,GenPtr x) { v->data[0] = x; }
inline void graph::assign(edge e,GenPtr x) { e->data[0] = x; }
inline void graph::assign(face f,GenPtr x) { f->data[0] = x; }


inline node graph::first_node()      const { return (node)v_list.head(); }
inline node graph::last_node()       const { return (node)v_list.tail(); }
inline node graph::succ_node(node v) const { return (node)v_list.succ(v); }
inline node graph::pred_node(node v) const { return (node)v_list.pred(v); }

inline edge graph::first_edge()      const { return (edge)e_list.head(); }
inline edge graph::last_edge()       const { return (edge)e_list.tail(); }
inline edge graph::succ_edge(edge e) const { return (edge)e_list.succ(e); }
inline edge graph::pred_edge(edge e) const { return (edge)e_list.pred(e); } 

inline face graph::first_face()      const { return (face)f_list.head(); }
inline face graph::last_face()       const { return (face)f_list.tail(); }
inline face graph::succ_face(face f) const { return (face)f_list.succ(f); }
inline face graph::pred_face(face f) const { return (face)f_list.pred(f); } 



inline edge graph::first_adj_edge(node v) const { return v->first_adj_edge[0]; }
inline edge graph::last_adj_edge(node v) const { return v->last_adj_edge[0]; }

inline edge graph::adj_succ(edge e) const { return e->succ_adj_edge[0]; }
inline edge graph::adj_pred(edge e) const { return e->pred_adj_edge[0]; }

inline edge graph::cyclic_adj_succ(edge e) const 
{ edge e1 = adj_succ(e);
  return e1 ? e1 : first_adj_edge(source(e)); }

inline edge graph::cyclic_adj_pred(edge e) const 
{ edge e1 = adj_pred(e);
  return e1 ? e1 : last_adj_edge(source(e)); }



inline edge graph::first_in_edge(node v) const { return v->first_adj_edge[1]; }
inline edge graph::last_in_edge(node v) const { return v->last_adj_edge[1]; }

inline edge graph::in_succ(edge e) const { return e->succ_adj_edge[1]; }
inline edge graph::in_pred(edge e) const { return e->pred_adj_edge[1]; }

inline edge graph::cyclic_in_succ(edge e) const 
{ edge e1 = in_succ(e);
  return e1 ? e1 : first_in_edge(target(e)); }

inline edge graph::cyclic_in_pred(edge e) const 
{ edge e1 = in_pred(e);
  return e1 ? e1 : last_in_edge(target(e)); }


// undirected 

inline edge graph::adj_succ(edge e, node v) const 
{ return e->succ_adj_edge[(v==source(e)) ? 0 : 1]; }

inline edge graph::adj_pred(edge e, node v) const 
{ return e->pred_adj_edge[(v==source(e)) ? 0 : 1]; }

inline edge graph::cyclic_adj_succ(edge e, node v)  const
{ edge r = adj_succ(e,v);
  return (r) ? r :  v->first_adj_edge[0];
 }

inline edge graph::cyclic_adj_pred(edge e, node v) const
{ edge r = adj_pred(e,v);
  return (r) ? r : v->last_adj_edge[0];
 }



inline ostream& operator<<(ostream& O, const graph& G) { G.write(O); return O; }
inline istream& operator>>(istream& I, graph& G)  { G.read(I);  return I; }


//------------------------------------------------------------------------------
// Iteration   (macros)
//------------------------------------------------------------------------------

/*{\Mtext            
\bigskip
{\bf h) Iteration} }*/

/*{\Mtext            
All iteration macros listed in this section traverse the corresponding
node and edge lists of the graph, i.e. they visit nodes and edges in 
the order in which they are stored in these lists.
}*/


#define forall_nodes(v,G) for (v=(G).first_node(); v; v=(G).succ_node(v) )

/*{\Mtext            
\bigskip
{\bf forall\_nodes}($v,G$)\\
$\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$ }*/

#define forall_edges(e,G) for (e=(G).first_edge(); e; e=(G).succ_edge(e) )

/*{\Mtext            
\bigskip
{\bf forall\_edges}($e,G$)\\
$\{$ ``the edges of $G$ are successively assigned to $e$" $\}$ }*/

#define forall_rev_nodes(v,G) for (v=(G).last_node(); v; v=(G).pred_node(v) )
#define Forall_nodes(v,G)      for (v=(G).last_node(); v; v=(G).pred_node(v) )

/*{\Mtext            
\bigskip
{\bf forall\_rev\_nodes}($v,G$)\\
$\{$ ``the nodes of $G$ are successively assigned to $v$ in reverse order" $\}$ }*/

#define forall_rev_edges(e,G) for (e=(G).last_edge(); e; e=(G).pred_edge(e) )
#define Forall_edges(e,G)     for (e=(G).last_edge(); e; e=(G).pred_edge(e) )

/*{\Mtext            
\bigskip
{\bf forall\_rev\_edges}($e,G$)\\
$\{$ ``the edges of $G$ are successively assigned to $e$ in reverse order" $\}$ }*/


#define forall_adj_edges(e,v)\
for(e = First_Adj_Edge(v,0); e != nil; e = Succ_Adj_Edge(e,v))

/*{\Mtext
\bigskip
{\bf forall\_adj\_edges}($e,w$)\\
$\{$ ``the edges adjacent to node $w$ are successively assigned to $e$" $\}$ }*/


#define forall_out_edges(e,v)\
if (graph_of(v)->is_undirected()); else \
for(e = First_Adj_Edge(v,0); e != nil; e = Succ_Adj_Edge(e,0))

/*{\Mtext
\bigskip
{\bf forall\_out\_edges}($e,w$) a faster version of {\bf forall\_adj\_edges}
for directed graphs.  }*/


#define forall_in_edges(e,v)\
for(e = First_Adj_Edge(v,1); e != nil; e = Succ_Adj_Edge(e,1))\

/*{\Mtext
\bigskip
{\bf forall\_in\_edges}($e,w$)\\
$\{$ ``the edges of $in\_edges(w)$ are successively assigned to $e$" $\}$ }*/


#define forall_inout_edges(e,v)\
LEDA_FORALL_PREAMBLE \
for(int for_loop_var(__LINE__) = 0; for_loop_var(__LINE__) < 2; for_loop_var(__LINE__)++)\
for(e = First_Adj_Edge(v,for_loop_var(__LINE__)); e != nil;\
e = Succ_Adj_Edge(e,(v==terminal(e,for_loop_var(__LINE__)) ? for_loop_var(__LINE__) : 1-for_loop_var(__LINE__))))


/*{\Mtext
\bigskip
{\bf forall\_inout\_edges}($e,w$)\\
$\{$ ``the edges of $adj\_edges(w)$ and $in\_edges(w)$ are successively assigned to $e$" $\}$ }*/


#define forall_adj_nodes(u,v)\
LEDA_FORALL_PREAMBLE \
for(edge for_loop_var(__LINE__) = First_Adj_Edge(v,0);\
for_loop_var(__LINE__) && ((u=opposite(v,for_loop_var(__LINE__))) != 0 || 1);\
for_loop_var(__LINE__) = Succ_Adj_Edge(for_loop_var(__LINE__),v))



/*{\Mtext
\bigskip
{\bf forall\_adj\_nodes}($v,w$)\\
$\{$ ``the nodes adjacent to node $w$ are successively assigned to v" $\}$ }*/




// Iteration for faces

#define forall_faces(f,G)\
for(f=(G).first_face(); f; f=(G).succ_face(f))

#define forall_face_edges(e,F)\
for(e=graph_of(F)->first_face_edge(F); e; e=graph_of(F)->next_face_edge(e,F))

#define forall_adj_faces(f,v)\
LEDA_FORALL_PREAMBLE \
for(edge for_loop_var(__LINE__)=graph_of(v)->first_adj_edge(v);\
for_loop_var(__LINE__) && (f = graph_of(v)->adj_face(for_loop_var(__LINE__)));\
for_loop_var(__LINE__)=graph_of(v)->adj_succ(for_loop_var(__LINE__)))


/*{\Mtext
\bigskip
{\bf Faces}\\
Before using any of the following face iterators the list of faces
has to be computed by calling |G.compute_faces()|. Note, that
any update operation invalidates this list.


{\bf forall\_faces}($f,M$)
$\{$ ``the faces of $M$ are successively assigned to $f$" $\}$

{\bf forall\_face\_edges}($e,f$) \\
\phantom{{\bf forall\_faces}($f,M$)}
$\{$ ``the edges of face $f$ are successively assigned to $e$" $\}$

{\bf forall\_adj\_faces}($f,v$) \\
\phantom{{\bf forall\_faces}($f,M$)}
$\{$ ``the faces adjacent to node $v$ are successively assigned to $f$" $\}$ }*/





// Iterators for static graphs
/*
#define static_forall_nodes(v,G)\
if (G.first_node() == nil); else \
for(v=G.first_node(); v != G.last_node()+1; v++)

#define static_forall_edges(e,G)\
if (G.first_edge() == nil); else \
for(e=G.first_edge(); e != G.last_edge()+1; e++)

#define static_forall_adj_edges(e,v)\
if (First_Adj_Edge(v,0) == nil); else \
for(e=First_Adj_Edge(v,0); e != Last_Adj_Edge(v,0)+1; e++)
*/



/*{\Mimplementation
Graphs are implemented by doubly linked lists of nodes and edges. Most 
operations take constant time, except for all\_nodes, all\_edges, 
del\_all\_nodes, del\_all\_edges, make\_map, make\_planar\_map, 
compute\_faces,
all\_faces, make\_map, clear, write, and read which take time 
$O(n+m)$, and adj\_edges, adj\_nodes, out\_edges, in\_edges, and adj\_faces
which take time $O(output\ size)$ where $n$ is the current number of nodes and $m$ is the current 
number of edges. The space requirement is $O(n+m)$.}*/



#include <LEDA/node_array.h>
#include <LEDA/edge_array.h>
#include <LEDA/node_map.h>
#include <LEDA/edge_map.h>
#include <LEDA/node_list.h>
#include <LEDA/graph_gen.h>
#include <LEDA/graph_misc.h>


//------------------------------------------------------------------------------
// GRAPH<vtype,etype> : parameterized directed graphs
//------------------------------------------------------------------------------


/*{\Manpage {GRAPH} {vtype,etype} {Parameterized Graphs}}*/

template<class vtype, class etype> 

class GRAPH : public graph {

/*{\Mdefinition 
A parameterized graph $G$ is a graph whose nodes and edges contain additional
(user defined) data. Every node contains an element of a data type $vtype$, 
called the node type of $G$ and every edge contains an element of a data type 
$etype$ called the edge type of $G$. We use $\<v,w,y\>$ to denote an edge 
$(v,w)$ with information $y$ and $\<x\>$ to denote a node with information $x$.

All operations defined for the basic graph type $graph$ are also defined on
instances of any parameterized graph type |\Mname|. For parameterized graphs 
there are additional operations to access or update the information 
associated with its nodes and edges.  
Instances of a parameterized graph type can be used wherever an instance 
of the data type $graph$ can be used, e.g., in assignments and as 
arguments to functions with formal parameters of type $graph\&$. 
If a function $f(graph\&\ G)$ is called with an argument $Q$ of type 
|\Mname| then inside $f$ only the basic graph structure of $Q$ can be 
accessed. The node and edge entries are hidden. This allows the design 
of generic graph algorithms, i.e., algorithms accepting
instances of any parametrized graph type as argument.}*/


#if !defined(LEDA_COMPARE_TEMPLATE)
decl_compare_func<vtype> cmp_node_func;
decl_compare_func<etype> cmp_edge_func;
#endif


int (*cmp_node_ptr)(const vtype&, const vtype&);
int (*cmp_edge_ptr)(const etype&, const etype&);


void init_node_entry(GenPtr& x) const { LEDA_CREATE(vtype,x); }
void init_edge_entry(GenPtr& x) const { LEDA_CREATE(etype,x); }

void copy_node_entry(GenPtr& x) const  { LEDA_COPY(vtype,x); }
void copy_edge_entry(GenPtr& x) const  { LEDA_COPY(etype,x); }

void clear_node_entry(GenPtr& x) const { LEDA_CLEAR(vtype,x); }
void clear_edge_entry(GenPtr& x) const { LEDA_CLEAR(etype,x); }

void write_node_entry(ostream& o, GenPtr& x) const { LEDA_PRINT(vtype,x,o);}
void write_edge_entry(ostream& o, GenPtr& x) const { LEDA_PRINT(etype,x,o);}

void read_node_entry(istream& i, GenPtr& x) { LEDA_READ(vtype,x,i); }
void read_edge_entry(istream& i, GenPtr& x) { LEDA_READ(etype,x,i); }

void print_node_entry(ostream& o, GenPtr& x)  const
     { o << "("; LEDA_PRINT(vtype,x,o); o << ")"; }
void print_edge_entry(ostream& o, GenPtr& x)  const
     { o << "("; LEDA_PRINT(etype,x,o); o << ")"; }


public:


char* node_type()  const { return LEDA_TYPE_NAME(vtype); }
char* edge_type()  const { return LEDA_TYPE_NAME(etype); }

int cmp_node_entry(node x, node y) const 
{ return cmp_node_ptr(inf(x),inf(y)); }

int cmp_edge_entry(edge x, edge y) const
{ return cmp_edge_ptr(inf(x),inf(y)); }


/*{\Mcreation G }*/

GRAPH()  {}

/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it to 
            the empty graph. }*/

GRAPH(int sz1, int sz2)  : graph(sz1,sz2) {}


GRAPH<vtype,etype>& operator=(const GRAPH<vtype,etype>& a)
{ clear_all_entries();
  graph::operator=(a);
  copy_all_entries();
  return *this; 
 }

GRAPH(const GRAPH<vtype,etype>& a) : graph(a) { a.copy_all_entries(); } 

// subgraphs
/*
GRAPH(GRAPH<vtype,etype>& a, const list<node>& b, const list<edge>& c) 
: graph(a,b,c) {}
GRAPH(GRAPH<vtype,etype>& a, const list<edge>& c) 
: graph(a,c) {}
*/

virtual ~GRAPH()   { if (parent==0) clear_all_entries(); }



/*{\Moperations 1.5 4.5 }*/

vtype  inf(node v)    const   { return LEDA_ACCESS(vtype,graph::inf(v)); }
/*{\Mop    returns the information of node $v$. }*/
/*{\Moptions nextwarning=no }*/
const
vtype& operator[] (node v) const { return LEDA_ACCESS(vtype,entry(v)); }
vtype& operator[] (node v)       { return LEDA_ACCESS(vtype,entry(v)); }
/*{\Marrop      returns a reference to $G$.inf($v$).}*/

etype  inf(edge e)    const   { return LEDA_ACCESS(etype,graph::inf(e)); }
/*{\Mop    returns the information of edge $e$. }*/

/*{\Moptions nextwarning=no }*/
const
etype& operator[] (edge e) const { return LEDA_ACCESS(etype,entry(e)); }
etype& operator[] (edge e)       { return LEDA_ACCESS(etype,entry(e)); }
/*{\Marrop      returns a reference to $G$.inf($e$).}*/


node_array<vtype> node_data() 
{ graph_map M = graph::node_data();
  return (node_array<vtype>&)M;
}
/*{\Mopl   makes the information associated with the nodes of $G$ 
           available as a node array of type |node_array<vtype>|. }*/

edge_array<etype> edge_data()
{ graph_map M = graph::edge_data();
  return (edge_array<etype>&)M;
}
/*{\Mopl   makes the information associated with the edges of $G$ 
           available as an edge array of type |edge_array<etype>|. }*/


void   assign(node v, const vtype& x) { operator[](v) = x; }
/*{\Mopl   makes $x$ the information of node $v$. }*/

void   assign(edge e, const etype& x) { operator[](e) = x; }
/*{\Mopl   makes $x$ the information of edge $e$. }*/
                
node   new_node(const vtype& x)  { return graph::new_node(leda_copy(x)); }
/*{\Mop    adds a new node $\<x\>$ to $G$ and returns it. }*/


edge   new_edge(node v, node w, const etype& x) 
{ return graph::new_edge(v,w,leda_copy(x)); }
/*{\Mopl   adds a new edge $\<v,w,x\>$ to $G$ by appending it 
           to $adj\_edges(v)$ and to $in\_edges(w)$ and returns it. }*/


edge   new_edge(edge e, node w, const etype& x, int dir=after)
{ return graph::new_edge(e,w,leda_copy(x),dir); }
/*{\Mopl   adds a new edge $\<source(e),w,x\>$ to $G$
	   by inserting it after ($dir$=after) or before ($dir$ =before) 
           edge $e$ into $adj\_edges(source(e))$ and appending it to 
           $in\_edges(w)$. Returns the new edge.}*/



edge   new_edge(node v, edge e, const etype& x, int dir=after)
{ return graph::new_edge(v,e,leda_copy(x),dir); }
/*{\Mopl   adds a new edge $\<v,target(e),x\>$ to $G$
	   by inserting it after ($dir$=after) or before ($dir$ =before) 
           edge $e$ into $in\_edges(target(e))$ and appending it to 
           $adj\_edges(v)$. Returns the new edge.}*/


edge new_edge(edge e1, edge e2, const etype& x, int d1=after, int d2=after) 
{ return graph::new_edge(e1,e2,leda_copy(x),d1,d2); }
/*{\Mopl       adds a new edge $x = (source(e1),target(e2),x)$ to |\Mvar|. $x$ is 
               inserted before (if $d1=before$) or after (if $d1=after$) 
               edge $e1$ into $adj\_edges(source(e1))$ and before 
               (if $d2=before$) or after (if $d2=after$) edge $e2$ into 
               $in\_edges(target(e2))$ (if |\Mvar| is directed) or 
               $adj\_edges(target(e2))$, if |\Mvar| is undirected.
               The operation returns the new edge $x$.}*/


// undirected graphs only

edge new_edge(node v, edge e1, node w, edge e2, const etype& x, int d1=after, int d2=after)
{ return graph::new_edge(v,e1,w,e2,leda_copy(x),d1,d2); }
/*{\Mopl       adds a new edge $(v,w,x)$ to |\Mvar| by inserting it before 
               (if $d1=before$) or after (if $d1=after$) edge $e1$ into 
               $adj\_edges(v)$ and before (if $d2=before$) or after 
               (if $d2=after$) edge $e2$ into $adj\_edges(w)$, 
               and returns it.\\ \precond  |\Mvar| is undirected, $v \ne w$,
               $e1$ is incident to $v$, and $e2$ is incident to $w$. }*/ 


edge new_edge(node v, edge e, node w, const etype& x, int d=after)
{ return graph::new_edge(v,e,w,leda_copy(x),d); }

/*{\Mopl       adds a new edge $(v,w,x)$ to |\Mvar| by inserting it before 
               (if $d=before$) or after (if $d=after$) edge $e$ into 
               $adj\_edges(v)$ and appending it to $adj\_edges(w)$, 
               and returns it.\\ \precond  |\Mvar| is undirected, $v \ne w$,
               $e1$ is incident to $v$, and $e$ is incident to $v$. }*/ 




//------------------------------------------------------------------
// new_node & new_edge operations using default values for  node and 
// edge information
//------------------------------------------------------------------

node new_node()  
{ return graph::new_node(); }

edge new_edge(node v, node w) 
{ return graph::new_edge(v,w); }

edge new_edge(edge e, node w, int dir=after)
{ return graph::new_edge(e,w,dir); }

edge new_edge(node v, edge e, int dir=after)
{ return graph::new_edge(v,e,dir); }

edge new_edge(edge e1, edge e2, int d1=after, int d2=after) 
{ return graph::new_edge(e1,e2,d1,d2); }


edge new_edge(node v, edge e1, node w, edge e2, int d1=after, int d2=after)
{ return graph::new_edge(v,e1,w,e2,d1,d2); }

edge new_edge(node v, edge e, node w, int d)
{ return graph::new_edge(v,e,w,d); }

void join(GRAPH<vtype,etype>& H) { graph::join(H); }


node split_edge(edge e, const vtype& x, edge& e1, edge& e2)
{ return graph::split_edge(e,leda_copy(x),e1,e2); }
/*{\Xop   experimental }*/



void sort_nodes(int (*cmp)(const node&, const node&)){ graph::sort_nodes(cmp); }
void sort_edges(int (*cmp)(const edge&, const edge&)){ graph::sort_edges(cmp); }
void sort_nodes(const graph_map& A) { graph::sort_nodes(A); }
void sort_edges(const graph_map& A) { graph::sort_edges(A); }


void sort_nodes() { cmp_node_ptr = compare; graph::sort_nodes(); }
/*{\Mop    the nodes of $G$ are sorted increasingly according to their
           contents.\\ \precond $vtype$ is linearly ordered.}*/

void sort_edges() { cmp_edge_ptr = compare; graph::sort_edges(); }
/*{\Mop    the edges of $G$ are sorted increasingly according to their
	   contents.\\ \precond $etype$ is linearly ordered.}*/




/*{\Moptions nextwarning=no }*/
/* inherited 
void write(string fname) const { graph::write(fname); }
*/

/*{\Mop    writes $G$ to the file with name $fname$. The
           output operators |operator<<(ostream&, const vtype&)| and
           |operator<<(ostream&, const etype&)|(cf. section 1.6) must
           be defined.}*/

/*{\Moptions nextwarning=no }*/
/* inherited 
int read(string fname) { return graph::read(fname); }
*/

/*{\Mop    reads $G$ from the file with name $fname$. The 
	   input operators |operator>>(istream&,vtype&)| and 
	   |operator>>(istream&,etype&)| (cf.~section 1.6) must
	   be defined. Returns error code\\
	   1 \quad if file $fname$ does not exist\\
	   2 \quad if graph is not of type |\Mname|\\
	   3 \quad if file $fname$ does not contain a graph\\
	   0 \quad if reading was successful.}*/

void   clear()  { clear_all_entries(); graph::clear(); }

};



/*{\Mimplementation
Parameterized graphs are derived from directed graphs. All additional 
operations for manipulating the node and edge entries take constant
time.}*/



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

#endif

