Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_LP_UTILS_H
20 #define LEMON_LP_UTILS_H
22 #include <lemon/lp_base.h>
24 #include <lemon/lemon_reader.h>
25 #include <lemon/lemon_writer.h>
35 /// \brief The map for the result of the lp variables.
37 /// The map for the result of the lp variables.
40 typedef LpSolverBase::Col Key;
41 typedef LpSolverBase::Value Value;
43 /// \brief Constructor
46 LpResultMap(const LpSolverBase& _lp) : lp(_lp) {}
47 LpSolverBase::Value operator[](const LpSolverBase::Col col) const {
48 return lp.primal(col);
51 const LpSolverBase& lp;
56 /// \brief Returns an \ref LpResultMap class
58 /// This function just returns an \ref LpResultMap class.
59 /// \relates LpResultMap
60 LpResultMap lpResultMap(const LpSolverBase& lp) {
61 return LpResultMap(lp);
66 /// \brief The map for the name of the lp variables.
68 /// The map for the name of the lp variables.
71 typedef LpSolverBase::Col Key;
72 typedef std::string Value;
74 /// \brief Constructor
77 LpColNameMap(const LpSolverBase& _lp) : lp(_lp) {}
78 std::string operator[](const LpSolverBase::Col col) const {
79 return lp.colName(col);
82 const LpSolverBase& lp;
87 /// \brief Writeable map for the name of the lp variables.
89 /// Writeable map for the name of the lp variables.
90 class LpColNameWriteMap {
92 typedef LpSolverBase::Col Key;
93 typedef std::string Value;
95 /// \brief Constructor
98 LpColNameWriteMap(LpSolverBase& _lp) : lp(_lp) {}
99 std::string operator[](const LpSolverBase::Col col) const {
100 return lp.colName(col);
102 void set(const LpSolverBase::Col col, const std::string& name) {
103 lp.colName(col, name);
109 /// \ingroup lp_utils
111 /// \brief Returns an \ref LpColNameMap class
113 /// This function just returns an \ref LpColNameMap class.
114 /// \relates LpColNameMap
115 LpColNameMap lpColNameMap(const LpSolverBase& lp) {
116 return LpColNameMap(lp);
119 LpColNameWriteMap lpColNameMap(LpSolverBase& lp) {
120 return LpColNameWriteMap(lp);
123 /// \ingroup lp_utils
125 /// \brief Lp variable item reader for Lemon IO
127 /// This class is an Lp variable item reader for Lemon IO. It makes
128 /// possible to store lp variables in lemon file. The usage of this
129 /// class is very simple:
134 /// Graph::EdgeMap<Lp::Col> var(graph);
136 /// GraphReader<Graph> reader(cin, graph);
137 /// reader.readEdgeMap("lpvar", var, LpColReader(lp));
141 /// If there is already a variable with the same name in the lp then
142 /// it will be used for the return value. If there is no such variable
143 /// then it will be constructed. The file could contain \c '-' as value
144 /// which means that no lp variable associated to the current item and
145 /// in this case INVALID will be returned.
149 /// \brief The value type of reader.
151 /// The value type of reader.
152 typedef LpSolverBase::Col Value;
154 /// \brief Constructor for the reader.
156 /// Constructor for the reader.
157 LpColReader(LpSolverBase& _lp) : lp(_lp) {}
159 /// \brief Reads an lp variable from the given stream.
161 /// Reads an lp variable string from the given stream.
162 void read(std::istream& is, LpSolverBase::Col& col) const {
166 throw DataFormatError("Wrong Lp Column format!");
167 if (varFirstChar(x)) {
171 while (is.get(x) && varChar(x)) {
179 col = lp.colByName(var);
180 if (col == INVALID) {
182 lp.colName(col, var);
184 } else if (x == '-') {
188 std::cerr << x << std::endl;
189 throw DataFormatError("Wrong Lp Column format");
195 static bool varFirstChar(char c) {
196 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
199 static bool varChar(char c) {
200 return (c >= '0' && c <= '9') ||
201 (c >= 'a' && c <= 'z') ||
202 (c >= 'A' && c <= 'Z') ||
203 c == '[' || c == ']';
210 /// \ingroup lp_utils
212 /// \brief Lp variable item writer for Lemon IO
214 /// This class is an Lp variable item writer for Lemon IO. It makes
215 /// possible to store lp variables in lemon file. The usage of this
216 /// class is very simple:
221 /// Graph::EdgeMap<Lp::Col> var(graph);
223 /// GraphWriter<Graph> writer(cin, graph);
224 /// writer.writeEdgeMap("lpvar", var, LpColWriter(lp));
228 /// If there is no name associated to the current item then the name
229 /// will automatically constructed. If the value is INVALID then it
230 /// will write an \c '-' value to the file.
234 /// \brief The value type of writer.
236 /// The value type of writer.
237 typedef LpSolverBase::Col Value;
239 /// \brief Constructor for the writer.
241 /// Constructor for the writer.
242 LpColWriter(const LpSolverBase& _lp) : lp(_lp), num(0) {}
244 /// \brief Writes an lp variable to the given stream.
246 /// Writes an lp variable to the given stream.
247 void write(std::ostream& os, const LpSolverBase::Col& col) const {
248 if (col != INVALID) {
249 std::string name = lp.colName(col);
251 std::ostringstream ls;
254 while (lp.colByName(ls.str()) != INVALID) {
255 ls.str(std::string());
259 const_cast<LpSolverBase&>(lp).colName(col, ls.str());
271 const LpSolverBase& lp;
276 /// \ingroup lp_utils
278 /// \brief Lp section reader for lemon IO
280 /// This section reader provides an easy way to read an Lp problem
281 /// from a file. The lemon lp section format contains three parts.
287 /// 2 * x1 + x3 / 2 <= 7
288 /// x2 + -3 * x3 >= 8
289 /// 3 <= x2 - 2 * x1 <= 8
295 /// min x1 + 2 * x2 - x3
298 /// The first part gives the constraints to the lp. The constraints
299 /// could be equality, lower bound, upper bound or range for an
300 /// expression or equality, less or more for two expressions.
302 /// The second part gives the bounds for the variables. The bounds
303 /// could be the same as for the single expression so equality,
304 /// lower bound, upper bound or range.
306 /// The third part is the objective function, it should start with
307 /// \c min or \c max and then a valid linear expression.
309 /// The reader constructs automatically the variable for a name if
310 /// there is not already a variable with the same name.
312 /// The basic way to read an LP problem is made by the next code:
316 /// LemonReader reader(filename_or_istream);
317 /// LpReader lpreader(reader, lp);
322 /// Of course instead of \c LemonReader you can give a \c
323 /// GraphReader to the LpReader constructor. Also useful that you
324 /// can mix lp problems and graphs in the same file.
325 class LpReader : public LemonReader::SectionReader {
326 typedef LemonReader::SectionReader Parent;
330 /// \brief Constructor.
332 /// Constructor for LpReader. It creates the LpReader and attachs
333 /// it into the given LemonReader. The lp reader will add
334 /// variables, constraints and objective function to the
336 LpReader(LemonReader& _reader, LpSolverBase& _lp,
337 const std::string& _name = std::string())
338 : Parent(_reader), lp(_lp), name(_name) {}
341 /// \brief Destructor.
343 /// Destructor for LpReader.
344 virtual ~LpReader() {}
347 LpReader(const LpReader&);
348 void operator=(const LpReader&);
352 /// \brief Gives back true when the SectionReader can process
353 /// the section with the given header line.
355 /// It gives back true when the header line starts with \c \@lp,
356 /// and the header line's name and the nodeset's name are the same.
357 virtual bool header(const std::string& line) {
358 std::istringstream ls(line);
362 return command == "@lp" && name == id;
368 CONSTRAINTS, BOUNDS, OBJECTIVE
375 std::istream& readConstraint(std::istream& is) {
376 LpSolverBase::Constr c;
378 LpSolverBase::Expr e1, e2;
381 readExpression(is, e1);
383 readRelation(is, op1);
385 readExpression(is, e2);
389 if (e1.size() == 0) {
395 } else if (op1 == GE) {
396 if (e1.size() == 0) {
402 if (e1.size() == 0) {
410 LpSolverBase::Expr e3;
412 readRelation(is, op2);
414 readExpression(is, e3);
415 if (!e1.empty() || !e3.empty()) {
416 throw DataFormatError("Wrong range format");
418 if (op2 != op1 || op1 == EQ) {
419 throw DataFormatError("Wrong range format");
422 c = e1.constComp() <= e2 <= e3.constComp();
424 c = e1.constComp() >= e2 >= e3.constComp();
428 throw DataFormatError("Wrong variable bounds format");
435 std::istream& readObjective(std::istream& is) {
439 if (sense != "min" && sense != "max") {
440 throw DataFormatError("Wrong objective function format");
442 LpSolverBase::Expr expr;
444 readExpression(is, expr);
446 if (sense == "min") {
454 std::istream& readBounds(std::istream& is) {
459 throw DataFormatError("Wrong variable bounds format");
461 if (varFirstChar(x)) {
466 readRelation(is, op1);
470 lp.colLowerBound(c, v);
471 lp.colUpperBound(c, v);
472 } else if (op1 == LE) {
473 lp.colUpperBound(c, v);
475 lp.colLowerBound(c, v);
479 throw DataFormatError("Wrong variable bounds format");
487 readRelation(is, op1);
495 readRelation(is, op2);
499 if (op2 != op1 || op1 == EQ) {
500 throw DataFormatError("Wrong range format");
503 lp.colLowerBound(c, v);
504 lp.colUpperBound(c, w);
506 lp.colLowerBound(c, w);
507 lp.colUpperBound(c, v);
511 throw DataFormatError("Wrong variable bounds format");
515 lp.colLowerBound(c, v);
516 lp.colUpperBound(c, v);
517 } else if (op1 == LE) {
518 lp.colLowerBound(c, v);
520 lp.colUpperBound(c, v);
527 std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {
531 readElement(is, c, d);
538 while (is.get(x) && (x == '+' || x == '-')) {
540 readElement(is, c, d);
542 e += (x == '+' ? d : -d) * c;
544 e += (x == '+' ? d : -d);
556 std::istream& readElement(std::istream& is,
557 LpSolverBase::Col& c, double& d) {
561 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
562 if (x == '+' || x == '-') {
564 d *= x == '-' ? -1 : 1;
565 while (is.get(x) && (x == '+' || x == '-')) {
566 d *= x == '-' ? -1 : 1;
569 if (!is) throw DataFormatError("Cannot find lp element");
571 if (numFirstChar(x)) {
576 } else if (varFirstChar(x)) {
582 throw DataFormatError("Invalid expression format");
585 while (is.get(y) && (y == '*' || y == '/')) {
587 if (!is.get(x)) throw DataFormatError("Cannot find lp element");
588 if (x == '+' || x == '-') {
590 d *= x == '-' ? -1 : 1;
591 while (is.get(x) && (x == '+' || x == '-')) {
592 d *= x == '-' ? -1 : 1;
595 if (!is) throw DataFormatError("Cannot find lp element");
597 if (numFirstChar(x)) {
606 } else if (varFirstChar(x)) {
614 throw DataFormatError("Quadratic element in expression");
617 throw DataFormatError("Division by variable");
620 throw DataFormatError("Invalid expression format");
632 std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {
635 while (is.get(x) && varChar(x)) {
643 c = lp.colByName(var);
651 std::istream& readNum(std::istream& is, double& d) {
653 if (!is) throw DataFormatError("Wrong number format");
657 std::istream& readRelation(std::istream& is, Relation& op) {
659 if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
660 throw DataFormatError("Wrong relation operator");
662 if (!is.get(y) || y != '=') {
663 throw DataFormatError("Wrong relation operator");
676 static bool relationFirstChar(char c) {
677 return c == '<' || c == '=' || c == '>';
680 static bool varFirstChar(char c) {
681 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
684 static bool numFirstChar(char c) {
685 return (c >= '0' && c <= '9') || c == '.';
688 static bool varChar(char c) {
689 return (c >= '0' && c <= '9') ||
690 (c >= 'a' && c <= 'z') ||
691 (c >= 'A' && c <= 'Z') ||
692 c == '[' || c == ']';
697 /// \brief Reader function of the section.
699 /// It reads the content of the section.
700 virtual void read(std::istream& is) {
702 Part part = CONSTRAINTS;
703 while (getline(is, line)) {
704 std::istringstream ls(line);
707 if (type == "constraints") {
712 throw DataFormatError("Wrong Lp format");
713 } else if (type == "bounds") {
718 throw DataFormatError("Wrong Lp format");
719 } else if (type == "objective") {
724 throw DataFormatError("Wrong Lp format");
742 virtual void missing() {
744 msg << "Lp section not found in file: @lp " << name;
745 throw IoParameterError(msg.message());
756 /// \ingroup lp_utils
758 /// \brief Lp section writer for lemon IO
760 /// This section reader provides an easy way to write an Lp problem
761 /// to a file. The lemon lp section format contains three parts.
767 /// 2 * x1 + x3 / 2 <= 7
768 /// x2 + -3 * x3 >= 8
769 /// 3 <= x2 - 2 * x1 <= 8
775 /// min x1 + 2 * x2 - x3
778 /// The first part gives the constraints to the lp. The constraints
779 /// could be equality, lower bound, upper bound or range for an
780 /// expression or equality, less or more for two expressions.
782 /// The second part gives the bounds for the variables. The bounds
783 /// could be the same as for the single expression so equality,
784 /// lower bound, upper bound or range.
786 /// The third part is the objective function, it should start with
787 /// \c min or \c max and then a valid linear expression.
789 /// If an LP variable does not have name in the writer, then it will
790 /// automatically created in the writer. This make a slight change
791 /// in the \c const variable.
793 /// The basic way to write an LP problem is made by the next code:
797 /// LemonWriter writer(filename_or_ostream);
798 /// LpWriter lpwriter(writer, lp);
803 /// Of course instead of \c LemonWriter you can give a \c
804 /// GraphWriter to the LpWriter constructor. Also useful that you
805 /// can mix lp problems and graphs in the same file.
806 class LpWriter : public LemonWriter::SectionWriter {
807 typedef LemonWriter::SectionWriter Parent;
811 /// \brief Constructor.
813 /// Constructor for LpWriter. It creates the LpWriter and attach
814 /// it into the given LemonWriter.
815 LpWriter(LemonWriter& _writer, const LpSolverBase& _lp,
816 const std::string& _name = std::string())
817 : Parent(_writer), lp(_lp), name(_name) {}
820 /// \brief Destructor.
822 /// Destructor for LpWriter.
823 virtual ~LpWriter() {}
826 LpWriter(const LpWriter&);
827 void operator=(const LpWriter&);
831 /// \brief Gives back true when the SectionWriter can process
832 /// the section with the given header line.
834 /// It gives back the header line of the \c \@lp section.
835 virtual std::string header() {
836 std::ostringstream ls;
837 ls << "@lp " << name;
846 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
847 std::string name = lp.colName(it);
849 std::ostringstream ls;
852 while (lp.colByName(ls.str()) != INVALID) {
853 ls.str(std::string());
857 const_cast<LpSolverBase&>(lp).colName(it, ls.str());
862 void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
864 for (LpSolverBase::Expr::const_iterator jt = e.begin();
865 jt != e.end(); ++jt) {
866 if (jt->second < 0.0) {
868 if (jt->second != -1.0) {
869 os << -jt->second << " * ";
871 } else if (jt->second > 0.0) {
875 if (jt->second != 1.0) {
876 os << jt->second << " * ";
880 os << lp.colName(jt->first) << " ";
882 if (e.constComp() < 0.0) {
883 os << "- " << -e.constComp() << " ";
884 } else if (e.constComp() > 0.0) {
888 os << e.constComp() << " ";
890 if (e.begin() == e.end() && e.constComp() == 0.0) {
897 /// \brief Writer function of the section.
899 /// It writes the content of the section.
900 virtual void write(std::ostream& os) {
903 os << "constraints" << std::endl;
905 for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
907 lp.getRowBounds(it, lower, upper);
908 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
912 if (lower != upper) {
913 if (lower != -LpSolverBase::INF) {
914 os << lower << " <= ";
917 writeExpression(os, lp.row(it));
919 if (upper != LpSolverBase::INF) {
920 os << "<= " << upper << " ";
924 writeExpression(os, lp.row(it));
925 os << "== " << upper << " ";
932 os << "bounds" << std::endl;
934 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
935 double lower = lp.colLowerBound(it);
936 double upper = lp.colUpperBound(it);
937 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
941 if (lower != upper) {
942 if (lower != -LpSolverBase::INF) {
943 os << lower << " <= ";
946 os << lp.colName(it) << " ";
948 if (upper != LpSolverBase::INF) {
949 os << "<= " << upper << " ";
952 os << lp.colName(it) << " == " << upper << " ";
957 os << "objective" << std::endl;
964 writeExpression(os, lp.obj());
971 const LpSolverBase& lp;