The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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
22 #include "test_tools.h"
23 #include <lemon/maps.h>
24 #include <lemon/kruskal.h>
25 #include <lemon/list_graph.h>
26 #include <lemon/concept/maps.h>
27 #include <lemon/concept/graph.h>
31 using namespace lemon;
33 void checkCompileKruskal()
35 concept::WriteMap<concept::StaticGraph::Edge,bool> w;
37 kruskal(concept::StaticGraph(),
38 concept::ReadMap<concept::StaticGraph::Edge,int>(),
44 typedef ListGraph::Node Node;
45 typedef ListGraph::Edge Edge;
46 typedef ListGraph::NodeIt NodeIt;
47 typedef ListGraph::EdgeIt EdgeIt;
58 Edge e1 = G.addEdge(s, v1);
59 Edge e2 = G.addEdge(s, v2);
60 Edge e3 = G.addEdge(v1, v2);
61 Edge e4 = G.addEdge(v2, v1);
62 Edge e5 = G.addEdge(v1, v3);
63 Edge e6 = G.addEdge(v3, v2);
64 Edge e7 = G.addEdge(v2, v4);
65 Edge e8 = G.addEdge(v4, v3);
66 Edge e9 = G.addEdge(v3, t);
67 Edge e10 = G.addEdge(v4, t);
69 typedef ListGraph::EdgeMap<int> ECostMap;
70 typedef ListGraph::EdgeMap<bool> EBoolMap;
72 ECostMap edge_cost_map(G, 2);
76 //Test with const map.
77 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
78 "Total cost should be 10");
79 //Test with a edge map (filled with uniform costs).
80 check(kruskal(G, edge_cost_map, tree_map)==10,
81 "Total cost should be 10");
83 edge_cost_map.set(e1, -10);
84 edge_cost_map.set(e2, -9);
85 edge_cost_map.set(e3, -8);
86 edge_cost_map.set(e4, -7);
87 edge_cost_map.set(e5, -6);
88 edge_cost_map.set(e6, -5);
89 edge_cost_map.set(e7, -4);
90 edge_cost_map.set(e8, -3);
91 edge_cost_map.set(e9, -2);
92 edge_cost_map.set(e10, -1);
94 vector<Edge> tree_edge_vec(5);
96 //Test with a edge map and inserter.
97 check(kruskal(G, edge_cost_map,
98 tree_edge_vec.begin())
100 "Total cost should be -31.");
102 tree_edge_vec.clear();
104 check(kruskal(G, edge_cost_map,
105 back_inserter(tree_edge_vec))
107 "Total cost should be -31.");
109 tree_edge_vec.clear();
111 //The above test could also be coded like this:
113 makeKruskalMapInput(G, edge_cost_map),
114 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
116 "Total cost should be -31.");
118 check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
120 check(tree_edge_vec[0]==e1 &&
121 tree_edge_vec[1]==e2 &&
122 tree_edge_vec[2]==e5 &&
123 tree_edge_vec[3]==e7 &&
124 tree_edge_vec[4]==e9,