Changeset 1071:2d583da4ba40 in lemon

Timestamp:

08/04/11 21:47:29 (13 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1066:f9e3f73e17f1 (diff), 1067:54464584b157 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #382

Files:

• doc/lgf.dox (modified) (2 diffs)
• doc/lgf.dox (modified) (1 diff)
• lemon/lgf_reader.h (modified) (3 diffs)
• lemon/lgf_reader.h (modified) (47 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/CMakeLists.txt (modified) (2 diffs)
• test/Makefile.am (modified) (2 diffs)
• test/Makefile.am (modified) (2 diffs)

doc/lgf.dox

@@ -64 +64 @@
 \endcode
 
-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,
-but the \c "label" map is not obligatory here. The following lines
-describe the arcs. The first two tokens of each line are
-the source and the target node of the arc, respectively, then come the map
+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, but
+the \c "label" map is not obligatory here. The following lines
+describe the arcs. The first two tokens of each line are the source
+and the target node of the arc, respectively, then come the map
 values. The source and target tokens must be node labels.
 
@@ -79 +79 @@
 \endcode
 
+If there is no map in the \c \@arcs section at all, then it must be
+indicated by a sole '-' sign in the first line.
+
+\code
+ @arcs
+         -
+ 1   2
+ 1   3
+ 2   3
+\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
+have the same caption with \c '+' and \c '-' prefix, then these columns
 can be regarded as the values of an arc map.
 

doc/lgf.dox

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/lgf_reader.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -965 +965 @@
         int index = 0;
         while (_reader_bits::readToken(line, map)) {
+          if(map == "-") {
+              if(index!=0)
+                throw FormatError("'-' is not allowed as a map name");
+              else if (line >> std::ws >> c)
+                throw FormatError("Extra character at the end of line");
+              else break;
+            }
           if (maps.find(map) != maps.end()) {
             std::ostringstream msg;
@@ -1835 +1842 @@
         int index = 0;
         while (_reader_bits::readToken(line, map)) {
+          if(map == "-") {
+              if(index!=0)
+                throw FormatError("'-' is not allowed as a map name");
+              else if (line >> std::ws >> c)
+                throw FormatError("Extra character at the end of line");
+              else break;
+            }
           if (maps.find(map) != maps.end()) {
             std::ostringstream msg;

lemon/lgf_reader.h

@@ -102 +102 @@
     };
 
-    template <typename _Graph, bool _dir, typename _Map,
+    template <typename _GR, bool _dir, typename _Map,
               typename _Converter = DefaultConverter<typename _Map::Value> >
-    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
+    class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> {
     public:
       typedef _Map Map;
       typedef _Converter Converter;
-      typedef _Graph Graph;
-      typedef typename Graph::Edge Item;
+      typedef _GR GR;
+      typedef typename GR::Edge Item;
       static const bool dir = _dir;
 
     private:
-      const Graph& _graph;
+      const GR& _graph;
       Map& _map;
       Converter _converter;
 
     public:
-      GraphArcMapStorage(const Graph& graph, Map& map,
+      GraphArcMapStorage(const GR& graph, Map& map,
                          const Converter& converter = Converter())
         : _graph(graph), _map(map), _converter(converter) {}
@@ -174 +174 @@
     };
 
-    template <typename Graph>
+    template <typename GR>
     struct GraphArcLookUpConverter {
-      const Graph& _graph;
-      const std::map<std::string, typename Graph::Edge>& _map;
-
-      GraphArcLookUpConverter(const Graph& graph,
+      const GR& _graph;
+      const std::map<std::string, typename GR::Edge>& _map;
+
+      GraphArcLookUpConverter(const GR& graph,
                               const std::map<std::string,
-                                             typename Graph::Edge>& map)
+                                             typename GR::Edge>& map)
         : _graph(graph), _map(map) {}
 
-      typename Graph::Arc operator()(const std::string& str) {
+      typename GR::Arc operator()(const std::string& str) {
         if (str.empty() || (str[0] != '+' && str[0] != '-')) {
           throw FormatError("Item must start with '+' or '-'");
         }
-        typename std::map<std::string, typename Graph::Edge>
+        typename std::map<std::string, typename GR::Edge>
           ::const_iterator it = _map.find(str.substr(1));
         if (it == _map.end()) {
@@ -388 +388 @@
   }
 
-  template <typename Digraph>
+  template <typename DGR>
   class DigraphReader;
 
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph, 
-                                       std::istream& is = std::cin);
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin);
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn);
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
 
   /// \ingroup lemon_io
@@ -420 +419 @@
   ///
   ///\code
-  /// DigraphReader<Digraph>(digraph, std::cin).
+  /// DigraphReader<DGR>(digraph, std::cin).
   ///   nodeMap("coordinates", coord_map).
   ///   arcMap("capacity", cap_map).
@@ -429 +428 @@
   ///\endcode
   ///
-  /// By default the reader uses the first section in the file of the
+  /// By default, the reader uses the first section in the file of the
   /// proper type. If a section has an optional name, then it can be
   /// selected for reading by giving an optional name parameter to the
@@ -449 +448 @@
   /// a single pass, because the arcs are not constructed when the node
   /// maps are read.
-  template <typename _Digraph>
+  template <typename DGR>
   class DigraphReader {
   public:
 
-    typedef _Digraph Digraph;
-    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+    typedef DGR Digraph;
 
   private:
 
+    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
 
     std::istream* _is;
@@ -463 +462 @@
     std::string _filename;
 
-    Digraph& _digraph;
+    DGR& _digraph;
 
     std::string _nodes_caption;
@@ -501 +500 @@
     /// Construct a directed graph reader, which reads from the given
     /// input stream.
-    DigraphReader(Digraph& digraph, std::istream& is = std::cin)
+    DigraphReader(DGR& digraph, std::istream& is = std::cin)
       : _is(&is), local_is(false), _digraph(digraph),
         _use_nodes(false), _use_arcs(false),
@@ -510 +509 @@
     /// Construct a directed graph reader, which reads from the given
     /// file.
-    DigraphReader(Digraph& digraph, const std::string& fn)
+    DigraphReader(DGR& digraph, const std::string& fn)
       : _is(new std::ifstream(fn.c_str())), local_is(true),
         _filename(fn), _digraph(digraph),
@@ -525 +524 @@
     /// Construct a directed graph reader, which reads from the given
     /// file.
-    DigraphReader(Digraph& digraph, const char* fn)
+    DigraphReader(DGR& digraph, const char* fn)
       : _is(new std::ifstream(fn)), local_is(true),
         _filename(fn), _digraph(digraph),
@@ -561 +560 @@
   private:
 
-    template <typename DGR>
-    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
-    template <typename DGR>
-    friend DigraphReader<DGR> digraphReader(DGR& digraph, 
-                                            const std::string& fn);
-    template <typename DGR>
-    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
+    template <typename TDGR>
+    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
+    template <typename TDGR>
+    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
+                                             const std::string& fn);
+    template <typename TDGR>
+    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
 
     DigraphReader(DigraphReader& other)
@@ -594 +593 @@
   public:
 
-    /// \name Reading rules
+    /// \name Reading Rules
     /// @{
 
@@ -699 +698 @@
     /// @}
 
-    /// \name Select section by name
+    /// \name Select Section by Name
     /// @{
 
@@ -728 +727 @@
     /// @}
 
-    /// \name Using previously constructed node or arc set
+    /// \name Using Previously Constructed Node or Arc Set
     /// @{
 
@@ -848 +847 @@
         readLine();
       }
-      line.putback(c);
+      if (readSuccess()) {
+        line.putback(c);
+      }
     }
 
@@ -1122 +1123 @@
   public:
 
-    /// \name Execution of the reader
+    /// \name Execution of the Reader
     /// @{
 
@@ -1195 +1196 @@
   };
 
+  /// \ingroup lemon_io
+  ///
+  /// \brief Return a \ref DigraphReader class
+  ///
+  /// This function just returns a \ref DigraphReader class.
+  ///
+  /// With this function a digraph can be read from an
+  /// \ref lgf-format "LGF" file or input stream with several maps and
+  /// attributes. For example, there is network flow problem on a
+  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
+  /// \e source and \e target nodes. This digraph can be read with the
+  /// following code:
+  ///
+  ///\code
+  ///ListDigraph digraph;
+  ///ListDigraph::ArcMap<int> cm(digraph);
+  ///ListDigraph::Node src, trg;
+  ///digraphReader(digraph, std::cin).
+  ///  arcMap("capacity", cap).
+  ///  node("source", src).
+  ///  node("target", trg).
+  ///  run();
+  ///\endcode
+  ///
+  /// For a complete documentation, please see the \ref DigraphReader
+  /// class documentation.
+  /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
+  /// to the end of the parameter list.
+  /// \relates DigraphReader
+  /// \sa digraphReader(TDGR& digraph, const std::string& fn)
+  /// \sa digraphReader(TDGR& digraph, const char* fn)
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
+    DigraphReader<TDGR> tmp(digraph, is);
+    return tmp;
+  }
+
   /// \brief Return a \ref DigraphReader class
   ///
   /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
-    DigraphReader<Digraph> tmp(digraph, is);
+  /// \sa digraphReader(TDGR& digraph, std::istream& is)
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
+    DigraphReader<TDGR> tmp(digraph, fn);
     return tmp;
   }
@@ -1209 +1248 @@
   /// This function just returns a \ref DigraphReader class.
   /// \relates DigraphReader
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph,
-                                       const std::string& fn) {
-    DigraphReader<Digraph> tmp(digraph, fn);
+  /// \sa digraphReader(TDGR& digraph, std::istream& is)
+  template <typename TDGR>
+  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
+    DigraphReader<TDGR> tmp(digraph, fn);
     return tmp;
   }
 
