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