1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/include/dimacs.h	Mon Apr 26 17:10:27 2004 +0000
     1.3 @@ -0,0 +1,69 @@
     1.4 +// -*- c++ -*-
     1.5 +#ifndef HUGO_DIMACS_H
     1.6 +#define HUGO_DIMACS_H
     1.7 +
     1.8 +#include <iostream>
     1.9 +#include <string>
    1.10 +#include <vector>
    1.11 +
    1.12 +namespace hugo {
    1.13 +
    1.14 +  /// Dimacs flow files.
    1.15 +
    1.16 +  /// This function reads a flow instance from dimacs flow format.
    1.17 +  /// At the beginning \c g is destroyed by \c g.clear().
    1.18 +  /// If the data coming from \c is is a max flow innstance, then 
    1.19 +  /// \c s and \t will be respectively the source and target nodes 
    1.20 +  /// and \c capacity will contain the edge capacities.
    1.21 +  /// If the data is a shortest path problem then \c s will be the 
    1.22 +  /// source node and \capacity will contain the edge lengths.
    1.23 +  template<typename Graph, typename CapacityMap>
    1.24 +  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    1.25 +    g.clear();
    1.26 +    int cap;
    1.27 +    char d;
    1.28 +    std::string problem;
    1.29 +    char c;
    1.30 +    int i, j;
    1.31 +    std::string str;
    1.32 +    int n, m; 
    1.33 +    typename Graph::Edge e;
    1.34 +    std::vector<typename Graph::Node> nodes;
    1.35 +    while (is>>c) {
    1.36 +      switch (c) {
    1.37 +      case 'c': //comment
    1.38 +	getline(is, str);
    1.39 +	break;
    1.40 +      case 'p': //problem definition
    1.41 +	is >> problem >> n >> m;
    1.42 +	getline(is, str);
    1.43 +	nodes.resize(n+1);
    1.44 +	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
    1.45 +	break;
    1.46 +      case 'n': //node definition
    1.47 +	if (problem=="sp") { //shortest path problem
    1.48 +	  is >> i;
    1.49 +	  getline(is, str);
    1.50 +	  s=nodes[i];
    1.51 +	}
    1.52 +	if (problem=="max") { //max flow problem
    1.53 +	  is >> i >> d;
    1.54 +	  getline(is, str);
    1.55 +	  if (d=='s') s=nodes[i];
    1.56 +	  if (d=='t') t=nodes[i];
    1.57 +	}
    1.58 +	break;
    1.59 +      case 'a':
    1.60 +	is >> i >> j >> cap;
    1.61 +	getline(is, str);
    1.62 +	e=g.addEdge(nodes[i], nodes[j]);
    1.63 +	capacity.update();
    1.64 +	capacity.set(e, cap);
    1.65 +	break;
    1.66 +      }
    1.67 +    }
    1.68 +  }
    1.69 +  
    1.70 +} //namespace hugo
    1.71 +
    1.72 +#endif //HUGO_DIMACS_H