# HG changeset patch
# User alpar
# Date 1126503336 0
# Node ID b7b7125a5fe81b18019e0be602b497c78ab03cc0
# Parent  a9f923a4d998dcc8cb91e87abb9f34976df70160
graph_orientation.cc: A thoroughly documented demo application.

diff -r a9f923a4d998 -r b7b7125a5fe8 demo/Makefile.am
--- a/demo/Makefile.am	Mon Sep 12 05:31:55 2005 +0000
+++ b/demo/Makefile.am	Mon Sep 12 05:35:36 2005 +0000
@@ -9,6 +9,7 @@
 	reader_writer_demo \
 	dim_to_lgf \
 	graph_to_eps_demo \
+	graph_orientation \
 	min_route \
 	hello_lemon \
 	sub_graph_adaptor_demo \
@@ -36,6 +37,8 @@
 
 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
 
+graph_orientation_SOURCES = graph_orientation.cc
+
 min_route_SOURCES = min_route.cc
 
 hello_lemon_SOURCES = hello_lemon.cc
diff -r a9f923a4d998 -r b7b7125a5fe8 demo/graph_orientation.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/graph_orientation.cc	Mon Sep 12 05:35:36 2005 +0000
@@ -0,0 +1,124 @@
+/* -*- C++ -*-
+ * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 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.
+ *
+ */
+
+
+#include <lemon/list_graph.h>
+#include <lemon/graph_reader.h>
+#include <lemon/iterable_maps.h>
+#include <lemon/xy.h>
+#include <lemon/graph_to_eps.h>
+
+
+using namespace lemon;
+ 
+
+typedef ListGraph::Node Node;
+typedef ListGraph::NodeIt NodeIt;
+typedef ListGraph::Edge Edge;
+typedef ListGraph::EdgeIt EdgeIt;
+typedef ListGraph::OutEdgeIt OutEdgeIt;
+typedef ListGraph::InEdgeIt InEdgeIt;
+
+int main(int argc, char** argv) 
+{
+  if(argc!=2) {
+    std::cerr << "\n  USAGE: " << argv[0]
+	      << " input_file.lgf" << std::endl << std::endl;
+    std::cerr << "  The file 'input_file.lgf' has to contain "
+	      << "at least three node maps called \n  'f', 'coordinates_x' "
+	      << "and 'coordinates_y'.\n"
+	      << "  The in-degree requirement is given by 'f', while the two "
+	      << "others is used\n  to create to output drawing."
+	      << std::endl;
+    return 1;
+  }
+  
+  ListGraph g;
+
+  ListGraph::NodeMap<int> f(g); //in-deg requirement;
+  ListGraph::NodeMap<int> id(g);
+  ListGraph::NodeMap<xy<double> > coords(g);
+  
+  try {
+    GraphReader<ListGraph> reader(argv[1],g);
+    reader.readNodeMap("f",f);
+    reader.readNodeMap("id",id);
+    reader.readNodeMap("coordinates_x",xMap(coords));
+    reader.readNodeMap("coordinates_y",yMap(coords));
+    reader.run();
+  } catch (DataFormatError& error) {
+    std::cerr << error.what() << std::endl;
+    return 1;
+  }
+
+  
+  ListGraph::NodeMap<int> level(g,0);
+  
+  ListGraph::NodeMap<int> def(g); //deficiency of the nodes
+  def = subMap(f,InDegMap<ListGraph>(g));
+  
+  IterableBoolNodeMap<ListGraph> active(g,false);
+  for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
+  
+  ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be 
+                                         //                  reversed
+
+  int nodeNum=countNodes(g);
+  
+  Node act;
+  while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
+    std::cout << "Process node " << id[act]
+	      << " (def=" << def[act]
+	      << " lev=" << level[act] << "): ";
+    OutEdgeIt e(g,act);
+    while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
+    if(e!=INVALID) {
+      std::cout << " REVERT EDGE " << g.id(e)
+		<< " (" << id[g.source(e)] << "---"
+		<< id[g.target(e)] << ")"
+		<< std::endl;
+      if(--def[act]==0) active[act]=false;
+      if(++def[g.target(e)]>0) active[g.target(e)]=true;
+      g.reverseEdge(e);
+      rev[e]!=rev[e];
+    }
+    else {
+      std::cout << " LIFT" << std::endl;
+      if(++level[act]>nodeNum) {
+	std::cout << "NINCS ILYEN\n";
+	return 1;
+      }
+    }
+  }
+  
+  //Show the graph
+
+  graphToEps(g,"indeg_graph_rev_out.eps").scaleToA4().
+    title("Sample .eps figure (fits to A4)").
+    copyright("(C) 2005 LEMON Project").
+    nodeScale(15).
+    coords(coords).
+    negateY().
+    edgeColors(composeMap(ColorSet(),rev)).
+    edgeWidthScale(1).
+    nodeTexts(f).nodeTextSize(20).
+    drawArrows().arrowWidth(10).arrowLength(10).
+    run();
+
+  
+} //end of main()
+
+
diff -r a9f923a4d998 -r b7b7125a5fe8 doc/graph_orientation.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/graph_orientation.dox	Mon Sep 12 05:35:36 2005 +0000
@@ -0,0 +1,142 @@
+namespace lemon {
+/**
+
+\ingroup demos
+\file graph_orientation.cc
+\brief Graph orientation with lower bound requirement on the
+in-degree of the nodes.
+
+
+
+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 xy
+
+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 <tt>typedef</tt>s will also save a lot of typing.
+\skip typedef
+\until InEdgeIt
+
+Well, we are ready to start <tt>main()</tt>.
+\skip main
+\until {
+
+First we check whether the program is called with exactly 1 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 id) 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 a "level" integer value assigned to each node. In the
+beginning, the nodes are on level 0.
+\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 which edges are reverted. Actually this is only
+used to draw these edges with different color in the output picture. The
+algorithm will update this map called \c rev, 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 algorithms itself. 
+In each iteration we choose an active node (\c act will store it). 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 that steps 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::ColorSet "ColorSet"
+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.)
+
+*/
+
+}
\ No newline at end of file