alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
alpar@1678: namespace lemon {
alpar@1678: /**
alpar@1678: 
alpar@1678: \ingroup demos
alpar@1678: \file graph_orientation.cc
alpar@1678: \brief Graph orientation with lower bound requirement on the
alpar@1678: in-degree of the nodes.
alpar@1678: 
alpar@1684: This demo shows an adaptation of the well-known "preflow push" algorithm to
alpar@1684: a simple graph orientation problem.
alpar@1678: 
alpar@1684: The input of the problem is a(n undirected) graph and an integer value
alpar@1684: <i>f(n)</i> assigned to each node \e n. The task is to find an orientation
alpar@2158: of the edges for which the number of edge arriving at each node \e n is at
alpar@1684: least least <i>f(n)</i>.
alpar@1684: 
alpar@1684: In fact, the algorithm reads a directed graph and computes a set of edges to
alpar@1684: be reversed in order to achieve the in-degree requirement.
alpar@1684: This input is given using 
alpar@1684: \ref graph-io-page ".lgf (Lemon Graph Format)" file. It should contain
alpar@1684: three node maps. The one called "f" contains the in-degree requirements, while
alpar@1684: "coordinate_x" and "coordinate_y" indicate the position of the nodes. These
alpar@1684: latter ones are used to generate the output, which is a <tt>.eps</tt> file.
alpar@1684: 
alpar@1684: 
alpar@1684: \section go-alg-dec The C++ source file
alpar@1684: 
alpar@1684: Here you find how to solve the problem above using lemon.
alpar@1684: 
alpar@1684: \subsection go-alg-head Headers and convenience typedefs
alpar@1678: 
alpar@1678: First we include some important headers.
alpar@1678: 
alpar@1678: The first one defines \ref lemon::ListGraph "ListGraph",
alpar@1678: the "Swiss army knife" graph implementation.
alpar@1678: \dontinclude graph_orientation.cc
alpar@1678: \skipline list_graph
alpar@1678: 
alpar@1678: The next is  to read a \ref graph-io-page ".lgf" (Lemon Graph Format) file.
alpar@1678: \skipline reader
alpar@1678: 
alpar@1678: This provides us with some special purpose graph \ref maps "maps".
alpar@1678: \skipline iterable
alpar@1678: 
alpar@1678: The following header defines a simple data structure to store and manipulate
alpar@1678: planar coordinates. It will be used to draw the result.
alpar@2310: \skipline dim2
alpar@1678: 
alpar@1678: And finally, this header contains a simple graph drawing utility.
alpar@1678: \skipline eps
alpar@1678: 
alpar@1678: As we don't want to type in \ref lemon "lemon::" million times, the
alpar@1678: following line seems to be useful.
alpar@1678: \skipline namespace
alpar@1678: 
alpar@2172: The following macro will also save a lot of typing by defining some
alpar@2172: convenience <tt>typedef</tt>s.
alpar@2172: 
alpar@2172: \skipline TYPEDEF
alpar@2172: 
alpar@2172: Actually, the macro above would be equivalent with the following
alpar@2172: <tt>typedef</tt>s.
alpar@2172: 
alpar@2172: \code
alpar@2172: typedef ListGraph::Node Node;
alpar@2172: typedef ListGraph::NodeIt NodeIt;
alpar@2172: typedef ListGraph::Edge Edge;
alpar@2172: typedef ListGraph::EdgeIt EdgeIt;
alpar@2172: typedef ListGraph::OutEdgeIt OutEdgeIt;
alpar@2172: typedef ListGraph::InEdgeIt InEdgeIt;
alpar@2172: \endcode
alpar@1678: 
alpar@1684: \subsection go-alg-main The main() function
alpar@1684: 
alpar@1678: Well, we are ready to start <tt>main()</tt>.
alpar@1678: \skip main
alpar@1678: \until {
alpar@1678: 
alpar@1953: First we check whether the program is called with exactly one parameter.
alpar@1678: If it isn't, we print a short help message end exit.
alpar@1678: The vast majority of people would probably skip this block.
alpar@1678: \skip if
alpar@1678: \until }
alpar@1678: 
alpar@1678: Now, we read a graph \c g, and a map \c f containing
alpar@1684: the in-deg requirements from a \ref graph-io-page ".lgf (Lemon Graph Format)"
alpar@1953: file. To generate the output picture, we also read the node titles (\c label)
alpar@1953: and
alpar@1678: coordinates (\c coords).
alpar@1678: So, first we create the graph
alpar@1678: \skipline ListGraph
alpar@1678: and the corresponding NodeMaps.
alpar@1678: \skipline NodeMap
alpar@1678: \until coords
alpar@1678: \note The graph must be given to the maps' constructor.
alpar@1678: 
alpar@1678: Then, the following block will read these data from the file, or exit if
alpar@1678: the file is missing or corrupt.
alpar@1678: \skip try
alpar@1678: \until }
alpar@1678: \until }
alpar@1678: 
alpar@1953: The algorithm needs an integer value assigned to each node. We call this "level" and the nodes are on level 0 at the
alpar@1953: beginning of the execution.
alpar@1953: 
alpar@1678: \skipline level
alpar@1678: 
alpar@1678: The deficiency (\c def) of a node is the in-degree requirement minus the 
alpar@1678: actual in-degree.
alpar@1678: 
alpar@1678: \skip def
alpar@1678: \until subMap
alpar@1678: 
alpar@1678: A node is \e active if its deficiency is positive (i.e. if it doesn't meet
alpar@1678: the degree requirement).
alpar@1678: \skip active
alpar@1678: \until def
alpar@1678: 
alpar@2454: We also store a bool map indicating which edges are reverted.
alpar@1953: Actually this map called \c rev is only
alpar@1678: used to draw these edges with different color in the output picture. The
alpar@1953: algorithm updates this map, but will not use it otherwise.
alpar@1678: \skip rev
alpar@1678: \until reversed
alpar@1678: 
alpar@1678: The variable \c nodeNum will refer to the number of nodes.
alpar@1678: \skipline nodeNum
alpar@1678: 
alpar@2158: Here comes the algorithm itself. 
alpar@1953: In each iteration we choose an active node (\c act will do it for us).
alpar@1953: If there is
alpar@1678: no such a node, then the orientation is feasible so we are done.
alpar@1678: \skip act
alpar@1678: \until while
alpar@1678: 
alpar@2158: Then we check if there exists an edge leaving this node and
alpar@2158: stepping down exactly
alpar@1678: one level.
alpar@1678: \skip OutEdge
alpar@1678: \until while
alpar@1678: 
alpar@1678: If there exists, we decrease the "activity" of the node \c act by reverting
alpar@1678: this egde.
alpar@1678: Fortunately, \ref lemon::ListGraph "ListGraph"
alpar@1678: has a special function \ref lemon::ListGraph::reverseEdge() "reverseEdge()"
alpar@1678: that makes this easy.
alpar@1678: We also have to update the maps \c def and
alpar@1678: \c rev.
alpar@1678: \skipline if
alpar@1678: \skip if
alpar@1678: \until }
alpar@2454: Otherwise (i.e. if there is no edge stepping down one level) we lift up the
alpar@1678: current active node \c act. If it reaches level \c nodeNum, then there
alpar@1678: exists no appropriate orientation so we stop.
alpar@1678: \skipline else
alpar@1678: \skipline if
alpar@1678: \skipline return
alpar@1678: \until }
alpar@1678: \until }
alpar@1678: \until }
alpar@1678: 
alpar@1678: Believe it or not, this algorithm works and runs fast.
alpar@1678: 
alpar@1678: Finally, we print the obtained orientation. Note, how the different
alpar@1678: \c bool values of
alpar@1678: \c rev are transformed into different \ref lemon::Color "RGB color"s
alpar@1678: using the class
alpar@2172: \ref lemon::Palette "Palette"
alpar@1678: and the \ref map_adaptors "map adaptor" called
alpar@1678: \ref lemon::ComposeMap "composeMap".
alpar@1678: 
alpar@1678: \skip graphToEps
alpar@1678: \until run
alpar@1678: 
alpar@1678: 
alpar@1678: \until end of main
alpar@1678: 
alpar@1678: Finally here are again the list of the used include files (because I can't turn
alpar@1678: this section off.)
alpar@1678: 
alpar@1678: */
alpar@1678: 
alpar@2391: }