Changeset 528:c00f6ebbe1e6 in lemon-0.x

Timestamp:

05/04/04 18:16:49 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@694

Message:

Able to read min cost flow, max flow, shortest path, matching testgraphs

File:

• src/include/dimacs.h (modified) (3 diffs)

src/include/dimacs.h

@@ -6 +6 @@
 #include <string>
 #include <vector>
+#include <maps.h>
 
 /// \file
@@ -24 +25 @@
   ///\author Marton Makai
   template<typename Graph, typename CapacityMap>
-  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
+  void readDimacsMaxFlow(std::istream& is, Graph &g, 
+                         typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
     g.clear();
     int cap;
@@ -69 +71 @@
     }
   }
+
+  /// matching problem
+  template<typename Graph>
+  void readDimacs(std::istream& is, Graph &g) {
+    typename Graph::Node u;
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, n, u, u, n);
+    std::cout<<"igen en.";
+  }
+
+  /// sg problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
+    typename Graph::Node u;
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, cap, u, u, n);
+  }
+
+  /// shortest path problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+                  typename Graph::Node &s) {
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, capacity, s, s, n);
+  }
+
+  /// max flow problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+                  typename Graph::Node &s, typename Graph::Node &t) {
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, capacity, s, t, n);
+  }
+
+  /// min cost flow problem
+  template<typename Graph, typename CapacityMap, typename CostMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+                  typename Graph::Node &s, typename Graph::Node &t, 
+                  CostMap& cost) {
+    g.clear();
+    typename CapacityMap::ValueType _cap;
+    typename CostMap::ValueType _cost;
+    char d;
+    std::string problem;
+    char c;
+    int i, j;
+    std::string str;
+    int n, m; 
+    typename Graph::Edge e;
+    std::vector<typename Graph::Node> nodes;
+    while (is>>c) {
+      switch (c) {
+      case 'c': //comment
+        getline(is, str);
+        break;
+      case 'p': //problem definition
+        is >> problem >> n >> m;
+        getline(is, str);
+        nodes.resize(n+1);
+        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
+        break;
+      case 'n': //node definition
+        if (problem=="sp") { //shortest path problem
+          is >> i;
+          getline(is, str);
+          s=nodes[i];
+        }
+        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
+          is >> i >> d;
+          getline(is, str);
+          if (d=='s') s=nodes[i];
+          if (d=='t') t=nodes[i];
+        }
+        break;
+      case 'a':
+        if ( problem == "mat" ) {
+          is >> i >> j;
+          getline(is, str);
+          g.addEdge(nodes[i], nodes[j]);
+        }
+        if ( problem == "max" || problem == "sp") {
+          is >> i >> j >> _cap;
+          getline(is, str);
+          e=g.addEdge(nodes[i], nodes[j]);
+          capacity.update();
+          capacity.set(e, _cap);
+        }
+        if ( problem == "min" ) {
+          is >> i >> j >> _cap >> _cost;
+          getline(is, str);
+          e=g.addEdge(nodes[i], nodes[j]);
+          capacity.update();
+          capacity.set(e, _cap);
+          cost.update();
+          cost.set(e, _cost);
+        }
+        break;
+      }
+    }
+  }
+
+
   
+  /// write matching problem
+  template<typename Graph>
+  void writeDimacs(std::ostream& os, const Graph &g) {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EdgeIt EdgeIt;  
+    
+    typename Graph::template NodeMap<int> nodes(g);
+
+    os << "c matching problem" << std::endl;
+
+    int i=1;
+    NodeIt v;
+    for(g.first(v); g.valid(v); g.next(v)) {
+      nodes.set(v, i);
+      ++i;
+    }    
+    
+    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
+
+    EdgeIt e;
+    for(g.first(e); g.valid(e); g.next(e)) {
+      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; 
+    }
+
+  }
+
+
+
 } //namespace hugo