-  /// \brief Return a \ref DigraphReader class
-  ///
-  /// This function just returns a \ref DigraphReader class.
-  /// \relates DigraphReader
-  template <typename Digraph>
-  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
-    DigraphReader<Digraph> tmp(digraph, fn);
-    return tmp;
-  }
-
-  template <typename Graph>
+  template <typename GR>
   class GraphReader;
- 
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, 
-                                 std::istream& is = std::cin);
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, const char *fn);
+
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
 
   /// \ingroup lemon_io
@@ -1252 +1280 @@
   /// 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>
+  template <typename GR>
   class GraphReader {
   public:
 
-    typedef _Graph Graph;
-    TEMPLATE_GRAPH_TYPEDEFS(Graph);
+    typedef GR Graph;
 
   private:
+
+    TEMPLATE_GRAPH_TYPEDEFS(GR);
 
     std::istream* _is;
@@ -1265 +1294 @@
     std::string _filename;
 
-    Graph& _graph;
+    GR& _graph;
 
     std::string _nodes_caption;
@@ -1303 +1332 @@
     /// Construct an undirected graph reader, which reads from the given
     /// input stream.
-    GraphReader(Graph& graph, std::istream& is = std::cin)
+    GraphReader(GR& graph, std::istream& is = std::cin)
       : _is(&is), local_is(false), _graph(graph),
         _use_nodes(false), _use_edges(false),
@@ -1312 +1341 @@
     /// Construct an undirected graph reader, which reads from the given
     /// file.
-    GraphReader(Graph& graph, const std::string& fn)
+    GraphReader(GR& graph, const std::string& fn)
       : _is(new std::ifstream(fn.c_str())), local_is(true),
         _filename(fn), _graph(graph),
@@ -1327 +1356 @@
     /// Construct an undirected graph reader, which reads from the given
     /// file.
-    GraphReader(Graph& graph, const char* fn)
+    GraphReader(GR& graph, const char* fn)
       : _is(new std::ifstream(fn)), local_is(true),
         _filename(fn), _graph(graph),
@@ -1362 +1391 @@
 
   private:
-    template <typename GR>
-    friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
-    template <typename GR>
-    friend GraphReader<GR> graphReader(GR& graph, const std::string& fn); 
-    template <typename GR>
-    friend GraphReader<GR> graphReader(GR& graph, const char *fn);
+    template <typename TGR>
+    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
+    template <typename TGR>
+    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
+    template <typename TGR>
+    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
 
     GraphReader(GraphReader& other)
@@ -1394 +1423 @@
   public:
 
-    /// \name Reading rules
+    /// \name Reading Rules
     /// @{
 
@@ -1459 +1488 @@
       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
       _reader_bits::MapStorageBase<Edge>* backward_storage =
-        new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
+        new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
       return *this;
@@ -1473 +1502 @@
       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
       _reader_bits::MapStorageBase<Edge>* forward_storage =
-        new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
+        new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
         (_graph, map, converter);
       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
       _reader_bits::MapStorageBase<Edge>* backward_storage =
-        new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
+        new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
         (_graph, map, converter);
       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
@@ -1535 +1564 @@
     /// Add an arc reading rule to reader.
     GraphReader& arc(const std::string& caption, Arc& arc) {
-      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
+      typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
       Converter converter(_graph, _edge_index);
       _reader_bits::ValueStorageBase* storage =
@@ -1545 +1574 @@
     /// @}
 
-    /// \name Select section by name
+    /// \name Select Section by Name
     /// @{
 
@@ -1574 +1603 @@
     /// @}
 
-    /// \name Using previously constructed node or edge set
+    /// \name Using Previously Constructed Node or Edge Set
     /// @{
 
@@ -1695 +1724 @@
         readLine();
       }
-      line.putback(c);
+      if (readSuccess()) {
+        line.putback(c);
+      }
     }
 
