author | marci |
Fri, 12 Mar 2004 20:09:35 +0000 | |
changeset 180 | 95f0c5f3fc70 |
parent 174 | 44700ed9ffaa |
child 206 | 47f62d789fe7 |
permissions | -rw-r--r-- |
marci@174 | 1 |
// -*- c++ -*- |
marci@174 | 2 |
#ifndef DIMACS_H |
marci@174 | 3 |
#define DIMACS_H |
marci@174 | 4 |
|
marci@174 | 5 |
#include <iostream> |
marci@174 | 6 |
#include <string> |
marci@174 | 7 |
#include <vector> |
marci@174 | 8 |
|
marci@174 | 9 |
namespace hugo { |
marci@174 | 10 |
|
marci@174 | 11 |
template<typename Graph, typename CapacityMap> |
marci@174 | 12 |
void readDimacsMaxFlow(std::istream& is, Graph &G, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { |
marci@174 | 13 |
G.clear(); |
marci@174 | 14 |
int cap; |
marci@174 | 15 |
char d; |
marci@174 | 16 |
std::string problem; |
marci@174 | 17 |
char c; |
marci@174 | 18 |
int i, j; |
marci@174 | 19 |
std::string str; |
marci@174 | 20 |
int n, m; |
marci@180 | 21 |
typename Graph::Edge e; |
marci@174 | 22 |
std::vector<typename Graph::Node> nodes; |
marci@174 | 23 |
while (is>>c) { |
marci@174 | 24 |
switch (c) { |
marci@174 | 25 |
case 'c': //comment |
marci@174 | 26 |
getline(is, str); |
marci@174 | 27 |
break; |
marci@174 | 28 |
// case 't': //type |
marci@174 | 29 |
// getline(is, str); |
marci@174 | 30 |
// break; |
marci@174 | 31 |
case 'p': //problem definition |
marci@174 | 32 |
is >> problem >> n >> m; |
marci@174 | 33 |
getline(is, str); |
marci@174 | 34 |
nodes.resize(n+1); |
marci@174 | 35 |
for (int k=1; k<=n; ++k) nodes[k]=G.addNode(); |
marci@174 | 36 |
break; |
marci@174 | 37 |
case 'n': //node definition |
marci@174 | 38 |
if (problem=="sp") { //shortest path problem |
marci@174 | 39 |
is >> i; |
marci@174 | 40 |
getline(is, str); |
marci@174 | 41 |
s=nodes[i]; |
marci@174 | 42 |
} |
marci@174 | 43 |
if (problem=="max") { //max flow problem |
marci@174 | 44 |
is >> i >> d; |
marci@174 | 45 |
getline(is, str); |
marci@174 | 46 |
if (d=='s') s=nodes[i]; |
marci@174 | 47 |
if (d=='t') t=nodes[i]; |
marci@174 | 48 |
} |
marci@174 | 49 |
break; |
marci@174 | 50 |
case 'a': |
marci@174 | 51 |
is >> i >> j >> cap; |
marci@174 | 52 |
getline(is, str); |
marci@180 | 53 |
e=G.addEdge(nodes[i], nodes[j]); |
marci@174 | 54 |
capacity.update(); |
marci@174 | 55 |
capacity.set(e, cap); |
marci@174 | 56 |
break; |
marci@174 | 57 |
} |
marci@174 | 58 |
} |
marci@174 | 59 |
} |
marci@174 | 60 |
|
marci@174 | 61 |
} //namespace hugo |
marci@174 | 62 |
|
marci@174 | 63 |
#endif //DIMACS_H |