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

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 (deleted)
• test/heap_test.cc (modified) (2 diffs)
• test/heap_test.h (added)

demo/arg_parser_demo.cc

@@ -30 +30 @@
 int main(int argc, const char **argv)
 {
-  // Initialize the argument parser
-  ArgParser ap(argc, argv);
+  ArgParser ap(argc,argv);
   int i;
   std::string s;
-  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.")
+  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.")
     .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";
 
-  std::cout << "  Value of -n: " << i << std::endl;
+  if(ap.given("n")) 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: " << nh << std::endl;
+  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << sil << 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:
@@ -100 +81 @@
     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 read and write a digraph
-/// and additional maps from/to a stream or a file using the 
-/// \ref lgf-format "LGF" format.
+/// 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.
 ///
 /// The \c "digraph.lgf" file:
 /// \include digraph.lgf
 ///
-/// And the program which reads it and prints the digraph to the
-/// standard output:
+/// And the program which reads it:
 /// \include lgf_demo.cc
 
@@ -36 +35 @@
 #include <lemon/lgf_reader.h>
 #include <lemon/lgf_writer.h>
+#include <lemon/random.h>
+
 
 using namespace lemon;
@@ -43 +44 @@
   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;
-  }
 
-  std::cout << "A digraph is read from 'digraph.lgf'." << std::endl;
+  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 << "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 \ref lgf-format "Lemon Graph Format".
-
-This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format".
+\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.
 */
 

doc/lgf.dox

@@ -47 +47 @@
 
 The \c \@nodes section describes a set of nodes and associated
-maps. The first is a header line, its columns are the names of the
+maps. The first is a header line, it 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 maps,
+it again starts with a header line describing the names of the arc,
 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 @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 \@edges is just a synonym of \c \@arcs.
 
 The \c \@attributes section contains key-value pairs, each line
-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.
+consists of two tokens, an attribute name, and then an attribute value.
 
 \code

lemon/Makefile.am

@@ -33 +33 @@
         lemon/kruskal.h \
         lemon/lgf_reader.h \
-        lemon/lgf_writer.h \
         lemon/list_graph.h \
         lemon/maps.h \
@@ -61 +60 @@
         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/path.h \
+        lemon/concepts/graph_components.h

lemon/arg_parser.h

@@ -119 +119 @@
   public:
 
-    ///Constructor
+    ///\e
     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.
@@ -142 +136 @@
     ///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.
@@ -153 +146 @@
     ///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.
@@ -165 +157 @@
     ///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.
@@ -174 +165 @@
                       std::string value="", bool obl=false);
 
-    ///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
+    ///\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.
@@ -192 +173 @@
     ///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.
@@ -203 +183 @@
     ///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.
@@ -214 +193 @@
     ///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.
@@ -226 +204 @@
     ///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.
@@ -242 +219 @@
     ///@{
 
-    ///Bundle some options into a group
+    ///Boundle some options into a group
 
     /// You can group some option by calling this function repeatedly for each
@@ -254 +231 @@
 
     ///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);
   
@@ -271 +248 @@
     
     ///@}
+
+    ///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);
@@ -293 +287 @@
     }
     
-    ///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) 
@@ -370 +361 @@
       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_ARG_PARSER
+    
+
+#endif // LEMON_MAIN_PARAMS

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;
@@ -202 +204 @@
           
           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();
 
-          own_state = heap.state(own_item);
+          state = heap.state(item);
+          heap.state(item, state);
+          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.addEdge(nodeRefMap[from.u(it)], 
-                                      nodeRefMap[from.v(it)]);
+          edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 
+                                       nodeRefMap[from.target(it)]);
         }
       }
