Changeset 2413:21eb3ccdc3df in lemon-0.x for lemon/dimacs.h
- Timestamp:
- 03/22/07 16:40:50 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3244
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dimacs.h
r2391 r2413 28 28 /// \ingroup dimacs_group 29 29 /// \file 30 /// \brief D imacsfile format reader.30 /// \brief DIMACS file format reader. 31 31 32 32 namespace lemon { 33 33 34 ///35 34 ///@defgroup dimacs_group DIMACS format 36 35 ///\brief Read and write files in DIMACS format … … 42 41 /// \addtogroup dimacs_group 43 42 /// @{ 44 45 /// Dimacs min cost flow reader function. 46 47 /// This function reads a min cost flow instance from dimacs format, 48 /// i.e. from dimacs files having a line starting with 49 ///\code 50 /// p "min" 51 ///\endcode 52 /// At the beginning \c g is cleared by \c g.clear(). The edge 53 /// capacities are written to \c capacity, \c s and \c t are set to 54 /// the source and the target nodes resp. and the cost of the edges 55 /// are written to \c cost. 56 /// 57 /// \author Marton Makai 58 template<typename Graph, typename CapacityMap, typename CostMap> 59 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 60 typename Graph::Node &s, typename Graph::Node &t, 61 CostMap& cost) { 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 SupplyMap, 58 typename CapacityMap, typename CostMap> 59 void readDimacs( std::istream& is, 60 Graph &g, 61 SupplyMap& supply, 62 CapacityMap& lower, 63 CapacityMap& capacity, 64 CostMap& cost ) 65 { 62 66 g.clear(); 63 typename CapacityMap::Value _cap; 64 typename CostMap::Value _cost; 65 char d; 66 std::string problem; 67 std::vector<typename Graph::Node> nodes; 68 typename Graph::Edge e; 69 std::string problem, str; 67 70 char c; 71 int n, m; 68 72 int i, j; 69 std::string str;70 int n, m;71 typename Graph::Edge e;72 std::vector<typename Graph::Node> nodes;73 while (is >>c) {73 typename SupplyMap::Value sup; 74 typename CapacityMap::Value low; 75 typename CapacityMap::Value cap; 76 typename CostMap::Value co; 77 while (is >> c) { 74 78 switch (c) { 75 case 'c': // comment76 getline(is, str); 77 break; 78 case 'p': // problem definition79 case 'c': // comment line 80 getline(is, str); 81 break; 82 case 'p': // problem definition line 79 83 is >> problem >> n >> m; 80 84 getline(is, str); 81 nodes.resize(n+1); 82 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); 83 break; 84 case 'n': //node definition 85 if (problem=="sp") { //shortest path problem 86 is >> i; 87 getline(is, str); 88 s=nodes[i]; 89 } 90 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem 91 is >> i >> d; 92 getline(is, str); 93 if (d=='s') s=nodes[i]; 94 if (d=='t') t=nodes[i]; 95 } 96 break; 97 case 'a': 98 if ( problem == "max" || problem == "sp") { 99 is >> i >> j >> _cap; 100 getline(is, str); 101 e=g.addEdge(nodes[i], nodes[j]); 102 //capacity.update(); 103 capacity.set(e, _cap); 104 } else { 105 if ( problem == "min" ) { 106 is >> i >> j >> _cap >> _cost; 107 getline(is, str); 108 e=g.addEdge(nodes[i], nodes[j]); 109 //capacity.update(); 110 capacity.set(e, _cap); 111 //cost.update(); 112 cost.set(e, _cost); 113 } else { 114 is >> i >> j; 115 getline(is, str); 116 g.addEdge(nodes[i], nodes[j]); 117 } 118 } 85 if (problem != "min") return; 86 nodes.resize(n + 1); 87 for (int k = 1; k <= n; ++k) { 88 nodes[k] = g.addNode(); 89 supply[nodes[k]] = 0; 90 } 91 break; 92 case 'n': // node definition line 93 is >> i >> sup; 94 getline(is, str); 95 supply.set(nodes[i], sup); 96 break; 97 case 'a': // edge (arc) definition line 98 is >> i >> j >> low >> cap >> co; 99 getline(is, str); 100 e = g.addEdge(nodes[i], nodes[j]); 101 lower.set(e, low); 102 if (cap >= 0) 103 capacity.set(e, cap); 104 else 105 capacity.set(e, -1); 106 cost.set(e, co); 119 107 break; 120 108 } … … 122 110 } 123 111 124 125 /// Dimacs max flow reader function. 126 127 /// This function reads a max flow instance from dimacs format, 128 /// i.e. from dimacs files having a line starting with 129 ///\code 130 /// p "max" 131 ///\endcode 132 ///At the beginning \c g is cleared by \c g.clear(). The 133 /// edge capacities are written to \c capacity and \c s and \c t are 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 116 /// \code 117 /// p max 118 /// \endcode 119 /// At the beginning \c g is cleared by \c g.clear(). The edge 120 /// capacities are written to \c capacity and \c s and \c t are 134 121 /// set to the source and the target nodes. 135 122 /// … … 138 125 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 139 126 typename Graph::Node &s, typename Graph::Node &t) { 140 NullMap<typename Graph::Edge, int> n; 141 readDimacs(is, g, capacity, s, t, n); 142 } 143 144 145 /// Dimacs shortest path reader function. 146 147 /// This function reads a shortest path instance from dimacs format, 148 /// i.e. from dimacs files having a line starting with 149 ///\code 150 /// p "sp" 151 ///\endcode 127 g.clear(); 128 std::vector<typename Graph::Node> nodes; 129 typename Graph::Edge e; 130 std::string problem; 131 char c, d; 132 int n, m; 133 int i, j; 134 typename CapacityMap::Value _cap; 135 std::string str; 136 while (is >> c) { 137 switch (c) { 138 case 'c': // comment line 139 getline(is, str); 140 break; 141 case 'p': // problem definition line 142 is >> problem >> n >> m; 143 getline(is, str); 144 nodes.resize(n + 1); 145 for (int k = 1; k <= n; ++k) 146 nodes[k] = g.addNode(); 147 break; 148 case 'n': // node definition line 149 if (problem == "sp") { // shortest path problem 150 is >> i; 151 getline(is, str); 152 s = nodes[i]; 153 } 154 if (problem == "max") { // max flow problem 155 is >> i >> d; 156 getline(is, str); 157 if (d == 's') s = nodes[i]; 158 if (d == 't') t = nodes[i]; 159 } 160 break; 161 case 'a': // edge (arc) definition line 162 if (problem == "max" || problem == "sp") { 163 is >> i >> j >> _cap; 164 getline(is, str); 165 e = g.addEdge(nodes[i], nodes[j]); 166 capacity.set(e, _cap); 167 } else { 168 is >> i >> j; 169 getline(is, str); 170 g.addEdge(nodes[i], nodes[j]); 171 } 172 break; 173 } 174 } 175 } 176 177 /// DIMACS shortest path reader function. 178 /// 179 /// This function reads a shortest path instance from DIMACS format, 180 /// i.e. from DIMACS files having a line starting with 181 /// \code 182 /// p sp 183 /// \endcode 152 184 /// At the beginning \c g is cleared by \c g.clear(). The edge 153 185 /// capacities are written to \c capacity and \c s is set to the … … 158 190 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 159 191 typename Graph::Node &s) { 160 NullMap<typename Graph::Edge, int> n; 161 readDimacs(is, g, capacity, s, s, n); 162 } 163 164 165 /// Dimacs capacitated graph reader function. 166 192 readDimacs(is, g, capacity, s, s); 193 } 194 195 /// DIMACS capacitated graph reader function. 196 /// 167 197 /// This function reads an edge capacitated graph instance from 168 /// dimacs format.At the beginning \c g is cleared by \c g.clear()198 /// DIMACS format. At the beginning \c g is cleared by \c g.clear() 169 199 /// and the edge capacities are written to \c capacity. 170 200 /// … … 173 203 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { 174 204 typename Graph::Node u; 175 NullMap<typename Graph::Edge, int> n; 176 readDimacs(is, g, capacity, u, u, n); 177 } 178 179 180 /// Dimacs plain graph reader function. 181 205 readDimacs(is, g, capacity, u, u); 206 } 207 208 /// DIMACS plain graph reader function. 209 /// 182 210 /// This function reads a graph without any designated nodes and 183 /// maps from dimacs format, i.e. from dimacsfiles having a line211 /// maps from DIMACS format, i.e. from DIMACS files having a line 184 212 /// starting with 185 ///\code 186 /// p "mat" 187 ///\endcode 188 /// At the beginning \c g is cleared 189 /// by \c g.clear(). 213 /// \code 214 /// p mat 215 /// \endcode 216 /// At the beginning \c g is cleared by \c g.clear(). 190 217 /// 191 218 /// \author Marton Makai … … 194 221 typename Graph::Node u; 195 222 NullMap<typename Graph::Edge, int> n; 196 readDimacs(is, g, n, u, u , n);223 readDimacs(is, g, n, u, u); 197 224 } 198 225 199 200 201 202 /// write matching problem 226 /// DIMACS plain graph writer function. 227 /// 228 /// This function writes a graph without any designated nodes and 229 /// maps into DIMACS format, i.e. into DIMACS file having a line 230 /// starting with 231 /// \code 232 /// p mat 233 /// \endcode 234 /// 235 /// \author Marton Makai 203 236 template<typename Graph> 204 237 void writeDimacs(std::ostream& os, const Graph &g) { … … 206 239 typedef typename Graph::EdgeIt EdgeIt; 207 240 241 os << "c matching problem" << std::endl; 242 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; 243 208 244 typename Graph::template NodeMap<int> nodes(g); 209 210 os << "c matching problem" << std::endl; 211 212 int i=1; 213 for(NodeIt v(g); v!=INVALID; ++v) { 245 int i = 1; 246 for(NodeIt v(g); v != INVALID; ++v) { 214 247 nodes.set(v, i); 215 248 ++i; 216 249 } 217 218 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; 219 220 for(EdgeIt e(g); e!=INVALID; ++e) { 250 for(EdgeIt e(g); e != INVALID; ++e) { 221 251 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; 222 252 } 223 224 253 } 225 254
Note: See TracChangeset
for help on using the changeset viewer.