Major improvements in NetworkSimplex.
Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Use function parameter instead of #define commands to select pivot rule.
- Use much faster implementation for the candidate list pivot rule.
It is about 5-20 times faster now.
- Add a new pivot rule called "Limited Search" that is a modified
version of "Block Search". It is about 25 percent faster on rather
sparse graphs.
- By default "Limited Search" is used for sparse graphs and
"Block Search" is used otherwise. This combined method is the most
efficient on every input class.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Many doc improvements.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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
21 ///\brief DIMACS to LGF converter.
23 /// This program converts various DIMACS formats to the LEMON Graph Format
28 /// ./tools/dim_to_lgf
29 /// --mincostflow|-mcf|--maxflow|-mf|--shortestpath|-sp|--capacitated|-cap|--plain|-pl
30 /// [--help|-h|-help] [--input|-i str] [--output|-o str] [--version|-v]
32 /// --capacitated|-cap
33 /// set the type of the graph to "capacitated" graph
35 /// Print a short help message
37 /// use FILE as input instead of standard input
39 /// set the type of the graph to "maxflow" graph
40 /// --mincostflow|-mcf
41 /// set the type of the graph to "mincostflow" graph
43 /// use FILE as output instead of standard output
45 /// set the type of the graph to "plain" graph
46 /// --shortestpath|-sp
47 /// set the type of the graph to "shortestpath" graph
49 /// show version information
57 #include <lemon/smart_graph.h>
58 #include <lemon/dimacs.h>
59 #include <lemon/graph_writer.h>
61 #include <lemon/arg_parser.h>
64 using namespace lemon;
67 int main(int argc, const char *argv[]) {
68 typedef SmartGraph Graph;
70 typedef Graph::Edge Edge;
71 typedef Graph::Node Node;
72 typedef Graph::EdgeIt EdgeIt;
73 typedef Graph::NodeIt NodeIt;
74 typedef Graph::EdgeMap<double> DoubleEdgeMap;
75 typedef Graph::NodeMap<double> DoubleNodeMap;
77 std::string inputName;
78 std::string outputName;
89 ArgParser ap(argc, argv);
90 ap.refOption("-input",
91 "use FILE as input instead of standard input",
92 inputName).synonym("i", "-input")
94 "use FILE as output instead of standard output",
95 outputName).synonym("o", "-output")
96 .refOption("-mincostflow",
97 "set the type of the graph to \"mincostflow\" graph",
99 .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow")
100 .refOption("-maxflow",
101 "set the type of the graph to \"maxflow\" graph",
103 .optionGroup("type", "-maxflow").synonym("mf", "-maxflow")
104 .refOption("-shortestpath",
105 "set the type of the graph to \"shortestpath\" graph",
107 .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath")
108 .refOption("-capacitated",
109 "set the type of the graph to \"capacitated\" graph",
111 .optionGroup("type", "-capacitated").synonym("cap", "-capacitated")
113 "set the type of the graph to \"plain\" graph",
115 .optionGroup("type", "-plain").synonym("pl", "-plain")
116 .onlyOneGroup("type")
117 .mandatoryGroup("type")
118 .refOption("-version", "show version information", version)
119 .synonym("v", "-version")
123 if (!inputName.empty()) {
124 input.open(inputName.c_str());
126 cerr << "File open error" << endl;
130 istream& is = (inputName.empty() ? cin : input);
133 if (!outputName.empty()) {
134 output.open(outputName.c_str());
136 cerr << "File open error" << endl;
140 ostream& os = (outputName.empty() ? cout : output);
144 DoubleEdgeMap lower(graph), capacity(graph), cost(graph);
145 DoubleNodeMap supply(graph);
146 readDimacs(is, graph, lower, capacity, cost, supply);
147 GraphWriter<Graph>(os, graph).
148 writeNodeMap("supply", supply).
149 writeEdgeMap("lower", lower).
150 writeEdgeMap("capacity", capacity).
151 writeEdgeMap("cost", cost).
153 } else if (maxflow) {
156 DoubleEdgeMap capacity(graph);
157 readDimacs(is, graph, capacity, s, t);
158 GraphWriter<Graph>(os, graph).
159 writeEdgeMap("capacity", capacity).
160 writeNode("source", s).
161 writeNode("target", t).
163 } else if (shortestpath) {
166 DoubleEdgeMap capacity(graph);
167 readDimacs(is, graph, capacity, s);
168 GraphWriter<Graph>(os, graph).
169 writeEdgeMap("capacity", capacity).
170 writeNode("source", s).
172 } else if (capacitated) {
174 DoubleEdgeMap capacity(graph);
175 readDimacs(is, graph, capacity);
176 GraphWriter<Graph>(os, graph).
177 writeEdgeMap("capacity", capacity).
181 readDimacs(is, graph);
182 GraphWriter<Graph>(os, graph).run();
184 cerr << "Invalid type error" << endl;