@@ -926 +926 @@
 
       Value operator[](const Key& key) const {
-        bool forward = _from.u(key) != _from.v(key) ?
-          _node_ref[_from.source(key)] == 
-          _to.source(_to.direct(_edge_ref[key], true)) :
-          _from.direction(key);
+        bool forward = 
+          (_from.direction(key) == 
+           (_node_ref[_from.source(key)] == _to.source(_edge_ref[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 spanning tree
+///\brief Kruskal's algorithm to compute a minimum cost tree
 ///
-///Kruskal's algorithm to compute a minimum cost spanning tree.
+///Kruskal's algorithm to compute a minimum cost tree.
 ///
 
@@ -252 +252 @@
   /// \ingroup spantree
   ///
-  /// \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.
+  /// \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.
   /// Due to some C++ hacking, it accepts various input and output types.
   ///
@@ -265 +263 @@
   /// undirected by disregarding the direction of the arcs.
   ///
-  /// \param in This object is used to describe the arc/edge costs. 
-  /// It can be one of the following choices.
+  /// \param in This object is used to describe the arc costs. It can be one
+  /// of the following choices.
   /// - An STL compatible 'Forward Container' with
-  /// <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
+  /// <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
   /// along with the assigned cost. <em>They must be in a
   /// cost-ascending order.</em>
-  /// - 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
+  /// - 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
   /// to the tree, otherwise it will be set to \c false. The value of
-  /// each arc/edge will be set exactly once.
+  /// each arc will be set exactly once.
   /// - It can also be an iteraror of an STL Container with
-  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
+  /// <tt>GR::Edge</tt> or <tt>GR::Arc</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
@@ -294 +291 @@
   /// 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 spanning tree.
-  ///
-  /// \warning If Kruskal runs on an be consistent of using the same
+  /// \return The total cost of the found 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 \ref lgf-format "Lemon Graph Format" reader.
+///\brief Lemon Graph Format reader.
 
 
@@ -196 +196 @@
     };
 
-    inline bool isWhiteSpace(char c) {
+    bool isWhiteSpace(char c) {
       return c == ' ' || c == '\t' || c == '\v' || 
         c == '\n' || c == '\r' || c == '\f'; 
     }
     
-    inline bool isOct(char c) {
+    bool isOct(char c) {
       return '0' <= c && c <='7'; 
     }
     
-    inline int valueOct(char c) {
+    int valueOct(char c) {
       LEMON_ASSERT(isOct(c), "The character is not octal.");
       return c - '0';
     }
 
-    inline bool isHex(char c) {
+    bool isHex(char c) {
       return ('0' <= c && c <= '9') || 
         ('a' <= c && c <= 'z') || 
@@ -216 +216 @@
     }
     
-    inline int valueHex(char c) {
+    int valueHex(char c) {
       LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
       if ('0' <= c && c <= '9') return c - '0';
@@ -223 +223 @@
     }
 
-    inline bool isIdentifierFirstChar(char c) {
+    bool isIdentifierFirstChar(char c) {
       return ('a' <= c && c <= 'z') ||
         ('A' <= c && c <= 'Z') || c == '_';
     }
 
-    inline bool isIdentifierChar(char c) {
+    bool isIdentifierChar(char c) {
       return isIdentifierFirstChar(c) ||
         ('0' <= c && c <= '9');
     }
 
-    inline char readEscape(std::istream& is) {
+    char readEscape(std::istream& is) {
       char c;
       if (!is.get(c))
@@ -285 +285 @@
     }
     
-    inline std::istream& readToken(std::istream& is, std::string& str) {
+    std::istream& readToken(std::istream& is, std::string& str) {
       std::ostringstream os;
 
@@ -401 +401 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief \ref lgf-format "LGF" reader for directed graphs
+  /// \brief 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 \c std::string to the value type of the map. If it
+  /// converting from std::string to the value type of the map. If it
   /// is set, it will determine how the tokens in the file should be
-  /// converted to the value type of the map. If the functor is not set,
+  /// is converted to the map's value type. 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 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
+  /// 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
   /// 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 to read this in
+  /// paths are given as a node map or an arc map. It is impossible 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
-    /// \c std::string.
+    /// 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
-    /// \c std::string.
+    /// 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 abandoned, and the nodes of the graph
+    /// map reading rule will be abanoned, 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 \c skipArcs() function should also be used, or
-    /// \c useNodes() should be used to specify the label of the nodes.
+    /// 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.
     DigraphReader& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
@@ -799 +800 @@
     ///
     /// Omit the reading of the arc section. This implies that each arc
-    /// map reading rule will be abandoned, and the arcs of the graph
+    /// map reading rule will be abanoned, and the arcs of the graph
     /// will not be constructed.
     DigraphReader& skipArcs() {
@@ -1175 +1176 @@
   };
 
-  /// \brief Return a \ref DigraphReader class
-  /// 
-  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1185 +1183 @@
   }
 
-  /// \brief Return a \ref DigraphReader class
-  /// 
-  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1196 +1191 @@
   }
 
-  /// \brief Return a \ref DigraphReader class
-  /// 
-  /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
   template <typename Digraph>
@@ -1220 +1212 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief \ref lgf-format "LGF" reader for undirected graphs
+  /// \brief 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 {
@@ -1281 +1263 @@
     /// \brief Constructor
     ///
-    /// Construct an undirected graph reader, which reads from the given
+    /// Construct a undirected graph reader, which reads from the given
     /// input stream.
     GraphReader(std::istream& is, Graph& graph) 
@@ -1290 +1272 @@
     /// \brief Constructor
     ///
-    /// Construct an undirected graph reader, which reads from the given
+    /// Construct a undirected graph reader, which reads from the given
     /// file.
     GraphReader(const std::string& fn, Graph& graph) 
@@ -1299 +1281 @@
     /// \brief Constructor
     ///
-    /// Construct an undirected graph reader, which reads from the given
+    /// Construct a undirected graph reader, which reads from the given
     /// file.
     GraphReader(const char* fn, Graph& graph) 
@@ -1516 +1498 @@
     /// \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;
@@ -1524 +1506 @@
     /// \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;
@@ -1532 +1514 @@
     /// \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;
@@ -1563 +1545 @@
     /// Use previously constructed node set, and specify the node
     /// label map and a functor which converts the label map values to
-    /// \c std::string.
+    /// std::string.
     template <typename Map, typename Converter>
     GraphReader& useNodes(const Map& map, 
@@ -1596 +1578 @@
     /// Use previously constructed edge set, and specify the edge
     /// label map and a functor which converts the label map values to
-    /// \c std::string.
+    /// std::string.
     template <typename Map, typename Converter>
     GraphReader& useEdges(const Map& map, 
@@ -1609 +1591 @@
     }
 
-    /// \brief Skip the reading of node section
+    /// \brief Skips the reading of node section
     ///
     /// Omit the reading of the node section. This implies that each node
-    /// map reading rule will be abandoned, and the nodes of the graph
+    /// map reading rule will be abanoned, 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
-    /// 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.
+    /// resolving. Therefore, the \c skipEdges() should be used too, or
+    /// the useNodes() member function should be used to specify the
+    /// label of the nodes.
     GraphReader& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
@@ -1624 +1606 @@
     }
 
-    /// \brief Skip the reading of edge section
+    /// \brief Skips the reading of edge section
     ///
     /// Omit the reading of the edge section. This implies that each edge
-    /// map reading rule will be abandoned, and the edges of the graph
+    /// map reading rule will be abanoned, and the edges of the graph
     /// will not be constructed.
     GraphReader& skipEdges() {
@@ -2001 +1983 @@
   };
 
-  /// \brief Return a \ref GraphReader class
-  /// 
-  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -2011 +1990 @@
   }
 
-  /// \brief Return a \ref GraphReader class
-  /// 
-  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -2022 +1998 @@
   }
 
-  /// \brief Return a \ref GraphReader class
-  /// 
-  /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
   template <typename Graph>
@@ -2038 +2011 @@
   SectionReader sectionReader(const char* fn);
   
-  /// \ingroup lemon_io
-  ///
   /// \brief Section reader class
   ///
-  /// 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
+  /// 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
   /// sectionStream() member the section can be read from an input
   /// stream.
@@ -2135 +2106 @@
     ///\endcode
     ///
-    /// The functor is implemented as a struct:
+    /// The functor is implemented as an struct:
     ///\code
     ///  struct NumberSection {
@@ -2153 +2124 @@
     template <typename Functor>
     SectionReader& sectionLines(const std::string& type, Functor functor) {
-      LEMON_ASSERT(!type.empty(), "Type is empty.");
+      LEMON_ASSERT(!type.empty(), "Type is not empty.");
       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
                    "Multiple reading of section.");
@@ -2165 +2136 @@
     ///
     /// The first parameter is the type of the section, the second is
-    /// a functor, which takes an \c std::istream& and an \c int&
+    /// a functor, which takes an \c std::istream& and an int&
     /// parameter, the latter regard to the line number of stream. The
     /// functor can read the input while the section go on, and the
@@ -2171 +2142 @@
     template <typename Functor>
     SectionReader& sectionStream(const std::string& type, Functor functor) {
-      LEMON_ASSERT(!type.empty(), "Type is empty.");
+      LEMON_ASSERT(!type.empty(), "Type is not empty.");
       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
                    "Multiple reading of section.");
@@ -2216 +2187 @@
     /// \brief Start the batch processing
     ///
-    /// This function starts the batch processing.
+    /// This function starts the batch processing
     void run() {
       
@@ -2269 +2240 @@
   };
 
-  /// \brief Return a \ref SectionReader class
-  /// 
-  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(std::istream& is) {
@@ -2278 +2246 @@
   }
 
-  /// \brief Return a \ref SectionReader class
-  /// 
-  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(const std::string& fn) {
@@ -2287 +2252 @@
   }
 
-  /// \brief Return a \ref SectionReader class
-  /// 
-  /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
   inline SectionReader sectionReader(const char* fn) {
@@ -2308 +2270 @@
   /// 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
@@ -2392 +2353 @@
     }
 
-    /// \brief Returns the node section name at the given position. 
-    ///
-    /// Returns the node section name at the given position. 
+    /// \brief Returns the section name at the given position. 
+    ///
+    /// Returns the section name at the given position. 
     const std::string& nodeSection(int i) const {
       return _node_sections[i];
@@ -2419 +2380 @@
     }
 
-    /// \brief Returns the arc/edge section name at the given position. 
-    ///
-    /// Returns the arc/edge section name at the given position. 
+    /// \brief Returns the section name at the given position. 
+    ///
+    /// Returns the section name at the given position. 
     /// \note It is synonym of \c edgeSection().
     const std::string& arcSection(int i) const {
@@ -2476 +2437 @@
     }
 
-    /// \brief Returns the attribute section name at the given position. 
-    ///
-    /// Returns the attribute section name at the given position. 
+    /// \brief Returns the section name at the given position. 
+    ///
+    /// Returns the section name at the given position. 
     const std::string& attributeSectionNames(int i) const {
       return _attribute_sections[i];
@@ -2569 +2530 @@
     /// @{
 
-    /// \brief Starts the reading
-    ///
-    /// This function starts the reading.
+    /// \brief Start the reading
+    ///
+    /// This function starts the reading
     void run() {
 

lemon/lgf_writer.h

@@ -19 +19 @@
 ///\ingroup lemon_io
 ///\file
-///\brief \ref lgf-format "Lemon Graph Format" writer.
+///\brief Lemon Graph Format writer.
 
 
@@ -226 +226 @@
     };
 
-    inline bool isWhiteSpace(char c) {
+    bool isWhiteSpace(char c) {
       return c == ' ' || c == '\t' || c == '\v' || 
         c == '\n' || c == '\r' || c == '\f'; 
     }
 
-    inline bool isEscaped(char c) {
+    bool isEscaped(char c) {
       return c == '\\' || c == '\"' || c == '\'' || 
         c == '\a' || c == '\b';
     }
 
-    inline static void writeEscape(std::ostream& os, char c) {
+    static void writeEscape(std::ostream& os, char c) {
       switch (c) {
       case '\\':
@@ -277 +277 @@
     }
 
-    inline bool requireEscape(const std::string& str) {
+    bool requireEscape(const std::string& str) {
       if (str.empty() || str[0] == '@') return true;
       std::istringstream is(str);
@@ -289 +289 @@
     }
     
-    inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
+    std::ostream& writeToken(std::ostream& os, const std::string& str) {
 
       if (requireEscape(str)) {
@@ -323 +323 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief \ref lgf-format "LGF" writer for directed graphs
+  /// \brief 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 \c std::string. If it
-  /// is set, it will determine how the value type of the map is written to
+  /// 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
   /// 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 writing rule
-    ///
-    /// Add a node map writing rule to the writer.
+    /// \brief Node map reading rule
+    ///
+    /// Add a node map reading rule to the writer.
     template <typename Map>
     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
@@ -587 +587 @@
     }
 
-    /// \name Section captions
+    /// \name Select section by name
     /// @{
 
-    /// \brief Add an additional caption to the \c \@nodes section
-    ///
-    /// Add an additional caption to the \c \@nodes section.
+    /// \brief Set \c \@nodes section to be read
+    ///
+    /// Set \c \@nodes section to be read
     DigraphWriter& nodes(const std::string& caption) {
       _nodes_caption = caption;
@@ -598 +598 @@
     }
 
-    /// \brief Add an additional caption to the \c \@arcs section
-    ///
-    /// Add an additional caption to the \c \@arcs section.
+    /// \brief Set \c \@arcs section to be read
+    ///
+    /// Set \c \@arcs section to be read
     DigraphWriter& arcs(const std::string& caption) {
       _arcs_caption = caption;
@@ -606 +606 @@
     }
 
-    /// \brief Add an additional caption to the \c \@attributes section
-    ///
-    /// Add an additional caption to the \c \@attributes section.
+    /// \brief Set \c \@attributes section to be read
+    ///
+    /// Set \c \@attributes section to be read
     DigraphWriter& attributes(const std::string& caption) {
       _attributes_caption = caption;
@@ -619 +619 @@
     /// \brief Skip writing the node set
     ///
-    /// The \c \@nodes section will not be written to the stream.
+    /// The \c \@nodes section will be not 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 not be written to the stream.
+    /// The \c \@arcs section will be not 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 Give back the stream of the writer
-    ///
-    /// Give back the stream of the writer.
+    /// \brief Gives back the stream of the writer
+    ///
+    /// Gives 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>
@@ -872 +869 @@
   }
 
-  /// \brief Return a \ref DigraphWriter class
-  /// 
-  /// This function just returns a \ref DigraphWriter class.
   /// \relates DigraphWriter
   template <typename Digraph>
@@ -883 +877 @@
   }
 
-  /// \brief Return a \ref DigraphWriter class
-  /// 
-  /// This function just returns a \ref DigraphWriter class.
   /// \relates DigraphWriter
   template <typename Digraph>
@@ -908 +899 @@
   /// \ingroup lemon_io
   ///  
-  /// \brief \ref lgf-format "LGF" writer for directed graphs
+  /// \brief 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 {
@@ -1043 +1024 @@
     /// @{
     
-    /// \brief Node map writing rule
-    ///
-    /// Add a node map writing rule to the writer.
+    /// \brief Node map reading rule
+    ///
+    /// Add a node map reading rule to the writer.
     template <typename Map>
     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
@@ -1189 +1170 @@
     }
 
-    /// \name Section captions
+    /// \name Select section by name
     /// @{
 
-    /// \brief Add an additional caption to the \c \@nodes section
-    ///
-    /// Add an additional caption to the \c \@nodes section.
+    /// \brief Set \c \@nodes section to be read
+    ///
+    /// Set \c \@nodes section to be read
     GraphWriter& nodes(const std::string& caption) {
       _nodes_caption = caption;
@@ -1200 +1181 @@
     }
 
-    /// \brief Add an additional caption to the \c \@arcs section
-    ///
-    /// Add an additional caption to the \c \@arcs section.
+    /// \brief Set \c \@edges section to be read
+    ///
+    /// Set \c \@edges section to be read
     GraphWriter& edges(const std::string& caption) {
       _edges_caption = caption;
@@ -1208 +1189 @@
     }
 
-    /// \brief Add an additional caption to the \c \@attributes section
-    ///
-    /// Add an additional caption to the \c \@attributes section.
+    /// \brief Set \c \@attributes section to be read
+    ///
+    /// Set \c \@attributes section to be read
     GraphWriter& attributes(const std::string& caption) {
       _attributes_caption = caption;
@@ -1221 +1202 @@
     /// \brief Skip writing the node set
     ///
-    /// The \c \@nodes section will not be written to the stream.
+    /// The \c \@nodes section will be not written to the stream.
     GraphWriter& skipNodes() {
       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
@@ -1230 +1211 @@
     /// \brief Skip writing edge set
     ///
-    /// The \c \@edges section will not be written to the stream.
+    /// The \c \@edges section will be not written to the stream.
     GraphWriter& skipEdges() {
       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
@@ -1438 +1419 @@
     /// \brief Start the batch processing
     ///
-    /// This function starts the batch processing.
+    /// This function starts the batch processing
     void run() {
       if (!_skip_nodes) {
@@ -1453 +1434 @@
     }
 
-    /// \brief Give back the stream of the writer
-    ///
-    /// Give back the stream of the writer
+    /// \brief Gives back the stream of the writer
+    ///
+    /// Gives back the stream of the writer
     std::ostream& ostream() {
       return *_os;
@@ -1463 +1444 @@
   };
 
-  /// \brief Return a \ref GraphWriter class
-  /// 
-  /// This function just returns a \ref GraphWriter class.
   /// \relates GraphWriter
   template <typename Graph>
@@ -1473 +1451 @@
   }
 
-  /// \brief Return a \ref GraphWriter class
-  /// 
-  /// This function just returns a \ref GraphWriter class.
   /// \relates GraphWriter
   template <typename Graph>
@@ -1483 +1458 @@
   }
 
-  /// \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
@@ -15 +16 @@
         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 \
@@ -38 +37 @@
 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/smart_graph.h>
+#include <lemon/list_graph.h>
 
-#include <lemon/lgf_reader.h>
-#include <lemon/dijkstra.h>
-#include <lemon/maps.h>
+#include <lemon/digraph_reader.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() {
@@ -161 +47 @@
   typedef int Item;
   typedef int Prio;
-  typedef RangeMap<int> ItemIntMap;
+  typedef IntIntMap ItemIntMap;
+
+  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";
   
-  Digraph digraph;
-  IntArcMap length(digraph);
-  Node source;
-
-  std::istringstream input(test_lgf);
-  digraphReader(input, digraph).
-    arcMap("capacity", length).
-    node("source", source).
+  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).
     run();  
  
   {
+    std::cout << "Checking Bin Heap" << std::endl;
+
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
     
-    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+    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;
   }