author | marci |
Mon, 26 Apr 2004 09:55:31 +0000 | |
changeset 410 | d137525538dc |
parent 206 | 47f62d789fe7 |
child 421 | 54b943063901 |
permissions | -rw-r--r-- |
marci@174 | 1 |
// -*- c++ -*- |
marci@259 | 2 |
#ifndef HUGO_DIMACS_H |
marci@259 | 3 |
#define HUGO_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 'p': //problem definition |
marci@174 | 29 |
is >> problem >> n >> m; |
marci@174 | 30 |
getline(is, str); |
marci@174 | 31 |
nodes.resize(n+1); |
marci@174 | 32 |
for (int k=1; k<=n; ++k) nodes[k]=G.addNode(); |
marci@174 | 33 |
break; |
marci@174 | 34 |
case 'n': //node definition |
marci@174 | 35 |
if (problem=="sp") { //shortest path problem |
marci@174 | 36 |
is >> i; |
marci@174 | 37 |
getline(is, str); |
marci@174 | 38 |
s=nodes[i]; |
marci@174 | 39 |
} |
marci@174 | 40 |
if (problem=="max") { //max flow problem |
marci@174 | 41 |
is >> i >> d; |
marci@174 | 42 |
getline(is, str); |
marci@174 | 43 |
if (d=='s') s=nodes[i]; |
marci@174 | 44 |
if (d=='t') t=nodes[i]; |
marci@174 | 45 |
} |
marci@174 | 46 |
break; |
marci@174 | 47 |
case 'a': |
marci@174 | 48 |
is >> i >> j >> cap; |
marci@174 | 49 |
getline(is, str); |
marci@180 | 50 |
e=G.addEdge(nodes[i], nodes[j]); |
marci@174 | 51 |
capacity.update(); |
marci@174 | 52 |
capacity.set(e, cap); |
marci@174 | 53 |
break; |
marci@174 | 54 |
} |
marci@174 | 55 |
} |
marci@174 | 56 |
} |
marci@174 | 57 |
|
marci@174 | 58 |
} //namespace hugo |
marci@174 | 59 |
|
marci@259 | 60 |
#endif //HUGO_DIMACS_H |