Power-Programmierung/CD2.mdf/c/library/dos/diverses/leda/man/graph_al.tex

Text File | 1991-11-15 | 11.1 KB | 332 lines

\bigskip
\bigskip
{\magonebf 5.12 Graph Algorithms}
\bigskip

This sections 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($vtype,etype$) as arguments.

\bigskip
{\bf 5.12.1 Basic Algorithms}

\bigskip
$\bullet$ {\bf Topological Sorting}

$bool$ TOPSORT($graph\&\ G,\ node\_array(int)\&\ ord$)

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 |V|$ and $ord[v] < ord[w]$ for all edges
$(v,w) \in E$. TOPSORT returns true if $G$ is acyclic and false otherwise.

Running Time: $O(|V|+|E|)$



\bigskip
\bigskip
$\bullet$ {\bf Depth First Search}

$list(node)$  DFS($graph\&\ G,\ node\ s,\ node\_array(bool)\&\ reached$)

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.

Running Time: $O(|V|+|E|)$


\bigskip
\cleartabs
\+$list(edge)$  DFS\_NUM($graph\&\ G$, &$node\_array(int)\&\ dfsnum$,\cr
\+                                     &$node\_array(int)\&\ compnum$)\cr

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

Running Time: $O(|V|+|E|)$


\bigskip
\bigskip
$\bullet$ {\bf Breadth First Search}

$list(node)$   BFS($graph\&\ G,\ node\ s,\ node\_array(int)\&\ dist$)

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 (length of a shortest path) $dist[v]$ from $s$ to $v$.
BFS returns the list of all reached nodes.

Running Time: $O(|V|+|E|)$

\bigskip
\bigskip
$\bullet$ {\bf Connected Components}

$int$   COMPONENTS($ugraph\&\ G,\ node\_array(int)\&\ compnum$)

COMPONENTS takes an undirected 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 connected components of $G$ and
$v$ belongs to the $i$-th connected component iff $compnum[v] = i$.
COMPONENTS returns $c$.

Running Time: $O(|V|+|E|)$


\bigskip
$\bullet$ {\bf Strong Connected Components}

$int$   STRONG\_COMPONENTS($graph\&\ G,\ node\_array(int)\&\ compnum$)

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$.

Running Time: $O(|V|+|E|)$

\bigskip
$\bullet$ {\bf Transitive Closure}

$graph$ TRANSITIVE\_CLOSURE($graph\&\ G$)

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$.

Running Time: $O(|V|\cdot |E|)$





\bigskip
{\bf 5.12.2 Network Algorithms}

Most of the following network algorithms are overloaded. They work
for both integer and real valued edge costs.

\bigskip
$\bullet$ {\bf Single Source Shortest Paths }

\medskip
\cleartabs
\+$void$ DIJKSTRA($graph\&\ G,\ node\ s$,\ edge\_array(int)\ $cost$,
                                          &$node\_array(int)$\ \ \ &$dist$,\cr
\+                                        &$node\_array(edge)$     &$pred$)\cr
\medskip
\cleartabs
\+$void$ DIJKSTRA($graph\&\ G,\ node\ s$,\ edge\_array(real)\ $cost$,
                                          &$node\_array(real)$\ \ \ &$dist$,\cr
\+                                        &$node\_array(edge)$     &$pred$)\cr

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.

Running Time: $O(|E|+|V|\log |V|)$

\bigskip
\cleartabs
\+$bool$ BELLMAN\_FORD($graph\&\ G,\ node\ s$,
                       &$edge\_array(int)$\ \ &$cost$,\cr
\+                     &$node\_array(int)$    &$dist$,\cr
\+                     &$node\_array(int)$    &$pred$)\cr
\medskip
\cleartabs
\+$bool$ BELLMAN\_FORD($graph\&\ G,\ node\ s$,
                       &$edge\_array(real)$\ \ &$cost$,\cr
\+                     &$node\_array(real)$    &$dist$,\cr
\+                     &$node\_array(edge)$    &$pred$)\cr

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

Running Time: $O(|V|\cdot|E|)$

\bigskip
\bigskip
$\bullet$ {\bf All Pairs Shortest Paths }

