equal
deleted
inserted
replaced
|
1 /* -*- C++ -*- |
|
2 * demo/lp_maxflow_demo.cc - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 ///\ingroup demos |
|
18 ///\file |
|
19 ///\brief Max flow problem solved with an LP solver (demo). |
|
20 /// |
|
21 ///This demo program shows how to solve a maximum (or maximal) flow |
|
22 ///problem using the LEMON LP solver interface. We would like to lay |
|
23 ///the emphasis on the simplicity of the way one can formulate the LP |
|
24 ///constraints with LEMON that arise in graph theory. |
|
25 |
1 #ifdef HAVE_CONFIG_H |
26 #ifdef HAVE_CONFIG_H |
2 #include <config.h> |
27 #include <config.h> |
3 #endif |
28 #endif |
4 |
29 |
5 #include<lemon/graph_reader.h> |
30 #include<lemon/graph_reader.h> |
6 #include<lemon/list_graph.h> |
31 #include<lemon/list_graph.h> |
|
32 |
|
33 #include <fstream> |
|
34 #include <iostream> |
7 |
35 |
8 |
36 |
9 #ifdef HAVE_GLPK |
37 #ifdef HAVE_GLPK |
10 #include <lemon/lp_glpk.h> |
38 #include <lemon/lp_glpk.h> |
11 #elif HAVE_CPLEX |
39 #elif HAVE_CPLEX |
73 lp.solve(); |
101 lp.solve(); |
74 |
102 |
75 return lp.primalValue(); |
103 return lp.primalValue(); |
76 } |
104 } |
77 |
105 |
78 int main() |
106 int main(int argc, char *argv[]) |
79 { |
107 { |
|
108 if(argc<2) |
|
109 { |
|
110 std::cerr << "USAGE: lp_maxflow_demo <input_file.lgf>" << std::endl; |
|
111 std::cerr << "The file 'input_file.lgf' has to contain a max flow instance in LEMON format (e.g. sample.lgf is such a file)." << std::endl; |
|
112 return 0; |
|
113 } |
|
114 |
|
115 |
|
116 //input stream to read the graph from |
|
117 std::ifstream is(argv[1]); |
|
118 |
|
119 |
80 ListGraph g; |
120 ListGraph g; |
81 ListGraph::Node s; |
121 ListGraph::Node s; |
82 ListGraph::Node t; |
122 ListGraph::Node t; |
83 |
123 |
84 ListGraph::EdgeMap<double> cap(g); |
124 ListGraph::EdgeMap<double> cap(g); |
85 |
125 |
86 GraphReader<ListGraph> reader(std::cin,g); |
126 GraphReader<ListGraph> reader(is,g); |
87 reader.readNode("source",s).readNode("target",t) |
127 reader.readNode("source",s).readNode("target",t) |
88 .readEdgeMap("capacity",cap).run(); |
128 .readEdgeMap("capacity",cap).run(); |
89 |
129 |
90 // std::ifstream file("../test/preflow_"); |
|
91 // readDimacs(file, g, cap, s, t); |
|
92 |
|
93 std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl; |
130 std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl; |
94 |
131 |
95 } |
132 } |