COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dimacs.h @ 549:5531429143bc

Last change on this file since 549:5531429143bc was 549:5531429143bc, checked in by marci, 16 years ago
File size: 5.0 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_DIMACS_H
3#define HUGO_DIMACS_H
4
5#include <iostream>
6#include <string>
7#include <vector>
8#include <hugo/maps.h>
9
10/// \file
11/// \brief Dimacs file format reader.
12
13namespace hugo {
14
15  /// Dimacs flow file format reader function.
16
17  /// This function reads a flow instance from dimacs flow format.
18  /// At the beginning \c g is cleared by \c g.clear().
19  /// If the data coming from \c is is a max flow problem instance, then
20  /// \c s and \c t will be respectively the source and target nodes
21  /// and \c capacity will contain the edge capacities.
22  /// If the data is a shortest path problem instance then \c s will be the
23  /// source node and \c capacity will contain the edge lengths.
24  ///
25  ///\author Marton Makai
26  template<typename Graph, typename CapacityMap>
27  void readDimacsMaxFlow(std::istream& is, Graph &g,
28                         typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
29    g.clear();
30    int cap;
31    char d;
32    std::string problem;
33    char c;
34    int i, j;
35    std::string str;
36    int n, m;
37    typename Graph::Edge e;
38    std::vector<typename Graph::Node> nodes;
39    while (is>>c) {
40      switch (c) {
41      case 'c': //comment
42        getline(is, str);
43        break;
44      case 'p': //problem definition
45        is >> problem >> n >> m;
46        getline(is, str);
47        nodes.resize(n+1);
48        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
49        break;
50      case 'n': //node definition
51        if (problem=="sp") { //shortest path problem
52          is >> i;
53          getline(is, str);
54          s=nodes[i];
55        }
56        if (problem=="max") { //max flow problem
57          is >> i >> d;
58          getline(is, str);
59          if (d=='s') s=nodes[i];
60          if (d=='t') t=nodes[i];
61        }
62        break;
63      case 'a':
64        is >> i >> j >> cap;
65        getline(is, str);
66        e=g.addEdge(nodes[i], nodes[j]);
67        capacity.update();
68        capacity.set(e, cap);
69        break;
70      }
71    }
72  }
73
74  /// matching problem
75  template<typename Graph>
76  void readDimacs(std::istream& is, Graph &g) {
77    typename Graph::Node u;
78    NullMap<typename Graph::Edge, int> n;
79    readDimacs(is, g, n, u, u, n);
80  }
81
82  /// sg problem
83  template<typename Graph, typename CapacityMap>
84  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
85    typename Graph::Node u;
86    NullMap<typename Graph::Edge, int> n;
87    readDimacs(is, g, capacity, u, u, n);
88  }
89
90  /// shortest path problem
91  template<typename Graph, typename CapacityMap>
92  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
93                  typename Graph::Node &s) {
94    NullMap<typename Graph::Edge, int> n;
95    readDimacs(is, g, capacity, s, s, n);
96  }
97
98  /// max flow problem
99  template<typename Graph, typename CapacityMap>
100  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
101                  typename Graph::Node &s, typename Graph::Node &t) {
102    NullMap<typename Graph::Edge, int> n;
103    readDimacs(is, g, capacity, s, t, n);
104  }
105
106  /// min cost flow problem
107  template<typename Graph, typename CapacityMap, typename CostMap>
108  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
109                  typename Graph::Node &s, typename Graph::Node &t,
110                  CostMap& cost) {
111    g.clear();
112    typename CapacityMap::ValueType _cap;
113    typename CostMap::ValueType _cost;
114    char d;
115    std::string problem;
116    char c;
117    int i, j;
118    std::string str;
119    int n, m;
120    typename Graph::Edge e;
121    std::vector<typename Graph::Node> nodes;
122    while (is>>c) {
123      switch (c) {
124      case 'c': //comment
125        getline(is, str);
126        break;
127      case 'p': //problem definition
128        is >> problem >> n >> m;
129        getline(is, str);
130        nodes.resize(n+1);
131        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
132        break;
133      case 'n': //node definition
134        if (problem=="sp") { //shortest path problem
135          is >> i;
136          getline(is, str);
137          s=nodes[i];
138        }
139        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
140          is >> i >> d;
141          getline(is, str);
142          if (d=='s') s=nodes[i];
143          if (d=='t') t=nodes[i];
144        }
145        break;
146      case 'a':
147        if ( problem == "mat" ) {
148          is >> i >> j;
149          getline(is, str);
150          g.addEdge(nodes[i], nodes[j]);
151        }
152        if ( problem == "max" || problem == "sp") {
153          is >> i >> j >> _cap;
154          getline(is, str);
155          e=g.addEdge(nodes[i], nodes[j]);
156          capacity.update();
157          capacity.set(e, _cap);
158        }
159        if ( problem == "min" ) {
160          is >> i >> j >> _cap >> _cost;
161          getline(is, str);
162          e=g.addEdge(nodes[i], nodes[j]);
163          capacity.update();
164          capacity.set(e, _cap);
165          cost.update();
166          cost.set(e, _cost);
167        }
168        break;
169      }
170    }
171  }
172
173
174 
175  /// write matching problem
176  template<typename Graph>
177  void writeDimacs(std::ostream& os, const Graph &g) {
178    typedef typename Graph::NodeIt NodeIt;
179    typedef typename Graph::EdgeIt EdgeIt; 
180   
181    typename Graph::template NodeMap<int> nodes(g);
182
183    os << "c matching problem" << std::endl;
184
185    int i=1;
186    NodeIt v;
187    for(g.first(v); g.valid(v); g.next(v)) {
188      nodes.set(v, i);
189      ++i;
190    }   
191   
192    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
193
194    EdgeIt e;
195    for(g.first(e); g.valid(e); g.next(e)) {
196      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
197    }
198
199  }
200
201
202
203} //namespace hugo
204
205#endif //HUGO_DIMACS_H
Note: See TracBrowser for help on using the repository browser.