1.1 --- a/src/include/dimacs.h	Tue May 04 14:54:21 2004 +0000
     1.2 +++ b/src/include/dimacs.h	Tue May 04 16:16:49 2004 +0000
     1.3 @@ -5,6 +5,7 @@
     1.4  #include <iostream>
     1.5  #include <string>
     1.6  #include <vector>
     1.7 +#include <maps.h>
     1.8  
     1.9  /// \file
    1.10  /// \brief Dimacs file format reader.
    1.11 @@ -23,7 +24,8 @@
    1.12    ///
    1.13    ///\author Marton Makai
    1.14    template<typename Graph, typename CapacityMap>
    1.15 -  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    1.16 +  void readDimacsMaxFlow(std::istream& is, Graph &g, 
    1.17 +			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    1.18      g.clear();
    1.19      int cap;
    1.20      char d;
    1.21 @@ -68,7 +70,137 @@
    1.22        }
    1.23      }
    1.24    }
    1.25 +
    1.26 +  /// matching problem
    1.27 +  template<typename Graph>
    1.28 +  void readDimacs(std::istream& is, Graph &g) {
    1.29 +    typename Graph::Node u;
    1.30 +    NullMap<typename Graph::Edge, int> n;
    1.31 +    readDimacs(is, g, n, u, u, n);
    1.32 +    std::cout<<"igen en.";
    1.33 +  }
    1.34 +
    1.35 +  /// sg problem
    1.36 +  template<typename Graph, typename CapacityMap>
    1.37 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
    1.38 +    typename Graph::Node u;
    1.39 +    NullMap<typename Graph::Edge, int> n;
    1.40 +    readDimacs(is, g, cap, u, u, n);
    1.41 +  }
    1.42 +
    1.43 +  /// shortest path problem
    1.44 +  template<typename Graph, typename CapacityMap>
    1.45 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
    1.46 +		  typename Graph::Node &s) {
    1.47 +    NullMap<typename Graph::Edge, int> n;
    1.48 +    readDimacs(is, g, capacity, s, s, n);
    1.49 +  }
    1.50 +
    1.51 +  /// max flow problem
    1.52 +  template<typename Graph, typename CapacityMap>
    1.53 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
    1.54 +		  typename Graph::Node &s, typename Graph::Node &t) {
    1.55 +    NullMap<typename Graph::Edge, int> n;
    1.56 +    readDimacs(is, g, capacity, s, t, n);
    1.57 +  }
    1.58 +
    1.59 +  /// min cost flow problem
    1.60 +  template<typename Graph, typename CapacityMap, typename CostMap>
    1.61 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
    1.62 +		  typename Graph::Node &s, typename Graph::Node &t, 
    1.63 +		  CostMap& cost) {
    1.64 +    g.clear();
    1.65 +    typename CapacityMap::ValueType _cap;
    1.66 +    typename CostMap::ValueType _cost;
    1.67 +    char d;
    1.68 +    std::string problem;
    1.69 +    char c;
    1.70 +    int i, j;
    1.71 +    std::string str;
    1.72 +    int n, m; 
    1.73 +    typename Graph::Edge e;
    1.74 +    std::vector<typename Graph::Node> nodes;
    1.75 +    while (is>>c) {
    1.76 +      switch (c) {
    1.77 +      case 'c': //comment
    1.78 +	getline(is, str);
    1.79 +	break;
    1.80 +      case 'p': //problem definition
    1.81 +	is >> problem >> n >> m;
    1.82 +	getline(is, str);
    1.83 +	nodes.resize(n+1);
    1.84 +	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
    1.85 +	break;
    1.86 +      case 'n': //node definition
    1.87 +	if (problem=="sp") { //shortest path problem
    1.88 +	  is >> i;
    1.89 +	  getline(is, str);
    1.90 +	  s=nodes[i];
    1.91 +	}
    1.92 +	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
    1.93 +	  is >> i >> d;
    1.94 +	  getline(is, str);
    1.95 +	  if (d=='s') s=nodes[i];
    1.96 +	  if (d=='t') t=nodes[i];
    1.97 +	}
    1.98 +	break;
    1.99 +      case 'a':
   1.100 +	if ( problem == "mat" ) {
   1.101 +	  is >> i >> j;
   1.102 +	  getline(is, str);
   1.103 +	  g.addEdge(nodes[i], nodes[j]);
   1.104 +	}
   1.105 +	if ( problem == "max" || problem == "sp") {
   1.106 +	  is >> i >> j >> _cap;
   1.107 +	  getline(is, str);
   1.108 +	  e=g.addEdge(nodes[i], nodes[j]);
   1.109 +	  capacity.update();
   1.110 +	  capacity.set(e, _cap);
   1.111 +	}
   1.112 +	if ( problem == "min" ) {
   1.113 +	  is >> i >> j >> _cap >> _cost;
   1.114 +	  getline(is, str);
   1.115 +	  e=g.addEdge(nodes[i], nodes[j]);
   1.116 +	  capacity.update();
   1.117 +	  capacity.set(e, _cap);
   1.118 +	  cost.update();
   1.119 +	  cost.set(e, _cost);
   1.120 +	}
   1.121 +	break;
   1.122 +      }
   1.123 +    }
   1.124 +  }
   1.125 +
   1.126 +
   1.127    
   1.128 +  /// write matching problem
   1.129 +  template<typename Graph>
   1.130 +  void writeDimacs(std::ostream& os, const Graph &g) {
   1.131 +    typedef typename Graph::NodeIt NodeIt;
   1.132 +    typedef typename Graph::EdgeIt EdgeIt;  
   1.133 +    
   1.134 +    typename Graph::template NodeMap<int> nodes(g);
   1.135 +
   1.136 +    os << "c matching problem" << std::endl;
   1.137 +
   1.138 +    int i=1;
   1.139 +    NodeIt v;
   1.140 +    for(g.first(v); g.valid(v); g.next(v)) {
   1.141 +      nodes.set(v, i);
   1.142 +      ++i;
   1.143 +    }    
   1.144 +    
   1.145 +    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
   1.146 +
   1.147 +    EdgeIt e;
   1.148 +    for(g.first(e); g.valid(e); g.next(e)) {
   1.149 +      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; 
   1.150 +    }
   1.151 +
   1.152 +  }
   1.153 +
   1.154 +
   1.155 +
   1.156  } //namespace hugo
   1.157  
   1.158  #endif //HUGO_DIMACS_H