equal
deleted
inserted
replaced
1 // -*- c++ -*- |
|
2 #ifndef HUGO_DIMACS_H |
|
3 #define HUGO_DIMACS_H |
|
4 |
|
5 #include <iostream> |
|
6 #include <string> |
|
7 #include <vector> |
|
8 |
|
9 namespace hugo { |
|
10 |
|
11 /// Dimacs flow files. |
|
12 |
|
13 /// This function reads a flow instance from dimacs flow format. |
|
14 /// At the beginning \c g is destroyed by \c g.clear(). |
|
15 /// If the data coming from \c is is a max flow innstance, then |
|
16 /// \c s and \t will be respectively the source and target nodes |
|
17 /// and \c capacity will contain the edge capacities. |
|
18 /// If the data is a shortest path problem then \c s will be the |
|
19 /// source node and \capacity will contain the edge lengths. |
|
20 template<typename Graph, typename CapacityMap> |
|
21 void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { |
|
22 g.clear(); |
|
23 int cap; |
|
24 char d; |
|
25 std::string problem; |
|
26 char c; |
|
27 int i, j; |
|
28 std::string str; |
|
29 int n, m; |
|
30 typename Graph::Edge e; |
|
31 std::vector<typename Graph::Node> nodes; |
|
32 while (is>>c) { |
|
33 switch (c) { |
|
34 case 'c': //comment |
|
35 getline(is, str); |
|
36 break; |
|
37 case 'p': //problem definition |
|
38 is >> problem >> n >> m; |
|
39 getline(is, str); |
|
40 nodes.resize(n+1); |
|
41 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); |
|
42 break; |
|
43 case 'n': //node definition |
|
44 if (problem=="sp") { //shortest path problem |
|
45 is >> i; |
|
46 getline(is, str); |
|
47 s=nodes[i]; |
|
48 } |
|
49 if (problem=="max") { //max flow problem |
|
50 is >> i >> d; |
|
51 getline(is, str); |
|
52 if (d=='s') s=nodes[i]; |
|
53 if (d=='t') t=nodes[i]; |
|
54 } |
|
55 break; |
|
56 case 'a': |
|
57 is >> i >> j >> cap; |
|
58 getline(is, str); |
|
59 e=g.addEdge(nodes[i], nodes[j]); |
|
60 capacity.update(); |
|
61 capacity.set(e, cap); |
|
62 break; |
|
63 } |
|
64 } |
|
65 } |
|
66 |
|
67 } //namespace hugo |
|
68 |
|
69 #endif //HUGO_DIMACS_H |
|