@@ -1969 +2000 @@
   public:
 
-    /// \name Execution of the reader
+    /// \name Execution of the Reader
     /// @{
 
@@ -2043 +2074 @@
   };
 
+  /// \ingroup lemon_io
+  ///
+  /// \brief Return a \ref GraphReader class
+  ///
+  /// This function just returns a \ref GraphReader class.
+  ///
+  /// With this function a graph can be read from an
+  /// \ref lgf-format "LGF" file or input stream with several maps and
+  /// attributes. For example, there is weighted matching problem on a
+  /// graph, i.e. a graph with a \e weight map on the edges. This
+  /// graph can be read with the following code:
+  ///
+  ///\code
+  ///ListGraph graph;
+  ///ListGraph::EdgeMap<int> weight(graph);
+  ///graphReader(graph, std::cin).
+  ///  edgeMap("weight", weight).
+  ///  run();
+  ///\endcode
+  ///
+  /// For a complete documentation, please see the \ref GraphReader
+  /// class documentation.
+  /// \warning Don't forget to put the \ref GraphReader::run() "run()"
+  /// to the end of the parameter list.
+  /// \relates GraphReader
+  /// \sa graphReader(TGR& graph, const std::string& fn)
+  /// \sa graphReader(TGR& graph, const char* fn)
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
+    GraphReader<TGR> tmp(graph, is);
+    return tmp;
+  }
+
   /// \brief Return a \ref GraphReader class
   ///
   /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
