Changes in / [206:4e22275a2b52:207:574b963d0275] in lemon

Files:

• demo/arg_parser_demo.cc (modified) (2 diffs)
• demo/lgf_demo.cc (modified) (3 diffs)
• doc/groups.dox (modified) (1 diff)
• doc/lgf.dox (modified) (3 diffs)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/arg_parser.h (modified) (14 diffs)
• lemon/concepts/heap.h (modified) (3 diffs)
• lemon/graph_utils.h (modified) (3 diffs)
• lemon/kruskal.h (modified) (4 diffs)
• lemon/lgf_reader.h (modified) (44 diffs)
• lemon/lgf_writer.h (modified) (30 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (3 diffs)
• test/graph_copy_test.cc (added)
• test/heap_test.cc (modified) (2 diffs)
• test/heap_test.h (deleted)

demo/arg_parser_demo.cc

@@ -30 +30 @@
 int main(int argc, const char **argv)
 {
-  ArgParser ap(argc,argv);
+  // Initialize the argument parser
+  ArgParser ap(argc, argv);
   int i;
   std::string s;
-  double d;
-  bool b,sil;
-  bool g1,g2,g3;
-  ap.refOption("n", "An integer input.", i, true)
-    .refOption("val", "A double input.", d)
-    .doubleOption("val2", "A double input.", d)
-    .synonym("vals","val")
-    .refOption("name", "A string input.", s)
-    .refOption("f", "A switch.", b)
-    .refOption("nohelp", "", sil)
-    .refOption("gra","Choice A",g1)
-    .refOption("grb","Choice B",g2)
-    .refOption("grc","Choice C",g3)
-    .optionGroup("gr","gra")
-    .optionGroup("gr","grb")
-    .optionGroup("gr","grc")
-    .mandatoryGroup("gr")
-    .onlyOneGroup("gr")
-    .other("infile","The input file.")
+  double d = 1.0;
+  bool b, nh;
+  bool g1, g2, g3;
+
+  // Add a mandatory integer option with storage reference
+  ap.refOption("n", "An integer input.", i, true);
+  // Add a double option with storage reference (the default value is 1.0)
+  ap.refOption("val", "A double input.", d);
+  // Add a double option without storage reference (the default value is 3.14)
+  ap.doubleOption("val2", "A double input.", 3.14);
+  // Set synonym for -val option
+  ap.synonym("vals", "val");
+  // Add a string option
+  ap.refOption("name", "A string input.", s);
+  // Add bool options
+  ap.refOption("f", "A switch.", b)
+    .refOption("nohelp", "", nh)
+    .refOption("gra", "Choice A", g1)
+    .refOption("grb", "Choice B", g2)
+    .refOption("grc", "Choice C", g3);
+  // Bundle -gr* options into a group
+  ap.optionGroup("gr", "gra")
+    .optionGroup("gr", "grb")
+    .optionGroup("gr", "grc");
+  // Set the group mandatory
+  ap.mandatoryGroup("gr");
+  // Set the options of the group exclusive (only one option can be given)
+  ap.onlyOneGroup("gr");
+  // Add non-parsed arguments (e.g. input files)
+  ap.other("infile", "The input file.")
     .other("...");
   
+  // Perform the parsing process
+  // (in case of any error it terminates the program)
   ap.parse();
 
+  // Check each option if it has been given and print its value
   std::cout << "Parameters of '" << ap.commandName() << "':\n";
 
-  if(ap.given("n")) std::cout << "  Value of -n: " << i << std::endl;
+  std::cout << "  Value of -n: " << i << std::endl;
   if(ap.given("val")) std::cout << "  Value of -val: " << d << std::endl;
+  if(ap.given("val2")) {
+    d = ap["val2"];
+    std::cout << "  Value of -val2: " << d << std::endl;
+  }
   if(ap.given("name")) std::cout << "  Value of -name: " << s << std::endl;
   if(ap.given("f")) std::cout << "  -f is given\n";
-  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << sil << std::endl;
+  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << nh << std::endl;
   if(ap.given("gra")) std::cout << "  -gra is given\n";
   if(ap.given("grb")) std::cout << "  -grb is given\n";
   if(ap.given("grc")) std::cout << "  -grc is given\n";
-                                     
+  
   switch(ap.files().size()) {
   case 0:
@@ -81 +100 @@
     std::cout << "    '" << ap.files()[i] << "'\n";
   
+  return 0;
 }

demo/lgf_demo.cc

@@ -21 +21 @@
 ///\brief Demonstrating graph input and output
 ///
-/// This program gives an example of how to load a directed graph from
-/// an \ref lgf-format "LGF" file with the \ref lemon::DigraphReader
-/// "DigraphReader" class.
+/// This program gives an example of how to read and write a digraph
+/// and additional maps from/to a stream or a file using the 
+/// \ref lgf-format "LGF" format.
 ///
 /// The \c "digraph.lgf" file:
 /// \include digraph.lgf
 ///
-/// And the program which reads it:
+/// And the program which reads it and prints the digraph to the
+/// standard output:
 /// \include lgf_demo.cc
 
@@ -35 +36 @@
 #include <lemon/lgf_reader.h>
 #include <lemon/lgf_writer.h>
-#include <lemon/random.h>
-
 
 using namespace lemon;
@@ -44 +43 @@
   SmartDigraph::ArcMap<int> cap(g);
   SmartDigraph::Node s, t;
+  
+  try {
+    digraphReader("digraph.lgf", g). // read the directed graph into g
+      arcMap("capacity", cap).       // read the 'capacity' arc map into cap
+      node("source", s).             // read 'source' node to s
+      node("target", t).             // read 'target' node to t
+      run();
+  } catch (DataFormatError& error) { // check if there was any error
+    std::cerr << "Error: " << error.what() << std::endl;
+    return -1;
+  }
 
-  digraphReader("digraph.lgf", g). // read the directeg graph into g
-    arcMap("capacity", cap).       // read the 'capacity' arc map into cap
-    node("source", s).             // read 'source' node to s
-    node("target", t).             // read 'target' node to t
-    run();
-
-  std::cout << "Digraph read from 'digraph.lgf'" << std::endl;
+  std::cout << "A digraph is read from 'digraph.lgf'." << std::endl;
   std::cout << "Number of nodes: " << countNodes(g) << std::endl;
   std::cout << "Number of arcs: " << countArcs(g) << std::endl;

doc/groups.dox

@@ -476 +476 @@
 @defgroup lemon_io Lemon Input-Output
 @ingroup io_group
-\brief Reading and writing LEMON format
-
-This group describes methods for reading and writing LEMON format. 
-You can find more about this format on the \ref graph-io-page "Graph Input-Output"
-tutorial pages.
+\brief Reading and writing \ref lgf-format "Lemon Graph Format".
+
+This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format".
 */
 

doc/lgf.dox

@@ -47 +47 @@
 
 The \c \@nodes section describes a set of nodes and associated
-maps. The first is a header line, it columns are the names of the
+maps. The first is a header line, its columns are the names of the
 maps appearing in the following lines.
 One of the maps must be called \c
@@ -65 +65 @@
 
 The \c \@arcs section is very similar to the \c \@nodes section,
-it again starts with a header line describing the names of the arc,
+it again starts with a header line describing the names of the maps,
 but the \c "label" map is not obligatory here. The following lines
 describe the arcs. The first two tokens of each line are
@@ -79 +79 @@
 \endcode
 
-The \c \@edges is just a synonym of \c \@arcs.
+The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
+also store the edge set of an undirected graph. In such case there is
+a conventional method for store arc maps in the file, if two columns
+has the same caption with \c '+' and \c '-' prefix, then these columns
+can be regarded as the values of an arc map.
 
 The \c \@attributes section contains key-value pairs, each line
-consists of two tokens, an attribute name, and then an attribute value.
+consists of two tokens, an attribute name, and then an attribute
+value. The value of the attribute could be also a label value of a
+node or an edge, or even an edge label prefixed with \c '+' or \c '-',
+which regards to the forward or backward directed arc of the
+corresponding edge.
 
 \code

lemon/Makefile.am

@@ -33 +33 @@
         lemon/kruskal.h \
         lemon/lgf_reader.h \
+        lemon/lgf_writer.h \
         lemon/list_graph.h \
         lemon/maps.h \
@@ -60 +61 @@
         lemon/concepts/digraph.h \
         lemon/concepts/graph.h \
+        lemon/concepts/graph_components.h \
         lemon/concepts/heap.h \
         lemon/concepts/maps.h \
-        lemon/concepts/path.h \
-        lemon/concepts/graph_components.h
+        lemon/concepts/path.h

lemon/arg_parser.h

@@ -119 +119 @@
   public:
 
-    ///\e
+    ///Constructor
     ArgParser(int argc, const char **argv);
 
     ~ArgParser();
 
+    ///\name Options
+    ///
+
+    ///@{
+
     ///Add a new integer type option
 
+    ///Add a new integer type option.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -136 +142 @@
     ///Add a new floating point type option
 
+    ///Add a new floating point type option.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -146 +153 @@
     ///Add a new bool type option
 
+    ///Add a new bool type option.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -157 +165 @@
     ///Add a new string type option
 
+    ///Add a new string type option.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -165 +174 @@
                       std::string value="", bool obl=false);
 
-    ///\name Options with external storage
+    ///Give help string for non-parsed arguments.
+
+    ///With this function you can give help string for non-parsed arguments.
+    ///The parameter \c name will be printed in the short usage line, while
+    ///\c help gives a more detailed description.
+    ArgParser &other(const std::string &name,
+                     const std::string &help="");
+    
+    ///@}
+
+    ///\name Options with External Storage
     ///Using this functions, the value of the option will be directly written
     ///into a variable once the option appears in the command line.
@@ -173 +192 @@
     ///Add a new integer type option with a storage reference
 
+    ///Add a new integer type option with a storage reference.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -183 +203 @@
     ///Add a new floating type option with a storage reference
 
+    ///Add a new floating type option with a storage reference.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -193 +214 @@
     ///Add a new bool type option with a storage reference
 
+    ///Add a new bool type option with a storage reference.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -204 +226 @@
     ///Add a new string type option with a storage reference
 
+    ///Add a new string type option with a storage reference.
     ///\param name The name of the option. The leading '-' must be omitted.
     ///\param help A help string.
@@ -219 +242 @@
     ///@{
 
-    ///Boundle some options into a group
+    ///Bundle some options into a group
 
     /// You can group some option by calling this function repeatedly for each
@@ -231 +254 @@
 
     ///If you call this function for a group, than at most one of them can be
-    ///given at the same time
+    ///given at the same time.
     ArgParser &onlyOneGroup(const std::string &group);
   
@@ -248 +271 @@
     
     ///@}
-
-    ///Give help string for non-parsed arguments.
-
-    ///With this function you can give help string for non-parsed arguments.
-    ///The parameter \c name will be printed in the short usage line, while
-    ///\c help gives a more detailed description.
-    ArgParser &other(const std::string &name,
-                     const std::string &help="");
-    
-    ///Give back the non-option type arguments.
-
-    ///Give back a reference to a vector consisting of the program arguments
-    ///not starting with a '-' character.
-    std::vector<std::string> &files() { return _file_args; }
-
-    ///Give back the command name (the 0th argument)
-    const std::string &commandName() { return _command_name; }
 
     void show(std::ostream &os,Opts::iterator i);
@@ -287 +293 @@
     }
     
