Changes in / [576:f5bc148f7e1f:577:1c5d6e47921f] in lemon

Files:

• CMakeLists.txt (modified) (3 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/dimacs.h (modified) (2 diffs)
• lemon/min_cost_arborescence.h (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/min_cost_arborescence_test.cc (added)
• tools/CMakeLists.txt (added)
• tools/Makefile.am (modified) (2 diffs)
• tools/dimacs-solver.cc (added)

CMakeLists.txt

@@ -40 +40 @@
 ADD_SUBDIRECTORY(lemon)
 ADD_SUBDIRECTORY(demo)
+ADD_SUBDIRECTORY(tools)
 ADD_SUBDIRECTORY(doc)
 ADD_SUBDIRECTORY(test)
@@ -57 +58 @@
     "${PROJECT_NAME} ${PROJECT_VERSION}")
 
-  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 
   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
+  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 
@@ -67 +69 @@
   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     "DLL and import library")
+  SET(CPACK_COMPONENT_BIN_DESCRIPTION
+    "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     "Doxygen generated documentation")

lemon/Makefile.am

@@ -84 +84 @@
         lemon/math.h \
         lemon/max_matching.h \
+        lemon/min_cost_arborescence.h \
         lemon/nauty_reader.h \
         lemon/path.h \

lemon/dimacs.h

@@ -296 +296 @@
   }
 
-  /// DIMACS plain digraph reader function.
-  ///
-  /// This function reads a digraph without any designated nodes and
+  template<typename Graph>
+  typename enable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
+  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
+              dummy<0> = 0)
+  {
+    g.addEdge(s,t);
+  }
+  template<typename Graph>
+  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type
+  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,
+              dummy<1> = 1)
+  {
+    g.addArc(s,t);
+  }
+  
+  /// DIMACS plain (di)graph reader function.
+  ///
+  /// This function reads a (di)graph without any designated nodes and
   /// maps from DIMACS format, i.e. from DIMACS files having a line
   /// starting with
@@ -308 +323 @@
   /// If the file type was previously evaluated by dimacsType(), then
   /// the descriptor struct should be given by the \c dest parameter.
-  template<typename Digraph>
-  void readDimacsMat(std::istream& is, Digraph &g,
-                     DimacsDescriptor desc=DimacsDescriptor()) {
-    typename Digraph::Node u,v;
-    NullMap<typename Digraph::Arc, int> n;
+  template<typename Graph>
+  void readDimacsMat(std::istream& is, Graph &g,
+                     DimacsDescriptor desc=DimacsDescriptor())
+  {
     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
     if(desc.type!=DimacsDescriptor::MAT)
       throw FormatError("Problem type mismatch");
-    _readDimacs(is, g, n, u, v, desc);
+
+    g.clear();
+    std::vector<typename Graph::Node> nodes;
+    char c;
+    int i, j;
+    std::string str;
+    nodes.resize(desc.nodeNum + 1);
+    for (int k = 1; k <= desc.nodeNum; ++k) {
+      nodes[k] = g.addNode();
+    }
+    
+    while (is >> c) {
+      switch (c) {
+      case 'c': // comment line
+        getline(is, str);
+        break;
+      case 'n': // node definition line
+        break;
+      case 'a': // arc (arc) definition line
+        is >> i >> j;
+        getline(is, str);
+        _addArcEdge(g,nodes[i], nodes[j]);
+        break;
+      }
+    }
   }
 

test/CMakeLists.txt

@@ -30 +30 @@
   maps_test
   max_matching_test
+  min_cost_arborescence_test
   path_test
   preflow_test

test/Makefile.am

@@ -26 +26 @@
         test/maps_test \
         test/max_matching_test \
+        test/min_cost_arborescence_test \
         test/path_test \
         test/preflow_test \
@@ -67 +68 @@
 test_mip_test_SOURCES = test/mip_test.cc
 test_max_matching_test_SOURCES = test/max_matching_test.cc
+test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc

tools/Makefile.am

@@ -2 +2 @@
 
 bin_PROGRAMS += \
+        tools/dimacs-solver \
         tools/dimacs-to-lgf \
         tools/lgf-gen
@@ -9 +10 @@
 endif WANT_TOOLS
 
+tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc
 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
 tools_lgf_gen_SOURCES = tools/lgf-gen.cc