COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dimacs.h

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 6.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIMACS_H
20#define LEMON_DIMACS_H
21
22#include <iostream>
23#include <string>
24#include <vector>
25#include <lemon/maps.h>
26#include <lemon/bits/invalid.h>
27
28/// \ingroup dimacs_group
29/// \file
30/// \brief DIMACS file format reader.
31
32namespace lemon {
33
34  ///@defgroup dimacs_group DIMACS format
35  ///\brief Read and write files in DIMACS format
36  ///
37  ///Tools to read a graph from or write it to a file in DIMACS format
38  ///data
39  ///\ingroup io_group
40
41  /// \addtogroup dimacs_group
42  /// @{
43 
44  /// DIMACS min cost flow reader function.
45  ///
46  /// This function reads a min cost flow instance from DIMACS format,
47  /// i.e. from DIMACS files having a line starting with
48  /// \code
49  ///   p min
50  /// \endcode
51  /// At the beginning \c g is cleared by \c g.clear(). The supply
52  /// amount of the nodes are written to \c supply (signed). The
53  /// lower bounds, capacities and costs of the edges are written to
54  /// \c lower, \c capacity and \c cost.
55  ///
56  /// \author Marton Makai and Peter Kovacs
57  template <typename Graph, typename LowerMap,
58    typename CapacityMap, typename CostMap,
59    typename SupplyMap>
60  void readDimacs( std::istream& is,
61                   Graph &g,
62                   LowerMap& lower,
63                   CapacityMap& capacity,
64                   CostMap& cost,
65                   SupplyMap& supply )
66  {
67    g.clear();
68    std::vector<typename Graph::Node> nodes;
69    typename Graph::Edge e;
70    std::string problem, str;
71    char c;
72    int n, m;
73    int i, j;
74    typename SupplyMap::Value sup;
75    typename CapacityMap::Value low;
76    typename CapacityMap::Value cap;
77    typename CostMap::Value co;
78    while (is >> c) {
79      switch (c) {
80      case 'c': // comment line
81        getline(is, str);
82        break;
83      case 'p': // problem definition line
84        is >> problem >> n >> m;
85        getline(is, str);
86        if (problem != "min") return;
87        nodes.resize(n + 1);
88        for (int k = 1; k <= n; ++k) {
89          nodes[k] = g.addNode();
90          supply.set(nodes[k], 0);
91        }
92        break;
93      case 'n': // node definition line
94        is >> i >> sup;
95        getline(is, str);
96        supply.set(nodes[i], sup);
97        break;
98      case 'a': // edge (arc) definition line
99        is >> i >> j >> low >> cap >> co;
100        getline(is, str);
101        e = g.addEdge(nodes[i], nodes[j]);
102        lower.set(e, low);
103        if (cap >= 0)
104          capacity.set(e, cap);
105        else
106          capacity.set(e, -1);
107        cost.set(e, co);
108        break;
109      }
110    }
111  }
112
113  /// DIMACS max flow reader function.
114  ///
115  /// This function reads a max flow instance from DIMACS format,
116  /// i.e. from DIMACS files having a line starting with
117  /// \code
118  ///   p max
119  /// \endcode
120  /// At the beginning \c g is cleared by \c g.clear(). The edge
121  /// capacities are written to \c capacity and \c s and \c t are
122  /// set to the source and the target nodes.
123  ///
124  /// \author Marton Makai
125  template<typename Graph, typename CapacityMap>
126  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
127                  typename Graph::Node &s, typename Graph::Node &t) {
128    g.clear();
129    std::vector<typename Graph::Node> nodes;
130    typename Graph::Edge e;
131    std::string problem;
132    char c, d;
133    int n, m;
134    int i, j;
135    typename CapacityMap::Value _cap;
136    std::string str;
137    while (is >> c) {
138      switch (c) {
139      case 'c': // comment line
140        getline(is, str);
141        break;
142      case 'p': // problem definition line
143        is >> problem >> n >> m;
144        getline(is, str);
145        nodes.resize(n + 1);
146        for (int k = 1; k <= n; ++k)
147          nodes[k] = g.addNode();
148        break;
149      case 'n': // node definition line
150        if (problem == "sp") { // shortest path problem
151          is >> i;
152          getline(is, str);
153          s = nodes[i];
154        }
155        if (problem == "max") { // max flow problem
156          is >> i >> d;
157          getline(is, str);
158          if (d == 's') s = nodes[i];
159          if (d == 't') t = nodes[i];
160        }
161        break;
162      case 'a': // edge (arc) definition line
163        if (problem == "max" || problem == "sp") {
164          is >> i >> j >> _cap;
165          getline(is, str);
166          e = g.addEdge(nodes[i], nodes[j]);
167          capacity.set(e, _cap);
168        } else {
169          is >> i >> j;
170          getline(is, str);
171          g.addEdge(nodes[i], nodes[j]);
172        }
173        break;
174      }
175    }
176  }
177
178  /// DIMACS shortest path reader function.
179  ///
180  /// This function reads a shortest path instance from DIMACS format,
181  /// i.e. from DIMACS files having a line starting with
182  /// \code
183  ///   p sp
184  /// \endcode
185  /// At the beginning \c g is cleared by \c g.clear(). The edge
186  /// capacities are written to \c capacity and \c s is set to the
187  /// source node.
188  ///
189  /// \author Marton Makai
190  template<typename Graph, typename CapacityMap>
191  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
192                  typename Graph::Node &s) {
193    readDimacs(is, g, capacity, s, s);
194  }
195
196  /// DIMACS capacitated graph reader function.
197  ///
198  /// This function reads an edge capacitated graph instance from
199  /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
200  /// and the edge capacities are written to \c capacity.
201  ///
202  /// \author Marton Makai
203  template<typename Graph, typename CapacityMap>
204  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
205    typename Graph::Node u;
206    readDimacs(is, g, capacity, u, u);
207  }
208
209  /// DIMACS plain graph reader function.
210  ///
211  /// This function reads a graph without any designated nodes and
212  /// maps from DIMACS format, i.e. from DIMACS files having a line
213  /// starting with
214  /// \code
215  ///   p mat
216  /// \endcode
217  /// At the beginning \c g is cleared by \c g.clear().
218  ///
219  /// \author Marton Makai
220  template<typename Graph>
221  void readDimacs(std::istream& is, Graph &g) {
222    typename Graph::Node u;
223    NullMap<typename Graph::Edge, int> n;
224    readDimacs(is, g, n, u, u);
225  }
226 
227  /// DIMACS plain graph writer function.
228  ///
229  /// This function writes a graph without any designated nodes and
230  /// maps into DIMACS format, i.e. into DIMACS file having a line
231  /// starting with
232  /// \code
233  ///   p mat
234  /// \endcode
235  ///
236  /// \author Marton Makai
237  template<typename Graph>
238  void writeDimacs(std::ostream& os, const Graph &g) {
239    typedef typename Graph::NodeIt NodeIt;
240    typedef typename Graph::EdgeIt EdgeIt; 
241   
242    os << "c matching problem" << std::endl;
243    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
244
245    typename Graph::template NodeMap<int> nodes(g);
246    int i = 1;
247    for(NodeIt v(g); v != INVALID; ++v) {
248      nodes.set(v, i);
249      ++i;
250    }   
251    for(EdgeIt e(g); e != INVALID; ++e) {
252      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
253    }
254  }
255
256  /// @}
257
258} //namespace lemon
259
260#endif //LEMON_DIMACS_H
Note: See TracBrowser for help on using the repository browser.