+    ///Give back the command name (the 0th argument)
+    const std::string &commandName() { return _command_name; }
+
     ///Check if an opion has been given to the command.
     bool given(std::string op) 
@@ -361 +370 @@
       return RefType(*this, n);
     }    
+
+    ///Give back the non-option type arguments.
+
+    ///Give back a reference to a vector consisting of the program arguments
+    ///not starting with a '-' character.
+    std::vector<std::string> &files() { return _file_args; }
  
   };
 }
 
-    
-
-#endif // LEMON_MAIN_PARAMS
+#endif // LEMON_ARG_PARSER

lemon/concepts/heap.h

@@ -182 +182 @@
           Item item;
           Prio prio;
-          State state;
           item=Item();
           prio=Prio();
           ignore_unused_variable_warning(item);
           ignore_unused_variable_warning(prio);
-          ignore_unused_variable_warning(state);
 
           OwnItem own_item;
@@ -204 +202 @@
           
           int s = heap.size();
+          ignore_unused_variable_warning(s);
           bool e = heap.empty();
+          ignore_unused_variable_warning(e);
 
           prio = heap.prio();
@@ -228 +228 @@
           heap.clear();
 
-          state = heap.state(item);
-          heap.state(item, state);
-          state = heap.state(own_item);
+          own_state = heap.state(own_item);
           heap.state(own_item, own_state);
 