\cleartabs
\+$void$ ALL\_PAIRS\_SHORTEST\_PATHS($graph\&\ G$,
                                     &$edge\_array(int)$\&\ \ \ &$cost$,\cr
\+                                   &$node\_matrix(int)$\&  &$dist$)\cr
\medskip
\cleartabs
\+$void$ ALL\_PAIRS\_SHORTEST\_PATHS($graph\&\ G$,
                                     &$edge\_array(real)$\&\ \ \ &$cost$,\cr
\+                                   &$node\_matrix(real)$\&  &$dist$)\cr

ALL\_PAIRS\_SHORTES\_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$).

Running Time: $O(|V|\cdot|E| + |V|^2 \log|V|)$

\bigskip
\bigskip
$\bullet$ {\bf Maximum Flow }

\medskip
\cleartabs
\+$int$ MAX\_FLOW($graph\&\ G,\ node\ s,\ node\ t$,
                                               &$edge\_array(int)\&\ cap$,\cr
\+                                             &$edge\_array(int)\&\ flow$)\cr
\medskip
\+$int$ MAX\_FLOW($graph\&\ G,\ node\ s,\ node\ t$,
                                               &$edge\_array(real)\&\ cap$,\cr
\+                                             &$edge\_array(real)\&\ flow$)\cr

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$.
MAXFLOW returns the total flow from $s$ to $t$.

Running Time: $O(|V|^3)$


\bigskip
\bigskip
$\bullet$ {\bf Maximum Cardinality Bipartite Matching}

\medskip
\cleartabs
\+$list(edge)$ MAX\_CARD\_BIPARTITE\_MATCHING($graph\&\ G$,
                                              &$list(node)\&\ A$,\cr
\+                                            &$list(node)\&\ B$)\cr

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 computes a maximum cardinality bipartite matching
of $G$, i.e., a maximal set of edges $M$ such that no two edges in $M$ share
an end point (target or source). MAX\_CARD\_BIPARTITE\_MATCHING returns $M$ as
a list of edges.

Running Time: $O(|E|\sqrt{|V|})$


\bigskip
$\bullet$ {\bf Maximum Weight Bipartite Matching}

\cleartabs
\+$list(edge)$ MAX\_WEIGHT\_BIPARTITE\_MATCHING(&$graph\&\ G$,\cr
\+                                              &$list(node)\&\ A$,\cr
\+                                              &$list(node)\&\ B$,\cr
\+                                              &$edge\_array(int)\&\ weight$)\cr

\vfill\eject

\cleartabs
\+$list(edge)$ MAX\_WEIGHT\_BIPARTITE\_MATCHING(&$graph\&\ G$,\cr
\+                                              &$list(node)\&\ A$,\cr
\+                                              &$list(node)\&\ B$,\cr
\+                                              &$edge\_array(real)\&\ weight$)\cr

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.

Running Time: $O(|V|\cdot |E|)$

\bigskip
\bigskip
$\bullet$ {\bf Spanning Tree}

\medskip
$list(edge)$ SPANNING\_TREE($ugraph\&\ G$)

SPANNING\_TREE takes as argument an undirected graph $G(V,E)$. It computes
a spanning tree $T$ of $G$, SPANNING\_TREE returns the list of edges of $T$.

Running Time: $O(|V|+|E|)$

\bigskip
\bigskip
$\bullet$ {\bf Minimum Spanning Tree}

$list(edge)$ MIN\_SPANNING\_TREE($ugraph\& G,\ edge\_array(int)\&\ cost$)
\medskip
$list(edge)$ MIN\_SPANNING\_TREE($ugraph\& G,\ edge\_array(real)\&\ cost$)

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$.

Running Time: $O(|E|\log|V|)$


\vfill\eject

\bigskip
\bigskip
{\bf 5.12.3 Algorithms for Planar Graphs}

\bigskip
$\bullet$ {\bf Planarity Test}

$bool$ PLANAR($graph\& G$)

PLANAR takes as input a directed graph $G(V,E)$ and performs a planarity test
for $G$. If $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.

Running Time: $O(|V|+|E|)$

\bigskip
\bigskip
$\bullet$ {\bf Triangulation}

$list(edge)$ TRIANGULATE\_PLANAR\_MAP($graph\&\ G$)

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.

Running Time: $O(|V|+|E|)$

\bigskip
\bigskip
$\bullet$ {\bf Straight Line Embedding}

\cleartabs
\+$int$ STRAIGHT\_LINE\_EMBEDDING($graph\&\ G$, &$node\_array(int)\&\ xcoord$,\cr
\+                                        &$node\_array(int)\&\ ycoord$)\cr

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.

Running Time: $O(|V|^2)$

\vfill\eject