Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt	(revision 502)
+++ CMakeLists.txt	(revision 511)
@@ -40,4 +40,5 @@
 ADD_SUBDIRECTORY(lemon)
 ADD_SUBDIRECTORY(demo)
+ADD_SUBDIRECTORY(tools)
 ADD_SUBDIRECTORY(doc)
 ADD_SUBDIRECTORY(test)
@@ -57,8 +58,9 @@
     "${PROJECT_NAME} ${PROJECT_VERSION}")
 
-  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 
   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
+  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 
@@ -67,4 +69,6 @@
   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     "DLL and import library")
+  SET(CPACK_COMPONENT_BIN_DESCRIPTION
+    "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     "Doxygen generated documentation")
Index: INSTALL
===================================================================
--- INSTALL	(revision 318)
+++ INSTALL	(revision 523)
@@ -5,4 +5,10 @@
 tarballs and successfully extracted it. The latest version of LEMON is
 available at our web page (http://lemon.cs.elte.hu/).
+
+LEMON provides two different build environments, one is based on "autotool",
+while the other is based on "cmake". This file contains instructions only for
+the former one, which is the recommended build environment on Linux, Mac OSX
+and other unices or if you use Cygwin on Windows. For cmake installation
+instructions visit http://lemon.cs.elte.hu.
 
 In order to install LEMON from the extracted source tarball you have to
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 506)
+++ lemon/Makefile.am	(revision 513)
@@ -84,4 +84,5 @@
 	lemon/math.h \
 	lemon/max_matching.h \
+	lemon/min_cost_arborescence.h \
 	lemon/nauty_reader.h \
 	lemon/path.h \
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h	(revision 440)
+++ lemon/bfs.h	(revision 519)
@@ -50,9 +50,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-    ///Instantiates a PredMap.
-
-    ///This function instantiates a PredMap.
+    ///Instantiates a \c PredMap.
+
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
-    ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -65,9 +65,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-    ///Instantiates a ProcessedMap.
-
-    ///This function instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
+
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
@@ -84,9 +84,9 @@
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-
-    ///This function instantiates a ReachedMap.
+    ///Instantiates a \c ReachedMap.
+
+    ///This function instantiates a \ref ReachedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ReachedMap.
+    ///we would like to define the \ref ReachedMap.
     static ReachedMap *createReachedMap(const Digraph &g)
     {
@@ -99,9 +99,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
-    ///Instantiates a DistMap.
-
-    ///This function instantiates a DistMap.
+    ///Instantiates a \c DistMap.
+
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the
-    ///DistMap.
+    ///\ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
     {
@@ -222,8 +222,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -242,8 +242,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -262,8 +262,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
@@ -282,8 +282,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -301,8 +301,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap :
@@ -1195,7 +1195,7 @@
   /// This class defines the interface of the BfsVisit events, and
   /// it could be the base of a real visitor class.
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1225,7 +1225,7 @@
   };
 #else
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1255,10 +1255,10 @@
   ///
   /// Default traits class of BfsVisit class.
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  template<class _Digraph>
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  template<class GR>
   struct BfsVisitDefaultTraits {
 
     /// \brief The type of the digraph the algorithm runs on.
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that indicates which nodes are reached.
@@ -1281,10 +1281,10 @@
   /// \ingroup search
   ///
-  /// \brief %BFS algorithm class with visitor interface.
+  /// \brief BFS algorithm class with visitor interface.
   ///
-  /// This class provides an efficient implementation of the %BFS algorithm
+  /// This class provides an efficient implementation of the BFS algorithm
   /// with visitor interface.
   ///
-  /// The %BfsVisit class provides an alternative interface to the Bfs
+  /// The BfsVisit class provides an alternative interface to the Bfs
   /// class. It works with callback mechanism, the BfsVisit object calls
   /// the member functions of the \c Visitor class on every BFS event.
@@ -1295,23 +1295,23 @@
   /// instead.
   ///
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  /// The default value is
-  /// \ref ListDigraph. The value of _Digraph is not used directly by
-  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
-  /// \tparam _Visitor The Visitor type that is used by the algorithm.
-  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// The default type is \ref ListDigraph.
+  /// The value of GR is not used directly by \ref BfsVisit,
+  /// it is only passed to \ref BfsVisitDefaultTraits.
+  /// \tparam VS The Visitor type that is used by the algorithm.
+  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
   /// does not observe the BFS events. If you want to observe the BFS
   /// events, you should implement your own visitor class.
-  /// \tparam _Traits Traits class to set various data types used by the
+  /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
-  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
+  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a BFS visit traits class.
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _Visitor, typename _Traits>
+  template <typename GR, typename VS, typename TR>
 #else
-  template <typename _Digraph = ListDigraph,
-            typename _Visitor = BfsVisitor<_Digraph>,
-            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
+  template <typename GR = ListDigraph,
+            typename VS = BfsVisitor<GR>,
+            typename TR = BfsVisitDefaultTraits<GR> >
 #endif
   class BfsVisit {
@@ -1319,5 +1319,5 @@
 
     ///The traits class.
-    typedef _Traits Traits;
+    typedef TR Traits;
 
     ///The type of the digraph the algorithm runs on.
@@ -1325,5 +1325,5 @@
 
     ///The visitor type used by the algorithm.
-    typedef _Visitor Visitor;
+    typedef VS Visitor;
 
     ///The type of the map that indicates which nodes are reached.
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h	(revision 440)
+++ lemon/bits/array_map.h	(revision 519)
@@ -136,5 +136,5 @@
     // \brief Template assign operator.
     //
-    // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h	(revision 500)
+++ lemon/bits/default_map.h	(revision 522)
@@ -20,4 +20,5 @@
 #define LEMON_BITS_DEFAULT_MAP_H
 
+#include <lemon/config.h>
 #include <lemon/bits/array_map.h>
 #include <lemon/bits/vector_map.h>
Index: lemon/bits/path_dump.h
===================================================================
--- lemon/bits/path_dump.h	(revision 503)
+++ lemon/bits/path_dump.h	(revision 514)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_BITS_PRED_MAP_PATH_H
-#define LEMON_BITS_PRED_MAP_PATH_H
+#ifndef LEMON_BITS_PATH_DUMP_H
+#define LEMON_BITS_PATH_DUMP_H
 
 #include <lemon/core.h>
Index: lemon/bits/vector_map.h
===================================================================
--- lemon/bits/vector_map.h	(revision 440)
+++ lemon/bits/vector_map.h	(revision 519)
@@ -125,5 +125,5 @@
     // \brief Template assign operator.
     //
-    // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
Index: lemon/bits/windows.h
===================================================================
--- lemon/bits/windows.h	(revision 491)
+++ lemon/bits/windows.h	(revision 514)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_WINDOWS_H
-#define LEMON_WINDOWS_H
+#ifndef LEMON_BITS_WINDOWS_H
+#define LEMON_BITS_WINDOWS_H
 
 #include <string>
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h	(revision 440)
+++ lemon/circulation.h	(revision 519)
@@ -32,14 +32,14 @@
   ///
   /// Default traits class of Circulation class.
-  /// \tparam _Diraph Digraph type.
-  /// \tparam _LCapMap Lower bound capacity map type.
-  /// \tparam _UCapMap Upper bound capacity map type.
-  /// \tparam _DeltaMap Delta map type.
-  template <typename _Diraph, typename _LCapMap,
-            typename _UCapMap, typename _DeltaMap>
+  /// \tparam GR Digraph type.
+  /// \tparam LM Lower bound capacity map type.
+  /// \tparam UM Upper bound capacity map type.
+  /// \tparam DM Delta map type.
+  template <typename GR, typename LM,
+            typename UM, typename DM>
   struct CirculationDefaultTraits {
 
     /// \brief The type of the digraph the algorithm runs on.
-    typedef _Diraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that stores the circulation lower
@@ -48,5 +48,5 @@
     /// The type of the map that stores the circulation lower bound.
     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef _LCapMap LCapMap;
+    typedef LM LCapMap;
 
     /// \brief The type of the map that stores the circulation upper
@@ -55,5 +55,5 @@
     /// The type of the map that stores the circulation upper bound.
     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef _UCapMap UCapMap;
+    typedef UM UCapMap;
 
     /// \brief The type of the map that stores the lower bound for
@@ -63,5 +63,5 @@
     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
     /// concept.
-    typedef _DeltaMap DeltaMap;
+    typedef DM DeltaMap;
 
     /// \brief The type of the flow values.
@@ -138,27 +138,25 @@
      in this way.
 
-     \tparam _Digraph The type of the digraph the algorithm runs on.
-     \tparam _LCapMap The type of the lower bound capacity map. The default
-     map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
-     \tparam _UCapMap The type of the upper bound capacity map. The default
-     map type is \c _LCapMap.
-     \tparam _DeltaMap The type of the map that stores the lower bound
+     \tparam GR The type of the digraph the algorithm runs on.
+     \tparam LM The type of the lower bound capacity map. The default
+     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+     \tparam UM The type of the upper bound capacity map. The default
+     map type is \c LM.
+     \tparam DM The type of the map that stores the lower bound
      for the supply of the nodes. The default map type is
-     \c _Digraph::ArcMap<_UCapMap::Value>.
+     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   */
 #ifdef DOXYGEN
-template< typename _Digraph,
-          typename _LCapMap,
-          typename _UCapMap,
-          typename _DeltaMap,
-          typename _Traits >
+template< typename GR,
+          typename LM,
+          typename UM,
+          typename DM,
+          typename TR >
 #else
-template< typename _Digraph,
-          typename _LCapMap = typename _Digraph::template ArcMap<int>,
-          typename _UCapMap = _LCapMap,
-          typename _DeltaMap = typename _Digraph::
-                               template NodeMap<typename _UCapMap::Value>,
-          typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
-                                                    _UCapMap, _DeltaMap> >
+template< typename GR,
+          typename LM = typename GR::template ArcMap<int>,
+          typename UM = LM,
+          typename DM = typename GR::template NodeMap<typename UM::Value>,
+          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
 #endif
   class Circulation {
@@ -166,5 +164,5 @@
 
     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
-    typedef _Traits Traits;
+    typedef TR Traits;
     ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h	(revision 440)
+++ lemon/concepts/digraph.h	(revision 514)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_CONCEPT_DIGRAPH_H
-#define LEMON_CONCEPT_DIGRAPH_H
+#ifndef LEMON_CONCEPTS_DIGRAPH_H
+#define LEMON_CONCEPTS_DIGRAPH_H
 
 ///\ingroup graph_concepts
@@ -485,3 +485,3 @@
 
 
-#endif // LEMON_CONCEPT_DIGRAPH_H
+#endif
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h	(revision 440)
+++ lemon/concepts/graph.h	(revision 514)
@@ -21,9 +21,8 @@
 ///\brief The concept of Undirected Graphs.
 
-#ifndef LEMON_CONCEPT_GRAPH_H
-#define LEMON_CONCEPT_GRAPH_H
+#ifndef LEMON_CONCEPTS_GRAPH_H
+#define LEMON_CONCEPTS_GRAPH_H
 
 #include <lemon/concepts/graph_components.h>
-#include <lemon/concepts/graph.h>
 #include <lemon/core.h>
 
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h	(revision 440)
+++ lemon/concepts/graph_components.h	(revision 521)
@@ -22,6 +22,6 @@
 
 
-#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
-#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
+#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
+#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 
 #include <lemon/core.h>
@@ -115,5 +115,5 @@
     ///
     /// This class provides the minimal set of features needed for a
-    /// directed graph structure. All digraph concepts have to be
+    /// directed graph structure. All digraph concepts have to
     /// conform to this base directed graph. It just provides types
     /// for nodes and arcs and functions to get the source and the
@@ -180,5 +180,5 @@
     /// This class provides the minimal set of features needed for an
     /// undirected graph structure. All undirected graph concepts have
-    /// to be conform to this base graph. It just provides types for
+    /// to conform to this base graph. It just provides types for
     /// nodes, arcs and edges and functions to get the
     /// source and the target of the arcs and edges,
@@ -295,5 +295,5 @@
     /// This class provides beside the core digraph features
     /// core id functions for the digraph structure.
-    /// The most of the base digraphs should be conform to this concept.
+    /// The most of the base digraphs should conform to this concept.
     /// The id's are unique and immutable.
     template <typename _Base = BaseDigraphComponent>
@@ -373,5 +373,5 @@
     /// This class provides beside the core undirected graph features
     /// core id functions for the undirected graph structure.  The
-    /// most of the base undirected graphs should be conform to this
+    /// most of the base undirected graphs should conform to this
     /// concept.  The id's are unique and immutable.
     template <typename _Base = BaseGraphComponent>
Index: lemon/concepts/heap.h
===================================================================
--- lemon/concepts/heap.h	(revision 503)
+++ lemon/concepts/heap.h	(revision 514)
@@ -21,6 +21,6 @@
 ///\brief The concept of heaps.
 
-#ifndef LEMON_CONCEPT_HEAP_H
-#define LEMON_CONCEPT_HEAP_H
+#ifndef LEMON_CONCEPTS_HEAP_H
+#define LEMON_CONCEPTS_HEAP_H
 
 #include <lemon/core.h>
@@ -244,3 +244,3 @@
   } // namespace lemon
 }
-#endif // LEMON_CONCEPT_PATH_H
+#endif
Index: lemon/concepts/maps.h
===================================================================
--- lemon/concepts/maps.h	(revision 440)
+++ lemon/concepts/maps.h	(revision 514)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_CONCEPT_MAPS_H
-#define LEMON_CONCEPT_MAPS_H
+#ifndef LEMON_CONCEPTS_MAPS_H
+#define LEMON_CONCEPTS_MAPS_H
 
 #include <lemon/core.h>
@@ -214,3 +214,3 @@
 } //namespace lemon
 
-#endif // LEMON_CONCEPT_MAPS_H
+#endif
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h	(revision 440)
+++ lemon/concepts/path.h	(revision 514)
@@ -22,6 +22,6 @@
 ///
 
-#ifndef LEMON_CONCEPT_PATH_H
-#define LEMON_CONCEPT_PATH_H
+#ifndef LEMON_CONCEPTS_PATH_H
+#define LEMON_CONCEPTS_PATH_H
 
 #include <lemon/core.h>
@@ -306,3 +306,3 @@
 } // namespace lemon
 
-#endif // LEMON_CONCEPT_PATH_H
+#endif
Index: lemon/core.h
===================================================================
--- lemon/core.h	(revision 440)
+++ lemon/core.h	(revision 522)
@@ -23,4 +23,5 @@
 #include <algorithm>
 
+#include <lemon/core.h>
 #include <lemon/bits/enable_if.h>
 #include <lemon/bits/traits.h>
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h	(revision 440)
+++ lemon/dfs.h	(revision 519)
@@ -50,9 +50,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-    ///Instantiates a PredMap.
-
-    ///This function instantiates a PredMap.
+    ///Instantiates a \c PredMap.
+
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
-    ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -65,9 +65,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-    ///Instantiates a ProcessedMap.
-
-    ///This function instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
+
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
@@ -84,9 +84,9 @@
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-
-    ///This function instantiates a ReachedMap.
+    ///Instantiates a \c ReachedMap.
+
+    ///This function instantiates a \ref ReachedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ReachedMap.
+    ///we would like to define the \ref ReachedMap.
     static ReachedMap *createReachedMap(const Digraph &g)
     {
@@ -99,9 +99,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
-    ///Instantiates a DistMap.
-
-    ///This function instantiates a DistMap.
+    ///Instantiates a \c DistMap.
+
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the
-    ///DistMap.
+    ///\ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
     {
@@ -221,8 +221,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -241,8 +241,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -261,8 +261,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
@@ -281,8 +281,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -299,8 +299,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap :
@@ -1127,7 +1127,7 @@
   /// This class defines the interface of the DfsVisit events, and
   /// it could be the base of a real visitor class.
-  template <typename _Digraph>
+  template <typename GR>
   struct DfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1165,7 +1165,7 @@
   };
 #else
-  template <typename _Digraph>
+  template <typename GR>
   struct DfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1200,9 +1200,9 @@
   /// Default traits class of DfsVisit class.
   /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  template<class _Digraph>
+  template<class GR>
   struct DfsVisitDefaultTraits {
 
     /// \brief The type of the digraph the algorithm runs on.
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that indicates which nodes are reached.
@@ -1225,10 +1225,10 @@
   /// \ingroup search
   ///
-  /// \brief %DFS algorithm class with visitor interface.
+  /// \brief DFS algorithm class with visitor interface.
   ///
-  /// This class provides an efficient implementation of the %DFS algorithm
+  /// This class provides an efficient implementation of the DFS algorithm
   /// with visitor interface.
   ///
-  /// The %DfsVisit class provides an alternative interface to the Dfs
+  /// The DfsVisit class provides an alternative interface to the Dfs
   /// class. It works with callback mechanism, the DfsVisit object calls
   /// the member functions of the \c Visitor class on every DFS event.
@@ -1239,23 +1239,23 @@
   /// instead.
   ///
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  /// The default value is
-  /// \ref ListDigraph. The value of _Digraph is not used directly by
-  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
-  /// \tparam _Visitor The Visitor type that is used by the algorithm.
-  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// The default type is \ref ListDigraph.
+  /// The value of GR is not used directly by \ref DfsVisit,
+  /// it is only passed to \ref DfsVisitDefaultTraits.
+  /// \tparam VS The Visitor type that is used by the algorithm.
+  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
   /// does not observe the DFS events. If you want to observe the DFS
   /// events, you should implement your own visitor class.
-  /// \tparam _Traits Traits class to set various data types used by the
+  /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
-  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
+  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
   /// See \ref DfsVisitDefaultTraits for the documentation of
   /// a DFS visit traits class.
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _Visitor, typename _Traits>
+  template <typename GR, typename VS, typename TR>
 #else
-  template <typename _Digraph = ListDigraph,
-            typename _Visitor = DfsVisitor<_Digraph>,
-            typename _Traits = DfsVisitDefaultTraits<_Digraph> >
+  template <typename GR = ListDigraph,
+            typename VS = DfsVisitor<GR>,
+            typename TR = DfsVisitDefaultTraits<GR> >
 #endif
   class DfsVisit {
@@ -1263,5 +1263,5 @@
 
     ///The traits class.
-    typedef _Traits Traits;
+    typedef TR Traits;
 
     ///The type of the digraph the algorithm runs on.
@@ -1269,5 +1269,5 @@
 
     ///The visitor type used by the algorithm.
-    typedef _Visitor Visitor;
+    typedef VS Visitor;
 
     ///The type of the map that indicates which nodes are reached.
Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h	(revision 440)
+++ lemon/dijkstra.h	(revision 519)
@@ -74,5 +74,5 @@
     typedef typename LM::Value Value;
 
-    /// Operation traits for Dijkstra algorithm.
+    /// Operation traits for %Dijkstra algorithm.
 
     /// This class defines the operations that are used in the algorithm.
@@ -85,5 +85,5 @@
     /// Usually it is \c Digraph::NodeMap<int>.
     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
-    ///Instantiates a \ref HeapCrossRef.
+    ///Instantiates a \c HeapCrossRef.
 
     ///This function instantiates a \ref HeapCrossRef.
@@ -95,5 +95,5 @@
     }
 
-    ///The heap type used by the Dijkstra algorithm.
+    ///The heap type used by the %Dijkstra algorithm.
 
     ///The heap type used by the Dijkstra algorithm.
@@ -102,5 +102,5 @@
     ///\sa Dijkstra
     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
-    ///Instantiates a \ref Heap.
+    ///Instantiates a \c Heap.
 
     ///This function instantiates a \ref Heap.
@@ -117,9 +117,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-    ///Instantiates a PredMap.
-
-    ///This function instantiates a PredMap.
+    ///Instantiates a \c PredMap.
+
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
-    ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -133,9 +133,9 @@
     ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-    ///Instantiates a ProcessedMap.
-
-    ///This function instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
+
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
@@ -152,9 +152,9 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
-    ///Instantiates a DistMap.
-
-    ///This function instantiates a DistMap.
+    ///Instantiates a \c DistMap.
+
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define
-    ///the DistMap
+    ///the \ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
     {
@@ -217,5 +217,6 @@
     ///The heap type used by the algorithm.
     typedef typename TR::Heap Heap;
-    ///The operation traits class.
+    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
+    ///of the algorithm.
     typedef typename TR::OperationTraits OperationTraits;
 
@@ -233,5 +234,5 @@
     const Digraph *G;
     //Pointer to the length map.
-    const LengthMap *length;
+    const LengthMap *_length;
     //Pointer to the map of predecessors arcs.
     PredMap *_pred;
@@ -298,8 +299,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -319,8 +320,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -340,8 +341,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -359,8 +360,8 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap
@@ -440,5 +441,5 @@
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///\ref OperationTraits type.
+    ///\c OperationTraits type.
     template <class T>
     struct SetOperationTraits
@@ -459,8 +460,8 @@
 
     ///Constructor.
-    ///\param _g The digraph the algorithm runs on.
-    ///\param _length The length map used by the algorithm.
-    Dijkstra(const Digraph& _g, const LengthMap& _length) :
-      G(&_g), length(&_length),
+    ///\param g The digraph the algorithm runs on.
+    ///\param length The length map used by the algorithm.
+    Dijkstra(const Digraph& g, const LengthMap& length) :
+      G(&g), _length(&length),
       _pred(NULL), local_pred(false),
       _dist(NULL), local_dist(false),
@@ -486,5 +487,5 @@
     Dijkstra &lengthMap(const LengthMap &m)
     {
-      length = &m;
+      _length = &m;
       return *this;
     }
@@ -639,10 +640,10 @@
         switch(_heap->state(w)) {
         case Heap::PRE_HEAP:
-          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
+          _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
           _pred->set(w,e);
           break;
         case Heap::IN_HEAP:
           {
-            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
+            Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
               _heap->decrease(w, newvalue);
Index: lemon/dimacs.h
===================================================================
--- lemon/dimacs.h	(revision 440)
+++ lemon/dimacs.h	(revision 509)
@@ -296,7 +296,22 @@
   }
 
-  /// DIMACS plain digraph reader function.
-  ///
-  /// This function reads a digraph without any designated nodes and
+  template<typename Graph>
+  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
+  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
+              dummy<0> = 0)
+  {
+    g.addEdge(s,t);
+  }
+  template<typename Graph>
+  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
+  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
+              dummy<1> = 1)
+  {
+    g.addArc(s,t);
+  }
+  
+  /// DIMACS plain (di)graph reader function.
+  ///
+  /// This function reads a (di)graph without any designated nodes and
   /// maps from DIMACS format, i.e. from DIMACS files having a line
   /// starting with
@@ -308,13 +323,36 @@
   /// If the file type was previously evaluated by dimacsType(), then
   /// the descriptor struct should be given by the \c dest parameter.
-  template<typename Digraph>
-  void readDimacsMat(std::istream& is, Digraph &g,
-                     DimacsDescriptor desc=DimacsDescriptor()) {
-    typename Digraph::Node u,v;
-    NullMap<typename Digraph::Arc, int> n;
+  template<typename Graph>
+  void readDimacsMat(std::istream& is, Graph &g,
+                     DimacsDescriptor desc=DimacsDescriptor())
+  {
     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     if(desc.type!=DimacsDescriptor::MAT)
       throw FormatError("Problem type mismatch");
-    _readDimacs(is, g, n, u, v, desc);
+
+    g.clear();
+    std::vector<typename Graph::Node> nodes;
+    char c;
+    int i, j;
+    std::string str;
+    nodes.resize(desc.nodeNum + 1);
+    for (int k = 1; k <= desc.nodeNum; ++k) {
+      nodes[k] = g.addNode();
+    }
+    
+    while (is >> c) {
+      switch (c) {
+      case 'c': // comment line
+        getline(is, str);
+        break;
+      case 'n': // node definition line
+        break;
+      case 'a': // arc (arc) definition line
+        is >> i >> j;
+        getline(is, str);
+        _addArcEdge(g,nodes[i], nodes[j]);
+        break;
+      }
+    }
   }
 
Index: lemon/glpk.cc
===================================================================
--- lemon/glpk.cc	(revision 526)
+++ lemon/glpk.cc	(revision 462)
@@ -522,10 +522,4 @@
     cols.clear();
   }
-
-  void GlpkBase::freeEnv() {
-    glp_free_env();
-  }
-
-  GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper;
 
   // GlpkLp members
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h	(revision 526)
+++ lemon/glpk.h	(revision 462)
@@ -101,16 +101,4 @@
     virtual void _clear();
 
-  private:
-
-    static void freeEnv();
-
-    struct FreeEnvHelper {
-      ~FreeEnvHelper() {
-        freeEnv();
-      }
-    };
-    
-    static FreeEnvHelper freeEnvHelper;
-    
   public:
 
Index: lemon/lp_skeleton.h
===================================================================
--- lemon/lp_skeleton.h	(revision 459)
+++ lemon/lp_skeleton.h	(revision 514)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_LP_SKELETON
-#define LEMON_LP_SKELETON
+#ifndef LEMON_LP_SKELETON_H
+#define LEMON_LP_SKELETON_H
 
 #include <lemon/lp_base.h>
@@ -227,3 +227,3 @@
 } //namespace lemon
 
-#endif // LEMON_LP_SKELETON
+#endif
Index: lemon/min_cost_arborescence.h
===================================================================
--- lemon/min_cost_arborescence.h	(revision 512)
+++ lemon/min_cost_arborescence.h	(revision 512)
@@ -0,0 +1,796 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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.
+ *
+ */
+
+#ifndef LEMON_MIN_COST_ARBORESCENCE_H
+#define LEMON_MIN_COST_ARBORESCENCE_H
+
+///\ingroup spantree
+///\file
+///\brief Minimum Cost Arborescence algorithm.
+
+#include <vector>
+
+#include <lemon/list_graph.h>
+#include <lemon/bin_heap.h>
+#include <lemon/assert.h>
+
+namespace lemon {
+
+
+  /// \brief Default traits class for MinCostArborescence class.
+  ///
+  /// Default traits class for MinCostArborescence class.
+  /// \param _Digraph Digraph type.
+  /// \param _CostMap Type of cost map.
+  template <class _Digraph, class _CostMap>
+  struct MinCostArborescenceDefaultTraits{
+
+    /// \brief The digraph type the algorithm runs on.
+    typedef _Digraph Digraph;
+
+    /// \brief The type of the map that stores the arc costs.
+    ///
+    /// The type of the map that stores the arc costs.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    typedef _CostMap CostMap;
+
+    /// \brief The value type of the costs.
+    ///
+    /// The value type of the costs.
+    typedef typename CostMap::Value Value;
+
+    /// \brief The type of the map that stores which arcs are in the
+    /// arborescence.
+    ///
+    /// The type of the map that stores which arcs are in the
+    /// arborescence.  It must meet the \ref concepts::WriteMap
+    /// "WriteMap" concept.  Initially it will be set to false on each
+    /// arc. After it will set all arborescence arcs once.
+    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
+
+    /// \brief Instantiates a ArborescenceMap.
+    ///
+    /// This function instantiates a \ref ArborescenceMap.
+    /// \param digraph is the graph, to which we would like to
+    /// calculate the ArborescenceMap.
+    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
+      return new ArborescenceMap(digraph);
+    }
+
+    /// \brief The type of the PredMap
+    ///
+    /// The type of the PredMap. It is a node map with an arc value type.
+    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    ///
+    /// This function instantiates a \ref PredMap.
+    /// \param _digraph is the digraph, to which we would like to define the
+    /// PredMap.
+    static PredMap *createPredMap(const Digraph &digraph){
+      return new PredMap(digraph);
+    }
+
+  };
+
+  /// \ingroup spantree
+  ///
+  /// \brief %MinCostArborescence algorithm class.
+  ///
+  /// This class provides an efficient implementation of
+  /// %MinCostArborescence algorithm. The arborescence is a tree
+  /// which is directed from a given source node of the digraph. One or
+  /// more sources should be given for the algorithm and it will calculate
+  /// the minimum cost subgraph which are union of arborescences with the
+  /// given sources and spans all the nodes which are reachable from the
+  /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
+  ///
+  /// The algorithm provides also an optimal dual solution, therefore
+  /// the optimality of the solution can be checked.
+  ///
+  /// \param _Digraph The digraph type the algorithm runs on. The default value
+  /// is \ref ListDigraph.
+  /// \param _CostMap This read-only ArcMap determines the costs of the
+  /// arcs. It is read once for each arc, so the map may involve in
+  /// relatively time consuming process to compute the arc cost if
+  /// it is necessary. The default map type is \ref
+  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
+  /// \param _Traits Traits class to set various data types used
+  /// by the algorithm. The default traits class is
+  /// \ref MinCostArborescenceDefaultTraits
+  /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>".  See \ref
+  /// MinCostArborescenceDefaultTraits for the documentation of a
+  /// MinCostArborescence traits class.
+  ///
+  /// \author Balazs Dezso
+#ifndef DOXYGEN
+  template <typename _Digraph = ListDigraph,
+            typename _CostMap = typename _Digraph::template ArcMap<int>,
+            typename _Traits =
+            MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
+#else
+  template <typename _Digraph, typename _CostMap, typedef _Traits>
+#endif
+  class MinCostArborescence {
+  public:
+
+    /// The traits.
+    typedef _Traits Traits;
+    /// The type of the underlying digraph.
+    typedef typename Traits::Digraph Digraph;
+    /// The type of the map that stores the arc costs.
+    typedef typename Traits::CostMap CostMap;
+    ///The type of the costs of the arcs.
+    typedef typename Traits::Value Value;
+    ///The type of the predecessor map.
+    typedef typename Traits::PredMap PredMap;
+    ///The type of the map that stores which arcs are in the arborescence.
+    typedef typename Traits::ArborescenceMap ArborescenceMap;
+
+    typedef MinCostArborescence Create;
+
+  private:
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+    struct CostArc {
+
+      Arc arc;
+      Value value;
+
+      CostArc() {}
+      CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
+
+    };
+
+    const Digraph *_digraph;
+    const CostMap *_cost;
+
+    PredMap *_pred;
+    bool local_pred;
+
+    ArborescenceMap *_arborescence;
+    bool local_arborescence;
+
+    typedef typename Digraph::template ArcMap<int> ArcOrder;
+    ArcOrder *_arc_order;
+
+    typedef typename Digraph::template NodeMap<int> NodeOrder;
+    NodeOrder *_node_order;
+
+    typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
+    CostArcMap *_cost_arcs;
+
+    struct StackLevel {
+
+      std::vector<CostArc> arcs;
+      int node_level;
+
+    };
+
+    std::vector<StackLevel> level_stack;
+    std::vector<Node> queue;
+
+    typedef std::vector<typename Digraph::Node> DualNodeList;
+
+    DualNodeList _dual_node_list;
+
+    struct DualVariable {
+      int begin, end;
+      Value value;
+
+      DualVariable(int _begin, int _end, Value _value)
+        : begin(_begin), end(_end), value(_value) {}
+
+    };
+
+    typedef std::vector<DualVariable> DualVariables;
+
+    DualVariables _dual_variables;
+
+    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
+
+    HeapCrossRef *_heap_cross_ref;
+
+    typedef BinHeap<int, HeapCrossRef> Heap;
+
+    Heap *_heap;
+
+  protected:
+
+    MinCostArborescence() {}
+
+  private:
+
+    void createStructures() {
+      if (!_pred) {
+        local_pred = true;
+        _pred = Traits::createPredMap(*_digraph);
+      }
+      if (!_arborescence) {
+        local_arborescence = true;
+        _arborescence = Traits::createArborescenceMap(*_digraph);
+      }
+      if (!_arc_order) {
+        _arc_order = new ArcOrder(*_digraph);
+      }
+      if (!_node_order) {
+        _node_order = new NodeOrder(*_digraph);
+      }
+      if (!_cost_arcs) {
+        _cost_arcs = new CostArcMap(*_digraph);
+      }
+      if (!_heap_cross_ref) {
+        _heap_cross_ref = new HeapCrossRef(*_digraph, -1);
+      }
+      if (!_heap) {
+        _heap = new Heap(*_heap_cross_ref);
+      }
+    }
+
+    void destroyStructures() {
+      if (local_arborescence) {
+        delete _arborescence;
+      }
+      if (local_pred) {
+        delete _pred;
+      }
+      if (_arc_order) {
+        delete _arc_order;
+      }
+      if (_node_order) {
+        delete _node_order;
+      }
+      if (_cost_arcs) {
+        delete _cost_arcs;
+      }
+      if (_heap) {
+        delete _heap;
+      }
+      if (_heap_cross_ref) {
+        delete _heap_cross_ref;
+      }
+    }
+
+    Arc prepare(Node node) {
+      std::vector<Node> nodes;
+      (*_node_order)[node] = _dual_node_list.size();
+      StackLevel level;
+      level.node_level = _dual_node_list.size();
+      _dual_node_list.push_back(node);
+      for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
+        Arc arc = it;
+        Node source = _digraph->source(arc);
+        Value value = (*_cost)[it];
+        if (source == node || (*_node_order)[source] == -3) continue;
+        if ((*_cost_arcs)[source].arc == INVALID) {
+          (*_cost_arcs)[source].arc = arc;
+          (*_cost_arcs)[source].value = value;
+          nodes.push_back(source);
+        } else {
+          if ((*_cost_arcs)[source].value > value) {
+            (*_cost_arcs)[source].arc = arc;
+            (*_cost_arcs)[source].value = value;
+          }
+        }
+      }
+      CostArc minimum = (*_cost_arcs)[nodes[0]];
+      for (int i = 1; i < int(nodes.size()); ++i) {
+        if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
+          minimum = (*_cost_arcs)[nodes[i]];
+        }
+      }
+      _arc_order->set(minimum.arc, _dual_variables.size());
+      DualVariable var(_dual_node_list.size() - 1,
+                       _dual_node_list.size(), minimum.value);
+      _dual_variables.push_back(var);
+      for (int i = 0; i < int(nodes.size()); ++i) {
+        (*_cost_arcs)[nodes[i]].value -= minimum.value;
+        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
+        (*_cost_arcs)[nodes[i]].arc = INVALID;
+      }
+      level_stack.push_back(level);
+      return minimum.arc;
+    }
+
+    Arc contract(Node node) {
+      int node_bottom = bottom(node);
+      std::vector<Node> nodes;
+      while (!level_stack.empty() &&
+             level_stack.back().node_level >= node_bottom) {
+        for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
+          Arc arc = level_stack.back().arcs[i].arc;
+          Node source = _digraph->source(arc);
+          Value value = level_stack.back().arcs[i].value;
+          if ((*_node_order)[source] >= node_bottom) continue;
+          if ((*_cost_arcs)[source].arc == INVALID) {
+            (*_cost_arcs)[source].arc = arc;
+            (*_cost_arcs)[source].value = value;
+            nodes.push_back(source);
+          } else {
+            if ((*_cost_arcs)[source].value > value) {
+              (*_cost_arcs)[source].arc = arc;
+              (*_cost_arcs)[source].value = value;
+            }
+          }
+        }
+        level_stack.pop_back();
+      }
+      CostArc minimum = (*_cost_arcs)[nodes[0]];
+      for (int i = 1; i < int(nodes.size()); ++i) {
+        if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
+          minimum = (*_cost_arcs)[nodes[i]];
+        }
+      }
+      _arc_order->set(minimum.arc, _dual_variables.size());
+      DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
+      _dual_variables.push_back(var);
+      StackLevel level;
+      level.node_level = node_bottom;
+      for (int i = 0; i < int(nodes.size()); ++i) {
+        (*_cost_arcs)[nodes[i]].value -= minimum.value;
+        level.arcs.push_back((*_cost_arcs)[nodes[i]]);
+        (*_cost_arcs)[nodes[i]].arc = INVALID;
+      }
+      level_stack.push_back(level);
+      return minimum.arc;
+    }
+
+    int bottom(Node node) {
+      int k = level_stack.size() - 1;
+      while (level_stack[k].node_level > (*_node_order)[node]) {
+        --k;
+      }
+      return level_stack[k].node_level;
+    }
+
+    void finalize(Arc arc) {
+      Node node = _digraph->target(arc);
+      _heap->push(node, (*_arc_order)[arc]);
+      _pred->set(node, arc);
+      while (!_heap->empty()) {
+        Node source = _heap->top();
+        _heap->pop();
+        _node_order->set(source, -1);
+        for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
+          if ((*_arc_order)[it] < 0) continue;
+          Node target = _digraph->target(it);
+          switch(_heap->state(target)) {
+          case Heap::PRE_HEAP:
+            _heap->push(target, (*_arc_order)[it]);
+            _pred->set(target, it);
+            break;
+          case Heap::IN_HEAP:
+            if ((*_arc_order)[it] < (*_heap)[target]) {
+              _heap->decrease(target, (*_arc_order)[it]);
+              _pred->set(target, it);
+            }
+            break;
+          case Heap::POST_HEAP:
+            break;
+          }
+        }
+        _arborescence->set((*_pred)[source], true);
+      }
+    }
+
+
+  public:
+
+    /// \name Named template parameters
+
+    /// @{
+
+    template <class T>
+    struct DefArborescenceMapTraits : public Traits {
+      typedef T ArborescenceMap;
+      static ArborescenceMap *createArborescenceMap(const Digraph &)
+      {
+        LEMON_ASSERT(false, "ArborescenceMap is not initialized");
+        return 0; // ignore warnings
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for
+    /// setting ArborescenceMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// ArborescenceMap type
+    template <class T>
+    struct DefArborescenceMap
+      : public MinCostArborescence<Digraph, CostMap,
+                                   DefArborescenceMapTraits<T> > {
+    };
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Digraph &)
+      {
+        LEMON_ASSERT(false, "PredMap is not initialized");
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for
+    /// setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting
+    /// PredMap type
+    template <class T>
+    struct DefPredMap
+      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
+    };
+
+    /// @}
+
+    /// \brief Constructor.
+    ///
+    /// \param _digraph The digraph the algorithm will run on.
+    /// \param _cost The cost map used by the algorithm.
+    MinCostArborescence(const Digraph& digraph, const CostMap& cost)
+      : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
+        _arborescence(0), local_arborescence(false),
+        _arc_order(0), _node_order(0), _cost_arcs(0),
+        _heap_cross_ref(0), _heap(0) {}
+
+    /// \brief Destructor.
+    ~MinCostArborescence() {
+      destroyStructures();
+    }
+
+    /// \brief Sets the arborescence map.
+    ///
+    /// Sets the arborescence map.
+    /// \return \c (*this)
+    MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
+      if (local_arborescence) {
+        delete _arborescence;
+      }
+      local_arborescence = false;
+      _arborescence = &m;
+      return *this;
+    }
+
+    /// \brief Sets the arborescence map.
+    ///
+    /// Sets the arborescence map.
+    /// \return \c (*this)
+    MinCostArborescence& predMap(PredMap& m) {
+      if (local_pred) {
+        delete _pred;
+      }
+      local_pred = false;
+      _pred = &m;
+      return *this;
+    }
+
+    /// \name Query Functions
+    /// The result of the %MinCostArborescence algorithm can be obtained
+    /// using these functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+
+    /// @{
+
+    /// \brief Returns a reference to the arborescence map.
+    ///
+    /// Returns a reference to the arborescence map.
+    const ArborescenceMap& arborescenceMap() const {
+      return *_arborescence;
+    }
+
+    /// \brief Returns true if the arc is in the arborescence.
+    ///
+    /// Returns true if the arc is in the arborescence.
+    /// \param arc The arc of the digraph.
+    /// \pre \ref run() must be called before using this function.
+    bool arborescence(Arc arc) const {
+      return (*_pred)[_digraph->target(arc)] == arc;
+    }
+
+    /// \brief Returns a reference to the pred map.
+    ///
+    /// Returns a reference to the pred map.
+    const PredMap& predMap() const {
+      return *_pred;
+    }
+
+    /// \brief Returns the predecessor arc of the given node.
+    ///
+    /// Returns the predecessor arc of the given node.
+    Arc pred(Node node) const {
+      return (*_pred)[node];
+    }
+
+    /// \brief Returns the cost of the arborescence.
+    ///
+    /// Returns the cost of the arborescence.
+    Value arborescenceValue() const {
+      Value sum = 0;
+      for (ArcIt it(*_digraph); it != INVALID; ++it) {
+        if (arborescence(it)) {
+          sum += (*_cost)[it];
+        }
+      }
+      return sum;
+    }
+
+    /// \brief Indicates that a node is reachable from the sources.
+    ///
+    /// Indicates that a node is reachable from the sources.
+    bool reached(Node node) const {
+      return (*_node_order)[node] != -3;
+    }
+
+    /// \brief Indicates that a node is processed.
+    ///
+    /// Indicates that a node is processed. The arborescence path exists
+    /// from the source to the given node.
+    bool processed(Node node) const {
+      return (*_node_order)[node] == -1;
+    }
+
+    /// \brief Returns the number of the dual variables in basis.
+    ///
+    /// Returns the number of the dual variables in basis.
+    int dualNum() const {
+      return _dual_variables.size();
+    }
+
+    /// \brief Returns the value of the dual solution.
+    ///
+    /// Returns the value of the dual solution. It should be
+    /// equal to the arborescence value.
+    Value dualValue() const {
+      Value sum = 0;
+      for (int i = 0; i < int(_dual_variables.size()); ++i) {
+        sum += _dual_variables[i].value;
+      }
+      return sum;
+    }
+
+    /// \brief Returns the number of the nodes in the dual variable.
+    ///
+    /// Returns the number of the nodes in the dual variable.
+    int dualSize(int k) const {
+      return _dual_variables[k].end - _dual_variables[k].begin;
+    }
+
+    /// \brief Returns the value of the dual variable.
+    ///
+    /// Returns the the value of the dual variable.
+    const Value& dualValue(int k) const {
+      return _dual_variables[k].value;
+    }
+
+    /// \brief Lemon iterator for get a dual variable.
+    ///
+    /// Lemon iterator for get a dual variable. This class provides
+    /// a common style lemon iterator which gives back a subset of
+    /// the nodes.
+    class DualIt {
+    public:
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for get the nodeset of the variable.
+      DualIt(const MinCostArborescence& algorithm, int variable)
+        : _algorithm(&algorithm)
+      {
+        _index = _algorithm->_dual_variables[variable].begin;
+        _last = _algorithm->_dual_variables[variable].end;
+      }
+
+      /// \brief Conversion to node.
+      ///
+      /// Conversion to node.
+      operator Node() const {
+        return _algorithm->_dual_node_list[_index];
+      }
+
+      /// \brief Increment operator.
+      ///
+      /// Increment operator.
+      DualIt& operator++() {
+        ++_index;
+        return *this;
+      }
+
+      /// \brief Validity checking
+      ///
+      /// Checks whether the iterator is invalid.
+      bool operator==(Invalid) const {
+        return _index == _last;
+      }
+
+      /// \brief Validity checking
+      ///
+      /// Checks whether the iterator is valid.
+      bool operator!=(Invalid) const {
+        return _index != _last;
+      }
+
+    private:
+      const MinCostArborescence* _algorithm;
+      int _index, _last;
+    };
+
+    /// @}
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...). \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then you can add several
+    /// source nodes with \ref addSource().
+    /// Finally \ref start() will perform the arborescence
+    /// computation.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures.
+    ///
+    void init() {
+      createStructures();
+      _heap->clear();
+      for (NodeIt it(*_digraph); it != INVALID; ++it) {
+        (*_cost_arcs)[it].arc = INVALID;
+        _node_order->set(it, -3);
+        _heap_cross_ref->set(it, Heap::PRE_HEAP);
+        _pred->set(it, INVALID);
+      }
+      for (ArcIt it(*_digraph); it != INVALID; ++it) {
+        _arborescence->set(it, false);
+        _arc_order->set(it, -1);
+      }
+      _dual_node_list.clear();
+      _dual_variables.clear();
+    }
+
+    /// \brief Adds a new source node.
+    ///
+    /// Adds a new source node to the algorithm.
+    void addSource(Node source) {
+      std::vector<Node> nodes;
+      nodes.push_back(source);
+      while (!nodes.empty()) {
+        Node node = nodes.back();
+        nodes.pop_back();
+        for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
+          Node target = _digraph->target(it);
+          if ((*_node_order)[target] == -3) {
+            (*_node_order)[target] = -2;
+            nodes.push_back(target);
+            queue.push_back(target);
+          }
+        }
+      }
+      (*_node_order)[source] = -1;
+    }
+
+    /// \brief Processes the next node in the priority queue.
+    ///
+    /// Processes the next node in the priority queue.
+    ///
+    /// \return The processed node.
+    ///
+    /// \warning The queue must not be empty!
+    Node processNextNode() {
+      Node node = queue.back();
+      queue.pop_back();
+      if ((*_node_order)[node] == -2) {
+        Arc arc = prepare(node);
+        Node source = _digraph->source(arc);
+        while ((*_node_order)[source] != -1) {
+          if ((*_node_order)[source] >= 0) {
+            arc = contract(source);
+          } else {
+            arc = prepare(source);
+          }
+          source = _digraph->source(arc);
+        }
+        finalize(arc);
+        level_stack.clear();
+      }
+      return node;
+    }
+
+    /// \brief Returns the number of the nodes to be processed.
+    ///
+    /// Returns the number of the nodes to be processed.
+    int queueSize() const {
+      return queue.size();
+    }
+
+    /// \brief Returns \c false if there are nodes to be processed.
+    ///
+    /// Returns \c false if there are nodes to be processed.
+    bool emptyQueue() const {
+      return queue.empty();
+    }
+
+    /// \brief Executes the algorithm.
+    ///
+    /// Executes the algorithm.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    ///\note mca.start() is just a shortcut of the following code.
+    ///\code
+    ///while (!mca.emptyQueue()) {
+    ///  mca.processNextNode();
+    ///}
+    ///\endcode
+    void start() {
+      while (!emptyQueue()) {
+        processNextNode();
+      }
+    }
+
+    /// \brief Runs %MinCostArborescence algorithm from node \c s.
+    ///
+    /// This method runs the %MinCostArborescence algorithm from
+    /// a root node \c s.
+    ///
+    /// \note mca.run(s) is just a shortcut of the following code.
+    /// \code
+    /// mca.init();
+    /// mca.addSource(s);
+    /// mca.start();
+    /// \endcode
+    void run(Node node) {
+      init();
+      addSource(node);
+      start();
+    }
+
+    ///@}
+
+  };
+
+  /// \ingroup spantree
+  ///
+  /// \brief Function type interface for MinCostArborescence algorithm.
+  ///
+  /// Function type interface for MinCostArborescence algorithm.
+  /// \param digraph The Digraph that the algorithm runs on.
+  /// \param cost The CostMap of the arcs.
+  /// \param source The source of the arborescence.
+  /// \retval arborescence The bool ArcMap which stores the arborescence.
+  /// \return The cost of the arborescence.
+  ///
+  /// \sa MinCostArborescence
+  template <typename Digraph, typename CostMap, typename ArborescenceMap>
+  typename CostMap::Value minCostArborescence(const Digraph& digraph,
+                                              const CostMap& cost,
+                                              typename Digraph::Node source,
+                                              ArborescenceMap& arborescence) {
+    typename MinCostArborescence<Digraph, CostMap>
+      ::template DefArborescenceMap<ArborescenceMap>
+      ::Create mca(digraph, cost);
+    mca.arborescenceMap(arborescence);
+    mca.run(source);
+    return mca.arborescenceValue();
+  }
+
+}
+
+#endif
Index: lemon/preflow.h
===================================================================
--- lemon/preflow.h	(revision 440)
+++ lemon/preflow.h	(revision 519)
@@ -32,11 +32,11 @@
   ///
   /// Default traits class of Preflow class.
