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