COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dimacs.h @ 575:bdf7fb750e0e

Last change on this file since 575:bdf7fb750e0e was 575:bdf7fb750e0e, checked in by jacint, 16 years ago

Docs added

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    NodeIt v;
176    for(g.first(v); g.valid(v); g.next(v)) {
177      nodes.set(v, i);
178      ++i;
179    }   
180   
181    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
182
183    EdgeIt e;
184    for(g.first(e); g.valid(e); g.next(e)) {
185      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
186    }
187
188  }
189
190
191  /// @}
192
193} //namespace hugo
194
195#endif //HUGO_DIMACS_H
196
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) {
200//     g.clear();
201//     int cap;
202//     char d;
203//     std::string problem;
204//     char c;
205//     int i, j;
206//     std::string str;
207//     int n, m;
208//     typename Graph::Edge e;
209//     std::vector<typename Graph::Node> nodes;
210//     while (is>>c) {
211//       switch (c) {
212//       case 'c': //comment
213//      getline(is, str);
214//      break;
215//       case 'p': //problem definition
216//      is >> problem >> n >> m;
217//      getline(is, str);
218//      nodes.resize(n+1);
219//      for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
220//      break;
221//       case 'n': //node definition
222//      if (problem=="sp") { //shortest path problem
223//        is >> i;
224//        getline(is, str);
225//        s=nodes[i];
226//      }
227//      if (problem=="max") { //max flow problem
228//        is >> i >> d;
229//        getline(is, str);
230//        if (d=='s') s=nodes[i];
231//        if (d=='t') t=nodes[i];
232//      }
233//      break;
234//       case 'a':
235//      is >> i >> j >> cap;
236//      getline(is, str);
237//      e=g.addEdge(nodes[i], nodes[j]);
238//      capacity.update();
239//      capacity.set(e, cap);
240//      break;
241//       }
242//     }
243//   }
Note: See TracBrowser for help on using the repository browser.