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