Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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/concepts/bpugraph.h>
20 #include <lemon/list_graph.h>
21 #include <lemon/smart_graph.h>
22 #include <lemon/full_graph.h>
23 #include <lemon/grid_ugraph.h>
25 #include <lemon/graph_utils.h>
27 #include "test_tools.h"
30 using namespace lemon;
31 using namespace lemon::concepts;
33 void check_concepts() {
35 { // checking graph components
36 checkConcept<BaseBpUGraphComponent, BaseBpUGraphComponent >();
38 checkConcept<IDableBpUGraphComponent<>,
39 IDableBpUGraphComponent<> >();
41 checkConcept<IterableBpUGraphComponent<>,
42 IterableBpUGraphComponent<> >();
44 checkConcept<MappableBpUGraphComponent<>,
45 MappableBpUGraphComponent<> >();
49 checkConcept<BpUGraph, ListBpUGraph>();
51 checkConcept<BpUGraph, SmartBpUGraph>();
53 checkConcept<BpUGraph, FullBpUGraph>();
55 checkConcept<BpUGraph, BpUGraph>();
60 template <typename Graph>
61 void check_item_counts(Graph &g, int an, int bn, int e) {
63 for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
67 check(nn == an + bn, "Wrong node number.");
68 check(countNodes(g) == an + bn, "Wrong node number.");
71 for (typename Graph::ANodeIt it(g); it != INVALID; ++it) {
75 check(ann == an, "Wrong node number.");
76 check(countANodes(g) == an, "Wrong node number.");
79 for (typename Graph::BNodeIt it(g); it != INVALID; ++it) {
83 check(bnn == bn, "Wrong node number.");
84 check(countBNodes(g) == bn, "Wrong node number.");
87 for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
91 check(ee == 2*e, "Wrong edge number.");
92 check(countEdges(g) == 2*e, "Wrong edge number.");
95 for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) {
99 check(uee == e, "Wrong uedge number.");
100 check(countUEdges(g) == e, "Wrong uedge number.");
103 template <typename Graph>
106 typedef typename Graph::Node Node;
107 typedef typename Graph::UEdge UEdge;
108 typedef typename Graph::Edge Edge;
109 typedef typename Graph::NodeIt NodeIt;
110 typedef typename Graph::UEdgeIt UEdgeIt;
111 typedef typename Graph::EdgeIt EdgeIt;
115 check_item_counts(g, 0, 0, 0);
125 e1 = g.addEdge(an1, bn1),
126 e2 = g.addEdge(an2, bn1),
127 e3 = g.addEdge(an3, bn2);
129 check_item_counts(g, 3, 2, 3);
135 check_graph<ListBpUGraph>();
136 check_graph<SmartBpUGraph>();
139 FullBpUGraph g(5, 10);
140 check_item_counts(g, 5, 10, 50);
143 std::cout << __FILE__ ": All tests passed.\n";