-          state = _Heap::PRE_HEAP;
-          state = _Heap::IN_HEAP;
-          state = _Heap::POST_HEAP;
           own_state = _Heap::PRE_HEAP;
           own_state = _Heap::IN_HEAP;

lemon/graph_utils.h

@@ -603 +603 @@
         for (typename From::ArcIt it(from); it != INVALID; ++it) {
           arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
-                                          nodeRefMap[from.target(it)]);
+                                    nodeRefMap[from.target(it)]);
         }
       }
@@ -629 +629 @@
         }
         for (typename From::EdgeIt it(from); it != INVALID; ++it) {
-          edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
-                                       nodeRefMap[from.target(it)]);
+          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 
+                                      nodeRefMap[from.v(it)]);
         }
       }
@@ -926 +926 @@
 
       Value operator[](const Key& key) const {
-        bool forward = 
-          (_from.direction(key) == 
-           (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
+        bool forward = _from.u(key) != _from.v(key) ?
+          _node_ref[_from.source(key)] == 
+          _to.source(_to.direct(_edge_ref[key], true)) :
+          _from.direction(key);
         return _to.direct(_edge_ref[key], forward); 
       }

lemon/kruskal.h

@@ -33 +33 @@
 ///\ingroup spantree
 ///\file
-///\brief Kruskal's algorithm to compute a minimum cost tree
+///\brief Kruskal's algorithm to compute a minimum cost spanning tree
 ///
-///Kruskal's algorithm to compute a minimum cost tree.
+///Kruskal's algorithm to compute a minimum cost spanning tree.
 ///
 
@@ -252 +252 @@
   /// \ingroup spantree
   ///
-  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
-  ///
-  /// This function runs Kruskal's algorithm to find a minimum cost tree.
+  /// \brief Kruskal algorithm to find a minimum cost spanning tree of
+  /// a graph.
+  ///
+  /// This function runs Kruskal's algorithm to find a minimum cost 
+  /// spanning tree.
   /// Due to some C++ hacking, it accepts various input and output types.
   ///
@@ -263 +265 @@
   /// undirected by disregarding the direction of the arcs.
   ///
-  /// \param in This object is used to describe the arc costs. It can be one
-  /// of the following choices.
+  /// \param in This object is used to describe the arc/edge costs. 
+  /// It can be one of the following choices.
   /// - An STL compatible 'Forward Container' with
-  /// <tt>std::pair<GR::Edge,X></tt> or
-  /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where
-  /// \c X is the type of the costs. The pairs indicates the arcs
+  /// <tt>std::pair<GR::Arc,X></tt> or
+  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
+  /// \c X is the type of the costs. The pairs indicates the arcs/edges
   /// along with the assigned cost. <em>They must be in a
   /// cost-ascending order.</em>
-  /// - Any readable Arc map. The values of the map indicate the arc costs.
-  ///
-  /// \retval out Here we also have a choise.
-  /// - It can be a writable \c bool arc map.  After running the
-  /// algorithm this will contain the found minimum cost spanning
-  /// tree: the value of an arc will be set to \c true if it belongs
+  /// - Any readable arc/edge map. The values of the map indicate the 
+  /// arc/edge costs.
+  ///
+  /// \retval out Here we also have a choice.
+  /// - It can be a writable \c bool arc/edge map. After running the
+  /// algorithm it will contain the found minimum cost spanning
+  /// tree: the value of an arc/edge will be set to \c true if it belongs
   /// to the tree, otherwise it will be set to \c false. The value of
-  /// each arc will be set exactly once.
+  /// each arc/edge will be set exactly once.
   /// - It can also be an iteraror of an STL Container with
-  /// <tt>GR::Edge</tt> or <tt>GR::Arc</tt> as its
+  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
   /// <tt>value_type</tt>.  The algorithm copies the elements of the
   /// found tree into this sequence.  For example, if we know that the
@@ -291 +294 @@
   /// Or if we don't know in advance the size of the tree, we can
   /// write this.  
-  ///\code std::vector<Arc> tree;
+  ///\code
+  /// std::vector<Arc> tree;
   /// kruskal(g,cost,std::back_inserter(tree)); 
   ///\endcode
   ///
-  /// \return The total cost of the found tree.
-  ///
-  /// \warning If kruskal runs on an be consistent of using the same
+  /// \return The total cost of the found spanning tree.
+  ///
+  /// \warning If Kruskal runs on an be consistent of using the same
   /// Arc type for input and output.
   ///

lemon/lgf_reader.h

@@ -19 +19 @@
 ///\ingroup lemon_io
 ///\file
-///\brief Lemon Graph Format reader.
+///\brief \ref lgf-format "Lemon Graph Format" reader.
 
 
@@ -196 +196 @@
     };
 
-    bool isWhiteSpace(char c) {
+    inline bool isWhiteSpace(char c) {
       return c == ' ' || c == '\t' || c == '\v' || 
         c == '\n' || c == '\r' || c == '\f'; 
     }
     
-    bool isOct(char c) {
+    inline bool isOct(char c) {
       return '0' <= c && c <='7'; 
     }
     
-    int valueOct(char c) {
+    inline int valueOct(char c) {
       LEMON_ASSERT(isOct(c), "The character is not octal.");
       return c - '0';
     }
 
-    bool isHex(char c) {
+    inline bool isHex(char c) {
       return ('0' <= c && c <= '9') || 
         ('a' <= c && c <= 'z') || 
@@ -216 +216 @@
     }
     
-    int valueHex(char c) {
+    inline int valueHex(char c) {
       LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
       if ('0' <= c && c <= '9') return c - '0';
@@ -223 +223 @@
     }
 
-    bool isIdentifierFirstChar(char c) {
+    inline bool isIdentifierFirstChar(char c) {
       return ('a' <= c && c <= 'z') ||
         ('A' <= c && c <= 'Z') || c == '_';
     }
 
-    bool isIdentifierChar(char c) {
+    inline bool isIdentifierChar(char c) {
       return isIdentifierFirstChar(c) ||
         ('0' <= c && c <= '9');
     }
 
-    char readEscape(std::istream& is) {
+    inline char readEscape(std::istream& is) {
       char c;
       if (!is.get(c))
@@ -285 +285 @@
     }
     
-    std::istream& readToken(std::istream& is, std::string& str) {
+    inline std::istream& readToken(std::istream& is, std::string& str) {
       std::ostringstream os;
 
@@ -401 +401 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief LGF reader for directed graphs
+  /// \brief \ref lgf-format "LGF" reader for directed graphs
   ///
   /// This utility reads an \ref lgf-format "LGF" file.
@@ -411 +411 @@
   /// with the \c nodeMap() or \c arcMap() members. An optional
   /// converter parameter can also be added as a standard functor
-  /// converting from std::string to the value type of the map. If it
+  /// converting from \c std::string to the value type of the map. If it
   /// is set, it will determine how the tokens in the file should be
-  /// is converted to the map's value type. If the functor is not set,
+  /// converted to the value type of the map. If the functor is not set,
   /// then a default conversion will be used. One map can be read into
   /// multiple map objects at the same time. The \c attribute(), \c
@@ -420 +420 @@
   ///
   ///\code
-  ///     DigraphReader<Digraph>(std::cin, digraph).
-  ///       nodeMap("coordinates", coord_map).
-  ///       arcMap("capacity", cap_map).
-  ///       node("source", src).
-  ///       node("target", trg).
-  ///       attribute("caption", caption).
-  ///       run();
+  /// DigraphReader<Digraph>(std::cin, digraph).
+  ///   nodeMap("coordinates", coord_map).
+  ///   arcMap("capacity", cap_map).
+  ///   node("source", src).
+  ///   node("target", trg).
+  ///   attribute("caption", caption).
+  ///   run();
   ///\endcode
   ///
@@ -438 +438 @@
   /// graph) during the reading, but instead the label map of the items
   /// are given as a parameter of these functions. An
-  /// application of these function is multipass reading, which is
-  /// important if two \e \@arcs sections must be read from the
-  /// file. In this example the first phase would read the node set and one
+  /// application of these functions is multipass reading, which is
+  /// important if two \c \@arcs sections must be read from the
+  /// file. In this case the first phase would read the node set and one
   /// of the arc sets, while the second phase would read the second arc
   /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
   /// The previously read label node map should be passed to the \c
   /// useNodes() functions. Another application of multipass reading when
-  /// paths are given as a node map or an arc map. It is impossible read this in
+  /// paths are given as a node map or an arc map. It is impossible to read this in
   /// a single pass, because the arcs are not constructed when the node
   /// maps are read.
@@ -736 +736 @@
     /// Use previously constructed node set, and specify the node
     /// label map and a functor which converts the label map values to
-    /// std::string.
+    /// \c std::string.
     template <typename Map, typename Converter>
     DigraphReader& useNodes(const Map& map, 
@@ -769 +769 @@
     /// Use previously constructed arc set, and specify the arc
     /// label map and a functor which converts the label map values to
-    /// std::string.
+    /// \c std::string.
     template <typename Map, typename Converter>
     DigraphReader& useArcs(const Map& map, 
@@ -785 +785 @@
     ///
     /// Omit the reading of the node section. This implies that each node
-    /// map reading rule will be abanoned, and the nodes of the graph
+    /// map reading rule will be abandoned, and the nodes of the graph
     /// will not be constructed, which usually cause that the arc set
-    /// could not be read due to lack of node name
-    /// resolving. Therefore, the \c skipArcs() should be used too, or
-    /// the useNodes() member function should be used to specify the
-    /// label of the nodes.
+    /// could not be read due to lack of node name resolving.
+    /// Therefore \c skipArcs() function should also be used, or
+    /// \c useNodes() should be used to specify the label of the nodes.
     DigraphReader& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
@@ -800 +799 @@
     ///
     /// Omit the reading of the arc section. This implies that each arc
-    /// map reading rule will be abanoned, and the arcs of the graph
+    /// map reading rule will be abandoned, and the arcs of the graph
     /// will not be constructed.
     DigraphReader& skipArcs() {
@@ -1176 +1175 @@
   };
 
+  /// \brief Return a \ref DigraphReader class
+  /// 
+  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1183 +1185 @@
   }
 
+  /// \brief Return a \ref DigraphReader class
+  /// 
+  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1191 +1196 @@
   }
 
+  /// \brief Return a \ref DigraphReader class
+  /// 
+  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1212 +1220 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief LGF reader for undirected graphs
+  /// \brief \ref lgf-format "LGF" reader for undirected graphs
   ///
   /// This utility reads an \ref lgf-format "LGF" file.
+  ///
+  /// It can be used almost the same way as \c DigraphReader.
+  /// The only difference is that this class can handle edges and
+  /// edge maps as well as arcs and arc maps.
+  ///
+  /// The columns in the \c \@edges (or \c \@arcs) section are the
+  /// edge maps. However, if there are two maps with the same name
+  /// prefixed with \c '+' and \c '-', then these can be read into an
+  /// arc map.  Similarly, an attribute can be read into an arc, if
+  /// it's value is an edge label prefixed with \c '+' or \c '-'.
   template <typename _Graph>
   class GraphReader {
@@ -1263 +1281 @@
     /// \brief Constructor
     ///
-    /// Construct a undirected graph reader, which reads from the given
+    /// Construct an undirected graph reader, which reads from the given
     /// input stream.
     GraphReader(std::istream& is, Graph& graph) 
@@ -1272 +1290 @@
     /// \brief Constructor
     ///
-    /// Construct a undirected graph reader, which reads from the given
+    /// Construct an undirected graph reader, which reads from the given
     /// file.
     GraphReader(const std::string& fn, Graph& graph) 
@@ -1281 +1299 @@
     /// \brief Constructor
     ///
-    /// Construct a undirected graph reader, which reads from the given
+    /// Construct an undirected graph reader, which reads from the given
     /// file.
     GraphReader(const char* fn, Graph& graph) 
@@ -1498 +1516 @@
     /// \brief Set \c \@nodes section to be read
     ///
-    /// Set \c \@nodes section to be read
+    /// Set \c \@nodes section to be read.
     GraphReader& nodes(const std::string& caption) {
       _nodes_caption = caption;
@@ -1506 +1524 @@
     /// \brief Set \c \@edges section to be read
     ///
-    /// Set \c \@edges section to be read
+    /// Set \c \@edges section to be read.
     GraphReader& edges(const std::string& caption) {
       _edges_caption = caption;
@@ -1514 +1532 @@
     /// \brief Set \c \@attributes section to be read
     ///
-    /// Set \c \@attributes section to be read
+    /// Set \c \@attributes section to be read.
     GraphReader& attributes(const std::string& caption) {
       _attributes_caption = caption;
@@ -1545 +1563 @@
     /// Use previously constructed node set, and specify the node
     /// label map and a functor which converts the label map values to
-    /// std::string.
+    /// \c std::string.
     template <typename Map, typename Converter>
     GraphReader& useNodes(const Map& map, 
@@ -1578 +1596 @@
     /// Use previously constructed edge set, and specify the edge
     /// label map and a functor which converts the label map values to
-    /// std::string.
+    /// \c std::string.
     template <typename Map, typename Converter>
     GraphReader& useEdges(const Map& map, 
@@ -1591 +1609 @@
     }
 
-    /// \brief Skips the reading of node section
+    /// \brief Skip the reading of node section
     ///
     /// Omit the reading of the node section. This implies that each node
-    /// map reading rule will be abanoned, and the nodes of the graph
+    /// map reading rule will be abandoned, and the nodes of the graph
     /// will not be constructed, which usually cause that the edge set
     /// could not be read due to lack of node name
-    /// resolving. Therefore, the \c skipEdges() should be used too, or
-    /// the useNodes() member function should be used to specify the
-    /// label of the nodes.
+    /// could not be read due to lack of node name resolving.
+    /// Therefore \c skipEdges() function should also be used, or
+    /// \c useNodes() should be used to specify the label of the nodes.
     GraphReader& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
@@ -1606 +1624 @@
     }
 
-    /// \brief Skips the reading of edge section
+    /// \brief Skip the reading of edge section
     ///
     /// Omit the reading of the edge section. This implies that each edge
-    /// map reading rule will be abanoned, and the edges of the graph
+    /// map reading rule will be abandoned, and the edges of the graph
     /// will not be constructed.
     GraphReader& skipEdges() {
@@ -1983 +2001 @@
   };
 
+  /// \brief Return a \ref GraphReader class
+  /// 
+  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -1990 +2011 @@
   }
 
+  /// \brief Return a \ref GraphReader class
+  /// 
+  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -1998 +2022 @@
   }
 
+  /// \brief Return a \ref GraphReader class
+  /// 
+  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -2011 +2038 @@
   SectionReader sectionReader(const char* fn);
   
+  /// \ingroup lemon_io
+  ///
   /// \brief Section reader class
   ///
-  /// In the \e LGF file extra sections can be placed, which contain
-  /// any data in arbitrary format. Such sections can be read with
-  /// this class. A reading rule can be added with two different
-  /// functions, with the \c sectionLines() function a functor can
-  /// process the section line-by-line. While with the \c
+  /// In the \ref lgf-format "LGF" file extra sections can be placed, 
+  /// which contain any data in arbitrary format. Such sections can be
+  /// read with this class. A reading rule can be added to the class 
+  /// with two different functions. With the \c sectionLines() function a
+  /// functor can process the section line-by-line, while with the \c
   /// sectionStream() member the section can be read from an input
   /// stream.
@@ -2106 +2135 @@
     ///\endcode
     ///
-    /// The functor is implemented as an struct:
+    /// The functor is implemented as a struct:
     ///\code
     ///  struct NumberSection {
@@ -2124 +2153 @@
     template <typename Functor>
     SectionReader& sectionLines(const std::string& type, Functor functor) {
-      LEMON_ASSERT(!type.empty(), "Type is not empty.");
+      LEMON_ASSERT(!type.empty(), "Type is empty.");
       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
                    "Multiple reading of section.");
@@ -2136 +2165 @@
     ///
     /// The first parameter is the type of the section, the second is
-    /// a functor, which takes an \c std::istream& and an int&
+    /// a functor, which takes an \c std::istream& and an \c int&
     /// parameter, the latter regard to the line number of stream. The
     /// functor can read the input while the section go on, and the
@@ -2142 +2171 @@
     template <typename Functor>
     SectionReader& sectionStream(const std::string& type, Functor functor) {
-      LEMON_ASSERT(!type.empty(), "Type is not empty.");
+      LEMON_ASSERT(!type.empty(), "Type is empty.");
       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
                    "Multiple reading of section.");
@@ -2187 +2216 @@
     /// \brief Start the batch processing
     ///
-    /// This function starts the batch processing
+    /// This function starts the batch processing.
     void run() {
       
@@ -2240 +2269 @@
   };
 
+  /// \brief Return a \ref SectionReader class
+  /// 
+  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(std::istream& is) {
@@ -2246 +2278 @@
   }
 
+  /// \brief Return a \ref SectionReader class
+  /// 
+  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(const std::string& fn) {
@@ -2252 +2287 @@
   }
 
+  /// \brief Return a \ref SectionReader class
+  /// 
+  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(const char* fn) {
@@ -2270 +2308 @@
   /// reading the graph.
   ///
-  ///\code LgfContents contents("graph.lgf"); 
+  ///\code 
+  /// LgfContents contents("graph.lgf"); 
   /// contents.run();
   ///
-  /// // does it contain any node section and arc section
+  /// // Does it contain any node section and arc section?
   /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
-  ///   std::cerr << "Failure, cannot find graph" << std::endl;
+  ///   std::cerr << "Failure, cannot find graph." << std::endl;
   ///   return -1;
   /// }
-  /// std::cout << "The name of the default node section : " 
+  /// std::cout << "The name of the default node section: " 
   ///           << contents.nodeSection(0) << std::endl;
-  /// std::cout << "The number of the arc maps : " 
+  /// std::cout << "The number of the arc maps: " 
   ///           << contents.arcMaps(0).size() << std::endl;
-  /// std::cout << "The name of second arc map : " 
+  /// std::cout << "The name of second arc map: " 
   ///           << contents.arcMaps(0)[1] << std::endl;
   ///\endcode
@@ -2353 +2392 @@
     }
 
-    /// \brief Returns the section name at the given position. 
-    ///
-    /// Returns the section name at the given position. 
+    /// \brief Returns the node section name at the given position. 
+    ///
+    /// Returns the node section name at the given position. 
     const std::string& nodeSection(int i) const {
       return _node_sections[i];
@@ -2380 +2419 @@
     }
 
-    /// \brief Returns the section name at the given position. 
-    ///
-    /// Returns the section name at the given position. 
+    /// \brief Returns the arc/edge section name at the given position. 
+    ///
+    /// Returns the arc/edge section name at the given position. 
     /// \note It is synonym of \c edgeSection().
     const std::string& arcSection(int i) const {
@@ -2437 +2476 @@
     }
 
-    /// \brief Returns the section name at the given position. 
-    ///
-    /// Returns the section name at the given position. 
+    /// \brief Returns the attribute section name at the given position. 
+    ///
+    /// Returns the attribute section name at the given position. 
     const std::string& attributeSectionNames(int i) const {
       return _attribute_sections[i];
@@ -2530 +2569 @@
     /// @{
 
-    /// \brief Start the reading
-    ///
-    /// This function starts the reading
+    /// \brief Starts the reading
+    ///
+    /// This function starts the reading.
     void run() {
 

lemon/lgf_writer.h

@@ -19 +19 @@
 ///\ingroup lemon_io
 ///\file
-///\brief Lemon Graph Format writer.
+///\brief \ref lgf-format "Lemon Graph Format" writer.
 
 
@@ -226 +226 @@
     };
 
-    bool isWhiteSpace(char c) {
+    inline bool isWhiteSpace(char c) {
       return c == ' ' || c == '\t' || c == '\v' || 
         c == '\n' || c == '\r' || c == '\f'; 
     }
 
-    bool isEscaped(char c) {
+    inline bool isEscaped(char c) {
       return c == '\\' || c == '\"' || c == '\'' || 
         c == '\a' || c == '\b';
     }
 
-    static void writeEscape(std::ostream& os, char c) {
+    inline static void writeEscape(std::ostream& os, char c) {
       switch (c) {
       case '\\':
@@ -277 +277 @@
     }
 
-    bool requireEscape(const std::string& str) {
+    inline bool requireEscape(const std::string& str) {
       if (str.empty() || str[0] == '@') return true;
       std::istringstream is(str);
@@ -289 +289 @@
     }
     
-    std::ostream& writeToken(std::ostream& os, const std::string& str) {
+    inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
 
       if (requireEscape(str)) {
@@ -323 +323 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief LGF writer for directed graphs
+  /// \brief \ref lgf-format "LGF" writer for directed graphs
   ///
   /// This utility writes an \ref lgf-format "LGF" file.
@@ -333 +333 @@
   /// with the \c nodeMap() or \c arcMap() members. An optional
   /// converter parameter can also be added as a standard functor
-  /// converting from the value type of the map to std::string. If it
-  /// is set, it will determine how the map's value type is written to
+  /// converting from the value type of the map to \c std::string. If it
+  /// is set, it will determine how the value type of the map is written to
   /// the output stream. If the functor is not set, then a default
   /// conversion will be used. The \c attribute(), \c node() and \c
@@ -340 +340 @@
   ///
   ///\code
-  ///     DigraphWriter<Digraph>(std::cout, digraph).
-  ///       nodeMap("coordinates", coord_map).
-  ///       nodeMap("size", size).
-  ///       nodeMap("title", title).
-  ///       arcMap("capacity", cap_map).
-  ///       node("source", src).
-  ///       node("target", trg).
-  ///       attribute("caption", caption).
-  ///       run();
+  /// DigraphWriter<Digraph>(std::cout, digraph).
+  ///   nodeMap("coordinates", coord_map).
+  ///   nodeMap("size", size).
+  ///   nodeMap("title", title).
+  ///   arcMap("capacity", cap_map).
+  ///   node("source", src).
+  ///   node("target", trg).
+  ///   attribute("caption", caption).
+  ///   run();
   ///\endcode
   ///
@@ -487 +487 @@
     /// @{
     
-    /// \brief Node map reading rule
-    ///
-    /// Add a node map reading rule to the writer.
+    /// \brief Node map writing rule
+    ///
+    /// Add a node map writing rule to the writer.
     template <typename Map>
     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
@@ -587 +587 @@
     }
 
-    /// \name Select section by name
+    /// \name Section captions
     /// @{
 
-    /// \brief Set \c \@nodes section to be read
-    ///
-    /// Set \c \@nodes section to be read
+    /// \brief Add an additional caption to the \c \@nodes section
+    ///
+    /// Add an additional caption to the \c \@nodes section.
     DigraphWriter& nodes(const std::string& caption) {
       _nodes_caption = caption;
@@ -598 +598 @@
     }
 
-    /// \brief Set \c \@arcs section to be read
-    ///
-    /// Set \c \@arcs section to be read
+    /// \brief Add an additional caption to the \c \@arcs section
+    ///
+    /// Add an additional caption to the \c \@arcs section.
     DigraphWriter& arcs(const std::string& caption) {
       _arcs_caption = caption;
@@ -606 +606 @@
     }
 
-    /// \brief Set \c \@attributes section to be read
-    ///
-    /// Set \c \@attributes section to be read
+    /// \brief Add an additional caption to the \c \@attributes section
+    ///
+    /// Add an additional caption to the \c \@attributes section.
     DigraphWriter& attributes(const std::string& caption) {
       _attributes_caption = caption;
@@ -619 +619 @@
     /// \brief Skip writing the node set
     ///
-    /// The \c \@nodes section will be not written to the stream.
+    /// The \c \@nodes section will not be written to the stream.
     DigraphWriter& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
@@ -628 +628 @@
     /// \brief Skip writing arc set
     ///
-    /// The \c \@arcs section will be not written to the stream.
+    /// The \c \@arcs section will not be written to the stream.
     DigraphWriter& skipArcs() {
       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
@@ -836 +836 @@
     /// \brief Start the batch processing
     ///
-    /// This function starts the batch processing
+    /// This function starts the batch processing.
     void run() {
       if (!_skip_nodes) {
@@ -851 +851 @@
     }
 
-    /// \brief Gives back the stream of the writer
-    ///
-    /// Gives back the stream of the writer
+    /// \brief Give back the stream of the writer
+    ///
+    /// Give back the stream of the writer.
     std::ostream& ostream() {
       return *_os;
@@ -861 +861 @@
   };
 
+  /// \brief Return a \ref DigraphWriter class
+  /// 
+  /// This function just returns a \ref DigraphWriter class.
   /// \relates DigraphWriter
   template <typename Digraph>
@@ -869 +872 @@
   }
 
+  /// \brief Return a \ref DigraphWriter class
+  /// 
+  /// This function just returns a \ref DigraphWriter class.
   /// \relates DigraphWriter
   template <typename Digraph>
@@ -877 +883 @@
   }
 
+  /// \brief Return a \ref DigraphWriter class
+  /// 
+  /// This function just returns a \ref DigraphWriter class.
   /// \relates DigraphWriter
   template <typename Digraph>
@@ -899 +908 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief LGF writer for directed graphs
+  /// \brief \ref lgf-format "LGF" writer for directed graphs
   ///
   /// This utility writes an \ref lgf-format "LGF" file.
+  ///
+  /// It can be used almost the same way as \c DigraphWriter.
+  /// The only difference is that this class can handle edges and
+  /// edge maps as well as arcs and arc maps.
+  ///
+  /// The arc maps are written into the file as two columns, the
+  /// caption of the columns are the name of the map prefixed with \c
+  /// '+' and \c '-'. The arcs are written into the \c \@attributes
+  /// section as a \c '+' or a \c '-' prefix (depends on the direction
+  /// of the arc) and the label of corresponding edge.
   template <typename _Graph>
   class GraphWriter {
@@ -1024 +1043 @@
     /// @{
     
-    /// \brief Node map reading rule
-    ///
-    /// Add a node map reading rule to the writer.
+    /// \brief Node map writing rule
+    ///
+    /// Add a node map writing rule to the writer.
     template <typename Map>
     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
@@ -1170 +1189 @@
     }
 
-    /// \name Select section by name
+    /// \name Section captions
     /// @{
 
-    /// \brief Set \c \@nodes section to be read
-    ///
-    /// Set \c \@nodes section to be read
+    /// \brief Add an additional caption to the \c \@nodes section
+    ///
+    /// Add an additional caption to the \c \@nodes section.
     GraphWriter& nodes(const std::string& caption) {
       _nodes_caption = caption;
@@ -1181 +1200 @@
     }
 
-    /// \brief Set \c \@edges section to be read
-    ///
-    /// Set \c \@edges section to be read
+    /// \brief Add an additional caption to the \c \@arcs section
+    ///
+    /// Add an additional caption to the \c \@arcs section.
     GraphWriter& edges(const std::string& caption) {
       _edges_caption = caption;
@@ -1189 +1208 @@
     }
 
-    /// \brief Set \c \@attributes section to be read
-    ///
-    /// Set \c \@attributes section to be read
+    /// \brief Add an additional caption to the \c \@attributes section
+    ///
+    /// Add an additional caption to the \c \@attributes section.
     GraphWriter& attributes(const std::string& caption) {
       _attributes_caption = caption;
@@ -1202 +1221 @@
     /// \brief Skip writing the node set
     ///
-    /// The \c \@nodes section will be not written to the stream.
+    /// The \c \@nodes section will not be written to the stream.
     GraphWriter& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
@@ -1211 +1230 @@
     /// \brief Skip writing edge set
     ///
-    /// The \c \@edges section will be not written to the stream.
+    /// The \c \@edges section will not be written to the stream.
     GraphWriter& skipEdges() {
       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
@@ -1419 +1438 @@
     /// \brief Start the batch processing
     ///
-    /// This function starts the batch processing
+    /// This function starts the batch processing.
     void run() {
       if (!_skip_nodes) {
@@ -1434 +1453 @@
     }
 
-    /// \brief Gives back the stream of the writer
-    ///
-    /// Gives back the stream of the writer
+    /// \brief Give back the stream of the writer
+    ///
+    /// Give back the stream of the writer
     std::ostream& ostream() {
       return *_os;
@@ -1444 +1463 @@
   };
 
+  /// \brief Return a \ref GraphWriter class
+  /// 
+  /// This function just returns a \ref GraphWriter class.
   /// \relates GraphWriter
   template <typename Graph>
@@ -1451 +1473 @@
   }
 
+  /// \brief Return a \ref GraphWriter class
+  /// 
+  /// This function just returns a \ref GraphWriter class.
   /// \relates GraphWriter
   template <typename Graph>
@@ -1458 +1483 @@
   }
 
+  /// \brief Return a \ref GraphWriter class
+  /// 
+  /// This function just returns a \ref GraphWriter class.
   /// \relates GraphWriter
   template <typename Graph>

test/CMakeLists.txt

@@ -11 +11 @@
   dim_test
   error_test
+  graph_copy_test
   graph_test
   graph_utils_test
+  heap_test
   kruskal_test
   maps_test

test/Makefile.am

@@ -4 +4 @@
 noinst_HEADERS += \
         test/graph_test.h \
-        test/heap_test.h \
         test/graph_maps_test.h \
         test/test_tools.h
@@ -16 +15 @@
         test/dim_test \
         test/error_test \
+        test/graph_copy_test \
         test/graph_test \
         test/graph_utils_test \
+        test/heap_test \
         test/kruskal_test \
         test/maps_test \
@@ -37 +38 @@
 test_dim_test_SOURCES = test/dim_test.cc
 test_error_test_SOURCES = test/error_test.cc
+test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
-# test_heap_test_SOURCES = test/heap_test.cc
+test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
 test_maps_test_SOURCES = test/maps_test.cc

test/heap_test.cc

@@ -25 +25 @@
 #include <lemon/concepts/heap.h>
 
-#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
 
-#include <lemon/digraph_reader.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/dijkstra.h>
+#include <lemon/maps.h>
 
 #include <lemon/bin_heap.h>
-#include <lemon/fib_heap.h>
-#include <lemon/radix_heap.h>
-#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
 
-#include "heap_test.h"
-
-#include <lemon/time_measure.h>
-
 using namespace lemon;
 using namespace lemon::concepts;
+
+typedef ListDigraph Digraph;
+DIGRAPH_TYPEDEFS(Digraph);
+
+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   capacity\n"     
+  "0    5       0       94\n"   
+  "3    9       1       11\n"   
+  "8    7       2       83\n"   
+  "1    2       3       94\n"   
+  "5    7       4       35\n"   
+  "7    4       5       84\n"   
+  "9    5       6       38\n"   
+  "0    4       7       96\n"   
+  "6    7       8       6\n"    
+  "3    1       9       27\n"   
+  "5    2       10      77\n"   
+  "5    6       11      69\n"   
+  "6    5       12      41\n"   
+  "4    6       13      70\n"   
+  "3    2       14      45\n"   
+  "7    9       15      93\n"   
+  "5    9       16      50\n"   
+  "9    0       17      94\n"   
+  "9    6       18      67\n"   
+  "0    9       19      86\n"   
+  "@attributes\n" 
+  "source 3\n";
+
+int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
+int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
+
+int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
+
+template <typename Heap>
+void heapSortTest() {
+  RangeMap<int> map(test_len, -1);
+
+  Heap heap(map);
+  
+  std::vector<int> v(test_len);
+
+  for (int i = 0; i < test_len; ++i) {
+    v[i] = test_seq[i];
+    heap.push(i, v[i]);
+  }
+  std::sort(v.begin(), v.end());
+  for (int i = 0; i < test_len; ++i) {
+    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+    heap.pop();
+  }
+}
+
+template <typename Heap>
+void heapIncreaseTest() {
+  RangeMap<int> map(test_len, -1);
+
+  Heap heap(map);
+  
+  std::vector<int> v(test_len);
+
+  for (int i = 0; i < test_len; ++i) {
+    v[i] = test_seq[i];
+    heap.push(i, v[i]);
+  }
+  for (int i = 0; i < test_len; ++i) {
+    v[i] += test_inc[i];
+    heap.increase(i, v[i]);
+  }
+  std::sort(v.begin(), v.end());
+  for (int i = 0; i < test_len; ++i) {
+    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+    heap.pop();
+  }
+}
+
+
+
+template <typename Heap>
+void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 
+                      Node source) {
+  
+  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
+    Create dijkstra(digraph, length);
+
+  dijkstra.run(source);
+
+  for(ArcIt a(digraph); a != INVALID; ++a) {
+    Node s = digraph.source(a); 
+    Node t = digraph.target(a);
+    if (dijkstra.reached(s)) {
+      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
+             "Error in a shortest path tree!");
+    }
+  }
+
+  for(NodeIt n(digraph); n != INVALID; ++n) {
+    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
+      Arc a = dijkstra.predArc(n);
+      Node s = digraph.source(a);
+      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
+             "Error in a shortest path tree!");
+    }
+  }
+
+}
 
 int main() {
@@ -47 +161 @@
   typedef int Item;
   typedef int Prio;
-  typedef IntIntMap ItemIntMap;
+  typedef RangeMap<int> ItemIntMap;
+  
+  Digraph digraph;
+  IntArcMap length(digraph);
+  Node source;
 
-  typedef ListDigraph Digraph;
-
-  typedef Digraph::Arc Arc;
-  typedef Digraph::Node Node;
-  typedef Digraph::ArcIt ArcIt;
-  typedef Digraph::NodeIt NodeIt;
-  typedef Digraph::ArcMap<int> LengthMap;
-
-  Digraph digraph;
-  LengthMap length(digraph);
-  Node start;
-
-  /// \todo create own test digraph
-
-  std::string f_name;
-  if( getenv("srcdir") )
-    f_name = std::string(getenv("srcdir"));
-  else f_name = ".";
-  f_name += "/test/dijkstra_test.lgf";
-  
-  std::ifstream input(f_name.c_str());
-  check(input, "Input file '" << f_name << "' not found.");
-  DigraphReader<Digraph>(input, digraph).
-    readArcMap("capacity", length).
-    readNode("source", start).
+  std::istringstream input(test_lgf);
+  digraphReader(input, digraph).
+    arcMap("capacity", length).
+    node("source", source).
     run();  
  
   {
-    std::cout << "Checking Bin Heap" << std::endl;
-
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
+    heapSortTest<IntHeap>();
+    heapIncreaseTest<IntHeap>();
     
-    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-  {
-    std::cout << "Checking Fib Heap" << std::endl;
-
-    typedef FibHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-  {
-    std::cout << "Checking Radix Heap" << std::endl;
-
-    typedef RadixHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
-  }
-
-  {
-    std::cout << "Checking Bucket Heap" << std::endl;
-
-    typedef BucketHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>(100);
-    heapIncreaseTest<IntHeap>(100);
-
-    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
-    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
-    Timer timer;
-    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
-    std::cout << timer << std::endl;
+    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
+    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+    dijkstraHeapTest<NodeHeap>(digraph, length, source);
   }