-    GraphReader<Graph> tmp(graph, is);
+  /// \sa graphReader(TGR& graph, std::istream& is)
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
+    GraphReader<TGR> tmp(graph, fn);
     return tmp;
   }
@@ -2057 +2122 @@
   /// This function just returns a \ref GraphReader class.
   /// \relates GraphReader
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
-    GraphReader<Graph> tmp(graph, fn);
-    return tmp;
-  }
-
-  /// \brief Return a \ref GraphReader class
-  ///
-  /// This function just returns a \ref GraphReader class.
-  /// \relates GraphReader
-  template <typename Graph>
-  GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
-    GraphReader<Graph> tmp(graph, fn);
+  /// \sa graphReader(TGR& graph, std::istream& is)
+  template <typename TGR>
+  GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
+    GraphReader<TGR> tmp(graph, fn);
     return tmp;
   }
@@ -2168 +2224 @@
   public:
 
-    /// \name Section readers
+    /// \name Section Readers
     /// @{
 
@@ -2180 +2236 @@
     /// whitespaces are trimmed from each processed string.
     ///
-    /// For example let's see a section, which contain several
+    /// For example, let's see a section, which contain several
     /// integers, which should be inserted into a vector.
     ///\code
@@ -2259 +2315 @@
         readLine();
       }
-      line.putback(c);
+      if (readSuccess()) {
+        line.putback(c);
+      }
     }
 
@@ -2265 +2323 @@
 
 
-    /// \name Execution of the reader
+    /// \name Execution of the Reader
     /// @{
 
@@ -2324 +2382 @@
   };
 
+  /// \ingroup lemon_io
+  ///
   /// \brief Return a \ref SectionReader class
   ///
   /// This function just returns a \ref SectionReader class.
+  ///
+  /// Please see SectionReader documentation about the custom section
+  /// input.
+  ///
   /// \relates SectionReader
