1.1 --- a/demo/dim_to_dot.cc Thu Mar 22 06:36:50 2007 +0000
1.2 +++ b/demo/dim_to_dot.cc Thu Mar 22 15:40:50 2007 +0000
1.3 @@ -17,17 +17,15 @@
1.4 */
1.5
1.6 ///\file
1.7 -///\brief Dim (Dimacs) to Dot (Graphviz) converter
1.8 +///\brief Dim (DIMACS) to Dot (Graphviz) converter
1.9 ///
1.10 -/// This program can convert the dimacs format to graphviz dot format.
1.11 +/// This program can convert the DIMACS format to Graphviz format.
1.12 ///
1.13 -/// Use a DIMACS max flow file as stdin.
1.14 +/// <tt>dim_to_dot dimacs_max_flow_file > dot_output_file</tt>
1.15 ///
1.16 -/// <tt>dim_to_dot < dimacs_max_flow_file > dot_output_file</tt>
1.17 -///
1.18 -/// This program makes a dot file from a dimacs max flow file.
1.19 -/// This program can be an aid in making up to date visualized documantation
1.20 -/// of demo programs.
1.21 +/// This program makes a dot file from a DIMACS max flow file.
1.22 +/// This program can be an aid in making up to date visualized
1.23 +/// documantation of demo programs.
1.24 ///
1.25 /// \include dim_to_dot.cc
1.26
1.27 @@ -46,12 +44,11 @@
1.28 {
1.29 if(argc<2)
1.30 {
1.31 - std::cerr << "USAGE: sub_graph_adaptor_demo input_file.dim" << std::endl;
1.32 + std::cerr << "USAGE: dim_to_dot input_file.dim" << std::endl;
1.33 std::cerr << "The file 'input_file.dim' has to contain a max flow instance in DIMACS format (e.g. sub_graph_adaptor_demo.dim is such a file)." << std::endl;
1.34 return 0;
1.35 }
1.36
1.37 -
1.38 //input stream to read the graph from
1.39 std::ifstream is(argv[1]);
1.40
2.1 --- a/lemon/dimacs.h Thu Mar 22 06:36:50 2007 +0000
2.2 +++ b/lemon/dimacs.h Thu Mar 22 15:40:50 2007 +0000
2.3 @@ -27,11 +27,10 @@
2.4
2.5 /// \ingroup dimacs_group
2.6 /// \file
2.7 -/// \brief Dimacs file format reader.
2.8 +/// \brief DIMACS file format reader.
2.9
2.10 namespace lemon {
2.11
2.12 - ///
2.13 ///@defgroup dimacs_group DIMACS format
2.14 ///\brief Read and write files in DIMACS format
2.15 ///
2.16 @@ -41,114 +40,147 @@
2.17
2.18 /// \addtogroup dimacs_group
2.19 /// @{
2.20 +
2.21 + /// DIMACS min cost flow reader function.
2.22 + ///
2.23 + /// This function reads a min cost flow instance from DIMACS format,
2.24 + /// i.e. from DIMACS files having a line starting with
2.25 + /// \code
2.26 + /// p min
2.27 + /// \endcode
2.28 + /// At the beginning \c g is cleared by \c g.clear(). The supply
2.29 + /// amount of the nodes are written to \c supply (signed). The
2.30 + /// lower bounds, capacities and costs of the edges are written to
2.31 + /// \c lower, \c capacity and \c cost.
2.32 + ///
2.33 + /// \author Marton Makai and Peter Kovacs
2.34 + template <typename Graph, typename SupplyMap,
2.35 + typename CapacityMap, typename CostMap>
2.36 + void readDimacs( std::istream& is,
2.37 + Graph &g,
2.38 + SupplyMap& supply,
2.39 + CapacityMap& lower,
2.40 + CapacityMap& capacity,
2.41 + CostMap& cost )
2.42 + {
2.43 + g.clear();
2.44 + std::vector<typename Graph::Node> nodes;
2.45 + typename Graph::Edge e;
2.46 + std::string problem, str;
2.47 + char c;
2.48 + int n, m;
2.49 + int i, j;
2.50 + typename SupplyMap::Value sup;
2.51 + typename CapacityMap::Value low;
2.52 + typename CapacityMap::Value cap;
2.53 + typename CostMap::Value co;
2.54 + while (is >> c) {
2.55 + switch (c) {
2.56 + case 'c': // comment line
2.57 + getline(is, str);
2.58 + break;
2.59 + case 'p': // problem definition line
2.60 + is >> problem >> n >> m;
2.61 + getline(is, str);
2.62 + if (problem != "min") return;
2.63 + nodes.resize(n + 1);
2.64 + for (int k = 1; k <= n; ++k) {
2.65 + nodes[k] = g.addNode();
2.66 + supply[nodes[k]] = 0;
2.67 + }
2.68 + break;
2.69 + case 'n': // node definition line
2.70 + is >> i >> sup;
2.71 + getline(is, str);
2.72 + supply.set(nodes[i], sup);
2.73 + break;
2.74 + case 'a': // edge (arc) definition line
2.75 + is >> i >> j >> low >> cap >> co;
2.76 + getline(is, str);
2.77 + e = g.addEdge(nodes[i], nodes[j]);
2.78 + lower.set(e, low);
2.79 + if (cap >= 0)
2.80 + capacity.set(e, cap);
2.81 + else
2.82 + capacity.set(e, -1);
2.83 + cost.set(e, co);
2.84 + break;
2.85 + }
2.86 + }
2.87 + }
2.88
2.89 - /// Dimacs min cost flow reader function.
2.90 -
2.91 - /// This function reads a min cost flow instance from dimacs format,
2.92 - /// i.e. from dimacs files having a line starting with
2.93 - ///\code
2.94 - /// p "min"
2.95 - ///\endcode
2.96 - /// At the beginning \c g is cleared by \c g.clear(). The edge
2.97 - /// capacities are written to \c capacity, \c s and \c t are set to
2.98 - /// the source and the target nodes resp. and the cost of the edges
2.99 - /// are written to \c cost.
2.100 + /// DIMACS max flow reader function.
2.101 + ///
2.102 + /// This function reads a max flow instance from DIMACS format,
2.103 + /// i.e. from DIMACS files having a line starting with
2.104 + /// \code
2.105 + /// p max
2.106 + /// \endcode
2.107 + /// At the beginning \c g is cleared by \c g.clear(). The edge
2.108 + /// capacities are written to \c capacity and \c s and \c t are
2.109 + /// set to the source and the target nodes.
2.110 ///
2.111 /// \author Marton Makai
2.112 - template<typename Graph, typename CapacityMap, typename CostMap>
2.113 + template<typename Graph, typename CapacityMap>
2.114 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
2.115 - typename Graph::Node &s, typename Graph::Node &t,
2.116 - CostMap& cost) {
2.117 + typename Graph::Node &s, typename Graph::Node &t) {
2.118 g.clear();
2.119 + std::vector<typename Graph::Node> nodes;
2.120 + typename Graph::Edge e;
2.121 + std::string problem;
2.122 + char c, d;
2.123 + int n, m;
2.124 + int i, j;
2.125 typename CapacityMap::Value _cap;
2.126 - typename CostMap::Value _cost;
2.127 - char d;
2.128 - std::string problem;
2.129 - char c;
2.130 - int i, j;
2.131 std::string str;
2.132 - int n, m;
2.133 - typename Graph::Edge e;
2.134 - std::vector<typename Graph::Node> nodes;
2.135 - while (is>>c) {
2.136 + while (is >> c) {
2.137 switch (c) {
2.138 - case 'c': //comment
2.139 + case 'c': // comment line
2.140 getline(is, str);
2.141 break;
2.142 - case 'p': //problem definition
2.143 + case 'p': // problem definition line
2.144 is >> problem >> n >> m;
2.145 getline(is, str);
2.146 - nodes.resize(n+1);
2.147 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
2.148 + nodes.resize(n + 1);
2.149 + for (int k = 1; k <= n; ++k)
2.150 + nodes[k] = g.addNode();
2.151 break;
2.152 - case 'n': //node definition
2.153 - if (problem=="sp") { //shortest path problem
2.154 + case 'n': // node definition line
2.155 + if (problem == "sp") { // shortest path problem
2.156 is >> i;
2.157 getline(is, str);
2.158 - s=nodes[i];
2.159 + s = nodes[i];
2.160 }
2.161 - if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
2.162 + if (problem == "max") { // max flow problem
2.163 is >> i >> d;
2.164 getline(is, str);
2.165 - if (d=='s') s=nodes[i];
2.166 - if (d=='t') t=nodes[i];
2.167 + if (d == 's') s = nodes[i];
2.168 + if (d == 't') t = nodes[i];
2.169 }
2.170 break;
2.171 - case 'a':
2.172 - if ( problem == "max" || problem == "sp") {
2.173 + case 'a': // edge (arc) definition line
2.174 + if (problem == "max" || problem == "sp") {
2.175 is >> i >> j >> _cap;
2.176 getline(is, str);
2.177 - e=g.addEdge(nodes[i], nodes[j]);
2.178 - //capacity.update();
2.179 + e = g.addEdge(nodes[i], nodes[j]);
2.180 capacity.set(e, _cap);
2.181 } else {
2.182 - if ( problem == "min" ) {
2.183 - is >> i >> j >> _cap >> _cost;
2.184 - getline(is, str);
2.185 - e=g.addEdge(nodes[i], nodes[j]);
2.186 - //capacity.update();
2.187 - capacity.set(e, _cap);
2.188 - //cost.update();
2.189 - cost.set(e, _cost);
2.190 - } else {
2.191 - is >> i >> j;
2.192 - getline(is, str);
2.193 - g.addEdge(nodes[i], nodes[j]);
2.194 - }
2.195 + is >> i >> j;
2.196 + getline(is, str);
2.197 + g.addEdge(nodes[i], nodes[j]);
2.198 }
2.199 break;
2.200 }
2.201 }
2.202 }
2.203
2.204 -
2.205 - /// Dimacs max flow reader function.
2.206 -
2.207 - /// This function reads a max flow instance from dimacs format,
2.208 - /// i.e. from dimacs files having a line starting with
2.209 - ///\code
2.210 - /// p "max"
2.211 - ///\endcode
2.212 - ///At the beginning \c g is cleared by \c g.clear(). The
2.213 - /// edge capacities are written to \c capacity and \c s and \c t are
2.214 - /// set to the source and the target nodes.
2.215 + /// DIMACS shortest path reader function.
2.216 ///
2.217 - /// \author Marton Makai
2.218 - template<typename Graph, typename CapacityMap>
2.219 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
2.220 - typename Graph::Node &s, typename Graph::Node &t) {
2.221 - NullMap<typename Graph::Edge, int> n;
2.222 - readDimacs(is, g, capacity, s, t, n);
2.223 - }
2.224 -
2.225 -
2.226 - /// Dimacs shortest path reader function.
2.227 -
2.228 - /// This function reads a shortest path instance from dimacs format,
2.229 - /// i.e. from dimacs files having a line starting with
2.230 - ///\code
2.231 - /// p "sp"
2.232 - ///\endcode
2.233 + /// This function reads a shortest path instance from DIMACS format,
2.234 + /// i.e. from DIMACS files having a line starting with
2.235 + /// \code
2.236 + /// p sp
2.237 + /// \endcode
2.238 /// At the beginning \c g is cleared by \c g.clear(). The edge
2.239 /// capacities are written to \c capacity and \c s is set to the
2.240 /// source node.
2.241 @@ -157,70 +189,67 @@
2.242 template<typename Graph, typename CapacityMap>
2.243 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
2.244 typename Graph::Node &s) {
2.245 - NullMap<typename Graph::Edge, int> n;
2.246 - readDimacs(is, g, capacity, s, s, n);
2.247 + readDimacs(is, g, capacity, s, s);
2.248 }
2.249
2.250 -
2.251 - /// Dimacs capacitated graph reader function.
2.252 -
2.253 + /// DIMACS capacitated graph reader function.
2.254 + ///
2.255 /// This function reads an edge capacitated graph instance from
2.256 - /// dimacs format. At the beginning \c g is cleared by \c g.clear()
2.257 + /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
2.258 /// and the edge capacities are written to \c capacity.
2.259 ///
2.260 /// \author Marton Makai
2.261 template<typename Graph, typename CapacityMap>
2.262 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
2.263 typename Graph::Node u;
2.264 - NullMap<typename Graph::Edge, int> n;
2.265 - readDimacs(is, g, capacity, u, u, n);
2.266 + readDimacs(is, g, capacity, u, u);
2.267 }
2.268
2.269 -
2.270 - /// Dimacs plain graph reader function.
2.271 -
2.272 + /// DIMACS plain graph reader function.
2.273 + ///
2.274 /// This function reads a graph without any designated nodes and
2.275 - /// maps from dimacs format, i.e. from dimacs files having a line
2.276 + /// maps from DIMACS format, i.e. from DIMACS files having a line
2.277 /// starting with
2.278 - ///\code
2.279 - /// p "mat"
2.280 - ///\endcode
2.281 - /// At the beginning \c g is cleared
2.282 - /// by \c g.clear().
2.283 + /// \code
2.284 + /// p mat
2.285 + /// \endcode
2.286 + /// At the beginning \c g is cleared by \c g.clear().
2.287 ///
2.288 /// \author Marton Makai
2.289 template<typename Graph>
2.290 void readDimacs(std::istream& is, Graph &g) {
2.291 typename Graph::Node u;
2.292 NullMap<typename Graph::Edge, int> n;
2.293 - readDimacs(is, g, n, u, u, n);
2.294 + readDimacs(is, g, n, u, u);
2.295 }
2.296
2.297 -
2.298 -
2.299 -
2.300 - /// write matching problem
2.301 + /// DIMACS plain graph writer function.
2.302 + ///
2.303 + /// This function writes a graph without any designated nodes and
2.304 + /// maps into DIMACS format, i.e. into DIMACS file having a line
2.305 + /// starting with
2.306 + /// \code
2.307 + /// p mat
2.308 + /// \endcode
2.309 + ///
2.310 + /// \author Marton Makai
2.311 template<typename Graph>
2.312 void writeDimacs(std::ostream& os, const Graph &g) {
2.313 typedef typename Graph::NodeIt NodeIt;
2.314 typedef typename Graph::EdgeIt EdgeIt;
2.315
2.316 + os << "c matching problem" << std::endl;
2.317 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
2.318 +
2.319 typename Graph::template NodeMap<int> nodes(g);
2.320 -
2.321 - os << "c matching problem" << std::endl;
2.322 -
2.323 - int i=1;
2.324 - for(NodeIt v(g); v!=INVALID; ++v) {
2.325 + int i = 1;
2.326 + for(NodeIt v(g); v != INVALID; ++v) {
2.327 nodes.set(v, i);
2.328 ++i;
2.329 }
2.330 -
2.331 - os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
2.332 -
2.333 - for(EdgeIt e(g); e!=INVALID; ++e) {
2.334 + for(EdgeIt e(g); e != INVALID; ++e) {
2.335 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
2.336 }
2.337 -
2.338 }
2.339
2.340 /// @}
3.1 --- a/lemon/min_mean_cycle.h Thu Mar 22 06:36:50 2007 +0000
3.2 +++ b/lemon/min_mean_cycle.h Thu Mar 22 15:40:50 2007 +0000
3.3 @@ -33,11 +33,11 @@
3.4 /// \addtogroup min_cost_flow
3.5 /// @{
3.6
3.7 - /// \brief Implementation of Karp's algorithm for finding a
3.8 - /// minimum mean cycle.
3.9 + /// \brief Implementation of Karp's algorithm for finding a
3.10 + /// minimum mean (directed) cycle.
3.11 ///
3.12 - /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
3.13 - /// algorithm for finding a minimum mean cycle.
3.14 + /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
3.15 + /// algorithm for finding a minimum mean (directed) cycle.
3.16 ///
3.17 /// \param Graph The directed graph type the algorithm runs on.
3.18 /// \param LengthMap The type of the length (cost) map.
3.19 @@ -57,11 +57,10 @@
3.20 typedef typename Graph::NodeIt NodeIt;
3.21 typedef typename Graph::Edge Edge;
3.22 typedef typename Graph::EdgeIt EdgeIt;
3.23 - typedef typename Graph::InEdgeIt InEdgeIt;
3.24 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.25
3.26 typedef typename LengthMap::Value Length;
3.27 -
3.28 +
3.29 typedef typename Graph::template NodeMap<int> IntNodeMap;
3.30 typedef typename Graph::template NodeMap<Edge> PredNodeMap;
3.31 typedef Path<Graph> Path;
3.32 @@ -69,22 +68,24 @@
3.33 typedef typename NodeVector::iterator NodeVectorIt;
3.34
3.35 protected:
3.36 -
3.37 +
3.38 /// \brief Data sturcture for path data.
3.39 - struct PathData {
3.40 + struct PathData
3.41 + {
3.42 bool found;
3.43 Length dist;
3.44 Edge pred;
3.45 - PathData(bool _found = false, Length _dist = 0) :
3.46 + PathData(bool _found = false, Length _dist = 0) :
3.47 found(_found), dist(_dist), pred(INVALID) {}
3.48 - PathData(bool _found, Length _dist, Edge _pred) :
3.49 + PathData(bool _found, Length _dist, Edge _pred) :
3.50 found(_found), dist(_dist), pred(_pred) {}
3.51 };
3.52 -
3.53 +
3.54 private:
3.55 -
3.56 - typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap;
3.57 -
3.58 +
3.59 + typedef typename Graph::template NodeMap<std::vector<PathData> >
3.60 + PathDataNodeMap;
3.61 +
3.62 protected:
3.63
3.64 /// \brief Node map for storing path data.
3.65 @@ -92,7 +93,7 @@
3.66 /// Node map for storing path data of all nodes in the current
3.67 /// component. dmap[v][k] is the length of a shortest directed walk
3.68 /// to node v from the starting node containing exactly k edges.
3.69 - PathVectorNodeMap dmap;
3.70 + PathDataNodeMap dmap;
3.71
3.72 /// \brief The directed graph the algorithm runs on.
3.73 const Graph& graph;
3.74 @@ -103,16 +104,20 @@
3.75 Length cycle_length;
3.76 /// \brief The number of edges in the found cycle.
3.77 int cycle_size;
3.78 + /// \brief A node for obtaining a minimum mean cycle.
3.79 + Node cycle_node;
3.80 +
3.81 /// \brief The found cycle.
3.82 Path *cycle_path;
3.83 - /// \brief The found cycle.
3.84 + /// \brief The algorithm uses local \ref lemon::Path "Path"
3.85 + /// structure to store the found cycle.
3.86 bool local_path;
3.87
3.88 /// \brief Node map for identifying strongly connected components.
3.89 IntNodeMap comp;
3.90 /// \brief The number of strongly connected components.
3.91 int comp_num;
3.92 - /// \brief %Counter for identifying the current component.
3.93 + /// \brief Counter for identifying the current component.
3.94 int comp_cnt;
3.95 /// \brief Nodes of the current component.
3.96 NodeVector nodes;
3.97 @@ -129,8 +134,8 @@
3.98 /// \param _length The length (cost) of the edges.
3.99 MinMeanCycle( const Graph& _graph,
3.100 const LengthMap& _length ) :
3.101 - graph(_graph), length(_length), dmap(_graph),
3.102 - cycle_length(0), cycle_size(-1), comp(_graph),
3.103 + graph(_graph), length(_length), dmap(_graph), comp(_graph),
3.104 + cycle_length(0), cycle_size(-1), cycle_node(INVALID),
3.105 cycle_path(NULL), local_path(false)
3.106 { }
3.107
3.108 @@ -140,15 +145,6 @@
3.109 }
3.110
3.111 protected:
3.112 -
3.113 - /// \brief Initializes the internal data structures.
3.114 - void init() {
3.115 - comp_num = stronglyConnectedComponents(graph, comp);
3.116 - if (!cycle_path) {
3.117 - local_path = true;
3.118 - cycle_path = new Path;
3.119 - }
3.120 - }
3.121
3.122 /// \brief Initializes the internal data structures for the current
3.123 /// component.
3.124 @@ -158,7 +154,6 @@
3.125 for (NodeIt v(graph); v != INVALID; ++v) {
3.126 if (comp[v] == comp_cnt) nodes.push_back(v);
3.127 }
3.128 -
3.129 // Creating vectors for all nodes
3.130 int n = nodes.size();
3.131 for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
3.132 @@ -166,16 +161,19 @@
3.133 }
3.134 }
3.135
3.136 - /// \brief Processes all rounds of computing required path data.
3.137 + /// \brief Processes all rounds of computing required path data for
3.138 + /// the current component.
3.139 void processRounds() {
3.140 dmap[nodes[0]][0] = PathData(true, 0);
3.141 process.clear();
3.142 - for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
3.143 - Node v = graph.target(oe);
3.144 + // Processing the first round
3.145 + for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {
3.146 + Node v = graph.target(e);
3.147 if (comp[v] != comp_cnt || v == nodes[0]) continue;
3.148 - dmap[v][1] = PathData(true, length[oe], oe);
3.149 + dmap[v][1] = PathData(true, length[e], e);
3.150 process.push_back(v);
3.151 }
3.152 + // Processing other rounds
3.153 int n = nodes.size(), k;
3.154 for (k = 2; k <= n && process.size() < n; ++k) {
3.155 processNextBuildRound(k);
3.156 @@ -190,12 +188,15 @@
3.157 void processNextBuildRound(int k) {
3.158 NodeVector next;
3.159 for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
3.160 - for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
3.161 - Node v = graph.target(oe);
3.162 + for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
3.163 + Node v = graph.target(e);
3.164 if (comp[v] != comp_cnt) continue;
3.165 - if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
3.166 - if (!dmap[v][k].found) next.push_back(v);
3.167 - dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
3.168 + if (!dmap[v][k].found) {
3.169 + next.push_back(v);
3.170 + dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
3.171 + }
3.172 + else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {
3.173 + dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
3.174 }
3.175 }
3.176 }
3.177 @@ -206,44 +207,39 @@
3.178 /// using \ref nodes vector instead of \ref process vector.
3.179 void processNextFullRound(int k) {
3.180 for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
3.181 - for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
3.182 - Node v = graph.target(oe);
3.183 + for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
3.184 + Node v = graph.target(e);
3.185 if (comp[v] != comp_cnt) continue;
3.186 - if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
3.187 - dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
3.188 + if ( !dmap[v][k].found ||
3.189 + dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
3.190 + dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
3.191 }
3.192 }
3.193 }
3.194 }
3.195
3.196 - /// \brief Finds the minimum cycle mean value according to the path
3.197 - /// data stored in \ref dmap.
3.198 - ///
3.199 - /// Finds the minimum cycle mean value according to the path data
3.200 - /// stored in \ref dmap.
3.201 - ///
3.202 - /// \retval min_length The total length of the found cycle.
3.203 - /// \retval min_size The number of edges in the found cycle.
3.204 - /// \retval min_node A node for obtaining a critical cycle.
3.205 - ///
3.206 - /// \return \c true if a cycle exists in the graph.
3.207 - bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
3.208 + /// \brief Finds the minimum cycle mean value in the current
3.209 + /// component.
3.210 + bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
3.211 bool found_min = false;
3.212 for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
3.213 + int n = nodes.size();
3.214 + if (!dmap[*vi][n].found) continue;
3.215 Length len;
3.216 int size;
3.217 bool found_one = false;
3.218 - int n = nodes.size();
3.219 for (int k = 0; k < n; ++k) {
3.220 + if (!dmap[*vi][k].found) continue;
3.221 Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
3.222 int _size = n - k;
3.223 - if ( dmap[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
3.224 + if (!found_one || len * _size < _len * size) {
3.225 found_one = true;
3.226 len = _len;
3.227 size = _size;
3.228 }
3.229 }
3.230 - if (found_one && (!found_min || len * min_size < min_length * size)) {
3.231 + if ( found_one &&
3.232 + (!found_min || len * min_size < min_length * size) ) {
3.233 found_min = true;
3.234 min_length = len;
3.235 min_size = size;
3.236 @@ -253,94 +249,152 @@
3.237 return found_min;
3.238 }
3.239
3.240 - /// \brief Finds a critical (minimum mean) cycle according to the
3.241 - /// path data stored in \ref dmap.
3.242 - void findCycle(const Node &min_n) {
3.243 - IntNodeMap reached(graph, -1);
3.244 - int r = reached[min_n] = dmap[min_n].size() - 1;
3.245 - Node u = graph.source(dmap[min_n][r].pred);
3.246 - while (reached[u] < 0) {
3.247 - reached[u] = --r;
3.248 - u = graph.source(dmap[u][r].pred);
3.249 - }
3.250 - r = reached[u];
3.251 - Edge ce = dmap[u][r].pred;
3.252 - cycle_path->addFront(ce);
3.253 - Node v;
3.254 - while ((v = graph.source(ce)) != u) {
3.255 - ce = dmap[v][--r].pred;
3.256 - cycle_path->addFront(ce);
3.257 - }
3.258 - }
3.259 + public:
3.260
3.261 - public:
3.262 -
3.263 /// \brief Runs the algorithm.
3.264 ///
3.265 /// Runs the algorithm.
3.266 ///
3.267 /// \return \c true if a cycle exists in the graph.
3.268 + ///
3.269 + /// \note Apart from the return value, m.run() is just a shortcut
3.270 + /// of the following code.
3.271 + /// \code
3.272 + /// m.init();
3.273 + /// m.findMinMean();
3.274 + /// m.findCycle();
3.275 + /// \endcode
3.276 bool run() {
3.277 init();
3.278 - // Searching for the minimum mean cycle in all components
3.279 - bool found_cycle = false;
3.280 - Node cycle_node;
3.281 + findMinMean();
3.282 + return findCycle();
3.283 + }
3.284 +
3.285 + /// \brief Initializes the internal data structures.
3.286 + void init() {
3.287 + comp_num = stronglyConnectedComponents(graph, comp);
3.288 + if (!cycle_path) {
3.289 + local_path = true;
3.290 + cycle_path = new Path;
3.291 + }
3.292 + }
3.293 +
3.294 + /// \brief Finds the minimum cycle mean value in the graph.
3.295 + ///
3.296 + /// Computes all the required path data and finds the minimum cycle
3.297 + /// mean value in the graph.
3.298 + ///
3.299 + /// \return \c true if a cycle exists in the graph.
3.300 + ///
3.301 + /// \pre \ref init() must be called before using this function.
3.302 + bool findMinMean() {
3.303 + cycle_node = INVALID;
3.304 for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
3.305 -
3.306 initCurrent();
3.307 processRounds();
3.308
3.309 Length min_length;
3.310 int min_size;
3.311 Node min_node;
3.312 - bool found_min = findMinCycleMean(min_length, min_size, min_node);
3.313 + bool found_min = findCurrentMin(min_length, min_size, min_node);
3.314
3.315 - if ( found_min && (!found_cycle || min_length * cycle_size < cycle_length * min_size) ) {
3.316 - found_cycle = true;
3.317 + if ( found_min && (cycle_node == INVALID ||
3.318 + min_length * cycle_size < cycle_length * min_size) ) {
3.319 cycle_length = min_length;
3.320 cycle_size = min_size;
3.321 cycle_node = min_node;
3.322 }
3.323 }
3.324 - if (found_cycle) findCycle(cycle_node);
3.325 - return found_cycle;
3.326 + return (cycle_node != INVALID);
3.327 }
3.328
3.329 - /// \brief Returns the total length of the found critical cycle.
3.330 + /// \brief Finds a critical (minimum mean) cycle.
3.331 ///
3.332 - /// Returns the total length of the found critical cycle.
3.333 + /// Finds a critical (minimum mean) cycle using the path data
3.334 + /// stored in \ref dmap.
3.335 + ///
3.336 + /// \return \c true if a cycle exists in the graph.
3.337 + ///
3.338 + /// \pre \ref init() and \ref findMinMean() must be called before
3.339 + /// using this function.
3.340 + bool findCycle() {
3.341 + if (cycle_node == INVALID) return false;
3.342 + cycle_length = 0;
3.343 + cycle_size = 0;
3.344 + IntNodeMap reached(graph, -1);
3.345 + int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
3.346 + Node u = graph.source(dmap[cycle_node][r].pred);
3.347 + while (reached[u] < 0) {
3.348 + reached[u] = --r;
3.349 + u = graph.source(dmap[u][r].pred);
3.350 + }
3.351 + r = reached[u];
3.352 + Edge e = dmap[u][r].pred;
3.353 + cycle_path->addFront(e);
3.354 + cycle_length = cycle_length + length[e];
3.355 + ++cycle_size;
3.356 + Node v;
3.357 + while ((v = graph.source(e)) != u) {
3.358 + e = dmap[v][--r].pred;
3.359 + cycle_path->addFront(e);
3.360 + cycle_length = cycle_length + length[e];
3.361 + ++cycle_size;
3.362 + }
3.363 + return true;
3.364 + }
3.365 +
3.366 + /// \brief Resets the internal data structures.
3.367 + ///
3.368 + /// Resets the internal data structures so that \ref findMinMean()
3.369 + /// and \ref findCycle() can be called again (e.g. when the
3.370 + /// underlaying graph has been modified).
3.371 + void reset() {
3.372 + for (NodeIt u(graph); u != INVALID; ++u)
3.373 + dmap[u].clear();
3.374 + cycle_node = INVALID;
3.375 + if (cycle_path) cycle_path->clear();
3.376 + comp_num = stronglyConnectedComponents(graph, comp);
3.377 + }
3.378 +
3.379 + /// \brief Returns the total length of the found cycle.
3.380 + ///
3.381 + /// Returns the total length of the found cycle.
3.382 ///
3.383 /// \pre \ref run() must be called before using this function.
3.384 Length cycleLength() const {
3.385 return cycle_length;
3.386 }
3.387
3.388 - /// \brief Returns the number of edges in the found critical
3.389 - /// cycle.
3.390 + /// \brief Returns the number of edges in the found cycle.
3.391 ///
3.392 - /// Returns the number of edges in the found critical cycle.
3.393 + /// Returns the number of edges in the found cycle.
3.394 ///
3.395 /// \pre \ref run() must be called before using this function.
3.396 int cycleEdgeNum() const {
3.397 return cycle_size;
3.398 }
3.399
3.400 - /// \brief Returns the mean length of the found critical cycle.
3.401 + /// \brief Returns the mean length of the found cycle.
3.402 ///
3.403 - /// Returns the mean length of the found critical cycle.
3.404 + /// Returns the mean length of the found cycle.
3.405 ///
3.406 /// \pre \ref run() must be called before using this function.
3.407 ///
3.408 /// \warning LengthMap::Value must be convertible to double.
3.409 + ///
3.410 + /// \note m.minMean() is just a shortcut of the following code.
3.411 + /// \code
3.412 + /// return m.cycleEdgeNum() / double(m.cycleLength());
3.413 + /// \endcode
3.414 double minMean() const {
3.415 - return (double)cycle_length / (double)cycle_size;
3.416 + return cycle_length / (double)cycle_size;
3.417 }
3.418
3.419 /// \brief Returns a const reference to the \ref lemon::Path "Path"
3.420 - /// structure of the found flow.
3.421 + /// structure of the found cycle.
3.422 ///
3.423 /// Returns a const reference to the \ref lemon::Path "Path"
3.424 - /// structure of the found flow.
3.425 + /// structure of the found cycle.
3.426 ///
3.427 /// \pre \ref run() must be called before using this function.
3.428 ///
4.1 --- a/lemon/tolerance.h Thu Mar 22 06:36:50 2007 +0000
4.2 +++ b/lemon/tolerance.h Thu Mar 22 15:40:50 2007 +0000
4.3 @@ -305,6 +305,73 @@
4.4 ///Returns zero
4.5 static Value zero() {return 0;}
4.6 };
4.7 +
4.8 +
4.9 + ///Long integer specialization of \ref Tolerance.
4.10 +
4.11 + ///Long integer specialization of \ref Tolerance.
4.12 + ///\sa Tolerance
4.13 + template<>
4.14 + class Tolerance<long int>
4.15 + {
4.16 + public:
4.17 + ///\e
4.18 + typedef long int Value;
4.19 +
4.20 + ///\name Comparisons
4.21 + ///See \ref Tolerance for more details.
4.22 +
4.23 + ///@{
4.24 +
4.25 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.26 + static bool less(Value a,Value b) { return a<b;}
4.27 + ///Returns \c true if \c a is \e surely different from \c b
4.28 + static bool different(Value a,Value b) { return a!=b; }
4.29 + ///Returns \c true if \c a is \e surely positive
4.30 + static bool positive(Value a) { return 0<a; }
4.31 + ///Returns \c true if \c a is \e surely negative
4.32 + static bool negative(Value a) { return 0>a; }
4.33 + ///Returns \c true if \c a is \e surely non-zero
4.34 + static bool nonZero(Value a) { return a!=0;};
4.35 +
4.36 + ///@}
4.37 +
4.38 + ///Returns zero
4.39 + static Value zero() {return 0;}
4.40 + };
4.41 +
4.42 + ///Unsigned long integer specialization of \ref Tolerance.
4.43 +
4.44 + ///Unsigned long integer specialization of \ref Tolerance.
4.45 + ///\sa Tolerance
4.46 + template<>
4.47 + class Tolerance<unsigned long int>
4.48 + {
4.49 + public:
4.50 + ///\e
4.51 + typedef unsigned long int Value;
4.52 +
4.53 + ///\name Comparisons
4.54 + ///See \ref Tolerance for more details.
4.55 +
4.56 + ///@{
4.57 +
4.58 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.59 + static bool less(Value a,Value b) { return a<b;}
4.60 + ///Returns \c true if \c a is \e surely different from \c b
4.61 + static bool different(Value a,Value b) { return a!=b; }
4.62 + ///Returns \c true if \c a is \e surely positive
4.63 + static bool positive(Value a) { return 0<a; }
4.64 + ///Returns \c true if \c a is \e surely negative
4.65 + static bool negative(Value) { return false; }
4.66 + ///Returns \c true if \c a is \e surely non-zero
4.67 + static bool nonZero(Value a) { return a!=0;};
4.68 +
4.69 + ///@}
4.70 +
4.71 + ///Returns zero
4.72 + static Value zero() {return 0;}
4.73 + };
4.74
4.75 #if defined __GNUC__ && !defined __STRICT_ANSI__
4.76
5.1 --- a/tools/dim_to_lgf.cc Thu Mar 22 06:36:50 2007 +0000
5.2 +++ b/tools/dim_to_lgf.cc Thu Mar 22 15:40:50 2007 +0000
5.3 @@ -46,7 +46,8 @@
5.4 typedef Graph::Node Node;
5.5 typedef Graph::EdgeIt EdgeIt;
5.6 typedef Graph::NodeIt NodeIt;
5.7 - typedef Graph::EdgeMap<double> DoubleMap;
5.8 + typedef Graph::EdgeMap<double> DoubleEdgeMap;
5.9 + typedef Graph::NodeMap<double> DoubleNodeMap;
5.10
5.11 std::string inputName;
5.12 std::string outputName;
5.13 @@ -115,19 +116,19 @@
5.14
5.15 if (mincostflow) {
5.16 Graph graph;
5.17 - Node s, t;
5.18 - DoubleMap cost(graph), capacity(graph);
5.19 - readDimacs(is, graph, capacity, s, t, cost);
5.20 + DoubleNodeMap supply(graph);
5.21 + DoubleEdgeMap lower(graph), capacity(graph), cost(graph);
5.22 + readDimacs(is, graph, supply, lower, capacity, cost);
5.23 GraphWriter<Graph>(os, graph).
5.24 + writeNodeMap("supply", supply).
5.25 + writeEdgeMap("lower", lower).
5.26 writeEdgeMap("capacity", capacity).
5.27 - writeNode("source", s).
5.28 - writeNode("target", t).
5.29 writeEdgeMap("cost", cost).
5.30 run();
5.31 } else if (maxflow) {
5.32 Graph graph;
5.33 Node s, t;
5.34 - DoubleMap capacity(graph);
5.35 + DoubleEdgeMap capacity(graph);
5.36 readDimacs(is, graph, capacity, s, t);
5.37 GraphWriter<Graph>(os, graph).
5.38 writeEdgeMap("capacity", capacity).
5.39 @@ -137,7 +138,7 @@
5.40 } else if (shortestpath) {
5.41 Graph graph;
5.42 Node s;
5.43 - DoubleMap capacity(graph);
5.44 + DoubleEdgeMap capacity(graph);
5.45 readDimacs(is, graph, capacity, s);
5.46 GraphWriter<Graph>(os, graph).
5.47 writeEdgeMap("capacity", capacity).
5.48 @@ -145,7 +146,7 @@
5.49 run();
5.50 } else if (capacitated) {
5.51 Graph graph;
5.52 - DoubleMap capacity(graph);
5.53 + DoubleEdgeMap capacity(graph);
5.54 readDimacs(is, graph, capacity);
5.55 GraphWriter<Graph>(os, graph).
5.56 writeEdgeMap("capacity", capacity).