marci@423: // -*- c++ -*-
marci@423: #ifndef HUGO_DIMACS_H
marci@423: #define HUGO_DIMACS_H
marci@423: 
marci@423: #include <iostream>
marci@423: #include <string>
marci@423: #include <vector>
ladanyi@542: #include <hugo/maps.h>
marci@423: 
klao@442: /// \file
klao@442: /// \brief Dimacs file format reader.
klao@427: 
marci@423: namespace hugo {
marci@423: 
klao@427:   /// Dimacs flow file format reader function.
marci@423: 
marci@423:   /// This function reads a flow instance from dimacs flow format.
klao@427:   /// At the beginning \c g is cleared by \c g.clear().
klao@427:   /// If the data coming from \c is is a max flow problem instance, then 
klao@427:   /// \c s and \c t will be respectively the source and target nodes 
marci@423:   /// and \c capacity will contain the edge capacities.
klao@427:   /// If the data is a shortest path problem instance then \c s will be the 
klao@427:   /// source node and \c capacity will contain the edge lengths.
marci@465:   ///
marci@465:   ///\author Marton Makai
marci@423:   template<typename Graph, typename CapacityMap>
jacint@528:   void readDimacsMaxFlow(std::istream& is, Graph &g, 
jacint@528: 			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
marci@423:     g.clear();
marci@423:     int cap;
marci@423:     char d;
marci@423:     std::string problem;
marci@423:     char c;
marci@423:     int i, j;
marci@423:     std::string str;
marci@423:     int n, m; 
marci@423:     typename Graph::Edge e;
marci@423:     std::vector<typename Graph::Node> nodes;
marci@423:     while (is>>c) {
marci@423:       switch (c) {
marci@423:       case 'c': //comment
marci@423: 	getline(is, str);
marci@423: 	break;
marci@423:       case 'p': //problem definition
marci@423: 	is >> problem >> n >> m;
marci@423: 	getline(is, str);
marci@423: 	nodes.resize(n+1);
marci@423: 	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
marci@423: 	break;
marci@423:       case 'n': //node definition
marci@423: 	if (problem=="sp") { //shortest path problem
marci@423: 	  is >> i;
marci@423: 	  getline(is, str);
marci@423: 	  s=nodes[i];
marci@423: 	}
marci@423: 	if (problem=="max") { //max flow problem
marci@423: 	  is >> i >> d;
marci@423: 	  getline(is, str);
marci@423: 	  if (d=='s') s=nodes[i];
marci@423: 	  if (d=='t') t=nodes[i];
marci@423: 	}
marci@423: 	break;
marci@423:       case 'a':
marci@423: 	is >> i >> j >> cap;
marci@423: 	getline(is, str);
marci@423: 	e=g.addEdge(nodes[i], nodes[j]);
marci@423: 	capacity.update();
marci@423: 	capacity.set(e, cap);
marci@423: 	break;
marci@423:       }
marci@423:     }
marci@423:   }
jacint@528: 
jacint@528:   /// matching problem
jacint@528:   template<typename Graph>
jacint@528:   void readDimacs(std::istream& is, Graph &g) {
jacint@528:     typename Graph::Node u;
jacint@528:     NullMap<typename Graph::Edge, int> n;
jacint@528:     readDimacs(is, g, n, u, u, n);
jacint@528:   }
jacint@528: 
jacint@528:   /// sg problem
jacint@528:   template<typename Graph, typename CapacityMap>
jacint@528:   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
jacint@528:     typename Graph::Node u;
jacint@528:     NullMap<typename Graph::Edge, int> n;
alpar@533:     readDimacs(is, g, capacity, u, u, n);
jacint@528:   }
jacint@528: 
jacint@528:   /// shortest path problem
jacint@528:   template<typename Graph, typename CapacityMap>
jacint@528:   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
jacint@528: 		  typename Graph::Node &s) {
jacint@528:     NullMap<typename Graph::Edge, int> n;
jacint@528:     readDimacs(is, g, capacity, s, s, n);
jacint@528:   }
jacint@528: 
jacint@528:   /// max flow problem
jacint@528:   template<typename Graph, typename CapacityMap>
jacint@528:   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
jacint@528: 		  typename Graph::Node &s, typename Graph::Node &t) {
jacint@528:     NullMap<typename Graph::Edge, int> n;
jacint@528:     readDimacs(is, g, capacity, s, t, n);
jacint@528:   }
jacint@528: 
jacint@528:   /// min cost flow problem
jacint@528:   template<typename Graph, typename CapacityMap, typename CostMap>
jacint@528:   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
jacint@528: 		  typename Graph::Node &s, typename Graph::Node &t, 
jacint@528: 		  CostMap& cost) {
jacint@528:     g.clear();
jacint@528:     typename CapacityMap::ValueType _cap;
jacint@528:     typename CostMap::ValueType _cost;
jacint@528:     char d;
jacint@528:     std::string problem;
jacint@528:     char c;
jacint@528:     int i, j;
jacint@528:     std::string str;
jacint@528:     int n, m; 
jacint@528:     typename Graph::Edge e;
jacint@528:     std::vector<typename Graph::Node> nodes;
jacint@528:     while (is>>c) {
jacint@528:       switch (c) {
jacint@528:       case 'c': //comment
jacint@528: 	getline(is, str);
jacint@528: 	break;
jacint@528:       case 'p': //problem definition
jacint@528: 	is >> problem >> n >> m;
jacint@528: 	getline(is, str);
jacint@528: 	nodes.resize(n+1);
jacint@528: 	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
jacint@528: 	break;
jacint@528:       case 'n': //node definition
jacint@528: 	if (problem=="sp") { //shortest path problem
jacint@528: 	  is >> i;
jacint@528: 	  getline(is, str);
jacint@528: 	  s=nodes[i];
jacint@528: 	}
jacint@528: 	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
jacint@528: 	  is >> i >> d;
jacint@528: 	  getline(is, str);
jacint@528: 	  if (d=='s') s=nodes[i];
jacint@528: 	  if (d=='t') t=nodes[i];
jacint@528: 	}
jacint@528: 	break;
jacint@528:       case 'a':
jacint@528: 	if ( problem == "mat" ) {
jacint@528: 	  is >> i >> j;
jacint@528: 	  getline(is, str);
jacint@528: 	  g.addEdge(nodes[i], nodes[j]);
jacint@528: 	}
jacint@528: 	if ( problem == "max" || problem == "sp") {
jacint@528: 	  is >> i >> j >> _cap;
jacint@528: 	  getline(is, str);
jacint@528: 	  e=g.addEdge(nodes[i], nodes[j]);
jacint@528: 	  capacity.update();
jacint@528: 	  capacity.set(e, _cap);
jacint@528: 	}
jacint@528: 	if ( problem == "min" ) {
jacint@528: 	  is >> i >> j >> _cap >> _cost;
jacint@528: 	  getline(is, str);
jacint@528: 	  e=g.addEdge(nodes[i], nodes[j]);
jacint@528: 	  capacity.update();
jacint@528: 	  capacity.set(e, _cap);
jacint@528: 	  cost.update();
jacint@528: 	  cost.set(e, _cost);
jacint@528: 	}
jacint@528: 	break;
jacint@528:       }
jacint@528:     }
jacint@528:   }
jacint@528: 
jacint@528: 
marci@423:   
jacint@528:   /// write matching problem
jacint@528:   template<typename Graph>
jacint@528:   void writeDimacs(std::ostream& os, const Graph &g) {
jacint@528:     typedef typename Graph::NodeIt NodeIt;
jacint@528:     typedef typename Graph::EdgeIt EdgeIt;  
jacint@528:     
jacint@528:     typename Graph::template NodeMap<int> nodes(g);
jacint@528: 
jacint@528:     os << "c matching problem" << std::endl;
jacint@528: 
jacint@528:     int i=1;
jacint@528:     NodeIt v;
jacint@528:     for(g.first(v); g.valid(v); g.next(v)) {
jacint@528:       nodes.set(v, i);
jacint@528:       ++i;
jacint@528:     }    
jacint@528:     
jacint@528:     os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
jacint@528: 
jacint@528:     EdgeIt e;
jacint@528:     for(g.first(e); g.valid(e); g.next(e)) {
jacint@528:       os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; 
jacint@528:     }
jacint@528: 
jacint@528:   }
jacint@528: 
jacint@528: 
jacint@528: 
marci@423: } //namespace hugo
marci@423: 
marci@423: #endif //HUGO_DIMACS_H