+  /// \sa sectionReader(const std::string& fn)
+  /// \sa sectionReader(const char *fn)
   inline SectionReader sectionReader(std::istream& is) {
     SectionReader tmp(is);
@@ -2337 +2403 @@
   /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
+  /// \sa sectionReader(std::istream& is)
   inline SectionReader sectionReader(const std::string& fn) {
     SectionReader tmp(fn);
@@ -2346 +2413 @@
   /// This function just returns a \ref SectionReader class.
   /// \relates SectionReader
+  /// \sa sectionReader(std::istream& is)
   inline SectionReader sectionReader(const char* fn) {
     SectionReader tmp(fn);
@@ -2447 +2515 @@
 
 
-    /// \name Node sections
+    /// \name Node Sections
     /// @{
 
@@ -2473 +2541 @@
     /// @}
 
-    /// \name Arc/Edge sections
+    /// \name Arc/Edge Sections
     /// @{
 
@@ -2531 +2599 @@
     /// @}
 
-    /// \name Attribute sections
+    /// \name Attribute Sections
     /// @{
 
@@ -2557 +2625 @@
     /// @}
 
-    /// \name Extra sections
+    /// \name Extra Sections
     /// @{
 
@@ -2600 +2668 @@
         readLine();
       }
-      line.putback(c);
+      if (readSuccess()) {
+        line.putback(c);
+      }
     }
 
@@ -2631 +2701 @@
   public:
 
-    /// \name Execution of the contents reader
+    /// \name Execution of the Contents Reader
     /// @{
 

test/CMakeLists.txt

@@ -34 +34 @@
   heap_test
   kruskal_test
+  lgf_test
   maps_test
   matching_test

test/CMakeLists.txt

@@ -1 +1 @@
 INCLUDE_DIRECTORIES(
-  ${CMAKE_SOURCE_DIR}
+  ${PROJECT_SOURCE_DIR}
   ${PROJECT_BINARY_DIR}
 )
 
-LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(
+  ${PROJECT_BINARY_DIR}/lemon
+)
+
+SET(TEST_WITH_VALGRIND "NO" CACHE STRING
+  "Run the test with valgrind (YES/NO).")
+SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
 
 SET(TESTS
+  adaptors_test
+  bellman_ford_test
   bfs_test
+  circulation_test
+  connectivity_test
   counter_test
   dfs_test
@@ -13 +23 @@
   dijkstra_test
   dim_test
+  edge_set_test
   error_test
+  euler_test
+  fractional_matching_test
+  gomory_hu_test
   graph_copy_test
   graph_test
   graph_utils_test
+  hao_orlin_test
   heap_test
   kruskal_test
   lgf_test
   maps_test
+  matching_test
+  max_cardinality_search_test
+  max_clique_test
+  min_cost_arborescence_test
+  min_cost_flow_test
+  min_mean_cycle_test
+  nagamochi_ibaraki_test
+  path_test
+  planarity_test
+  preflow_test
+  radix_sort_test
   random_test
-  path_test
+  suurballe_test
   time_measure_test
-  unionfind_test)
+  unionfind_test
+)
+
+IF(LEMON_HAVE_LP)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(lp_test lp_test.cc)
+  ELSE()
+    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
+  ENDIF()
+
+  SET(LP_TEST_LIBS lemon)
+
+  IF(LEMON_HAVE_GLPK)
+    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
+  ENDIF()
+  IF(LEMON_HAVE_CPLEX)
+    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
+  ENDIF()
+  IF(LEMON_HAVE_CLP)
+    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
+  ENDIF()
+
+  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
+  ADD_TEST(lp_test lp_test)
+  ADD_DEPENDENCIES(check lp_test)
+
+  IF(WIN32 AND LEMON_HAVE_GLPK)
+    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
+    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
+    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+    )
+  ENDIF()
+
+  IF(WIN32 AND LEMON_HAVE_CPLEX)
+    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
+    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
+    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
+      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+    )
+  ENDIF()
+ENDIF()
+
+IF(LEMON_HAVE_MIP)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(mip_test mip_test.cc)
+  ELSE()
+    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
+  ENDIF()
+
+  SET(MIP_TEST_LIBS lemon)
+
+  IF(LEMON_HAVE_GLPK)
+    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
+  ENDIF()
+  IF(LEMON_HAVE_CPLEX)
+    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
+  ENDIF()
+  IF(LEMON_HAVE_CBC)
+    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
+  ENDIF()
+
+  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
+  ADD_TEST(mip_test mip_test)
+  ADD_DEPENDENCIES(check mip_test)
+
+  IF(WIN32 AND LEMON_HAVE_GLPK)
+    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
+    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
+    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
+      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+    )
+  ENDIF()
+
+  IF(WIN32 AND LEMON_HAVE_CPLEX)
+    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
+    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
+    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
+      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+    )
+  ENDIF()
+ENDIF()
 
 FOREACH(TEST_NAME ${TESTS})
-  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
+  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
+  ELSE()
+    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
+  ENDIF()
   TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
