COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dimacs.h @ 906:17f31d280385

Last change on this file since 906:17f31d280385 was 906:17f31d280385, checked in by Alpar Juttner, 20 years ago

Copyright header added.

File size: 5.7 KB
Line 
1/* -*- C++ -*-
2 * src/hugo/dimacs.h - Part of HUGOlib, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef HUGO_DIMACS_H
18#define HUGO_DIMACS_H
19
20#include <iostream>
21#include <string>
22#include <vector>
23#include <hugo/maps.h>
24
25/// \ingroup misc
26/// \file
27/// \brief Dimacs file format reader.
28
29namespace hugo {
30
31
32  /// \addtogroup misc
33  /// @{
34
35  /// Dimacs min cost flow reader function.
36
37  /// This function reads a min cost flow instance from dimacs format,
38  /// i.e. from dimacs files having a line starting with \c p \c "min".
39  /// At the beginning \c g is cleared by \c g.clear(). The edge
40  /// capacities are written to \c capacity, \c s and \c t are set to
41  /// the source and the target nodes resp. and the cost of the edges
42  /// are written to \c cost.
43  ///
44  /// \author Marton Makai
45  template<typename Graph, typename CapacityMap, typename CostMap>
46  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
47                  typename Graph::Node &s, typename Graph::Node &t,
48                  CostMap& cost) {
49    g.clear();
50    typename CapacityMap::ValueType _cap;
51    typename CostMap::ValueType _cost;
52    char d;
53    std::string problem;
54    char c;
55    int i, j;
56    std::string str;
57    int n, m;
58    typename Graph::Edge e;
59    std::vector<typename Graph::Node> nodes;
60    while (is>>c) {
61      switch (c) {
62      case 'c': //comment
63        getline(is, str);
64        break;
65      case 'p': //problem definition
66        is >> problem >> n >> m;
67        getline(is, str);
68        nodes.resize(n+1);
69        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
70        break;
71      case 'n': //node definition
72        if (problem=="sp") { //shortest path problem
73          is >> i;
74          getline(is, str);
75          s=nodes[i];
76        }
77        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
78          is >> i >> d;
79          getline(is, str);
80          if (d=='s') s=nodes[i];
81          if (d=='t') t=nodes[i];
82        }
83        break;
84      case 'a':
85        if ( problem == "max" || problem == "sp") {
86          is >> i >> j >> _cap;
87          getline(is, str);
88          e=g.addEdge(nodes[i], nodes[j]);
89          //capacity.update();
90          capacity.set(e, _cap);
91        } else {
92          if ( problem == "min" ) {
93            is >> i >> j >> _cap >> _cost;
94            getline(is, str);
95            e=g.addEdge(nodes[i], nodes[j]);
96            //capacity.update();
97            capacity.set(e, _cap);
98            //cost.update();
99            cost.set(e, _cost);
100          } else {
101            is >> i >> j;
102            getline(is, str);
103            g.addEdge(nodes[i], nodes[j]);
104          }
105        }
106        break;
107      }
108    }
109  }
110
111
112  /// Dimacs max flow reader function.
113
114  /// This function reads a max flow instance from dimacs format,
115  /// i.e. from dimacs files having a line starting with \c p \c
116  /// "max".  At the beginning \c g is cleared by \c g.clear(). The
117  /// edge capacities are written to \c capacity and \c s and \c t are
118  /// set to the source and the target nodes.
119  ///
120  /// \author Marton Makai
121  template<typename Graph, typename CapacityMap>
122  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
123                  typename Graph::Node &s, typename Graph::Node &t) {
124    NullMap<typename Graph::Edge, int> n;
125    readDimacs(is, g, capacity, s, t, n);
126  }
127
128
129  /// Dimacs shortest path reader function.
130
131  /// This function reads a shortest path instance from dimacs format,
132  /// i.e. from dimacs files having a line starting with \c p \c "sp".
133  /// At the beginning \c g is cleared by \c g.clear(). The edge
134  /// capacities are written to \c capacity and \c s is set to the
135  /// source node.
136  ///
137  /// \author Marton Makai
138  template<typename Graph, typename CapacityMap>
139  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
140                  typename Graph::Node &s) {
141    NullMap<typename Graph::Edge, int> n;
142    readDimacs(is, g, capacity, s, s, n);
143  }
144
145
146  /// Dimacs capacitated graph reader function.
147
148  /// This function reads an edge capacitated graph instance from
149  /// dimacs format.  At the beginning \c g is cleared by \c g.clear()
150  /// and the edge capacities are written to \c capacity.
151  ///
152  /// \author Marton Makai
153  template<typename Graph, typename CapacityMap>
154  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
155    typename Graph::Node u;
156    NullMap<typename Graph::Edge, int> n;
157    readDimacs(is, g, capacity, u, u, n);
158  }
159
160
161  /// Dimacs plain graph reader function.
162
163  /// This function reads a graph without any designated nodes and
164  /// maps from dimacs format, i.e. from dimacs files having a line
165  /// starting with \c p \c "mat".  At the beginning \c g is cleared
166  /// by \c g.clear().
167  ///
168  /// \author Marton Makai
169  template<typename Graph>
170  void readDimacs(std::istream& is, Graph &g) {
171    typename Graph::Node u;
172    NullMap<typename Graph::Edge, int> n;
173    readDimacs(is, g, n, u, u, n);
174  }
175 
176
177
178 
179  /// write matching problem
180  template<typename Graph>
181  void writeDimacs(std::ostream& os, const Graph &g) {
182    typedef typename Graph::NodeIt NodeIt;
183    typedef typename Graph::EdgeIt EdgeIt; 
184   
185    typename Graph::template NodeMap<int> nodes(g);
186
187    os << "c matching problem" << std::endl;
188
189    int i=1;
190    for(NodeIt v(g); v!=INVALID; ++v) {
191      nodes.set(v, i);
192      ++i;
193    }   
194   
195    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
196
197    for(EdgeIt e(g); e!=INVALID; ++e) {
198      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
199    }
200
201  }
202
203  /// @}
204
205} //namespace hugo
206
207#endif //HUGO_DIMACS_H
Note: See TracBrowser for help on using the repository browser.