source: lemon-0.x/doc/graph_orientation.dox @ 2399:ccf2a1fa1821

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**

\ingroup demos
\file graph_orientation.cc
\brief Graph orientation with lower bound requirement on the
in-degree of the nodes.

This demo shows an adaptation of the well-known "preflow push" algorithm to
a simple graph orientation problem.

The input of the problem is a(n undirected) graph and an integer value
<i>f(n)</i> assigned to each node \e n. The task is to find an orientation
of the edges for which the number of edge arriving at each node \e n is at
least least <i>f(n)</i>.

In fact, the algorithm reads a directed graph and computes a set of edges to
be reversed in order to achieve the in-degree requirement.
This input is given using 
\ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
three node maps. The one called "f" contains the in-degree requirements, while
"coordinate_x" and "coordinate_y" indicate the position of the nodes. These
latter ones are used to generate the output, which is a <tt>.eps</tt> file.


\section go-alg-dec The C++ source file

Here you find how to solve the problem above using lemon.

\subsection go-alg-head Headers and convenience typedefs

First we include some important headers.

The first one defines \ref lemon::ListGraph "ListGraph",
the "Swiss army knife" graph implementation.
\dontinclude graph_orientation.cc
\skipline list_graph

The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
\skipline reader

This provides us with some special purpose graph \ref maps "maps".
\skipline iterable

The following header defines a simple data structure to store and manipulate
planar coordinates. It will be used to draw the result.
\skipline dim2

And finally, this header contains a simple graph drawing utility.
\skipline eps

As we don't want to type in \ref lemon "lemon::" million times, the
following line seems to be useful.
\skipline namespace

The following macro will also save a lot of typing by defining some
convenience <tt>typedef</tt>s.

\skipline TYPEDEF

Actually, the macro above would be equivalent with the following
<tt>typedef</tt>s.

\code
typedef ListGraph::Node Node;
typedef ListGraph::NodeIt NodeIt;
typedef ListGraph::Edge Edge;
typedef ListGraph::EdgeIt EdgeIt;
typedef ListGraph::OutEdgeIt OutEdgeIt;
typedef ListGraph::InEdgeIt InEdgeIt;
\endcode

\subsection go-alg-main The main() function

Well, we are ready to start <tt>main()</tt>.
\skip main
\until {

First we check whether the program is called with exactly one parameter.
If it isn't, we print a short help message end exit.
The vast majority of people would probably skip this block.
\skip if
\until }

Now, we read a graph \c g, and a map \c f containing
the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
file. To generate the output picture, we also read the node titles (\c label)
and
coordinates (\c coords).
So, first we create the graph
\skipline ListGraph
and the corresponding NodeMaps.
\skipline NodeMap
\until coords
\note The graph must be given to the maps' constructor.

Then, the following block will read these data from the file, or exit if
the file is missing or corrupt.
\skip try
\until }
\until }

The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
beginning of the execution.

\skipline level

The deficiency (\c def) of a node is the in-degree requirement minus the 
actual in-degree.

\skip def
\until subMap

A node is \e active if its deficiency is positive (i.e. if it doesn't meet
the degree requirement).
\skip active
\until def

We also store in a bool map indicating which edges are reverted.
Actually this map called \c rev is only
used to draw these edges with different color in the output picture. The
algorithm updates this map, but will not use it otherwise.
\skip rev
\until reversed

The variable \c nodeNum will refer to the number of nodes.
\skipline nodeNum

Here comes the algorithm itself. 
In each iteration we choose an active node (\c act will do it for us).
If there is
no such a node, then the orientation is feasible so we are done.
\skip act
\until while

Then we check if there exists an edge leaving this node and
stepping down exactly
one level.
\skip OutEdge
\until while

If there exists, we decrease the "activity" of the node \c act by reverting
this egde.
Fortunately, \ref lemon::ListGraph "ListGraph"
has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
that makes this easy.
We also have to update the maps \c def and
\c rev.
\skipline if
\skip if
\until }
Otherwise (i.e. if there is no edge stepping down one level). We lift up the
current active node \c act. If it reaches level \c nodeNum, then there
exists no appropriate orientation so we stop.
\skipline else
\skipline if
\skipline return
\until }
\until }
\until }

Believe it or not, this algorithm works and runs fast.

Finally, we print the obtained orientation. Note, how the different
\c bool values of
\c rev are transformed into different \ref lemon::Color "RGB color"s
using the class
\ref lemon::Palette "Palette"
and the \ref map_adaptors "map adaptor" called
\ref lemon::ComposeMap "composeMap".

\skip graphToEps
\until run


\until end of main

Finally here are again the list of the used include files (because I can't turn
this section off.)

*/

}