-  ADD_TEST(${TEST_NAME} ${TEST_NAME})
-ENDFOREACH(TEST_NAME)
+    IF(TEST_WITH_VALGRIND)
+      ADD_TEST(${TEST_NAME}
+        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
+        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
+    ELSE()
+      ADD_TEST(${TEST_NAME} ${TEST_NAME})
+    ENDIF()
+  ADD_DEPENDENCIES(check ${TEST_NAME})
+ENDFOREACH()

test/Makefile.am

@@ -32 +32 @@
         test/heap_test \
         test/kruskal_test \
+        test/lgf_test \
         test/maps_test \
         test/matching_test \
@@ -81 +82 @@
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
+test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
-test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
+test_lgf_test_SOURCES = test/lgf_test.cc
 test_lp_test_SOURCES = test/lp_test.cc
 test_maps_test_SOURCES = test/maps_test.cc

test/Makefile.am

@@ +1 @@
+if USE_VALGRIND
+TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
+endif
+
 EXTRA_DIST += \
         test/CMakeLists.txt
@@ -4 +8 @@
 noinst_HEADERS += \
         test/graph_test.h \
-        test/test_tools.h
+        test/test_tools.h
 
 check_PROGRAMS += \
+        test/adaptors_test \
+        test/bellman_ford_test \
         test/bfs_test \
-        test/counter_test \
+        test/circulation_test \
+        test/connectivity_test \
+        test/counter_test \
         test/dfs_test \
         test/digraph_test \
         test/dijkstra_test \
-        test/dim_test \
+        test/dim_test \
+        test/edge_set_test \
         test/error_test \
+        test/euler_test \
+        test/fractional_matching_test \
+        test/gomory_hu_test \
         test/graph_copy_test \
         test/graph_test \
         test/graph_utils_test \
+        test/hao_orlin_test \
         test/heap_test \
         test/kruskal_test \
         test/lgf_test \
-        test/maps_test \
-        test/random_test \
-        test/path_test \
-        test/test_tools_fail \
-        test/test_tools_pass \
-        test/time_measure_test \
+        test/maps_test \
+        test/matching_test \
+        test/max_cardinality_search_test \
+        test/max_clique_test \
+        test/min_cost_arborescence_test \
+        test/min_cost_flow_test \
+        test/min_mean_cycle_test \
+        test/nagamochi_ibaraki_test \
+        test/path_test \
+        test/planarity_test \
+        test/preflow_test \
+        test/radix_sort_test \
+        test/random_test \
+        test/suurballe_test \
+        test/test_tools_fail \
+        test/test_tools_pass \
+        test/time_measure_test \
         test/unionfind_test
+
+test_test_tools_pass_DEPENDENCIES = demo
+
+if HAVE_LP
+check_PROGRAMS += test/lp_test
+endif HAVE_LP
+if HAVE_MIP
+check_PROGRAMS += test/mip_test
+endif HAVE_MIP
 
 TESTS += $(check_PROGRAMS)
 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 
+test_adaptors_test_SOURCES = test/adaptors_test.cc
+test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
 test_bfs_test_SOURCES = test/bfs_test.cc
+test_circulation_test_SOURCES = test/circulation_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
+test_connectivity_test_SOURCES = test/connectivity_test.cc
 test_dfs_test_SOURCES = test/dfs_test.cc
 test_digraph_test_SOURCES = test/digraph_test.cc
 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 test_dim_test_SOURCES = test/dim_test.cc
+test_edge_set_test_SOURCES = test/edge_set_test.cc
 test_error_test_SOURCES = test/error_test.cc
+test_euler_test_SOURCES = test/euler_test.cc
+test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
+test_gomory_hu_test_SOURCES = test/gomory_hu_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_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
 test_lgf_test_SOURCES = test/lgf_test.cc
+test_lp_test_SOURCES = test/lp_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
+test_mip_test_SOURCES = test/mip_test.cc
+test_matching_test_SOURCES = test/matching_test.cc
+test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc
+test_max_clique_test_SOURCES = test/max_clique_test.cc
+test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
+test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
+test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc
 test_path_test_SOURCES = test/path_test.cc
+test_planarity_test_SOURCES = test/planarity_test.cc
+test_preflow_test_SOURCES = test/preflow_test.cc
+test_radix_sort_test_SOURCES = test/radix_sort_test.cc
+test_suurballe_test_SOURCES = test/suurballe_test.cc
 test_random_test_SOURCES = test/random_test.cc
 test_test_tools_fail_SOURCES = test/test_tools_fail.cc