/*******************************************************************************
+
+  LEDA 3.5
+
+  graph_alg.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_GRAPHALG_H
#define LEDA_GRAPHALG_H

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

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

/*{\Manpage {graph_alg} {} {Graph Algorithms}}*/

/*{\Mtext
\bigskip
This section gives a summary of the graph algorithms contained in LEDA.
All algorithms are generic, i.e., they accept instances of any user defined
parameterized graph type $GRAPH${\tt <}$vtype,etype${\tt >} as arguments.
The header file {\tt <}LEDA/graph\_alg.h{\tt >} has to be included.
\bigskip
}*/


//-----------------------------------------------------------------------------
// basic graph algorithms:
//-----------------------------------------------------------------------------

/*{\Mtext
\bigskip
\subsection{Basic Algorithms}
\label{Basic Algorithms}
\setopdims 1.9 1 
}*/


bool TOPSORT(const graph& G, node_array<int>& ord);

/*{\Mfuncl
TOPSORT takes as argument a directed graph $G(V,E)$. It sorts $G$ topologically 
(if $G$ is acyclic) by computing for every node $v \in V$ an integer $ord[v]$ 
such that $1\le ord[v]\le \Labs{V}$ and $ord[v] < ord[w]$ for all edges 
$(v,w) \in E$. TOPSORT returns true if $G$ is acyclic and false otherwise.
The algorithm (\cite{Ka62}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/


bool TOPSORT1(graph& G);


list<node> DFS(const graph& G, node s, node_array<bool>& reached) ;

/*{\Mfuncl
DFS takes as argument a directed graph $G(V,E)$, a node $s$ of $G$ and a 
node\_array $reached$ of boolean values. It performs a depth first search 
starting at $s$ visiting all reachable nodes $v$ with $reached[v]$ = false. 
For every visited node $v$ $reached[v]$ is changed to true. DFS returns the 
list of all reached nodes.
The algorithm (\cite{T72}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/

list<edge> DFS_NUM(const graph& G, node_array<int>& dfsnum, node_array<int>& compnum);
/*{\Mfuncl
DFS\_NUM takes as argument a directed graph $G(V,E)$. It performs a 
depth first search of $G$ numbering the nodes of $G$ in two different ways. 
$dfsnum$ is a numbering with respect to the calling time and $compnum$ a 
numbering with respect to the completion time of the recursive calls. DFS\_NUM 
returns a depth first search forest of $G$ (list of tree edges).
The algorithm (\cite{T72}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/


list<node> BFS(const graph& G, node s, node_array<int>& dist);

/*{\Mfuncl
BFS takes as argument a directed graph $G(V,E)$ and a node $s$ of $G$. It 
performs a breadth first search starting at $s$ computing for every visited 
node $v$ the distance $dist[v]$ from $s$ to $v$. BFS returns the list of all 
reached nodes.
The algorithm (\cite{M84}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/


int COMPONENTS(const graph& G, node_array<int>& compnum);

/*{\Mfuncl
COMPONENTS takes a graph $G(V,E)$ as argument and computes the connected
components of the underlying undirected graph, i.e., for every node $v\in V$ 
an integer $compnum[v]$ from $[0\dots c-1]$ where $c$ is the number of 
connected components of $G$ and $v$ belongs to the $i$-th connected 
component iff $compnum[v] = i$.  COMPONENTS returns $c$.
The algorithm (\cite{M84}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/


int COMPONENTS1(const graph& G, node_array<int>& compnum);


int STRONG_COMPONENTS(const graph& G, node_array<int>& compnum);

/*{\Mfuncl
STRONG\_COMPONENTS takes a directed graph $G(V,E)$ as argument and computes for 
every node $v\in V$ an integer $compnum[v]$ from $[0\dots c-1]$ where
$c$ is the number of strongly connected components of $G$ and
$v$ belongs to the $i$-th strongly connected component iff $compnum[v] = i$.
STRONG\_COMPONENTS returns $c$.
The algorithm (\cite{M84}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/

int STRONG_COMPONENTS1(const graph& G, node_array<int>& compnum);

int BICONNECTED_COMPONENTS(const graph& G, edge_array<int>& compnum);


graph TRANSITIVE_CLOSURE(const graph& G);

/*{\Mfuncl
TRANSITIVE\_CLOSURE takes a directed graph $G(V,E)$ as argument and computes 
the transitive closure of $G(V,E)$. It returns a directed graph $G'(V',E')$ 
with $V' = V$ and $(v,w) \in E'  \Leftrightarrow$ there is a path form
$v$ to $w$ in $G$.
The algorithm (\cite{GK79}) has running time $O(\Labs{V}\cdot \Labs{E})$.
\bigskip
}*/




/*{\Mtext
\subsection{Network Algorithms}

\label{Network Algorithms}

Most of the following network algorithms exist in two versions for both 
integer and real valued edge costs.
}*/


