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 "test_tools.h"
20 #include <lemon/smart_graph.h>
21 #include <lemon/bfs.h>
22 #include <lemon/path.h>
23 #include<lemon/concepts/graph.h>
25 using namespace lemon;
27 const int PET_SIZE =5;
30 void check_Bfs_Compile()
32 typedef concepts::Graph Graph;
34 typedef Graph::Edge Edge;
35 typedef Graph::Node Node;
36 typedef Graph::EdgeIt EdgeIt;
37 typedef Graph::NodeIt NodeIt;
39 typedef Bfs<Graph> BType;
48 // BType::PredNodeMap pn(G);
55 e = bfs_test.predEdge(n);
56 n = bfs_test.predNode(n);
57 d = bfs_test.distMap();
58 p = bfs_test.predMap();
59 // pn = bfs_test.predNodeMap();
60 b = bfs_test.reached(n);
62 Path<Graph> pp = bfs_test.path(n);
65 void check_Bfs_Function_Compile()
68 typedef concepts::Graph Graph;
70 typedef Graph::Edge Edge;
71 typedef Graph::Node Node;
72 typedef Graph::EdgeIt EdgeIt;
73 typedef Graph::NodeIt NodeIt;
74 typedef concepts::ReadMap<Edge,VType> LengthMap;
78 bfs(g).source(Node()).run();
80 .predMap(concepts::WriteMap<Node,Edge>())
81 .distMap(concepts::WriteMap<Node,VType>())
82 .reachedMap(concepts::ReadWriteMap<Node,bool>())
83 .processedMap(concepts::WriteMap<Node,bool>())
91 typedef SmartGraph Graph;
93 typedef Graph::Edge Edge;
94 typedef Graph::Node Node;
95 typedef Graph::EdgeIt EdgeIt;
96 typedef Graph::NodeIt NodeIt;
97 typedef Graph::EdgeMap<int> LengthMap;
101 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
106 Bfs<Graph> bfs_test(G);
109 check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
111 Path<Graph> p = bfs_test.path(t);
112 check(p.length()==3,"getPath() found a wrong path.");
113 check(checkPath(G, p),"path() found a wrong path.");
114 check(pathSource(G, p) == s,"path() found a wrong path.");
115 check(pathTarget(G, p) == t,"path() found a wrong path.");
118 for(EdgeIt e(G); e==INVALID; ++e) {
121 check( !bfs_test.reached(u) ||
122 (bfs_test.dist(v) > bfs_test.dist(u)+1),
126 for(NodeIt v(G); v==INVALID; ++v) {
127 check(bfs_test.reached(v),"Each node should be reached.");
128 if ( bfs_test.predEdge(v)!=INVALID ) {
129 Edge e=bfs_test.predEdge(v);
131 check(u==bfs_test.predNode(v),"Wrong tree.");
132 check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
133 "Wrong distance. Difference: "
134 << std::abs(bfs_test.dist(v) - bfs_test.dist(u)