11 #ifndef _LIMBO_SOLVERS_LPMCF_LGF_H
12 #define _LIMBO_SOLVERS_LPMCF_LGF_H
21 #include <lemon/network_simplex.h>
22 #include <lemon/cost_scaling.h>
26 #include <lemon/list_graph.h>
27 #include <lemon/smart_graph.h>
29 #include <lemon/lgf_reader.h>
30 #include <lemon/lgf_writer.h>
31 #include <lemon/graph_to_eps.h>
32 #include <lemon/math.h>
60 typedef value_type cost_type;
61 typedef lemon::SmartDigraph graph_type;
62 typedef graph_type::Node node_type;
63 typedef graph_type::Arc arc_type;
64 typedef graph_type::NodeMap<value_type> node_value_map_type;
65 typedef graph_type::NodeMap<string> node_name_map_type;
66 typedef graph_type::ArcMap<value_type> arc_value_map_type;
67 typedef graph_type::ArcMap<value_type> arc_cost_map_type;
68 typedef graph_type::ArcMap<value_type> arc_flow_map_type;
69 typedef graph_type::NodeMap<value_type> node_pot_map_type;
72 typedef lemon::NetworkSimplex<graph_type, value_type, cost_type> alg_network_simplex_type;
73 typedef lemon::CostScaling<graph_type, value_type, cost_type> alg_cost_scaling_type;
78 typedef alg_cost_scaling_type alg_type;
99 typename alg_type::ProblemType
operator() (
string const& filename)
103 typename alg_type::ProblemType status = this->
run();
114 typedef lemon::dim2::Point<int>
Point;
116 lemon::Palette palette;
118 graph_type::NodeMap<Point> coords(
m_graph);
119 graph_type::NodeMap<double> sizes(
m_graph);
120 graph_type::NodeMap<int> colors(
m_graph);
121 graph_type::NodeMap<int> shapes(
m_graph);
122 graph_type::ArcMap<int> acolors(
m_graph);
123 graph_type::ArcMap<int> widths(
m_graph);
128 for (graph_type::NodeIt v(
m_graph); v != lemon::INVALID; ++v, ++i)
131 10*(i+rand()%(
m_graph.maxNodeId()<<2)),
132 10*(i+rand()%(
m_graph.maxNodeId()<<2))
139 for (graph_type::ArcIt a(
m_graph); a != lemon::INVALID; ++a, ++i)
146 lemon::graphToEps(
m_graph, filename+
".eps")
147 .title(
"LpMcfD EPS figure")
149 .absoluteNodeSizes().absoluteArcWidths()
150 .nodeScale(2).nodeSizes(sizes)
152 .nodeColors(lemon::composeMap(palette,colors))
153 .arcColors(lemon::composeMap(palette,acolors))
154 .arcWidthScale(.4).arcWidths(widths)
155 .nodeTexts(
m_hName).nodeTextSize(3)
156 .enableParallel().parArcDist(1)
157 .drawArrows().arrowWidth(1).arrowLength(1)
160 lemon::DigraphWriter<graph_type>(
m_graph, filename+
".lgf")
172 std::ofstream out (filename.c_str());
175 cout <<
"failed to open " << filename << endl;
180 out <<
"############# MCF Flow #############" << endl;
181 for (graph_type::ArcIt a(
m_graph); a != lemon::INVALID; ++a)
187 out <<
"############# MCF Potential #############" << endl;
188 for (graph_type::NodeIt v(
m_graph); v != lemon::INVALID; ++v)
199 lemon::DigraphReader<graph_type>(
m_graph, lgfFile)
210 typename alg_type::ProblemType
run()
216 typename alg_type::ProblemType status = alg.reset().resetParams()
229 cout <<
"OPTIMAL" << endl;
232 cout <<
"INFEASIBLE" << endl;
235 cout <<
"UNBOUNDED" << endl;
arc_flow_map_type m_hFlow
solution of min-cost flow, which is the dual solution of LP
graph_type m_graph
input graph
virtual void print_solution(string const &filename) const
print solution
node_name_map_type m_hName
node name in mcf
node_value_map_type m_hSupply
node supply in mcf
alg_type::ProblemType operator()(string const &filename)
API to run the algorithm.
cost_type m_totalcost
total cost after solving
alg_type::ProblemType run()
run algorithm
arc_cost_map_type m_hCost
arc cost in mcf
solve network flow graph with min-cost flow
node_pot_map_type m_hPot
dual solution of min-cost flow, which is the solution of LP
arc_value_map_type m_hLower
lower bound of flow, usually zero
void read_lgf(string const &lgfFile)
read input file in .lgf format and initialize graph
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
virtual void print_graph(string const &filename) const
print graph
arc_value_map_type m_hUpper
upper bound of flow, arc capacity in mcf
#define assert_msg(condition, message)
assertion with message