-  /// \tparam _Digraph Digraph type.
-  /// \tparam _CapacityMap Capacity map type.
-  template <typename _Digraph, typename _CapacityMap>
+  /// \tparam GR Digraph type.
+  /// \tparam CM Capacity map type.
+  template <typename GR, typename CM>
   struct PreflowDefaultTraits {
 
     /// \brief The type of the digraph the algorithm runs on.
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that stores the arc capacities.
@@ -44,5 +44,5 @@
     /// The type of the map that stores the arc capacities.
     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef _CapacityMap CapacityMap;
+    typedef CM CapacityMap;
 
     /// \brief The type of the flow values.
@@ -105,13 +105,13 @@
   /// second phase constructs a feasible maximum flow on each arc.
   ///
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  /// \tparam _CapacityMap The type of the capacity map. The default map
-  /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// \tparam CM The type of the capacity map. The default map
+  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _CapacityMap, typename _Traits>
+  template <typename GR, typename CM, typename TR>
 #else
-  template <typename _Digraph,
-            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
-            typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
+  template <typename GR,
+            typename CM = typename GR::template ArcMap<int>,
+            typename TR = PreflowDefaultTraits<GR, CM> >
 #endif
   class Preflow {
@@ -119,5 +119,5 @@
 
     ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
-    typedef _Traits Traits;
+    typedef TR Traits;
     ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
Index: lemon/soplex.cc
===================================================================
--- lemon/soplex.cc	(revision 462)
+++ lemon/soplex.cc	(revision 527)
@@ -20,5 +20,5 @@
 #include <lemon/soplex.h>
 
-#include <soplex/soplex.h>
+#include <soplex.h>
 
 
Index: m4/lx_check_soplex.m4
===================================================================
--- m4/lx_check_soplex.m4	(revision 457)
+++ m4/lx_check_soplex.m4	(revision 527)
@@ -21,5 +21,5 @@
       SOPLEX_CXXFLAGS="-I$with_soplex_includedir"
     elif test x"$with_soplex" != x"yes"; then
-      SOPLEX_CXXFLAGS="-I$with_soplex/include"
+      SOPLEX_CXXFLAGS="-I$with_soplex/src"
     fi
 
@@ -39,5 +39,5 @@
 
     lx_soplex_test_prog='
-      #include <soplex/soplex.h>
+      #include <soplex.h>
 
       int main(int argc, char** argv)
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 506)
+++ test/CMakeLists.txt	(revision 513)
@@ -30,4 +30,5 @@
   maps_test
   max_matching_test
+  min_cost_arborescence_test
   path_test
   preflow_test
Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 506)
+++ test/Makefile.am	(revision 513)
@@ -26,4 +26,5 @@
 	test/maps_test \
 	test/max_matching_test \