/*{\Mtext
\bigskip
$\bullet$ {\bf Shortest Paths }
\setopdims 1 1.9 
}*/



void DIJKSTRA(const graph& G, node s, const edge_array<int>& cost, 
                                      node_array<int>& dist, 
                                      node_array<edge>& pred);

/*{\Mfuncl
DIJKSTRA takes as arguments a directed graph $G(V,E)$, a source node $s$ and an 
edge\_array $cost$ giving for each edge in $G$ a non-negative cost. It 
computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of the 
least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in the 
shortest path tree.
The algorithm (\cite{Di59}, \cite{FT87}) has running time $O(\Labs{E}+\Labs{V}\log \Labs{V})$.
\bigskip
}*/

void DIJKSTRA(const graph& G, node s, const edge_array<int>& cost, 
                                                      node_array<int>& dist);

void MOORE(const graph& G, node s, const edge_array<int>& cost, 
                                             node_array<int>& dist, node t=nil);


bool BELLMAN_FORD(const graph& G, node s, const edge_array<int>& cost,
                                                    node_array<int>& dist, 
                                                    node_array<edge>& pred);

/*{\Mfuncl
BELLMAN\_FORD takes as arguments a graph $G(V,E)$, a source node $s$ and an 
edge\_array $cost$ giving for each edge in $G$ a real (integer) cost. It 
computes for each node $v$ in $G$ the distance $dist[v]$ from $s$ (cost of 
the least cost path from $s$ to $v$) and the predecessor edge $pred[v]$ in 
the shortest path tree. BELLMAN\_FORD returns false if there is a negative
cycle in $G$ and true otherwise
The algorithm (\cite{Be58}) has running time $O(\Labs{V}\cdot \Labs{E})$.
\bigskip
}*/



bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<int>&  cost, 
                                              node_matrix<int>& dist);

/*{\Mfuncl
ALL\_PAIRS\_SHORTEST\_PATHS takes as arguments a graph $G(V,E)$ and an 
edge\_array $cost$ giving for each edge in $G$ a real (integer) valued cost. 
It computes for each node pair $(v,w)$ of $G$ the distance $dist(v,w)$ from 
$v$ to $w$ (cost of the least cost path from $v$ to $w$).
ALL\_PAIRS\_SHORTEST\_PATHS returns false if there is a negative cycle in $G$
and true otherwise.
The algorithm (\cite{Be58}, \cite{Fl62}) has running time $O(\Labs{V}\cdot \Labs{E} + \Labs{V}^2
 \log\Labs{V})$.
\bigskip
}*/



/*{\Mtext
\bigskip
$\bullet$ {\bf Flow Algorithms}
}*/



int MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap, 
                                              edge_array<int>& flow);

/*{\Mfuncl
MAX\_FLOW takes as arguments a directed graph $G(V,E)$, a source node $s$, a 
sink node $t$ and an edge\_array $cap$ giving for each edge in $G$ a capacity. 
It computes for every edge $e$ in $G$ a flow $flow[e]$ such that the total 
flow from $s$ to $t$ is maximal and $flow[e] \le cap[e]$ for all edges $e$. 
MAX\_FLOW returns the total flow from $s$ to $t$.
The algorithm (\cite{GT88}) has running time $O(\Labs{V}^3)$.
\bigskip
}*/


bool MIN_COST_FLOW(graph& G, const edge_array<int>& lcap,
                             const edge_array<int>& ucap,
                             const edge_array<int>& cost,
                             const node_array<int>& supply,
                                   edge_array<int>& flow);
                                                      
/*{\Mfuncl
MIN\_COST\_FLOW takes as arguments a directed graph $G(V,E)$, an edge\_array
$lcap$ ($ucap$) giving for each edge a lower (upper) capacity bound,
an edge\_array $cost$ specifying for each edge an integer cost and a
node\_array $supply$ defining for each node $v$ a supply or demand 
(if $supply[v] < 0$). If a feasible flow (fulfilling the capacity
and mass balance conditions) exists it computes such a $flow$ of minimal cost
and returnes |true| otherwise |false| is returned.
The algorithm is based on capacity scaling and successive shortest path
computation (cf. \cite{EK72} and \cite{AMO93}) and has running time 
$O(\Labs{E}\log U (\Labs{E} + \Labs{V}\log\Labs{V}))$.
}*/

bool MIN_COST_FLOW(graph& G, const edge_array<int>& cap,
                             const edge_array<int>& cost,
                             const node_array<int>& supply,
                                   edge_array<int>& flow);
/*{\Mfuncl
This variant of MIN\_COST\_FLOW assumes that $lcap[e] = 0$ for every
edge $e\in E$. }*/


