Changeset 575:bdf7fb750e0e in lemon0.x for src/hugo
 Timestamp:
 05/07/04 12:34:36 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@751
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/dimacs.h
r549 r575 8 8 #include <hugo/maps.h> 9 9 10 /// \ingroup misc 10 11 /// \file 11 12 /// \brief Dimacs file format reader. … … 13 14 namespace hugo { 14 15 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 } 81 82 /// sg problem 83 template<typename Graph, typename CapacityMap> 84 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { 85 typename Graph::Node u; 86 NullMap<typename Graph::Edge, int> n; 87 readDimacs(is, g, capacity, u, u, n); 88 } 89 90 /// shortest path problem 91 template<typename Graph, typename CapacityMap> 92 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 93 typename Graph::Node &s) { 94 NullMap<typename Graph::Edge, int> n; 95 readDimacs(is, g, capacity, s, s, n); 96 } 97 98 /// max flow problem 99 template<typename Graph, typename CapacityMap> 100 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 101 typename Graph::Node &s, typename Graph::Node &t) { 102 NullMap<typename Graph::Edge, int> n; 103 readDimacs(is, g, capacity, s, t, n); 104 } 105 106 /// min cost flow problem 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 107 30 template<typename Graph, typename CapacityMap, typename CostMap> 108 31 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, … … 145 68 break; 146 69 case 'a': 147 if ( problem == "mat" ) {148 is >> i >> j;149 getline(is, str);150 g.addEdge(nodes[i], nodes[j]);151 }152 70 if ( problem == "max"  problem == "sp") { 153 71 is >> i >> j >> _cap; … … 156 74 capacity.update(); 157 75 capacity.set(e, _cap); 158 } 159 if ( problem == "min" ) { 160 is >> i >> j >> _cap >> _cost; 161 getline(is, str); 162 e=g.addEdge(nodes[i], nodes[j]); 163 capacity.update(); 164 capacity.set(e, _cap); 165 cost.update(); 166 cost.set(e, _cost); 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 } 167 90 } 168 91 break; … … 170 93 } 171 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 172 161 173 162 … … 200 189 201 190 191 /// @} 202 192 203 193 } //namespace hugo 204 194 205 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 TracChangeset
for help on using the changeset viewer.