Query improvements in the min cost flow algorithms.
- External flow and potential maps can be used.
- New query functions: flow() and potential().
- CycleCanceling also provides dual solution (node potentials).
- 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
23 #include <lemon/smart_graph.h>
24 #include <lemon/list_graph.h>
26 #include <lemon/bpugraph_adaptor.h>
27 #include <lemon/bipartite_matching.h>
29 #include <lemon/graph_utils.h>
30 #include <lemon/graph_to_eps.h>
32 #include <lemon/time_measure.h>
33 #include <lemon/random.h>
36 using namespace lemon;
38 typedef SmartBpUGraph Graph;
39 typedef ListBpUGraph LGraph;
40 BPUGRAPH_TYPEDEFS(Graph);
45 for (int k = 1; k < 100; ++k) {
48 int m = (100 - k) * 100;
52 Timer nt(false), st(false);
53 Timer lnt(false), lst(false);
55 for (int i = 0; i < s; ++i) {
60 vector<LGraph::Node> laNodes;
61 vector<LGraph::Node> lbNodes;
63 for (int j = 0; j < n; ++j) {
64 Node node = graph.addANode();
65 aNodes.push_back(node);
66 LGraph::Node lnode = lgraph.addANode();
67 laNodes.push_back(lnode);
69 for (int j = 0; j < m; ++j) {
70 Node node = graph.addBNode();
71 bNodes.push_back(node);
72 LGraph::Node lnode = lgraph.addBNode();
73 lbNodes.push_back(lnode);
75 for (int j = 0; j < e; ++j) {
77 Node aNode = aNodes[a=rnd[n]];
78 Node bNode = bNodes[b=rnd[m]];
79 graph.addEdge(aNode, bNode);
80 LGraph::Node laNode = laNodes[a];
81 LGraph::Node lbNode = lbNodes[b];
82 lgraph.addEdge(laNode, lbNode);
86 MaxBipartiteMatching<Graph> bpmatch(graph);
96 typedef SwapBpUGraphAdaptor<Graph> SGraph;
98 MaxBipartiteMatching<SGraph> bpmatch(sgraph);
107 MaxBipartiteMatching<LGraph> bpmatch(lgraph);
117 typedef SwapBpUGraphAdaptor<LGraph> SGraph;
118 SGraph sgraph(lgraph);
119 MaxBipartiteMatching<SGraph> bpmatch(sgraph);
129 cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
130 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;