A remark added.
12 /// \brief Dimacs file format reader.
20 /// Dimacs min cost flow reader function.
22 /// This function reads a min cost flow instance from dimacs format,
23 /// i.e. from dimacs files having a line starting with \c p \c "min".
24 /// At the beginning \c g is cleared by \c g.clear(). The edge
25 /// capacities are written to \c capacity, \c s and \c t are set to
26 /// the source and the target nodes resp. and the cost of the edges
27 /// are written to \c cost.
29 /// \author Marton Makai
30 template<typename Graph, typename CapacityMap, typename CostMap>
31 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
32 typename Graph::Node &s, typename Graph::Node &t,
35 typename CapacityMap::ValueType _cap;
36 typename CostMap::ValueType _cost;
43 typename Graph::Edge e;
44 std::vector<typename Graph::Node> nodes;
50 case 'p': //problem definition
51 is >> problem >> n >> m;
54 for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
56 case 'n': //node definition
57 if (problem=="sp") { //shortest path problem
62 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
65 if (d=='s') s=nodes[i];
66 if (d=='t') t=nodes[i];
70 if ( problem == "max" || problem == "sp") {
73 e=g.addEdge(nodes[i], nodes[j]);
75 capacity.set(e, _cap);
77 if ( problem == "min" ) {
78 is >> i >> j >> _cap >> _cost;
80 e=g.addEdge(nodes[i], nodes[j]);
82 capacity.set(e, _cap);
88 g.addEdge(nodes[i], nodes[j]);
97 /// Dimacs max flow reader function.
99 /// This function reads a max flow instance from dimacs format,
100 /// i.e. from dimacs files having a line starting with \c p \c
101 /// "max". At the beginning \c g is cleared by \c g.clear(). The
102 /// edge capacities are written to \c capacity and \c s and \c t are
103 /// set to the source and the target nodes.
105 /// \author Marton Makai
106 template<typename Graph, typename CapacityMap>
107 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
108 typename Graph::Node &s, typename Graph::Node &t) {
109 NullMap<typename Graph::Edge, int> n;
110 readDimacs(is, g, capacity, s, t, n);
114 /// Dimacs shortest path reader function.
116 /// This function reads a shortest path instance from dimacs format,
117 /// i.e. from dimacs files having a line starting with \c p \c "sp".
118 /// At the beginning \c g is cleared by \c g.clear(). The edge
119 /// capacities are written to \c capacity and \c s is set to the
122 /// \author Marton Makai
123 template<typename Graph, typename CapacityMap>
124 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
125 typename Graph::Node &s) {
126 NullMap<typename Graph::Edge, int> n;
127 readDimacs(is, g, capacity, s, s, n);
131 /// Dimacs capacitated graph reader function.
133 /// This function reads an edge capacitated graph instance from
134 /// dimacs format. At the beginning \c g is cleared by \c g.clear()
135 /// and the edge capacities are written to \c capacity.
137 /// \author Marton Makai
138 template<typename Graph, typename CapacityMap>
139 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
140 typename Graph::Node u;
141 NullMap<typename Graph::Edge, int> n;
142 readDimacs(is, g, capacity, u, u, n);
146 /// Dimacs plain graph reader function.
148 /// This function reads a graph without any designated nodes and
149 /// maps from dimacs format, i.e. from dimacs files having a line
150 /// starting with \c p \c "mat". At the beginning \c g is cleared
153 /// \author Marton Makai
154 template<typename Graph>
155 void readDimacs(std::istream& is, Graph &g) {
156 typename Graph::Node u;
157 NullMap<typename Graph::Edge, int> n;
158 readDimacs(is, g, n, u, u, n);
164 /// write matching problem
165 template<typename Graph>
166 void writeDimacs(std::ostream& os, const Graph &g) {
167 typedef typename Graph::NodeIt NodeIt;
168 typedef typename Graph::EdgeIt EdgeIt;
170 typename Graph::template NodeMap<int> nodes(g);
172 os << "c matching problem" << std::endl;
176 for(g.first(v); g.valid(v); g.next(v)) {
181 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
184 for(g.first(e); g.valid(e); g.next(e)) {
185 os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
195 #endif //HUGO_DIMACS_H
197 // template<typename Graph, typename CapacityMap>
198 // void readDimacsMaxFlow(std::istream& is, Graph &g,
199 // typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
203 // std::string problem;
208 // typename Graph::Edge e;
209 // std::vector<typename Graph::Node> nodes;
212 // case 'c': //comment
215 // case 'p': //problem definition
216 // is >> problem >> n >> m;
218 // nodes.resize(n+1);
219 // for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
221 // case 'n': //node definition
222 // if (problem=="sp") { //shortest path problem
227 // if (problem=="max") { //max flow problem
230 // if (d=='s') s=nodes[i];
231 // if (d=='t') t=nodes[i];
235 // is >> i >> j >> cap;
237 // e=g.addEdge(nodes[i], nodes[j]);
238 // capacity.update();
239 // capacity.set(e, cap);