Docs added
authorjacint
Fri, 07 May 2004 10:34:36 +0000
changeset 575bdf7fb750e0e
parent 574 7b0b12eb603b
child 576 d00c33d07114
Docs added
src/hugo/dimacs.h
     1.1 --- a/src/hugo/dimacs.h	Fri May 07 10:22:30 2004 +0000
     1.2 +++ b/src/hugo/dimacs.h	Fri May 07 10:34:36 2004 +0000
     1.3 @@ -7,103 +7,26 @@
     1.4  #include <vector>
     1.5  #include <hugo/maps.h>
     1.6  
     1.7 +/// \ingroup misc
     1.8  /// \file
     1.9  /// \brief Dimacs file format reader.
    1.10  
    1.11  namespace hugo {
    1.12  
    1.13 -  /// Dimacs flow file format reader function.
    1.14  
    1.15 -  /// This function reads a flow instance from dimacs flow format.
    1.16 -  /// At the beginning \c g is cleared by \c g.clear().
    1.17 -  /// If the data coming from \c is is a max flow problem instance, then 
    1.18 -  /// \c s and \c t will be respectively the source and target nodes 
    1.19 -  /// and \c capacity will contain the edge capacities.
    1.20 -  /// If the data is a shortest path problem instance then \c s will be the 
    1.21 -  /// source node and \c capacity will contain the edge lengths.
    1.22 +  /// \addtogroup misc
    1.23 +  /// @{
    1.24 +
    1.25 +  /// Dimacs min cost flow reader function.
    1.26 +
    1.27 +  /// This function reads a min cost flow instance from dimacs format,
    1.28 +  /// i.e. from dimacs files having a line starting with \c p \c "min".
    1.29 +  /// At the beginning \c g is cleared by \c g.clear(). The edge
    1.30 +  /// capacities are written to \c capacity, \c s and \c t are set to
    1.31 +  /// the source and the target nodes resp. and the cost of the edges
    1.32 +  /// are written to \c cost.
    1.33    ///
    1.34 -  ///\author Marton Makai
    1.35 -  template<typename Graph, typename CapacityMap>
    1.36 -  void readDimacsMaxFlow(std::istream& is, Graph &g, 
    1.37 -			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    1.38 -    g.clear();
    1.39 -    int cap;
    1.40 -    char d;
    1.41 -    std::string problem;
    1.42 -    char c;
    1.43 -    int i, j;
    1.44 -    std::string str;
    1.45 -    int n, m; 
    1.46 -    typename Graph::Edge e;
    1.47 -    std::vector<typename Graph::Node> nodes;
    1.48 -    while (is>>c) {
    1.49 -      switch (c) {
    1.50 -      case 'c': //comment
    1.51 -	getline(is, str);
    1.52 -	break;
    1.53 -      case 'p': //problem definition
    1.54 -	is >> problem >> n >> m;
    1.55 -	getline(is, str);
    1.56 -	nodes.resize(n+1);
    1.57 -	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
    1.58 -	break;
    1.59 -      case 'n': //node definition
    1.60 -	if (problem=="sp") { //shortest path problem
    1.61 -	  is >> i;
    1.62 -	  getline(is, str);
    1.63 -	  s=nodes[i];
    1.64 -	}
    1.65 -	if (problem=="max") { //max flow problem
    1.66 -	  is >> i >> d;
    1.67 -	  getline(is, str);
    1.68 -	  if (d=='s') s=nodes[i];
    1.69 -	  if (d=='t') t=nodes[i];
    1.70 -	}
    1.71 -	break;
    1.72 -      case 'a':
    1.73 -	is >> i >> j >> cap;
    1.74 -	getline(is, str);
    1.75 -	e=g.addEdge(nodes[i], nodes[j]);
    1.76 -	capacity.update();
    1.77 -	capacity.set(e, cap);
    1.78 -	break;
    1.79 -      }
    1.80 -    }
    1.81 -  }
    1.82 -
    1.83 -  /// matching problem
    1.84 -  template<typename Graph>
    1.85 -  void readDimacs(std::istream& is, Graph &g) {
    1.86 -    typename Graph::Node u;
    1.87 -    NullMap<typename Graph::Edge, int> n;
    1.88 -    readDimacs(is, g, n, u, u, n);
    1.89 -  }
    1.90 -
    1.91 -  /// sg problem
    1.92 -  template<typename Graph, typename CapacityMap>
    1.93 -  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
    1.94 -    typename Graph::Node u;
    1.95 -    NullMap<typename Graph::Edge, int> n;
    1.96 -    readDimacs(is, g, capacity, u, u, n);
    1.97 -  }
    1.98 -
    1.99 -  /// shortest path problem
   1.100 -  template<typename Graph, typename CapacityMap>
   1.101 -  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
   1.102 -		  typename Graph::Node &s) {
   1.103 -    NullMap<typename Graph::Edge, int> n;
   1.104 -    readDimacs(is, g, capacity, s, s, n);
   1.105 -  }
   1.106 -
   1.107 -  /// max flow problem
   1.108 -  template<typename Graph, typename CapacityMap>
   1.109 -  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
   1.110 -		  typename Graph::Node &s, typename Graph::Node &t) {
   1.111 -    NullMap<typename Graph::Edge, int> n;
   1.112 -    readDimacs(is, g, capacity, s, t, n);
   1.113 -  }
   1.114 -
   1.115 -  /// min cost flow problem
   1.116 +  /// \author Marton Makai
   1.117    template<typename Graph, typename CapacityMap, typename CostMap>
   1.118    void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
   1.119  		  typename Graph::Node &s, typename Graph::Node &t, 
   1.120 @@ -144,26 +67,26 @@
   1.121  	}
   1.122  	break;
   1.123        case 'a':
   1.124 -	if ( problem == "mat" ) {
   1.125 -	  is >> i >> j;
   1.126 -	  getline(is, str);
   1.127 -	  g.addEdge(nodes[i], nodes[j]);
   1.128 -	}
   1.129  	if ( problem == "max" || problem == "sp") {
   1.130  	  is >> i >> j >> _cap;
   1.131  	  getline(is, str);
   1.132  	  e=g.addEdge(nodes[i], nodes[j]);
   1.133  	  capacity.update();
   1.134  	  capacity.set(e, _cap);
   1.135 -	}
   1.136 -	if ( problem == "min" ) {
   1.137 -	  is >> i >> j >> _cap >> _cost;
   1.138 -	  getline(is, str);
   1.139 -	  e=g.addEdge(nodes[i], nodes[j]);
   1.140 -	  capacity.update();
   1.141 -	  capacity.set(e, _cap);
   1.142 -	  cost.update();
   1.143 -	  cost.set(e, _cost);
   1.144 +	} else {
   1.145 +	  if ( problem == "min" ) {
   1.146 +	    is >> i >> j >> _cap >> _cost;
   1.147 +	    getline(is, str);
   1.148 +	    e=g.addEdge(nodes[i], nodes[j]);
   1.149 +	    capacity.update();
   1.150 +	    capacity.set(e, _cap);
   1.151 +	    cost.update();
   1.152 +	    cost.set(e, _cost);
   1.153 +	  } else {
   1.154 +	    is >> i >> j;
   1.155 +	    getline(is, str);
   1.156 +	    g.addEdge(nodes[i], nodes[j]);
   1.157 +	  }
   1.158  	}
   1.159  	break;
   1.160        }
   1.161 @@ -171,6 +94,72 @@
   1.162    }
   1.163  
   1.164  
   1.165 +  /// Dimacs max flow reader function.
   1.166 +
   1.167 +  /// This function reads a max flow instance from dimacs format,
   1.168 +  /// i.e. from dimacs files having a line starting with \c p \c
   1.169 +  /// "max".  At the beginning \c g is cleared by \c g.clear(). The
   1.170 +  /// edge capacities are written to \c capacity and \c s and \c t are
   1.171 +  /// set to the source and the target nodes.
   1.172 +  ///
   1.173 +  /// \author Marton Makai
   1.174 +  template<typename Graph, typename CapacityMap>
   1.175 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
   1.176 +		  typename Graph::Node &s, typename Graph::Node &t) {
   1.177 +    NullMap<typename Graph::Edge, int> n;
   1.178 +    readDimacs(is, g, capacity, s, t, n);
   1.179 +  }
   1.180 +
   1.181 +
   1.182 +  /// Dimacs shortest path reader function.
   1.183 +
   1.184 +  /// This function reads a shortest path instance from dimacs format,
   1.185 +  /// i.e. from dimacs files having a line starting with \c p \c "sp".
   1.186 +  /// At the beginning \c g is cleared by \c g.clear(). The edge
   1.187 +  /// capacities are written to \c capacity and \c s is set to the
   1.188 +  /// source node.
   1.189 +  ///
   1.190 +  /// \author Marton Makai
   1.191 +  template<typename Graph, typename CapacityMap>
   1.192 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
   1.193 +		  typename Graph::Node &s) {
   1.194 +    NullMap<typename Graph::Edge, int> n;
   1.195 +    readDimacs(is, g, capacity, s, s, n);
   1.196 +  }
   1.197 +
   1.198 +
   1.199 +  /// Dimacs capacitated graph reader function.
   1.200 +
   1.201 +  /// This function reads an edge capacitated graph instance from
   1.202 +  /// dimacs format.  At the beginning \c g is cleared by \c g.clear()
   1.203 +  /// and the edge capacities are written to \c capacity.
   1.204 +  ///
   1.205 +  /// \author Marton Makai
   1.206 +  template<typename Graph, typename CapacityMap>
   1.207 +  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
   1.208 +    typename Graph::Node u;
   1.209 +    NullMap<typename Graph::Edge, int> n;
   1.210 +    readDimacs(is, g, capacity, u, u, n);
   1.211 +  }
   1.212 +
   1.213 +
   1.214 +  /// Dimacs plain graph reader function.
   1.215 +
   1.216 +  /// This function reads a graph without any designated nodes and
   1.217 +  /// maps from dimacs format, i.e. from dimacs files having a line
   1.218 +  /// starting with \c p \c "mat".  At the beginning \c g is cleared
   1.219 +  /// by \c g.clear().
   1.220 +  ///
   1.221 +  /// \author Marton Makai
   1.222 +  template<typename Graph>
   1.223 +  void readDimacs(std::istream& is, Graph &g) {
   1.224 +    typename Graph::Node u;
   1.225 +    NullMap<typename Graph::Edge, int> n;
   1.226 +    readDimacs(is, g, n, u, u, n);
   1.227 +  }
   1.228 +  
   1.229 +
   1.230 +
   1.231    
   1.232    /// write matching problem
   1.233    template<typename Graph>
   1.234 @@ -199,7 +188,56 @@
   1.235    }
   1.236  
   1.237  
   1.238 +  /// @}
   1.239  
   1.240  } //namespace hugo
   1.241  
   1.242  #endif //HUGO_DIMACS_H
   1.243 +
   1.244 +//  template<typename Graph, typename CapacityMap>
   1.245 +//   void readDimacsMaxFlow(std::istream& is, Graph &g, 
   1.246 +// 			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
   1.247 +//     g.clear();
   1.248 +//     int cap;
   1.249 +//     char d;
   1.250 +//     std::string problem;
   1.251 +//     char c;
   1.252 +//     int i, j;
   1.253 +//     std::string str;
   1.254 +//     int n, m; 
   1.255 +//     typename Graph::Edge e;
   1.256 +//     std::vector<typename Graph::Node> nodes;
   1.257 +//     while (is>>c) {
   1.258 +//       switch (c) {
   1.259 +//       case 'c': //comment
   1.260 +// 	getline(is, str);
   1.261 +// 	break;
   1.262 +//       case 'p': //problem definition
   1.263 +// 	is >> problem >> n >> m;
   1.264 +// 	getline(is, str);
   1.265 +// 	nodes.resize(n+1);
   1.266 +// 	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
   1.267 +// 	break;
   1.268 +//       case 'n': //node definition
   1.269 +// 	if (problem=="sp") { //shortest path problem
   1.270 +// 	  is >> i;
   1.271 +// 	  getline(is, str);
   1.272 +// 	  s=nodes[i];
   1.273 +// 	}
   1.274 +// 	if (problem=="max") { //max flow problem
   1.275 +// 	  is >> i >> d;
   1.276 +// 	  getline(is, str);
   1.277 +// 	  if (d=='s') s=nodes[i];
   1.278 +// 	  if (d=='t') t=nodes[i];
   1.279 +// 	}
   1.280 +// 	break;
   1.281 +//       case 'a':
   1.282 +// 	is >> i >> j >> cap;
   1.283 +// 	getline(is, str);
   1.284 +// 	e=g.addEdge(nodes[i], nodes[j]);
   1.285 +// 	capacity.update();
   1.286 +// 	capacity.set(e, cap);
   1.287 +// 	break;
   1.288 +//       }
   1.289 +//     }
   1.290 +//   }