int MIN_COST_MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap, 
                                                const edge_array<int>& cost, 
                                                      edge_array<int>& flow);
/*{\Mfuncl
MIN\_COST\_MAX\_FLOW takes as arguments a directed graph $G(V,E)$, a source 
node $s$, a sink node $t$, an edge\_array $cap$ giving for each edge in $G$ a 
capacity, and an edge\_array $cost$ specifying for each edge an integer cost. 
It computes for every edge $e$ in $G$ a flow $flow[e]$ such that the total 
flow from $s$ to $t$ is maximal, the total cost of the flow is minimal,
and $0 \le flow[e] \le cap[e]$ for all edges $e$. 
MIN\_COST\_MAX\_FLOW returns the total flow from $s$ to $t$.
\bigskip
}*/




/*{\Mtext
\bigskip
$\bullet$ {\bf Minimum Cut}
\setopdims 1.9 1 
}*/

list<node> MIN_CUT(const graph& G, edge_array<int>& weight);

/*{\Mfuncl
MIN\_CUT($G$, $weight$) takes as arguments a graph $G$ and an edge\_array
giving for each edge an integer weight. The algorithm (\cite{SW94}) computes
the cut of minimum weight and returns it as a list of nodes. It
has running time $O(\Labs{V}\cdot \Labs{E} + \Labs{V}^2 \log \Labs{V})$.
\bigskip
}*/ 




/*{\Mtext
\bigskip
$\bullet$ {\bf Matching Algorithms}
}*/


// Edmond's algorithm

list<edge> MAX_CARD_MATCHING(graph& G, int heur = 1);    
/*{\Mfuncl
MAX\_CARD\_MATCHING($G$) computes a maximum cardinality matching of $G$, i.e., 
a maximal set of edges $M$ such that no two edges in $M$ share an end point.
It returns $M$ as a list of edges.
The algorithm (\cite{E65}, \cite{T83}) has running time $O(\Labs{V}\cdot \Labs{E}\cdot\alpha(\Labs{E}))$.
\bigskip
}*/



// Hopcroft/Karp


list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G, const list<node>& A, 
                                                 const list<node>& B);

/*{\Mfuncl
MAX\_CARD\_BIPARTITE\_MATCHING takes as arguments a directed graph $G(V,E)$ and
two lists $A$ and $B$ of nodes. All edges in $G$ must be directed from nodes
in $A$ to nodes in $B$. It returns a maximum cardinality matching of $G$.
The algorithm (\cite{HK75}) has running time $O(\Labs{E}\sqrt{\Labs{V}})$.
\bigskip
}*/

list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G);


list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G, const list<node>& A, 
                                                  const list<node>& B);

list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G);


list<edge> MAX_WEIGHT_MATCHING(const ugraph&, const edge_array<int>&);

/*{\Mfuncl
MAX\_WEIGHT\_MATCHING takes as arguments an undirected graph $G$ 
and an edge\_array giving for each edge an 
integer (real) weight. 
It computes a maximum weighted matching of $G$, i.e., a set of edges $M$
such that the sum of weights of all edges in $M$ is maximal and no two edges 
in $M$ share an end point. MAX\_WEIGHT\_MATCHING returns $M$ as a 
list of edges.
The algorithm (\cite{E65}, \cite{G74}, \cite{L76}) has running 
time $O(\Labs{V}^3)$.
\bigskip
}*/



list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&A, 
                                                   const list<node>&B, 
                                                   const edge_array<int>&);

/*{\Mfuncl
MAX\_WEIGHT\_BIPARTITE\_MATCHING takes as arguments a directed graph $G$, 
two lists $A$ and $B$ of nodes and an edge\_array giving for each edge an 
integer (real) weight. All edges in $G$ must be directed from nodes in $A$ 
to nodes in $B$. 
It computes a maximum weight bipartite matching of $G$, i.e., a set of edges $M$
such that the sum of weights of all edges in $M$ is maximal and no two edges 
in $M$ share an end point. MAX\_WEIGHT\_BIPARTITE\_MATCHING returns $M$ as a 
list of edges.
The algorithm (\cite{FT87}) has running time $O(\Labs{V}\cdot \Labs{E})$.
\bigskip
}*/




//-----------------------------------------------------------------------------
// spanning trees:
//-----------------------------------------------------------------------------

/*{\Mtext
\bigskip
$\bullet$ {\bf Spanning Tree Algorithms}
}*/

