COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dimacs.h @ 778:08a1d1e3070d

Last change on this file since 778:08a1d1e3070d was 778:08a1d1e3070d, checked in by marci, 16 years ago

.

File size: 6.3 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/// \ingroup misc
11/// \file
12/// \brief Dimacs file format reader.
13
14namespace hugo {
15
16
17  /// \addtogroup misc
18  /// @{
19
20  /// Dimacs min cost flow reader function.
21
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.
28  ///
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,
33                  CostMap& cost) {
34    g.clear();
35    typename CapacityMap::ValueType _cap;
36    typename CostMap::ValueType _cost;
37    char d;
38    std::string problem;
39    char c;
40    int i, j;
41    std::string str;
42    int n, m;
43    typename Graph::Edge e;
44    std::vector<typename Graph::Node> nodes;
45    while (is>>c) {
46      switch (c) {
47      case 'c': //comment
48        getline(is, str);
49        break;
50      case 'p': //problem definition
51        is >> problem >> n >> m;
52        getline(is, str);
53        nodes.resize(n+1);
54        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
55        break;
56      case 'n': //node definition
57        if (problem=="sp") { //shortest path problem
58          is >> i;
59          getline(is, str);
60          s=nodes[i];
61        }
62        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
63          is >> i >> d;
64          getline(is, str);
65          if (d=='s') s=nodes[i];
66          if (d=='t') t=nodes[i];
67        }
68        break;
69      case 'a':
70        if ( problem == "max" || problem == "sp") {
71          is >> i >> j >> _cap;
72          getline(is, str);
73          e=g.addEdge(nodes[i], nodes[j]);
74          capacity.update();
75          capacity.set(e, _cap);
76        } else {
77          if ( problem == "min" ) {
78            is >> i >> j >> _cap >> _cost;
79            getline(is, str);
80            e=g.addEdge(nodes[i], nodes[j]);
81            capacity.update();
82            capacity.set(e, _cap);
83            cost.update();
84            cost.set(e, _cost);
85          } else {
86            is >> i >> j;
87            getline(is, str);
88            g.addEdge(nodes[i], nodes[j]);
89          }
90        }
91        break;
92      }
93    }
94  }
95
96
97  /// Dimacs max flow reader function.
98
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.
104  ///
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);
111  }
112
113
114  /// Dimacs shortest path reader function.
115
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
120  /// source node.
121  ///
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);
128  }
129
130
131  /// Dimacs capacitated graph reader function.
132
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.
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 u;
141    NullMap<typename Graph::Edge, int> n;
142    readDimacs(is, g, capacity, u, u, n);
143  }
144
145
146  /// Dimacs plain graph reader function.
147
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
151  /// by \c g.clear().
152  ///
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);
159  }
160 
161
162
163 
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; 
169   
170    typename Graph::template NodeMap<int> nodes(g);
171
172    os << "c matching problem" << std::endl;
173
174    int i=1;
175    for(NodeIt v(g); v!=INVALID; ++v) {
176      nodes.set(v, i);
177      ++i;
178    }   
179   
180    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
181
182    for(EdgeIt e(g); e!=INVALID; ++e) {
183      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
184    }
185
186  }
187
188
189  /// @}
190
191} //namespace hugo
192
193#endif //HUGO_DIMACS_H
194
195//  template<typename Graph, typename CapacityMap>
196//   void readDimacsMaxFlow(std::istream& is, Graph &g,
197//                       typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
198//     g.clear();
199//     int cap;
200//     char d;
201//     std::string problem;
202//     char c;
203//     int i, j;
204//     std::string str;
205//     int n, m;
206//     typename Graph::Edge e;
207//     std::vector<typename Graph::Node> nodes;
208//     while (is>>c) {
209//       switch (c) {
210//       case 'c': //comment
211//      getline(is, str);
212//      break;
213//       case 'p': //problem definition
214//      is >> problem >> n >> m;
215//      getline(is, str);
216//      nodes.resize(n+1);
217//      for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
218//      break;
219//       case 'n': //node definition
220//      if (problem=="sp") { //shortest path problem
221//        is >> i;
222//        getline(is, str);
223//        s=nodes[i];
224//      }
225//      if (problem=="max") { //max flow problem
226//        is >> i >> d;
227//        getline(is, str);
228//        if (d=='s') s=nodes[i];
229//        if (d=='t') t=nodes[i];
230//      }
231//      break;
232//       case 'a':
233//      is >> i >> j >> cap;
234//      getline(is, str);
235//      e=g.addEdge(nodes[i], nodes[j]);
236//      capacity.update();
237//      capacity.set(e, cap);
238//      break;
239//       }
240//     }
241//   }
Note: See TracBrowser for help on using the repository browser.