COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/dimacs.h @ 528:c00f6ebbe1e6

Last change on this file since 528:c00f6ebbe1e6 was 528:c00f6ebbe1e6, checked in by jacint, 20 years ago

Able to read min cost flow, max flow, shortest path, matching testgraphs

File size: 5.0 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 <maps.h>
9
10/// \file
11/// \brief Dimacs file format reader.
12
13namespace hugo {
14
15  /// Dimacs flow file format reader function.
16
17  /// This function reads a flow instance from dimacs flow format.
18  /// At the beginning \c g is cleared by \c g.clear().
19  /// If the data coming from \c is is a max flow problem instance, then
20  /// \c s and \c t will be respectively the source and target nodes
21  /// and \c capacity will contain the edge capacities.
22  /// If the data is a shortest path problem instance then \c s will be the
23  /// source node and \c capacity will contain the edge lengths.
24  ///
25  ///\author Marton Makai
26  template<typename Graph, typename CapacityMap>
27  void readDimacsMaxFlow(std::istream& is, Graph &g,
28                         typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
29    g.clear();
30    int cap;
31    char d;
32    std::string problem;
33    char c;
34    int i, j;
35    std::string str;
36    int n, m;
37    typename Graph::Edge e;
38    std::vector<typename Graph::Node> nodes;
39    while (is>>c) {
40      switch (c) {
41      case 'c': //comment
42        getline(is, str);
43        break;
44      case 'p': //problem definition
45        is >> problem >> n >> m;
46        getline(is, str);
47        nodes.resize(n+1);
48        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
49        break;
50      case 'n': //node definition
51        if (problem=="sp") { //shortest path problem
52          is >> i;
53          getline(is, str);
54          s=nodes[i];
55        }
56        if (problem=="max") { //max flow problem
57          is >> i >> d;
58          getline(is, str);
59          if (d=='s') s=nodes[i];
60          if (d=='t') t=nodes[i];
61        }
62        break;
63      case 'a':
64        is >> i >> j >> cap;
65        getline(is, str);
66        e=g.addEdge(nodes[i], nodes[j]);
67        capacity.update();
68        capacity.set(e, cap);
69        break;
70      }
71    }
72  }
73
74  /// matching problem
75  template<typename Graph>
76  void readDimacs(std::istream& is, Graph &g) {
77    typename Graph::Node u;
78    NullMap<typename Graph::Edge, int> n;
79    readDimacs(is, g, n, u, u, n);
80    std::cout<<"igen en.";
81  }
82
83  /// sg problem
84  template<typename Graph, typename CapacityMap>
85  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
86    typename Graph::Node u;
87    NullMap<typename Graph::Edge, int> n;
88    readDimacs(is, g, cap, u, u, n);
89  }
90
91  /// shortest path problem
92  template<typename Graph, typename CapacityMap>
93  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
94                  typename Graph::Node &s) {
95    NullMap<typename Graph::Edge, int> n;
96    readDimacs(is, g, capacity, s, s, n);
97  }
98
99  /// max flow problem
100  template<typename Graph, typename CapacityMap>
101  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
102                  typename Graph::Node &s, typename Graph::Node &t) {
103    NullMap<typename Graph::Edge, int> n;
104    readDimacs(is, g, capacity, s, t, n);
105  }
106
107  /// min cost flow problem
108  template<typename Graph, typename CapacityMap, typename CostMap>
109  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
110                  typename Graph::Node &s, typename Graph::Node &t,
111                  CostMap& cost) {
112    g.clear();
113    typename CapacityMap::ValueType _cap;
114    typename CostMap::ValueType _cost;
115    char d;
116    std::string problem;
117    char c;
118    int i, j;
119    std::string str;
120    int n, m;
121    typename Graph::Edge e;
122    std::vector<typename Graph::Node> nodes;
123    while (is>>c) {
124      switch (c) {
125      case 'c': //comment
126        getline(is, str);
127        break;
128      case 'p': //problem definition
129        is >> problem >> n >> m;
130        getline(is, str);
131        nodes.resize(n+1);
132        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
133        break;
134      case 'n': //node definition
135        if (problem=="sp") { //shortest path problem
136          is >> i;
137          getline(is, str);
138          s=nodes[i];
139        }
140        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
141          is >> i >> d;
142          getline(is, str);
143          if (d=='s') s=nodes[i];
144          if (d=='t') t=nodes[i];
145        }
146        break;
147      case 'a':
148        if ( problem == "mat" ) {
149          is >> i >> j;
150          getline(is, str);
151          g.addEdge(nodes[i], nodes[j]);
152        }
153        if ( problem == "max" || problem == "sp") {
154          is >> i >> j >> _cap;
155          getline(is, str);
156          e=g.addEdge(nodes[i], nodes[j]);
157          capacity.update();
158          capacity.set(e, _cap);
159        }
160        if ( problem == "min" ) {
161          is >> i >> j >> _cap >> _cost;
162          getline(is, str);
163          e=g.addEdge(nodes[i], nodes[j]);
164          capacity.update();
165          capacity.set(e, _cap);
166          cost.update();
167          cost.set(e, _cost);
168        }
169        break;
170      }
171    }
172  }
173
174
175 
176  /// write matching problem
177  template<typename Graph>
178  void writeDimacs(std::ostream& os, const Graph &g) {
179    typedef typename Graph::NodeIt NodeIt;
180    typedef typename Graph::EdgeIt EdgeIt; 
181   
182    typename Graph::template NodeMap<int> nodes(g);
183
184    os << "c matching problem" << std::endl;
185
186    int i=1;
187    NodeIt v;
188    for(g.first(v); g.valid(v); g.next(v)) {
189      nodes.set(v, i);
190      ++i;
191    }   
192   
193    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
194
195    EdgeIt e;
196    for(g.first(e); g.valid(e); g.next(e)) {
197      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
198    }
199
200  }
201
202
203
204} //namespace hugo
205
206#endif //HUGO_DIMACS_H
Note: See TracBrowser for help on using the repository browser.