list<edge> SPANNING_TREE(const graph& G);
/*{\Mfuncl
SPANNING\_TREE takes as argument a graph $G(V,E)$. It computes a spanning
tree $T$ of the underlying undirected graph, SPANNING\_TREE returns the 
list of edges of $T$.
The algorithm (\cite{M84}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/



list<edge> MIN_SPANNING_TREE1(const graph& G, const edge_array<int>& cost);

list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<int>& cost);
/*{\Mfuncl
MIN\_SPANNING\_TREE takes as argument an undirected graph $G(V,E)$ and an 
edge\_array $cost$ giving for each edge an integer cost. 
It computes a minimum spanning 
tree $T$ of $G$, i.e., a spanning tree such that the sum of all edge costs
is minimal. MIN\_SPANNING\_TREE returns the list of edges of $T$.
The algorithm (\cite{Kr56}) has running time $O(\Labs{E}\log\Labs{V})$.
\bigskip
}*/


list<edge> MIN_SPANNING_TREE(const graph& G,
                                       int (*cmp)(const edge&,const edge&));
/*{\Mfuncl Variant using a function $cmp$ to compare edge costs. }*/




//-----------------------------------------------------------------------------
// planar graphs
//-----------------------------------------------------------------------------

/*{\Mtext
\subsection{Algorithms for Planar Graphs}
\label{Algorithms for Planar Graphs}
}*/


void ST_NUMBERING(graph&, node_array<int>&, list<node>&); 

bool HT_PLANAR(graph&, bool embed=false);
bool BL_PLANAR(graph&, bool embed=false);
bool PLANAR2(graph&, bool embed=false);

bool PLANAR(graph&, bool embed=false);

/*{\Mfuncl
PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
for it. $G$ must not contain selfloops. If the second argument $embed$ has 
value $true$ and $G$ is a planar 
graph it is transformed into a planar map (a combinatorial embedding such that
the edges in all adjacency lists are in clockwise ordering). PLANAR returns 
true if $G$ is planar and false otherwise. 
The algorithm (\cite{HT74}) has running time $O(\Labs{V}+\Labs{E})$.
\bigskip
}*/


bool HT_PLANAR(graph&, list<edge>&, bool embed=false);
bool BL_PLANAR(graph&, list<edge>&, bool embed=false);

//bool BL_PLANAR(graph&, list<edge>&, bool embed,int);

bool PLANAR(graph& G, list<edge>& el, bool embed=false);
/*{\Mfuncl
PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
for $G$. PLANAR returns true if $G$ is planar and false otherwise.
If $G$ is not planar a Kuratowsky-Subgraph is computed and returned in $el$.  
\bigskip
}*/

int KURATOWSKI(graph& G, list<node>& V, list<edge>& E, node_array<int>& deg);
/*{\Mfuncl
KURATOWKI computes a Kuratowski subdivision $K$ of $G$ as follows. $V$ is the 
list of all nodes and subdivision points of $K$. For all $v \in V$ the degree
$deg[v]$ is equal to 2 for subdivision points, 4 for all other nodes if $K$ 
is a $K_5$, and -3 (+3) for the nodes of the left (right) side if $K$ is a 
$K_{3,3}$. $E$ is the list of all edges in the Kuratowski subdivision. }*/



inline list<edge> TRIANGULATE_PLANAR_MAP(graph& G)
{ return G.triangulate_map(); }

/*{\Mfuncl
TRIANGULATE\_PLANAR\_MAP takes a directed graph $G$ representing a planar map.
It triangulates the faces of $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})$.
\bigskip
}*/



//-----------------------------------------------------------------------------
// floating point (double) versions 
//-----------------------------------------------------------------------------


void DIJKSTRA(const graph& G, node s, const edge_array<double>& cost, 
                                            node_array<double>& dist, 
                                            node_array<edge>& pred);

void DIJKSTRA(const graph& G, node s, const edge_array<double>& cost, 
                                                      node_array<double>& dist);

void MOORE(const graph& G, node s, const edge_array<double>& cost, 
                                     node_array<double>& dist, node t=nil);


bool BELLMAN_FORD(const graph& G, node s, const edge_array<double>& cost,
                                                node_array<double>& dist,
                                                node_array<edge>& pred);

bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<double>&  cost,
                                              node_matrix<double>& dist);


double MAX_FLOW(graph& G, node s, node t, const edge_array<double>& cap,
                                                edge_array<double>& flow);

list<edge> MAX_WEIGHT_MATCHING(const ugraph&, const edge_array<double>&);
				   

list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&, 
                                                   const list<node>&,
                                                   const edge_array<double>&);




list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<double>& cost);

list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<double>& cost);



/*{\Mtext
\subsection{Graph Drawing Algorithms}
\label{Graph Drawing Algorithms}
}*/


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);

                                                           
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);


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);



int ORTHO_EMBEDDING(const graph&,node_array<int>&,
                                           node_array<int>&,
                                           edge_array<list<int> >&,
                                           edge_array<list<int> >&,
                                           bool= false);


int SUGIYAMA_EMBEDDING(graph &G, node_array<int>& xcoord, 
                                           node_array<int>& level,
                                           edge_array<list<int> >& xpoly);


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

#endif
