author | marci |
Fri, 12 Mar 2004 09:19:54 +0000 | |
changeset 174 | 44700ed9ffaa |
child 180 | 95f0c5f3fc70 |
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 std::vector<typename Graph::Node> nodes;
22 while (is>>c) {
23 switch (c) {
24 case 'c': //comment
25 getline(is, str);
26 break;
27 // case 't': //type
28 // getline(is, str);
29 // break;
30 case 'p': //problem definition
31 is >> problem >> n >> m;
32 getline(is, str);
33 nodes.resize(n+1);
34 for (int k=1; k<=n; ++k) nodes[k]=G.addNode();
35 break;
36 case 'n': //node definition
37 if (problem=="sp") { //shortest path problem
38 is >> i;
39 getline(is, str);
40 s=nodes[i];
41 }
42 if (problem=="max") { //max flow problem
43 is >> i >> d;
44 getline(is, str);
45 if (d=='s') s=nodes[i];
46 if (d=='t') t=nodes[i];
47 }
48 break;
49 case 'a':
50 is >> i >> j >> cap;
51 getline(is, str);
52 typename Graph::Edge e=G.addEdge(nodes[i], nodes[j]);
53 capacity.update();
54 capacity.set(e, cap);
55 break;
56 }
57 }
58 }
60 } //namespace hugo
62 #endif //DIMACS_H