+	test/min_cost_arborescence_test \
 	test/path_test \
 	test/preflow_test \
@@ -67,4 +68,5 @@
 test_mip_test_SOURCES = test/mip_test.cc
 test_max_matching_test_SOURCES = test/max_matching_test.cc
+test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc
Index: test/euler_test.cc
===================================================================
--- test/euler_test.cc	(revision 506)
+++ test/euler_test.cc	(revision 517)
@@ -26,9 +26,9 @@
 void checkDiEulerIt(const Digraph& g)
 {
-  typename Digraph::template ArcMap<int> visitationNumber(g);
+  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
 
   DiEulerIt<Digraph> e(g);
   typename Digraph::Node firstNode = g.source(e);
-  typename Digraph::Node lastNode;
+  typename Digraph::Node lastNode = g.target(e);
 
   for (; e != INVALID; ++e)
@@ -54,9 +54,9 @@
 void checkEulerIt(const Graph& g)
 {
-  typename Graph::template EdgeMap<int> visitationNumber(g);
+  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
 
   EulerIt<Graph> e(g);
   typename Graph::Node firstNode = g.u(e);
-  typename Graph::Node lastNode;
+  typename Graph::Node lastNode = g.v(e);
 
   for (; e != INVALID; ++e)
Index: test/min_cost_arborescence_test.cc
===================================================================
--- test/min_cost_arborescence_test.cc	(revision 512)
+++ test/min_cost_arborescence_test.cc	(revision 512)
@@ -0,0 +1,146 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 <iostream>
+#include <set>
+#include <vector>
+#include <iterator>
+
+#include <lemon/smart_graph.h>
+#include <lemon/min_cost_arborescence.h>
+#include <lemon/lgf_reader.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+using namespace std;
+
+const char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "8\n"
+  "9\n"
+  "@arcs\n"
+  "     label  cost\n"
+  "1 8  0      107\n"
+  "0 3  1      70\n"
+  "2 1  2      46\n"
+  "4 1  3      28\n"
+  "4 4  4      91\n"
+  "3 9  5      76\n"
+  "9 8  6      61\n"
+  "8 1  7      39\n"
+  "9 8  8      74\n"
+  "8 0  9      39\n"
+  "4 3  10     45\n"
+  "2 2  11     34\n"
+  "0 1  12     100\n"
+  "6 3  13     95\n"
+  "4 1  14     22\n"
+  "1 1  15     31\n"
+  "7 2  16     51\n"
+  "2 6  17     29\n"
+  "8 3  18     115\n"
+  "6 9  19     32\n"
+  "1 1  20     60\n"
+  "0 3  21     40\n"
+  "@attributes\n"
+  "source 0\n";
+
+int main() {
+  typedef SmartDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+
+  typedef Digraph::ArcMap<double> CostMap;
+
+  Digraph digraph;
+  CostMap cost(digraph);
+  Node source;
+
+  std::istringstream is(test_lgf);
+  digraphReader(digraph, is).
+    arcMap("cost", cost).
+    node("source", source).run();
+
+  MinCostArborescence<Digraph, CostMap> mca(digraph, cost);
+  mca.run(source);
+
+  vector<pair<double, set<Node> > > dualSolution(mca.dualNum());
+
+  for (int i = 0; i < mca.dualNum(); ++i) {
+    dualSolution[i].first = mca.dualValue(i);
+    for (MinCostArborescence<Digraph, CostMap>::DualIt it(mca, i);
+         it != INVALID; ++it) {
+      dualSolution[i].second.insert(it);
+    }
+  }
+
+  for (ArcIt it(digraph); it != INVALID; ++it) {
+    if (mca.reached(digraph.source(it))) {
+      double sum = 0.0;
+      for (int i = 0; i < int(dualSolution.size()); ++i) {
+        if (dualSolution[i].second.find(digraph.target(it))
+            != dualSolution[i].second.end() &&
+            dualSolution[i].second.find(digraph.source(it))
+            == dualSolution[i].second.end()) {
+          sum += dualSolution[i].first;
+        }
+      }
+      if (mca.arborescence(it)) {
+        check(sum == cost[it], "INVALID DUAL");
+      }
+      check(sum <= cost[it], "INVALID DUAL");
+    }
+  }
+
+
+  check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
+
+  check(mca.reached(source), "INVALID ARBORESCENCE");
+  for (ArcIt a(digraph); a != INVALID; ++a) {
+    check(!mca.reached(digraph.source(a)) ||
+          mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
+  }
+
+  for (NodeIt n(digraph); n != INVALID; ++n) {
+    if (!mca.reached(n)) continue;
+    int cnt = 0;
+    for (InArcIt a(digraph, n); a != INVALID; ++a) {
+      if (mca.arborescence(a)) {
+        check(mca.pred(n) == a, "INVALID ARBORESCENCE");
+        ++cnt;
+      }
+    }
+    check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
+  }
+
+  Digraph::ArcMap<bool> arborescence(digraph);
+  check(mca.arborescenceValue() ==
+        minCostArborescence(digraph, cost, source, arborescence),
+        "WRONG FUNCTION");
+
+  return 0;
+}
Index: tools/CMakeLists.txt
===================================================================
--- tools/CMakeLists.txt	(revision 511)
+++ tools/CMakeLists.txt	(revision 511)
@@ -0,0 +1,28 @@
+INCLUDE_DIRECTORIES(
+  ${CMAKE_SOURCE_DIR}
+  ${CMAKE_BINARY_DIR}
+)
+
+LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
+
+ADD_EXECUTABLE(lgf-gen lgf-gen.cc)
+TARGET_LINK_LIBRARIES(lgf-gen lemon)
+
+ADD_EXECUTABLE(dimacs-to-lgf dimacs-to-lgf.cc)
+TARGET_LINK_LIBRARIES(dimacs-to-lgf lemon)
+
+ADD_EXECUTABLE(dimacs-solver dimacs-solver.cc)
+TARGET_LINK_LIBRARIES(dimacs-solver lemon)
+
+INSTALL(
+  TARGETS lgf-gen dimacs-to-lgf dimacs-solver
+  RUNTIME DESTINATION bin
+  COMPONENT bin
+)
+
+IF(NOT WIN32)
+  INSTALL(
+    FILES ${CMAKE_CURRENT_SOURCE_DIR}/lemon-0.x-to-1.x.sh
+    RUNTIME DESTINATION bin
+    COMPONENT bin)
+ENDIF(NOT WIN32)
Index: tools/Makefile.am
===================================================================
--- tools/Makefile.am	(revision 507)
+++ tools/Makefile.am	(revision 510)
@@ -2,4 +2,5 @@
 
 bin_PROGRAMS += \
+	tools/dimacs-solver \
 	tools/dimacs-to-lgf \
 	tools/lgf-gen
@@ -9,4 +10,5 @@
 endif WANT_TOOLS
 
+tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc
 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
 tools_lgf_gen_SOURCES = tools/lgf-gen.cc
Index: tools/dimacs-solver.cc
===================================================================
--- tools/dimacs-solver.cc	(revision 518)
+++ tools/dimacs-solver.cc	(revision 518)
@@ -0,0 +1,226 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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.
+ *
+ */
+
+///\ingroup tools
+///\file
+///\brief DIMACS problem solver.
+///
+/// This program solves various problems given in DIMACS format.
+///
+/// See
+/// \verbatim
+///  dimacs-solver --help
+/// \endverbatim
+/// for more info on usage.
+///
+
+#include <iostream>
+#include <fstream>
+#include <cstring>
+
+#include <lemon/smart_graph.h>
+#include <lemon/dimacs.h>
+#include <lemon/lgf_writer.h>
+#include <lemon/time_measure.h>
+
+#include <lemon/arg_parser.h>
+#include <lemon/error.h>
+
+#include <lemon/dijkstra.h>
+#include <lemon/preflow.h>
+#include <lemon/max_matching.h>
+
+using namespace lemon;
+typedef SmartDigraph Digraph;
+DIGRAPH_TYPEDEFS(Digraph);
+typedef SmartGraph Graph;
+
+template<class Value>
+void solve_sp(ArgParser &ap, std::istream &is, std::ostream &,
+              DimacsDescriptor &desc)
+{
+  bool report = !ap.given("q");
+  Digraph g;
+  Node s;
+  Digraph::ArcMap<Value> len(g);
+  Timer t;
+  t.restart();
+  readDimacsSp(is, g, len, s, desc);
+  if(report) std::cerr << "Read the file: " << t << '\n';
+  t.restart();
+  Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len);
+  if(report) std::cerr << "Setup Dijkstra class: " << t << '\n';
+  t.restart();
+  dij.run(s);
+  if(report) std::cerr << "Run Dijkstra: " << t << '\n';
+}
+
+template<class Value>
+void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
+              DimacsDescriptor &desc)
+{
+  bool report = !ap.given("q");
+  Digraph g;
+  Node s,t;
+  Digraph::ArcMap<Value> cap(g);
+  Timer ti;
+  ti.restart();
+  readDimacsMax(is, g, cap, s, t, desc);
+  if(report) std::cerr << "Read the file: " << ti << '\n';
+  ti.restart();
+  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);
+  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';
+  ti.restart();
+  pre.run();
+  if(report) std::cerr << "Run Preflow: " << ti << '\n';
+  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  
+}
+
+void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
+              DimacsDescriptor &desc)
+{
+  bool report = !ap.given("q");
+  Graph g;
+  Timer ti;
+  ti.restart();
+  readDimacsMat(is, g, desc);
+  if(report) std::cerr << "Read the file: " << ti << '\n';
+  ti.restart();
+  MaxMatching<Graph> mat(g);
+  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';
+  ti.restart();
+  mat.run();
+  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
+  if(report) std::cerr << "\nCardinality of max matching: "
+                       << mat.matchingSize() << '\n';  
+}
+
+
+template<class Value>
+void solve(ArgParser &ap, std::istream &is, std::ostream &os,
+           DimacsDescriptor &desc)
+{
+  switch(desc.type)
+    {
+    case DimacsDescriptor::MIN:
+      std::cerr <<
+        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
+      break;
+    case DimacsDescriptor::MAX:
+      solve_max<Value>(ap,is,os,desc);
+      break;
+    case DimacsDescriptor::SP:
+      solve_sp<Value>(ap,is,os,desc);
+      break;
+    case DimacsDescriptor::MAT:
+      solve_mat(ap,is,os,desc);
+      break;
+    default:
+      break;
+    }
+}
+
+int main(int argc, const char *argv[]) {
+  typedef SmartDigraph Digraph;
+
+  typedef Digraph::Arc Arc;
+
+  std::string inputName;
+  std::string outputName;
+
+  ArgParser ap(argc, argv);
+  ap.other("[INFILE [OUTFILE]]",
+           "If either the INFILE or OUTFILE file is missing the standard\n"
+           "     input/output will be used instead.")
+    .boolOption("q", "Do not print any report")
+    .boolOption("int","Use 'int' for capacities, costs etc. (default)")
+    .optionGroup("datatype","int")
+#ifdef HAVE_LONG_LONG
+    .boolOption("long","Use 'long long' for capacities, costs etc.")
+    .optionGroup("datatype","long")
+#endif
+    .boolOption("double","Use 'double' for capacities, costs etc.")
+    .optionGroup("datatype","double")
+    .boolOption("ldouble","Use 'long double' for capacities, costs etc.")
+    .optionGroup("datatype","ldouble")
+    .onlyOneGroup("datatype")
+    .run();
+
+  std::ifstream input;
+  std::ofstream output;
+
+  switch(ap.files().size())
+    {
+    case 2:
+      output.open(ap.files()[1].c_str());
+      if (!output) {
+        throw IoError("Cannot open the file for writing", ap.files()[1]);
+      }
+    case 1:
+      input.open(ap.files()[0].c_str());
+      if (!input) {
+        throw IoError("File cannot be found", ap.files()[0]);
+      }
+    case 0:
+      break;
+    default:
+      std::cerr << ap.commandName() << ": too many arguments\n";
+      return 1;
+    }
+  std::istream& is = (ap.files().size()<1 ? std::cin : input);
+  std::ostream& os = (ap.files().size()<2 ? std::cout : output);
+
+  DimacsDescriptor desc = dimacsType(is);
+  
+  if(!ap.given("q"))
+    {
+      std::cout << "Problem type: ";
+      switch(desc.type)
+        {
+        case DimacsDescriptor::MIN:
+          std::cout << "min";
+          break;
+        case DimacsDescriptor::MAX:
+          std::cout << "max";
+          break;
+        case DimacsDescriptor::SP:
+          std::cout << "sp";
+        case DimacsDescriptor::MAT:
+          std::cout << "mat";
+          break;
+        default:
+          exit(1);
+          break;
+        }
+      std::cout << "\nNum of nodes: " << desc.nodeNum;
+      std::cout << "\nNum of arcs:  " << desc.edgeNum;
+      std::cout << "\n\n";
+    }
+    
+  if(ap.given("double"))
+    solve<double>(ap,is,os,desc);
+  else if(ap.given("ldouble"))
+    solve<long double>(ap,is,os,desc);
+#ifdef HAVE_LONG_LONG
+  else if(ap.given("long"))
+    solve<long long>(ap,is,os,desc);
+#endif
+  else solve<int>(ap,is,os,desc);
+
+  return 0;
+}
