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
19 #include <lemon/random.h>
22 template <typename UGraph, typename CapacityMap>
23 void genNoiUGraph(UGraph& g, CapacityMap& c,
24 int n, int d, int k, int p) {
25 std::vector<typename UGraph::Node> nodes(n);
26 for (int i = 0; i < n; ++i) {
27 nodes[i] = g.addNode();
29 typename UGraph::template NodeMap<int> comp(g);
30 for (int i = 0; i < n; ++i) {
31 comp[nodes[i]] = rnd[k];
33 int m = (n * (n - 1) * d) / 200;
34 for (int i = 0; i < m; ++i) {
35 int s = rnd[n], t = rnd[n];
36 c[g.addEdge(nodes[s], nodes[t])] =
37 rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100];
41 template <typename UGraph, typename CapacityMap>
42 void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
43 std::vector<typename UGraph::Node> nodes(n);
44 for (int i = 0; i < n; ++i) {
45 nodes[i] = g.addNode();
47 for (int i = 0; i < n - 2; ++i) {
48 c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
50 for (int i = 1; i < n - 2; ++i) {
51 c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
53 c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
54 c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
57 template <typename UGraph, typename CapacityMap>
58 void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
59 std::vector<typename UGraph::Node> nodes(n);
60 for (int i = 0; i < n; ++i) {
61 nodes[i] = g.addNode();
63 for (int k = 0; k < d; ++k) {
64 for (int i = 0; i < n; ++i) {
66 typename UGraph::Node t = nodes[r];
70 for (int i = 1; i < n; ++i) {
71 c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
73 c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
77 template <typename UGraph, typename CapacityMap>
78 void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
79 std::vector<typename UGraph::Node> nodes(n);
80 for (int i = 0; i < n; ++i) {
81 nodes[i] = g.addNode();
83 std::vector<typename UGraph::Node> mix(n * d);
84 for (int i = 0; i < n; ++i) {
85 for (int j = 0; j < d; ++j) {
86 mix[i * d + j] = nodes[i];
89 while (mix.size() >= 2) {
92 typename UGraph::Node s = mix[r];
93 mix[r] = mix.back(); mix.pop_back();
95 typename UGraph::Node t = mix[r];
96 mix[r] = mix.back(); mix.pop_back();
97 c[g.addEdge(s, t)] = 1;