Changeset 528:c00f6ebbe1e6 in lemon0.x for src/include/dimacs.h
 Timestamp:
 05/04/04 18:16:49 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@694
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/dimacs.h
r465 r528 6 6 #include <string> 7 7 #include <vector> 8 #include <maps.h> 8 9 9 10 /// \file … … 24 25 ///\author Marton Makai 25 26 template<typename Graph, typename CapacityMap> 26 void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { 27 void readDimacsMaxFlow(std::istream& is, Graph &g, 28 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { 27 29 g.clear(); 28 30 int cap; … … 69 71 } 70 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 71 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 72 204 } //namespace hugo 73 205
Note: See TracChangeset
for help on using the changeset viewer.