r490:a1155a9e8e09
Mon, 12 Jan 2009 14:18:03
[Not Reviewed]
0 comments (0 inline)
1
4
1
12
13
841
339
| ... | ... |
@@ -2668,6 +2668,6 @@ |
| 2668 | 2668 |
/// |
| 2669 |
/// Residual can be used for composing the \e residual digraph for directed |
|
| 2670 |
/// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph |
|
| 2671 |
/// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be |
|
| 2672 |
/// functions on the arcs. |
|
| 2669 |
/// ResidualDigraph can be used for composing the \e residual digraph |
|
| 2670 |
/// for directed flow and circulation problems. Let \f$ G=(V, A) \f$ |
|
| 2671 |
/// be a directed graph and let \f$ F \f$ be a number type. |
|
| 2672 |
/// Let \f$ flow, cap: A\to F \f$ be functions on the arcs. |
|
| 2673 | 2673 |
/// This adaptor implements a digraph structure with node set \f$ V \f$ |
| ... | ... |
@@ -2706,3 +2706,3 @@ |
| 2706 | 2706 |
template<typename GR, typename CM, typename FM, typename TL> |
| 2707 |
class |
|
| 2707 |
class ResidualDigraph |
|
| 2708 | 2708 |
#else |
| ... | ... |
@@ -2712,3 +2712,3 @@ |
| 2712 | 2712 |
typename TL = Tolerance<typename CM::Value> > |
| 2713 |
class |
|
| 2713 |
class ResidualDigraph : |
|
| 2714 | 2714 |
public FilterArcs< |
| ... | ... |
@@ -2732,3 +2732,3 @@ |
| 2732 | 2732 |
typedef typename CapacityMap::Value Value; |
| 2733 |
typedef |
|
| 2733 |
typedef ResidualDigraph Adaptor; |
|
| 2734 | 2734 |
|
| ... | ... |
@@ -2763,4 +2763,4 @@ |
| 2763 | 2763 |
/// digraph, the capacity map, the flow map, and a tolerance object. |
| 2764 |
Residual(const Digraph& digraph, const CapacityMap& capacity, |
|
| 2765 |
FlowMap& flow, const Tolerance& tolerance = Tolerance()) |
|
| 2764 |
ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity, |
|
| 2765 |
FlowMap& flow, const Tolerance& tolerance = Tolerance()) |
|
| 2766 | 2766 |
: Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), |
| ... | ... |
@@ -2871,6 +2871,5 @@ |
| 2871 | 2871 |
template<typename GR, typename CM, typename FM> |
| 2872 |
Residual<GR, CM, FM> residual(const GR& digraph, |
|
| 2873 |
const CM& capacity_map, |
|
| 2874 |
FM& flow_map) {
|
|
| 2875 |
return Residual<GR, CM, FM> (digraph, capacity_map, flow_map); |
|
| 2872 |
ResidualDigraph<GR, CM, FM> |
|
| 2873 |
residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {
|
|
| 2874 |
return ResidualDigraph<GR, CM, FM> (digraph, capacity_map, flow_map); |
|
| 2876 | 2875 |
} |
| ... | ... |
@@ -8,2 +8,3 @@ |
| 8 | 8 |
check_PROGRAMS += \ |
| 9 |
test/adaptors_test \ |
|
| 9 | 10 |
test/bfs_test \ |
| ... | ... |
@@ -16,3 +17,2 @@ |
| 16 | 17 |
test/error_test \ |
| 17 |
test/graph_adaptor_test \ |
|
| 18 | 18 |
test/graph_copy_test \ |
| ... | ... |
@@ -45,2 +45,3 @@ |
| 45 | 45 |
|
| 46 |
test_adaptors_test_SOURCES = test/adaptors_test.cc |
|
| 46 | 47 |
test_bfs_test_SOURCES = test/bfs_test.cc |
| ... | ... |
@@ -53,3 +54,2 @@ |
| 53 | 54 |
test_error_test_SOURCES = test/error_test.cc |
| 54 |
test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc |
|
| 55 | 55 |
test_graph_copy_test_SOURCES = test/graph_copy_test.cc |
| ... | ... |
@@ -18,14 +18,7 @@ |
| 18 | 18 |
|
| 19 |
#include<iostream> |
|
| 20 |
#include<lemon/concept_check.h> |
|
| 19 |
#include <iostream> |
|
| 20 |
#include <limits> |
|
| 21 | 21 |
|
| 22 |
#include<lemon/list_graph.h> |
|
| 23 |
#include<lemon/smart_graph.h> |
|
| 24 |
|
|
| 25 |
#include<lemon/concepts/digraph.h> |
|
| 26 |
#include<lemon/concepts/graph.h> |
|
| 27 |
|
|
| 28 |
#include<lemon/adaptors.h> |
|
| 29 |
|
|
| 30 |
#include < |
|
| 22 |
#include <lemon/list_graph.h> |
|
| 23 |
#include <lemon/grid_graph.h> |
|
| 31 | 24 |
#include <lemon/bfs.h> |
| ... | ... |
@@ -33,4 +26,12 @@ |
| 33 | 26 |
|
| 34 |
#include"test/test_tools.h" |
|
| 35 |
#include"test/graph_test.h" |
|
| 27 |
#include <lemon/concepts/digraph.h> |
|
| 28 |
#include <lemon/concepts/graph.h> |
|
| 29 |
#include <lemon/concepts/graph_components.h> |
|
| 30 |
#include <lemon/concepts/maps.h> |
|
| 31 |
#include <lemon/concept_check.h> |
|
| 32 |
|
|
| 33 |
#include <lemon/adaptors.h> |
|
| 34 |
|
|
| 35 |
#include "test/test_tools.h" |
|
| 36 |
#include "test/graph_test.h" |
|
| 36 | 37 |
|
| ... | ... |
@@ -39,4 +40,15 @@ |
| 39 | 40 |
void checkReverseDigraph() {
|
| 41 |
// Check concepts |
|
| 40 | 42 |
checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); |
| 43 |
checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >(); |
|
| 44 |
checkConcept<concepts::AlterableDigraphComponent<>, |
|
| 45 |
ReverseDigraph<ListDigraph> >(); |
|
| 46 |
checkConcept<concepts::ExtendableDigraphComponent<>, |
|
| 47 |
ReverseDigraph<ListDigraph> >(); |
|
| 48 |
checkConcept<concepts::ErasableDigraphComponent<>, |
|
| 49 |
ReverseDigraph<ListDigraph> >(); |
|
| 50 |
checkConcept<concepts::ClearableDigraphComponent<>, |
|
| 51 |
ReverseDigraph<ListDigraph> >(); |
|
| 41 | 52 |
|
| 53 |
// Create a digraph and an adaptor |
|
| 42 | 54 |
typedef ListDigraph Digraph; |
| ... | ... |
@@ -47,2 +59,3 @@ |
| 47 | 59 |
|
| 60 |
// Add nodes and arcs to the original digraph |
|
| 48 | 61 |
Digraph::Node n1 = digraph.addNode(); |
| ... | ... |
@@ -55,2 +68,3 @@ |
| 55 | 68 |
|
| 69 |
// Check the adaptor |
|
| 56 | 70 |
checkGraphNodeList(adaptor, 3); |
| ... | ... |
@@ -73,2 +87,3 @@ |
| 73 | 87 |
|
| 88 |
// Check the orientation of the arcs |
|
| 74 | 89 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
| ... | ... |
@@ -77,2 +92,62 @@ |
| 77 | 92 |
} |
| 93 |
|
|
| 94 |
// Add and erase nodes and arcs in the digraph through the adaptor |
|
| 95 |
Adaptor::Node n4 = adaptor.addNode(); |
|
| 96 |
|
|
| 97 |
Adaptor::Arc a4 = adaptor.addArc(n4, n3); |
|
| 98 |
Adaptor::Arc a5 = adaptor.addArc(n2, n4); |
|
| 99 |
Adaptor::Arc a6 = adaptor.addArc(n2, n4); |
|
| 100 |
Adaptor::Arc a7 = adaptor.addArc(n1, n4); |
|
| 101 |
Adaptor::Arc a8 = adaptor.addArc(n1, n2); |
|
| 102 |
|
|
| 103 |
adaptor.erase(a1); |
|
| 104 |
adaptor.erase(n3); |
|
| 105 |
|
|
| 106 |
// Check the adaptor |
|
| 107 |
checkGraphNodeList(adaptor, 3); |
|
| 108 |
checkGraphArcList(adaptor, 4); |
|
| 109 |
checkGraphConArcList(adaptor, 4); |
|
| 110 |
|
|
| 111 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 112 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 113 |
checkGraphOutArcList(adaptor, n4, 0); |
|
| 114 |
|
|
| 115 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 116 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 117 |
checkGraphInArcList(adaptor, n4, 3); |
|
| 118 |
|
|
| 119 |
checkNodeIds(adaptor); |
|
| 120 |
checkArcIds(adaptor); |
|
| 121 |
|
|
| 122 |
checkGraphNodeMap(adaptor); |
|
| 123 |
checkGraphArcMap(adaptor); |
|
| 124 |
|
|
| 125 |
// Check the digraph |
|
| 126 |
checkGraphNodeList(digraph, 3); |
|
| 127 |
checkGraphArcList(digraph, 4); |
|
| 128 |
checkGraphConArcList(digraph, 4); |
|
| 129 |
|
|
| 130 |
checkGraphOutArcList(digraph, n1, 0); |
|
| 131 |
checkGraphOutArcList(digraph, n2, 1); |
|
| 132 |
checkGraphOutArcList(digraph, n4, 3); |
|
| 133 |
|
|
| 134 |
checkGraphInArcList(digraph, n1, 2); |
|
| 135 |
checkGraphInArcList(digraph, n2, 2); |
|
| 136 |
checkGraphInArcList(digraph, n4, 0); |
|
| 137 |
|
|
| 138 |
checkNodeIds(digraph); |
|
| 139 |
checkArcIds(digraph); |
|
| 140 |
|
|
| 141 |
checkGraphNodeMap(digraph); |
|
| 142 |
checkGraphArcMap(digraph); |
|
| 143 |
|
|
| 144 |
// Check the conversion of nodes and arcs |
|
| 145 |
Digraph::Node nd = n4; |
|
| 146 |
nd = n4; |
|
| 147 |
Adaptor::Node na = n1; |
|
| 148 |
na = n2; |
|
| 149 |
Digraph::Arc ad = a4; |
|
| 150 |
ad = a5; |
|
| 151 |
Adaptor::Arc aa = a1; |
|
| 152 |
aa = a2; |
|
| 78 | 153 |
} |
| ... | ... |
@@ -80,7 +155,15 @@ |
| 80 | 155 |
void checkSubDigraph() {
|
| 81 |
checkConcept<concepts::Digraph, |
|
| 82 |
SubDigraph<concepts::Digraph, |
|
| 83 |
concepts::Digraph::NodeMap<bool>, |
|
| 84 |
concepts::Digraph::ArcMap<bool> > >(); |
|
| 156 |
// Check concepts |
|
| 157 |
checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >(); |
|
| 158 |
checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >(); |
|
| 159 |
checkConcept<concepts::AlterableDigraphComponent<>, |
|
| 160 |
SubDigraph<ListDigraph> >(); |
|
| 161 |
checkConcept<concepts::ExtendableDigraphComponent<>, |
|
| 162 |
SubDigraph<ListDigraph> >(); |
|
| 163 |
checkConcept<concepts::ErasableDigraphComponent<>, |
|
| 164 |
SubDigraph<ListDigraph> >(); |
|
| 165 |
checkConcept<concepts::ClearableDigraphComponent<>, |
|
| 166 |
SubDigraph<ListDigraph> >(); |
|
| 85 | 167 |
|
| 168 |
// Create a digraph and an adaptor |
|
| 86 | 169 |
typedef ListDigraph Digraph; |
| ... | ... |
@@ -95,5 +178,8 @@ |
| 95 | 178 |
|
| 179 |
// Add nodes and arcs to the original digraph and the adaptor |
|
| 96 | 180 |
Digraph::Node n1 = digraph.addNode(); |
| 97 | 181 |
Digraph::Node n2 = digraph.addNode(); |
| 98 |
|
|
| 182 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 183 |
|
|
| 184 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
| 99 | 185 |
|
| ... | ... |
@@ -101,169 +187,3 @@ |
| 101 | 187 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
| 102 |
Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
| 103 |
|
|
| 104 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
| 105 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
|
| 106 |
|
|
| 107 |
checkGraphNodeList(adaptor, 3); |
|
| 108 |
checkGraphArcList(adaptor, 3); |
|
| 109 |
checkGraphConArcList(adaptor, 3); |
|
| 110 |
|
|
| 111 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 112 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 113 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 114 |
|
|
| 115 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 116 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 117 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 118 |
|
|
| 119 |
checkNodeIds(adaptor); |
|
| 120 |
checkArcIds(adaptor); |
|
| 121 |
|
|
| 122 |
checkGraphNodeMap(adaptor); |
|
| 123 |
checkGraphArcMap(adaptor); |
|
| 124 |
|
|
| 125 |
arc_filter[a2] = false; |
|
| 126 |
|
|
| 127 |
checkGraphNodeList(adaptor, 3); |
|
| 128 |
checkGraphArcList(adaptor, 2); |
|
| 129 |
checkGraphConArcList(adaptor, 2); |
|
| 130 |
|
|
| 131 |
checkGraphOutArcList(adaptor, n1, 1); |
|
| 132 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 133 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 134 |
|
|
| 135 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 136 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 137 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 138 |
|
|
| 139 |
checkNodeIds(adaptor); |
|
| 140 |
checkArcIds(adaptor); |
|
| 141 |
|
|
| 142 |
checkGraphNodeMap(adaptor); |
|
| 143 |
checkGraphArcMap(adaptor); |
|
| 144 |
|
|
| 145 |
node_filter[n1] = false; |
|
| 146 |
|
|
| 147 |
checkGraphNodeList(adaptor, 2); |
|
| 148 |
checkGraphArcList(adaptor, 1); |
|
| 149 |
checkGraphConArcList(adaptor, 1); |
|
| 150 |
|
|
| 151 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 152 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 153 |
|
|
| 154 |
checkGraphInArcList(adaptor, n2, 0); |
|
| 155 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 156 |
|
|
| 157 |
checkNodeIds(adaptor); |
|
| 158 |
checkArcIds(adaptor); |
|
| 159 |
|
|
| 160 |
checkGraphNodeMap(adaptor); |
|
| 161 |
checkGraphArcMap(adaptor); |
|
| 162 |
|
|
| 163 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
| 164 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; |
|
| 165 |
|
|
| 166 |
checkGraphNodeList(adaptor, 0); |
|
| 167 |
checkGraphArcList(adaptor, 0); |
|
| 168 |
checkGraphConArcList(adaptor, 0); |
|
| 169 |
|
|
| 170 |
checkNodeIds(adaptor); |
|
| 171 |
checkArcIds(adaptor); |
|
| 172 |
|
|
| 173 |
checkGraphNodeMap(adaptor); |
|
| 174 |
checkGraphArcMap(adaptor); |
|
| 175 |
} |
|
| 176 |
|
|
| 177 |
void checkFilterNodes1() {
|
|
| 178 |
checkConcept<concepts::Digraph, |
|
| 179 |
FilterNodes<concepts::Digraph, |
|
| 180 |
concepts::Digraph::NodeMap<bool> > >(); |
|
| 181 |
|
|
| 182 |
typedef ListDigraph Digraph; |
|
| 183 |
typedef Digraph::NodeMap<bool> NodeFilter; |
|
| 184 |
typedef FilterNodes<Digraph, NodeFilter> Adaptor; |
|
| 185 |
|
|
| 186 |
Digraph digraph; |
|
| 187 |
NodeFilter node_filter(digraph); |
|
| 188 |
Adaptor adaptor(digraph, node_filter); |
|
| 189 |
|
|
| 190 |
Digraph::Node n1 = digraph.addNode(); |
|
| 191 |
Digraph::Node n2 = digraph.addNode(); |
|
| 192 |
Digraph::Node n3 = digraph.addNode(); |
|
| 193 |
|
|
| 194 |
Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
| 195 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
| 196 |
Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
| 197 |
|
|
| 198 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
| 199 |
|
|
| 200 |
checkGraphNodeList(adaptor, 3); |
|
| 201 |
checkGraphArcList(adaptor, 3); |
|
| 202 |
checkGraphConArcList(adaptor, 3); |
|
| 203 |
|
|
| 204 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 205 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 206 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 207 |
|
|
| 208 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 209 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 210 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 211 |
|
|
| 212 |
checkNodeIds(adaptor); |
|
| 213 |
checkArcIds(adaptor); |
|
| 214 |
|
|
| 215 |
checkGraphNodeMap(adaptor); |
|
| 216 |
checkGraphArcMap(adaptor); |
|
| 217 |
|
|
| 218 |
node_filter[n1] = false; |
|
| 219 |
|
|
| 220 |
checkGraphNodeList(adaptor, 2); |
|
| 221 |
checkGraphArcList(adaptor, 1); |
|
| 222 |
checkGraphConArcList(adaptor, 1); |
|
| 223 |
|
|
| 224 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 225 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 226 |
|
|
| 227 |
checkGraphInArcList(adaptor, n2, 0); |
|
| 228 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 229 |
|
|
| 230 |
checkNodeIds(adaptor); |
|
| 231 |
checkArcIds(adaptor); |
|
| 232 |
|
|
| 233 |
checkGraphNodeMap(adaptor); |
|
| 234 |
checkGraphArcMap(adaptor); |
|
| 235 |
|
|
| 236 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
| 237 |
|
|
| 238 |
checkGraphNodeList(adaptor, 0); |
|
| 239 |
checkGraphArcList(adaptor, 0); |
|
| 240 |
checkGraphConArcList(adaptor, 0); |
|
| 241 |
|
|
| 242 |
checkNodeIds(adaptor); |
|
| 243 |
checkArcIds(adaptor); |
|
| 244 |
|
|
| 245 |
checkGraphNodeMap(adaptor); |
|
| 246 |
checkGraphArcMap(adaptor); |
|
| 247 |
} |
|
| 248 |
|
|
| 249 |
void checkFilterArcs() {
|
|
| 250 |
checkConcept<concepts::Digraph, |
|
| 251 |
FilterArcs<concepts::Digraph, |
|
| 252 |
concepts::Digraph::ArcMap<bool> > >(); |
|
| 253 |
|
|
| 254 |
typedef ListDigraph Digraph; |
|
| 255 |
typedef Digraph::ArcMap<bool> ArcFilter; |
|
| 256 |
typedef FilterArcs<Digraph, ArcFilter> Adaptor; |
|
| 257 |
|
|
| 258 |
Digraph digraph; |
|
| 259 |
ArcFilter arc_filter(digraph); |
|
| 260 |
Adaptor adaptor(digraph, arc_filter); |
|
| 261 |
|
|
| 262 |
Digraph::Node n1 = digraph.addNode(); |
|
| 263 |
Digraph::Node n2 = digraph.addNode(); |
|
| 264 |
Digraph::Node n3 = digraph.addNode(); |
|
| 265 |
|
|
| 266 |
Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
| 267 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
| 268 |
|
|
| 188 |
Adaptor::Arc a3 = adaptor.addArc(n2, n3); |
|
| 269 | 189 |
|
| ... | ... |
@@ -289,3 +209,6 @@ |
| 289 | 209 |
|
| 290 |
|
|
| 210 |
// Hide an arc |
|
| 211 |
adaptor.status(a2, false); |
|
| 212 |
adaptor.disable(a3); |
|
| 213 |
if (!adaptor.status(a3)) adaptor.enable(a3); |
|
| 291 | 214 |
|
| ... | ... |
@@ -309,2 +232,219 @@ |
| 309 | 232 |
|
| 233 |
// Hide a node |
|
| 234 |
adaptor.status(n1, false); |
|
| 235 |
adaptor.disable(n3); |
|
| 236 |
if (!adaptor.status(n3)) adaptor.enable(n3); |
|
| 237 |
|
|
| 238 |
checkGraphNodeList(adaptor, 2); |
|
| 239 |
checkGraphArcList(adaptor, 1); |
|
| 240 |
checkGraphConArcList(adaptor, 1); |
|
| 241 |
|
|
| 242 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 243 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 244 |
|
|
| 245 |
checkGraphInArcList(adaptor, n2, 0); |
|
| 246 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 247 |
|
|
| 248 |
checkNodeIds(adaptor); |
|
| 249 |
checkArcIds(adaptor); |
|
| 250 |
|
|
| 251 |
checkGraphNodeMap(adaptor); |
|
| 252 |
checkGraphArcMap(adaptor); |
|
| 253 |
|
|
| 254 |
// Hide all nodes and arcs |
|
| 255 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
| 256 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; |
|
| 257 |
|
|
| 258 |
checkGraphNodeList(adaptor, 0); |
|
| 259 |
checkGraphArcList(adaptor, 0); |
|
| 260 |
checkGraphConArcList(adaptor, 0); |
|
| 261 |
|
|
| 262 |
checkNodeIds(adaptor); |
|
| 263 |
checkArcIds(adaptor); |
|
| 264 |
|
|
| 265 |
checkGraphNodeMap(adaptor); |
|
| 266 |
checkGraphArcMap(adaptor); |
|
| 267 |
|
|
| 268 |
// Check the conversion of nodes and arcs |
|
| 269 |
Digraph::Node nd = n3; |
|
| 270 |
nd = n3; |
|
| 271 |
Adaptor::Node na = n1; |
|
| 272 |
na = n2; |
|
| 273 |
Digraph::Arc ad = a3; |
|
| 274 |
ad = a3; |
|
| 275 |
Adaptor::Arc aa = a1; |
|
| 276 |
aa = a2; |
|
| 277 |
} |
|
| 278 |
|
|
| 279 |
void checkFilterNodes1() {
|
|
| 280 |
// Check concepts |
|
| 281 |
checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >(); |
|
| 282 |
checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >(); |
|
| 283 |
checkConcept<concepts::AlterableDigraphComponent<>, |
|
| 284 |
FilterNodes<ListDigraph> >(); |
|
| 285 |
checkConcept<concepts::ExtendableDigraphComponent<>, |
|
| 286 |
FilterNodes<ListDigraph> >(); |
|
| 287 |
checkConcept<concepts::ErasableDigraphComponent<>, |
|
| 288 |
FilterNodes<ListDigraph> >(); |
|
| 289 |
checkConcept<concepts::ClearableDigraphComponent<>, |
|
| 290 |
FilterNodes<ListDigraph> >(); |
|
| 291 |
|
|
| 292 |
// Create a digraph and an adaptor |
|
| 293 |
typedef ListDigraph Digraph; |
|
| 294 |
typedef Digraph::NodeMap<bool> NodeFilter; |
|
| 295 |
typedef FilterNodes<Digraph, NodeFilter> Adaptor; |
|
| 296 |
|
|
| 297 |
Digraph digraph; |
|
| 298 |
NodeFilter node_filter(digraph); |
|
| 299 |
Adaptor adaptor(digraph, node_filter); |
|
| 300 |
|
|
| 301 |
// Add nodes and arcs to the original digraph and the adaptor |
|
| 302 |
Digraph::Node n1 = digraph.addNode(); |
|
| 303 |
Digraph::Node n2 = digraph.addNode(); |
|
| 304 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 305 |
|
|
| 306 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
| 307 |
|
|
| 308 |
Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
| 309 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
| 310 |
Adaptor::Arc a3 = adaptor.addArc(n2, n3); |
|
| 311 |
|
|
| 312 |
checkGraphNodeList(adaptor, 3); |
|
| 313 |
checkGraphArcList(adaptor, 3); |
|
| 314 |
checkGraphConArcList(adaptor, 3); |
|
| 315 |
|
|
| 316 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 317 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 318 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 319 |
|
|
| 320 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 321 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 322 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 323 |
|
|
| 324 |
checkNodeIds(adaptor); |
|
| 325 |
checkArcIds(adaptor); |
|
| 326 |
|
|
| 327 |
checkGraphNodeMap(adaptor); |
|
| 328 |
checkGraphArcMap(adaptor); |
|
| 329 |
|
|
| 330 |
// Hide a node |
|
| 331 |
adaptor.status(n1, false); |
|
| 332 |
adaptor.disable(n3); |
|
| 333 |
if (!adaptor.status(n3)) adaptor.enable(n3); |
|
| 334 |
|
|
| 335 |
checkGraphNodeList(adaptor, 2); |
|
| 336 |
checkGraphArcList(adaptor, 1); |
|
| 337 |
checkGraphConArcList(adaptor, 1); |
|
| 338 |
|
|
| 339 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 340 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 341 |
|
|
| 342 |
checkGraphInArcList(adaptor, n2, 0); |
|
| 343 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 344 |
|
|
| 345 |
checkNodeIds(adaptor); |
|
| 346 |
checkArcIds(adaptor); |
|
| 347 |
|
|
| 348 |
checkGraphNodeMap(adaptor); |
|
| 349 |
checkGraphArcMap(adaptor); |
|
| 350 |
|
|
| 351 |
// Hide all nodes |
|
| 352 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
| 353 |
|
|
| 354 |
checkGraphNodeList(adaptor, 0); |
|
| 355 |
checkGraphArcList(adaptor, 0); |
|
| 356 |
checkGraphConArcList(adaptor, 0); |
|
| 357 |
|
|
| 358 |
checkNodeIds(adaptor); |
|
| 359 |
checkArcIds(adaptor); |
|
| 360 |
|
|
| 361 |
checkGraphNodeMap(adaptor); |
|
| 362 |
checkGraphArcMap(adaptor); |
|
| 363 |
|
|
| 364 |
// Check the conversion of nodes and arcs |
|
| 365 |
Digraph::Node nd = n3; |
|
| 366 |
nd = n3; |
|
| 367 |
Adaptor::Node na = n1; |
|
| 368 |
na = n2; |
|
| 369 |
Digraph::Arc ad = a3; |
|
| 370 |
ad = a3; |
|
| 371 |
Adaptor::Arc aa = a1; |
|
| 372 |
aa = a2; |
|
| 373 |
} |
|
| 374 |
|
|
| 375 |
void checkFilterArcs() {
|
|
| 376 |
// Check concepts |
|
| 377 |
checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >(); |
|
| 378 |
checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >(); |
|
| 379 |
checkConcept<concepts::AlterableDigraphComponent<>, |
|
| 380 |
FilterArcs<ListDigraph> >(); |
|
| 381 |
checkConcept<concepts::ExtendableDigraphComponent<>, |
|
| 382 |
FilterArcs<ListDigraph> >(); |
|
| 383 |
checkConcept<concepts::ErasableDigraphComponent<>, |
|
| 384 |
FilterArcs<ListDigraph> >(); |
|
| 385 |
checkConcept<concepts::ClearableDigraphComponent<>, |
|
| 386 |
FilterArcs<ListDigraph> >(); |
|
| 387 |
|
|
| 388 |
// Create a digraph and an adaptor |
|
| 389 |
typedef ListDigraph Digraph; |
|
| 390 |
typedef Digraph::ArcMap<bool> ArcFilter; |
|
| 391 |
typedef FilterArcs<Digraph, ArcFilter> Adaptor; |
|
| 392 |
|
|
| 393 |
Digraph digraph; |
|
| 394 |
ArcFilter arc_filter(digraph); |
|
| 395 |
Adaptor adaptor(digraph, arc_filter); |
|
| 396 |
|
|
| 397 |
// Add nodes and arcs to the original digraph and the adaptor |
|
| 398 |
Digraph::Node n1 = digraph.addNode(); |
|
| 399 |
Digraph::Node n2 = digraph.addNode(); |
|
| 400 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 401 |
|
|
| 402 |
Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
| 403 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
| 404 |
Adaptor::Arc a3 = adaptor.addArc(n2, n3); |
|
| 405 |
|
|
| 406 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
|
| 407 |
|
|
| 408 |
checkGraphNodeList(adaptor, 3); |
|
| 409 |
checkGraphArcList(adaptor, 3); |
|
| 410 |
checkGraphConArcList(adaptor, 3); |
|
| 411 |
|
|
| 412 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 413 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 414 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 415 |
|
|
| 416 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 417 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 418 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 419 |
|
|
| 420 |
checkNodeIds(adaptor); |
|
| 421 |
checkArcIds(adaptor); |
|
| 422 |
|
|
| 423 |
checkGraphNodeMap(adaptor); |
|
| 424 |
checkGraphArcMap(adaptor); |
|
| 425 |
|
|
| 426 |
// Hide an arc |
|
| 427 |
adaptor.status(a2, false); |
|
| 428 |
adaptor.disable(a3); |
|
| 429 |
if (!adaptor.status(a3)) adaptor.enable(a3); |
|
| 430 |
|
|
| 431 |
checkGraphNodeList(adaptor, 3); |
|
| 432 |
checkGraphArcList(adaptor, 2); |
|
| 433 |
checkGraphConArcList(adaptor, 2); |
|
| 434 |
|
|
| 435 |
checkGraphOutArcList(adaptor, n1, 1); |
|
| 436 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 437 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 438 |
|
|
| 439 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 440 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 441 |
checkGraphInArcList(adaptor, n3, 1); |
|
| 442 |
|
|
| 443 |
checkNodeIds(adaptor); |
|
| 444 |
checkArcIds(adaptor); |
|
| 445 |
|
|
| 446 |
checkGraphNodeMap(adaptor); |
|
| 447 |
checkGraphArcMap(adaptor); |
|
| 448 |
|
|
| 449 |
// Hide all arcs |
|
| 310 | 450 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; |
| ... | ... |
@@ -320,2 +460,12 @@ |
| 320 | 460 |
checkGraphArcMap(adaptor); |
| 461 |
|
|
| 462 |
// Check the conversion of nodes and arcs |
|
| 463 |
Digraph::Node nd = n3; |
|
| 464 |
nd = n3; |
|
| 465 |
Adaptor::Node na = n1; |
|
| 466 |
na = n2; |
|
| 467 |
Digraph::Arc ad = a3; |
|
| 468 |
ad = a3; |
|
| 469 |
Adaptor::Arc aa = a1; |
|
| 470 |
aa = a2; |
|
| 321 | 471 |
} |
| ... | ... |
@@ -323,4 +473,16 @@ |
| 323 | 473 |
void checkUndirector() {
|
| 474 |
// Check concepts |
|
| 324 | 475 |
checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); |
| 476 |
checkConcept<concepts::Graph, Undirector<ListDigraph> >(); |
|
| 477 |
checkConcept<concepts::AlterableGraphComponent<>, |
|
| 478 |
Undirector<ListDigraph> >(); |
|
| 479 |
checkConcept<concepts::ExtendableGraphComponent<>, |
|
| 480 |
Undirector<ListDigraph> >(); |
|
| 481 |
checkConcept<concepts::ErasableGraphComponent<>, |
|
| 482 |
Undirector<ListDigraph> >(); |
|
| 483 |
checkConcept<concepts::ClearableGraphComponent<>, |
|
| 484 |
Undirector<ListDigraph> >(); |
|
| 325 | 485 |
|
| 486 |
|
|
| 487 |
// Create a digraph and an adaptor |
|
| 326 | 488 |
typedef ListDigraph Digraph; |
| ... | ... |
@@ -331,5 +493,6 @@ |
| 331 | 493 |
|
| 494 |
// Add nodes and arcs/edges to the original digraph and the adaptor |
|
| 332 | 495 |
Digraph::Node n1 = digraph.addNode(); |
| 333 | 496 |
Digraph::Node n2 = digraph.addNode(); |
| 334 |
|
|
| 497 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 335 | 498 |
|
| ... | ... |
@@ -337,4 +500,24 @@ |
| 337 | 500 |
Digraph::Arc a2 = digraph.addArc(n1, n3); |
| 338 |
|
|
| 501 |
Adaptor::Edge e3 = adaptor.addEdge(n2, n3); |
|
| 339 | 502 |
|
| 503 |
// Check the original digraph |
|
| 504 |
checkGraphNodeList(digraph, 3); |
|
| 505 |
checkGraphArcList(digraph, 3); |
|
| 506 |
checkGraphConArcList(digraph, 3); |
|
| 507 |
|
|
| 508 |
checkGraphOutArcList(digraph, n1, 2); |
|
| 509 |
checkGraphOutArcList(digraph, n2, 1); |
|
| 510 |
checkGraphOutArcList(digraph, n3, 0); |
|
| 511 |
|
|
| 512 |
checkGraphInArcList(digraph, n1, 0); |
|
| 513 |
checkGraphInArcList(digraph, n2, 1); |
|
| 514 |
checkGraphInArcList(digraph, n3, 2); |
|
| 515 |
|
|
| 516 |
checkNodeIds(digraph); |
|
| 517 |
checkArcIds(digraph); |
|
| 518 |
|
|
| 519 |
checkGraphNodeMap(digraph); |
|
| 520 |
checkGraphArcMap(digraph); |
|
| 521 |
|
|
| 522 |
// Check the adaptor |
|
| 340 | 523 |
checkGraphNodeList(adaptor, 3); |
| ... | ... |
@@ -345,13 +528,5 @@ |
| 345 | 528 |
|
| 346 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 347 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 348 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 349 |
|
|
| 350 |
checkGraphInArcList(adaptor, n1, 2); |
|
| 351 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 352 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 353 |
|
|
| 354 |
checkGraphIncEdgeList(adaptor, n1, 2); |
|
| 355 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 356 |
|
|
| 529 |
checkGraphIncEdgeArcLists(adaptor, n1, 2); |
|
| 530 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 531 |
checkGraphIncEdgeArcLists(adaptor, n3, 2); |
|
| 357 | 532 |
|
| ... | ... |
@@ -365,2 +540,3 @@ |
| 365 | 540 |
|
| 541 |
// Check the edges of the adaptor |
|
| 366 | 542 |
for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
|
| ... | ... |
@@ -370,13 +546,48 @@ |
| 370 | 546 |
|
| 547 |
// Check CombinedArcMap |
|
| 548 |
typedef Adaptor::CombinedArcMap |
|
| 549 |
<Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap; |
|
| 550 |
typedef Adaptor::CombinedArcMap |
|
| 551 |
<Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap; |
|
| 552 |
checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>, |
|
| 553 |
IntCombinedMap>(); |
|
| 554 |
checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>, |
|
| 555 |
BoolCombinedMap>(); |
|
| 556 |
|
|
| 557 |
Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph); |
|
| 558 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 559 |
fw_map[a] = digraph.id(a); |
|
| 560 |
bk_map[a] = -digraph.id(a); |
|
| 561 |
} |
|
| 562 |
|
|
| 563 |
Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> > |
|
| 564 |
comb_map(fw_map, bk_map); |
|
| 565 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
|
| 566 |
if (adaptor.source(a) == digraph.source(a)) {
|
|
| 567 |
check(comb_map[a] == fw_map[a], "Wrong combined map"); |
|
| 568 |
} else {
|
|
| 569 |
check(comb_map[a] == bk_map[a], "Wrong combined map"); |
|
| 570 |
} |
|
| 571 |
} |
|
| 572 |
|
|
| 573 |
// Check the conversion of nodes and arcs/edges |
|
| 574 |
Digraph::Node nd = n3; |
|
| 575 |
nd = n3; |
|
| 576 |
Adaptor::Node na = n1; |
|
| 577 |
na = n2; |
|
| 578 |
Digraph::Arc ad = e3; |
|
| 579 |
ad = e3; |
|
| 580 |
Adaptor::Edge ea = a1; |
|
| 581 |
ea = a2; |
|
| 371 | 582 |
} |
| 372 | 583 |
|
| 373 |
void checkResidual() {
|
|
| 374 |
checkConcept<concepts::Digraph, |
|
| 375 |
Residual<concepts::Digraph, |
|
| 376 |
concepts::Digraph::ArcMap<int>, |
|
| 377 |
|
|
| 584 |
void checkResidualDigraph() {
|
|
| 585 |
// Check concepts |
|
| 586 |
checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >(); |
|
| 587 |
checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >(); |
|
| 378 | 588 |
|
| 589 |
// Create a digraph and an adaptor |
|
| 379 | 590 |
typedef ListDigraph Digraph; |
| 380 | 591 |
typedef Digraph::ArcMap<int> IntArcMap; |
| 381 |
typedef |
|
| 592 |
typedef ResidualDigraph<Digraph, IntArcMap> Adaptor; |
|
| 382 | 593 |
|
| ... | ... |
@@ -405,3 +616,4 @@ |
| 405 | 616 |
|
| 406 |
|
|
| 617 |
// Check the adaptor with various flow values |
|
| 618 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 407 | 619 |
flow[a] = 0; |
| ... | ... |
@@ -423,3 +635,3 @@ |
| 423 | 635 |
|
| 424 |
for ( |
|
| 636 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 425 | 637 |
flow[a] = capacity[a] / 2; |
| ... | ... |
@@ -447,3 +659,3 @@ |
| 447 | 659 |
|
| 448 |
for ( |
|
| 660 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 449 | 661 |
flow[a] = capacity[a]; |
| ... | ... |
@@ -465,7 +677,26 @@ |
| 465 | 677 |
|
| 678 |
// Saturate all backward arcs |
|
| 679 |
// (set the flow to zero on all forward arcs) |
|
| 466 | 680 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
| 467 |
|
|
| 681 |
if (adaptor.backward(a)) |
|
| 682 |
adaptor.augment(a, adaptor.residualCapacity(a)); |
|
| 468 | 683 |
} |
| 469 | 684 |
|
| 685 |
checkGraphNodeList(adaptor, 4); |
|
| 686 |
checkGraphArcList(adaptor, 6); |
|
| 687 |
checkGraphConArcList(adaptor, 6); |
|
| 688 |
|
|
| 689 |
checkGraphOutArcList(adaptor, n1, 3); |
|
| 690 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 691 |
checkGraphOutArcList(adaptor, n3, 1); |
|
| 692 |
checkGraphOutArcList(adaptor, n4, 0); |
|
| 693 |
|
|
| 694 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 695 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 696 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 697 |
checkGraphInArcList(adaptor, n4, 3); |
|
| 698 |
|
|
| 699 |
// Find maximum flow by augmenting along shortest paths |
|
| 470 | 700 |
int flow_value = 0; |
| 701 |
Adaptor::ResidualCapacity res_cap(adaptor); |
|
| 471 | 702 |
while (true) {
|
| ... | ... |
@@ -481,4 +712,3 @@ |
| 481 | 712 |
for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
|
| 482 |
if (adaptor.residualCapacity(a) < min) |
|
| 483 |
min = adaptor.residualCapacity(a); |
|
| 713 |
if (res_cap[a] < min) min = res_cap[a]; |
|
| 484 | 714 |
} |
| ... | ... |
@@ -493,2 +723,18 @@ |
| 493 | 723 |
|
| 724 |
// Check forward() and backward() |
|
| 725 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
|
| 726 |
check(adaptor.forward(a) != adaptor.backward(a), |
|
| 727 |
"Wrong forward() or backward()"); |
|
| 728 |
check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) || |
|
| 729 |
(adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a), |
|
| 730 |
"Wrong forward() or backward()"); |
|
| 731 |
} |
|
| 732 |
|
|
| 733 |
// Check the conversion of nodes and arcs |
|
| 734 |
Digraph::Node nd = Adaptor::NodeIt(adaptor); |
|
| 735 |
nd = ++Adaptor::NodeIt(adaptor); |
|
| 736 |
Adaptor::Node na = n1; |
|
| 737 |
na = n2; |
|
| 738 |
Digraph::Arc ad = Adaptor::ArcIt(adaptor); |
|
| 739 |
ad = ++Adaptor::ArcIt(adaptor); |
|
| 494 | 740 |
} |
| ... | ... |
@@ -496,4 +742,7 @@ |
| 496 | 742 |
void checkSplitNodes() {
|
| 743 |
// Check concepts |
|
| 497 | 744 |
checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); |
| 745 |
checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >(); |
|
| 498 | 746 |
|
| 747 |
// Create a digraph and an adaptor |
|
| 499 | 748 |
typedef ListDigraph Digraph; |
| ... | ... |
@@ -536,2 +785,3 @@ |
| 536 | 785 |
|
| 786 |
// Check split |
|
| 537 | 787 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
| ... | ... |
@@ -549,2 +799,62 @@ |
| 549 | 799 |
} |
| 800 |
|
|
| 801 |
// Check combined node map |
|
| 802 |
typedef Adaptor::CombinedNodeMap |
|
| 803 |
<Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap; |
|
| 804 |
typedef Adaptor::CombinedNodeMap |
|
| 805 |
<Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap; |
|
| 806 |
checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>, |
|
| 807 |
IntCombinedNodeMap>(); |
|
| 808 |
//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>, |
|
| 809 |
// BoolCombinedNodeMap>(); |
|
| 810 |
checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>, |
|
| 811 |
BoolCombinedNodeMap>(); |
|
| 812 |
|
|
| 813 |
Digraph::NodeMap<int> in_map(digraph), out_map(digraph); |
|
| 814 |
for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
|
|
| 815 |
in_map[n] = digraph.id(n); |
|
| 816 |
out_map[n] = -digraph.id(n); |
|
| 817 |
} |
|
| 818 |
|
|
| 819 |
Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> > |
|
| 820 |
node_map(in_map, out_map); |
|
| 821 |
for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
|
|
| 822 |
if (adaptor.inNode(n)) {
|
|
| 823 |
check(node_map[n] == in_map[n], "Wrong combined node map"); |
|
| 824 |
} else {
|
|
| 825 |
check(node_map[n] == out_map[n], "Wrong combined node map"); |
|
| 826 |
} |
|
| 827 |
} |
|
| 828 |
|
|
| 829 |
// Check combined arc map |
|
| 830 |
typedef Adaptor::CombinedArcMap |
|
| 831 |
<Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap; |
|
| 832 |
typedef Adaptor::CombinedArcMap |
|
| 833 |
<Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap; |
|
| 834 |
checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>, |
|
| 835 |
IntCombinedArcMap>(); |
|
| 836 |
//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>, |
|
| 837 |
// BoolCombinedArcMap>(); |
|
| 838 |
checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>, |
|
| 839 |
BoolCombinedArcMap>(); |
|
| 840 |
|
|
| 841 |
Digraph::ArcMap<int> a_map(digraph); |
|
| 842 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 843 |
a_map[a] = digraph.id(a); |
|
| 844 |
} |
|
| 845 |
|
|
| 846 |
Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> > |
|
| 847 |
arc_map(a_map, out_map); |
|
| 848 |
for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
|
|
| 849 |
check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map"); |
|
| 850 |
} |
|
| 851 |
for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
|
|
| 852 |
check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map"); |
|
| 853 |
} |
|
| 854 |
|
|
| 855 |
// Check the conversion of nodes |
|
| 856 |
Digraph::Node nd = adaptor.inNode(n1); |
|
| 857 |
check (nd == n1, "Wrong node conversion"); |
|
| 858 |
nd = adaptor.outNode(n2); |
|
| 859 |
check (nd == n2, "Wrong node conversion"); |
|
| 550 | 860 |
} |
| ... | ... |
@@ -552,7 +862,15 @@ |
| 552 | 862 |
void checkSubGraph() {
|
| 553 |
checkConcept<concepts::Graph, |
|
| 554 |
SubGraph<concepts::Graph, |
|
| 555 |
concepts::Graph::NodeMap<bool>, |
|
| 556 |
concepts::Graph::EdgeMap<bool> > >(); |
|
| 863 |
// Check concepts |
|
| 864 |
checkConcept<concepts::Graph, SubGraph<concepts::Graph> >(); |
|
| 865 |
checkConcept<concepts::Graph, SubGraph<ListGraph> >(); |
|
| 866 |
checkConcept<concepts::AlterableGraphComponent<>, |
|
| 867 |
SubGraph<ListGraph> >(); |
|
| 868 |
checkConcept<concepts::ExtendableGraphComponent<>, |
|
| 869 |
SubGraph<ListGraph> >(); |
|
| 870 |
checkConcept<concepts::ErasableGraphComponent<>, |
|
| 871 |
SubGraph<ListGraph> >(); |
|
| 872 |
checkConcept<concepts::ClearableGraphComponent<>, |
|
| 873 |
SubGraph<ListGraph> >(); |
|
| 557 | 874 |
|
| 875 |
// Create a graph and an adaptor |
|
| 558 | 876 |
typedef ListGraph Graph; |
| ... | ... |
@@ -567,6 +885,9 @@ |
| 567 | 885 |
|
| 886 |
// Add nodes and edges to the original graph and the adaptor |
|
| 568 | 887 |
Graph::Node n1 = graph.addNode(); |
| 569 | 888 |
Graph::Node n2 = graph.addNode(); |
| 570 |
Graph::Node n3 = graph.addNode(); |
|
| 571 |
Graph::Node n4 = graph.addNode(); |
|
| 889 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 890 |
Adaptor::Node n4 = adaptor.addNode(); |
|
| 891 |
|
|
| 892 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
| 572 | 893 |
|
| ... | ... |
@@ -574,6 +895,5 @@ |
| 574 | 895 |
Graph::Edge e2 = graph.addEdge(n1, n3); |
| 575 |
Graph::Edge e3 = graph.addEdge(n2, n3); |
|
| 576 |
Graph::Edge e4 = graph.addEdge(n3, n4); |
|
| 896 |
Adaptor::Edge e3 = adaptor.addEdge(n2, n3); |
|
| 897 |
Adaptor::Edge e4 = adaptor.addEdge(n3, n4); |
|
| 577 | 898 |
|
| 578 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
| 579 | 899 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; |
| ... | ... |
@@ -586,16 +906,6 @@ |
| 586 | 906 |
|
| 587 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 588 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 589 |
checkGraphOutArcList(adaptor, n3, 3); |
|
| 590 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 591 |
|
|
| 592 |
checkGraphInArcList(adaptor, n1, 2); |
|
| 593 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 594 |
checkGraphInArcList(adaptor, n3, 3); |
|
| 595 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 596 |
|
|
| 597 |
checkGraphIncEdgeList(adaptor, n1, 2); |
|
| 598 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 599 |
checkGraphIncEdgeList(adaptor, n3, 3); |
|
| 600 |
checkGraphIncEdgeList(adaptor, n4, 1); |
|
| 907 |
checkGraphIncEdgeArcLists(adaptor, n1, 2); |
|
| 908 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 909 |
checkGraphIncEdgeArcLists(adaptor, n3, 3); |
|
| 910 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 601 | 911 |
|
| ... | ... |
@@ -609,3 +919,6 @@ |
| 609 | 919 |
|
| 610 |
|
|
| 920 |
// Hide an edge |
|
| 921 |
adaptor.status(e2, false); |
|
| 922 |
adaptor.disable(e3); |
|
| 923 |
if (!adaptor.status(e3)) adaptor.enable(e3); |
|
| 611 | 924 |
|
| ... | ... |
@@ -617,16 +930,6 @@ |
| 617 | 930 |
|
| 618 |
checkGraphOutArcList(adaptor, n1, 1); |
|
| 619 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 620 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 621 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 622 |
|
|
| 623 |
checkGraphInArcList(adaptor, n1, 1); |
|
| 624 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 625 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 626 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 627 |
|
|
| 628 |
checkGraphIncEdgeList(adaptor, n1, 1); |
|
| 629 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 630 |
checkGraphIncEdgeList(adaptor, n3, 2); |
|
| 631 |
checkGraphIncEdgeList(adaptor, n4, 1); |
|
| 931 |
checkGraphIncEdgeArcLists(adaptor, n1, 1); |
|
| 932 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 933 |
checkGraphIncEdgeArcLists(adaptor, n3, 2); |
|
| 934 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 632 | 935 |
|
| ... | ... |
@@ -640,3 +943,6 @@ |
| 640 | 943 |
|
| 641 |
|
|
| 944 |
// Hide a node |
|
| 945 |
adaptor.status(n1, false); |
|
| 946 |
adaptor.disable(n3); |
|
| 947 |
if (!adaptor.status(n3)) adaptor.enable(n3); |
|
| 642 | 948 |
|
| ... | ... |
@@ -648,13 +954,5 @@ |
| 648 | 954 |
|
| 649 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 650 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 651 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 652 |
|
|
| 653 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 654 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 655 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 656 |
|
|
| 657 |
checkGraphIncEdgeList(adaptor, n2, 1); |
|
| 658 |
checkGraphIncEdgeList(adaptor, n3, 2); |
|
| 659 |
|
|
| 955 |
checkGraphIncEdgeArcLists(adaptor, n2, 1); |
|
| 956 |
checkGraphIncEdgeArcLists(adaptor, n3, 2); |
|
| 957 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 660 | 958 |
|
| ... | ... |
@@ -668,2 +966,3 @@ |
| 668 | 966 |
|
| 967 |
// Hide all nodes and edges |
|
| 669 | 968 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; |
| ... | ... |
@@ -684,2 +983,12 @@ |
| 684 | 983 |
checkGraphEdgeMap(adaptor); |
| 984 |
|
|
| 985 |
// Check the conversion of nodes and edges |
|
| 986 |
Graph::Node ng = n3; |
|
| 987 |
ng = n4; |
|
| 988 |
Adaptor::Node na = n1; |
|
| 989 |
na = n2; |
|
| 990 |
Graph::Edge eg = e3; |
|
| 991 |
eg = e4; |
|
| 992 |
Adaptor::Edge ea = e1; |
|
| 993 |
ea = e2; |
|
| 685 | 994 |
} |
| ... | ... |
@@ -687,6 +996,15 @@ |
| 687 | 996 |
void checkFilterNodes2() {
|
| 688 |
checkConcept<concepts::Graph, |
|
| 689 |
FilterNodes<concepts::Graph, |
|
| 690 |
|
|
| 997 |
// Check concepts |
|
| 998 |
checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >(); |
|
| 999 |
checkConcept<concepts::Graph, FilterNodes<ListGraph> >(); |
|
| 1000 |
checkConcept<concepts::AlterableGraphComponent<>, |
|
| 1001 |
FilterNodes<ListGraph> >(); |
|
| 1002 |
checkConcept<concepts::ExtendableGraphComponent<>, |
|
| 1003 |
FilterNodes<ListGraph> >(); |
|
| 1004 |
checkConcept<concepts::ErasableGraphComponent<>, |
|
| 1005 |
FilterNodes<ListGraph> >(); |
|
| 1006 |
checkConcept<concepts::ClearableGraphComponent<>, |
|
| 1007 |
FilterNodes<ListGraph> >(); |
|
| 691 | 1008 |
|
| 1009 |
// Create a graph and an adaptor |
|
| 692 | 1010 |
typedef ListGraph Graph; |
| ... | ... |
@@ -695,2 +1013,3 @@ |
| 695 | 1013 |
|
| 1014 |
// Add nodes and edges to the original graph and the adaptor |
|
| 696 | 1015 |
Graph graph; |
| ... | ... |
@@ -701,4 +1020,6 @@ |
| 701 | 1020 |
Graph::Node n2 = graph.addNode(); |
| 702 |
Graph::Node n3 = graph.addNode(); |
|
| 703 |
Graph::Node n4 = graph.addNode(); |
|
| 1021 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 1022 |
Adaptor::Node n4 = adaptor.addNode(); |
|
| 1023 |
|
|
| 1024 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
| 704 | 1025 |
|
| ... | ... |
@@ -706,6 +1027,4 @@ |
| 706 | 1027 |
Graph::Edge e2 = graph.addEdge(n1, n3); |
| 707 |
Graph::Edge e3 = graph.addEdge(n2, n3); |
|
| 708 |
Graph::Edge e4 = graph.addEdge(n3, n4); |
|
| 709 |
|
|
| 710 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
| 1028 |
Adaptor::Edge e3 = adaptor.addEdge(n2, n3); |
|
| 1029 |
Adaptor::Edge e4 = adaptor.addEdge(n3, n4); |
|
| 711 | 1030 |
|
| ... | ... |
@@ -717,16 +1036,6 @@ |
| 717 | 1036 |
|
| 718 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 719 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 720 |
checkGraphOutArcList(adaptor, n3, 3); |
|
| 721 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 722 |
|
|
| 723 |
checkGraphInArcList(adaptor, n1, 2); |
|
| 724 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 725 |
checkGraphInArcList(adaptor, n3, 3); |
|
| 726 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 727 |
|
|
| 728 |
checkGraphIncEdgeList(adaptor, n1, 2); |
|
| 729 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 730 |
checkGraphIncEdgeList(adaptor, n3, 3); |
|
| 731 |
checkGraphIncEdgeList(adaptor, n4, 1); |
|
| 1037 |
checkGraphIncEdgeArcLists(adaptor, n1, 2); |
|
| 1038 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 1039 |
checkGraphIncEdgeArcLists(adaptor, n3, 3); |
|
| 1040 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 732 | 1041 |
|
| ... | ... |
@@ -740,3 +1049,6 @@ |
| 740 | 1049 |
|
| 741 |
|
|
| 1050 |
// Hide a node |
|
| 1051 |
adaptor.status(n1, false); |
|
| 1052 |
adaptor.disable(n3); |
|
| 1053 |
if (!adaptor.status(n3)) adaptor.enable(n3); |
|
| 742 | 1054 |
|
| ... | ... |
@@ -748,13 +1060,5 @@ |
| 748 | 1060 |
|
| 749 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 750 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 751 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 752 |
|
|
| 753 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 754 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 755 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 756 |
|
|
| 757 |
checkGraphIncEdgeList(adaptor, n2, 1); |
|
| 758 |
checkGraphIncEdgeList(adaptor, n3, 2); |
|
| 759 |
|
|
| 1061 |
checkGraphIncEdgeArcLists(adaptor, n2, 1); |
|
| 1062 |
checkGraphIncEdgeArcLists(adaptor, n3, 2); |
|
| 1063 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 760 | 1064 |
|
| ... | ... |
@@ -768,2 +1072,3 @@ |
| 768 | 1072 |
|
| 1073 |
// Hide all nodes |
|
| 769 | 1074 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; |
| ... | ... |
@@ -783,2 +1088,12 @@ |
| 783 | 1088 |
checkGraphEdgeMap(adaptor); |
| 1089 |
|
|
| 1090 |
// Check the conversion of nodes and edges |
|
| 1091 |
Graph::Node ng = n3; |
|
| 1092 |
ng = n4; |
|
| 1093 |
Adaptor::Node na = n1; |
|
| 1094 |
na = n2; |
|
| 1095 |
Graph::Edge eg = e3; |
|
| 1096 |
eg = e4; |
|
| 1097 |
Adaptor::Edge ea = e1; |
|
| 1098 |
ea = e2; |
|
| 784 | 1099 |
} |
| ... | ... |
@@ -786,6 +1101,15 @@ |
| 786 | 1101 |
void checkFilterEdges() {
|
| 787 |
checkConcept<concepts::Graph, |
|
| 788 |
FilterEdges<concepts::Graph, |
|
| 789 |
concepts |
|
| 1102 |
// Check concepts |
|
| 1103 |
checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >(); |
|
| 1104 |
checkConcept<concepts::Graph, FilterEdges<ListGraph> >(); |
|
| 1105 |
checkConcept<concepts::AlterableGraphComponent<>, |
|
| 1106 |
FilterEdges<ListGraph> >(); |
|
| 1107 |
checkConcept<concepts::ExtendableGraphComponent<>, |
|
| 1108 |
FilterEdges<ListGraph> >(); |
|
| 1109 |
checkConcept<concepts::ErasableGraphComponent<>, |
|
| 1110 |
FilterEdges<ListGraph> >(); |
|
| 1111 |
checkConcept<concepts::ClearableGraphComponent<>, |
|
| 1112 |
FilterEdges<ListGraph> >(); |
|
| 790 | 1113 |
|
| 1114 |
// Create a graph and an adaptor |
|
| 791 | 1115 |
typedef ListGraph Graph; |
| ... | ... |
@@ -798,6 +1122,7 @@ |
| 798 | 1122 |
|
| 1123 |
// Add nodes and edges to the original graph and the adaptor |
|
| 799 | 1124 |
Graph::Node n1 = graph.addNode(); |
| 800 | 1125 |
Graph::Node n2 = graph.addNode(); |
| 801 |
Graph::Node n3 = graph.addNode(); |
|
| 802 |
Graph::Node n4 = graph.addNode(); |
|
| 1126 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 1127 |
Adaptor::Node n4 = adaptor.addNode(); |
|
| 803 | 1128 |
|
| ... | ... |
@@ -805,4 +1130,4 @@ |
| 805 | 1130 |
Graph::Edge e2 = graph.addEdge(n1, n3); |
| 806 |
Graph::Edge e3 = graph.addEdge(n2, n3); |
|
| 807 |
Graph::Edge e4 = graph.addEdge(n3, n4); |
|
| 1131 |
Adaptor::Edge e3 = adaptor.addEdge(n2, n3); |
|
| 1132 |
Adaptor::Edge e4 = adaptor.addEdge(n3, n4); |
|
| 808 | 1133 |
|
| ... | ... |
@@ -816,16 +1141,6 @@ |
| 816 | 1141 |
|
| 817 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 818 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 819 |
checkGraphOutArcList(adaptor, n3, 3); |
|
| 820 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 821 |
|
|
| 822 |
checkGraphInArcList(adaptor, n1, 2); |
|
| 823 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 824 |
checkGraphInArcList(adaptor, n3, 3); |
|
| 825 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 826 |
|
|
| 827 |
checkGraphIncEdgeList(adaptor, n1, 2); |
|
| 828 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 829 |
checkGraphIncEdgeList(adaptor, n3, 3); |
|
| 830 |
checkGraphIncEdgeList(adaptor, n4, 1); |
|
| 1142 |
checkGraphIncEdgeArcLists(adaptor, n1, 2); |
|
| 1143 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 1144 |
checkGraphIncEdgeArcLists(adaptor, n3, 3); |
|
| 1145 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 831 | 1146 |
|
| ... | ... |
@@ -839,3 +1154,6 @@ |
| 839 | 1154 |
|
| 840 |
|
|
| 1155 |
// Hide an edge |
|
| 1156 |
adaptor.status(e2, false); |
|
| 1157 |
adaptor.disable(e3); |
|
| 1158 |
if (!adaptor.status(e3)) adaptor.enable(e3); |
|
| 841 | 1159 |
|
| ... | ... |
@@ -847,16 +1165,6 @@ |
| 847 | 1165 |
|
| 848 |
checkGraphOutArcList(adaptor, n1, 1); |
|
| 849 |
checkGraphOutArcList(adaptor, n2, 2); |
|
| 850 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 851 |
checkGraphOutArcList(adaptor, n4, 1); |
|
| 852 |
|
|
| 853 |
checkGraphInArcList(adaptor, n1, 1); |
|
| 854 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 855 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 856 |
checkGraphInArcList(adaptor, n4, 1); |
|
| 857 |
|
|
| 858 |
checkGraphIncEdgeList(adaptor, n1, 1); |
|
| 859 |
checkGraphIncEdgeList(adaptor, n2, 2); |
|
| 860 |
checkGraphIncEdgeList(adaptor, n3, 2); |
|
| 861 |
checkGraphIncEdgeList(adaptor, n4, 1); |
|
| 1166 |
checkGraphIncEdgeArcLists(adaptor, n1, 1); |
|
| 1167 |
checkGraphIncEdgeArcLists(adaptor, n2, 2); |
|
| 1168 |
checkGraphIncEdgeArcLists(adaptor, n3, 2); |
|
| 1169 |
checkGraphIncEdgeArcLists(adaptor, n4, 1); |
|
| 862 | 1170 |
|
| ... | ... |
@@ -870,2 +1178,3 @@ |
| 870 | 1178 |
|
| 1179 |
// Hide all edges |
|
| 871 | 1180 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; |
| ... | ... |
@@ -885,2 +1194,12 @@ |
| 885 | 1194 |
checkGraphEdgeMap(adaptor); |
| 1195 |
|
|
| 1196 |
// Check the conversion of nodes and edges |
|
| 1197 |
Graph::Node ng = n3; |
|
| 1198 |
ng = n4; |
|
| 1199 |
Adaptor::Node na = n1; |
|
| 1200 |
na = n2; |
|
| 1201 |
Graph::Edge eg = e3; |
|
| 1202 |
eg = e4; |
|
| 1203 |
Adaptor::Edge ea = e1; |
|
| 1204 |
ea = e2; |
|
| 886 | 1205 |
} |
| ... | ... |
@@ -888,5 +1207,15 @@ |
| 888 | 1207 |
void checkOrienter() {
|
| 889 |
checkConcept<concepts::Digraph, |
|
| 890 |
Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); |
|
| 1208 |
// Check concepts |
|
| 1209 |
checkConcept<concepts::Digraph, Orienter<concepts::Graph> >(); |
|
| 1210 |
checkConcept<concepts::Digraph, Orienter<ListGraph> >(); |
|
| 1211 |
checkConcept<concepts::AlterableDigraphComponent<>, |
|
| 1212 |
Orienter<ListGraph> >(); |
|
| 1213 |
checkConcept<concepts::ExtendableDigraphComponent<>, |
|
| 1214 |
Orienter<ListGraph> >(); |
|
| 1215 |
checkConcept<concepts::ErasableDigraphComponent<>, |
|
| 1216 |
Orienter<ListGraph> >(); |
|
| 1217 |
checkConcept<concepts::ClearableDigraphComponent<>, |
|
| 1218 |
Orienter<ListGraph> >(); |
|
| 891 | 1219 |
|
| 1220 |
// Create a graph and an adaptor |
|
| 892 | 1221 |
typedef ListGraph Graph; |
| ... | ... |
@@ -896,8 +1225,9 @@ |
| 896 | 1225 |
Graph graph; |
| 897 |
DirMap dir(graph |
|
| 1226 |
DirMap dir(graph); |
|
| 898 | 1227 |
Adaptor adaptor(graph, dir); |
| 899 | 1228 |
|
| 1229 |
// Add nodes and edges to the original graph and the adaptor |
|
| 900 | 1230 |
Graph::Node n1 = graph.addNode(); |
| 901 | 1231 |
Graph::Node n2 = graph.addNode(); |
| 902 |
|
|
| 1232 |
Adaptor::Node n3 = adaptor.addNode(); |
|
| 903 | 1233 |
|
| ... | ... |
@@ -905,4 +1235,26 @@ |
| 905 | 1235 |
Graph::Edge e2 = graph.addEdge(n1, n3); |
| 906 |
|
|
| 1236 |
Adaptor::Arc e3 = adaptor.addArc(n2, n3); |
|
| 907 | 1237 |
|
| 1238 |
dir[e1] = dir[e2] = dir[e3] = true; |
|
| 1239 |
|
|
| 1240 |
// Check the original graph |
|
| 1241 |
checkGraphNodeList(graph, 3); |
|
| 1242 |
checkGraphArcList(graph, 6); |
|
| 1243 |
checkGraphConArcList(graph, 6); |
|
| 1244 |
checkGraphEdgeList(graph, 3); |
|
| 1245 |
checkGraphConEdgeList(graph, 3); |
|
| 1246 |
|
|
| 1247 |
checkGraphIncEdgeArcLists(graph, n1, 2); |
|
| 1248 |
checkGraphIncEdgeArcLists(graph, n2, 2); |
|
| 1249 |
checkGraphIncEdgeArcLists(graph, n3, 2); |
|
| 1250 |
|
|
| 1251 |
checkNodeIds(graph); |
|
| 1252 |
checkArcIds(graph); |
|
| 1253 |
checkEdgeIds(graph); |
|
| 1254 |
|
|
| 1255 |
checkGraphNodeMap(graph); |
|
| 1256 |
checkGraphArcMap(graph); |
|
| 1257 |
checkGraphEdgeMap(graph); |
|
| 1258 |
|
|
| 1259 |
// Check the adaptor |
|
| 908 | 1260 |
checkGraphNodeList(adaptor, 3); |
| ... | ... |
@@ -911,2 +1263,17 @@ |
| 911 | 1263 |
|
| 1264 |
checkGraphOutArcList(adaptor, n1, 2); |
|
| 1265 |
checkGraphOutArcList(adaptor, n2, 1); |
|
| 1266 |
checkGraphOutArcList(adaptor, n3, 0); |
|
| 1267 |
|
|
| 1268 |
checkGraphInArcList(adaptor, n1, 0); |
|
| 1269 |
checkGraphInArcList(adaptor, n2, 1); |
|
| 1270 |
checkGraphInArcList(adaptor, n3, 2); |
|
| 1271 |
|
|
| 1272 |
checkNodeIds(adaptor); |
|
| 1273 |
checkArcIds(adaptor); |
|
| 1274 |
|
|
| 1275 |
checkGraphNodeMap(adaptor); |
|
| 1276 |
checkGraphArcMap(adaptor); |
|
| 1277 |
|
|
| 1278 |
// Check direction changing |
|
| 912 | 1279 |
{
|
| ... | ... |
@@ -950,2 +1317,7 @@ |
| 950 | 1317 |
|
| 1318 |
// Check the adaptor again |
|
| 1319 |
checkGraphNodeList(adaptor, 3); |
|
| 1320 |
checkGraphArcList(adaptor, 3); |
|
| 1321 |
checkGraphConArcList(adaptor, 3); |
|
| 1322 |
|
|
| 951 | 1323 |
checkGraphOutArcList(adaptor, n1, 1); |
| ... | ... |
@@ -964,7 +1336,133 @@ |
| 964 | 1336 |
|
| 1337 |
// Check reverseArc() |
|
| 1338 |
adaptor.reverseArc(e2); |
|
| 1339 |
adaptor.reverseArc(e3); |
|
| 1340 |
adaptor.reverseArc(e2); |
|
| 1341 |
|
|
| 1342 |
checkGraphNodeList(adaptor, 3); |
|
| 1343 |
checkGraphArcList(adaptor, 3); |
|
| 1344 |
checkGraphConArcList(adaptor, 3); |
|
| 1345 |
|
|
| 1346 |
checkGraphOutArcList(adaptor, n1, 1); |
|
| 1347 |
checkGraphOutArcList(adaptor, n2, 0); |
|
| 1348 |
checkGraphOutArcList(adaptor, n3, 2); |
|
| 1349 |
|
|
| 1350 |
checkGraphInArcList(adaptor, n1, 1); |
|
| 1351 |
checkGraphInArcList(adaptor, n2, 2); |
|
| 1352 |
checkGraphInArcList(adaptor, n3, 0); |
|
| 1353 |
|
|
| 1354 |
// Check the conversion of nodes and arcs/edges |
|
| 1355 |
Graph::Node ng = n3; |
|
| 1356 |
ng = n3; |
|
| 1357 |
Adaptor::Node na = n1; |
|
| 1358 |
na = n2; |
|
| 1359 |
Graph::Edge eg = e3; |
|
| 1360 |
eg = e3; |
|
| 1361 |
Adaptor::Arc aa = e1; |
|
| 1362 |
aa = e2; |
|
| 965 | 1363 |
} |
| 966 | 1364 |
|
| 1365 |
void checkCombiningAdaptors() {
|
|
| 1366 |
// Create a grid graph |
|
| 1367 |
GridGraph graph(2,2); |
|
| 1368 |
GridGraph::Node n1 = graph(0,0); |
|
| 1369 |
GridGraph::Node n2 = graph(0,1); |
|
| 1370 |
GridGraph::Node n3 = graph(1,0); |
|
| 1371 |
GridGraph::Node n4 = graph(1,1); |
|
| 1372 |
|
|
| 1373 |
GridGraph::EdgeMap<bool> dir_map(graph); |
|
| 1374 |
dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1; |
|
| 1375 |
dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1; |
|
| 1376 |
dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4; |
|
| 1377 |
dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4; |
|
| 1378 |
|
|
| 1379 |
// Apply several adaptors on the grid graph |
|
| 1380 |
typedef SplitNodes< ReverseDigraph< const Orienter< |
|
| 1381 |
const GridGraph, GridGraph::EdgeMap<bool> > > > |
|
| 1382 |
RevSplitGridGraph; |
|
| 1383 |
typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph; |
|
| 1384 |
typedef Undirector<const SplitGridGraph> USplitGridGraph; |
|
| 1385 |
typedef Undirector<const USplitGridGraph> UUSplitGridGraph; |
|
| 1386 |
checkConcept<concepts::Digraph, RevSplitGridGraph>(); |
|
| 1387 |
checkConcept<concepts::Digraph, SplitGridGraph>(); |
|
| 1388 |
checkConcept<concepts::Graph, USplitGridGraph>(); |
|
| 1389 |
checkConcept<concepts::Graph, UUSplitGridGraph>(); |
|
| 1390 |
|
|
| 1391 |
RevSplitGridGraph rev_adaptor = |
|
| 1392 |
splitNodes(reverseDigraph(orienter(graph, dir_map))); |
|
| 1393 |
SplitGridGraph adaptor = reverseDigraph(rev_adaptor); |
|
| 1394 |
USplitGridGraph uadaptor = undirector(adaptor); |
|
| 1395 |
UUSplitGridGraph uuadaptor = undirector(uadaptor); |
|
| 1396 |
|
|
| 1397 |
// Check adaptor |
|
| 1398 |
checkGraphNodeList(adaptor, 8); |
|
| 1399 |
checkGraphArcList(adaptor, 8); |
|
| 1400 |
checkGraphConArcList(adaptor, 8); |
|
| 1401 |
|
|
| 1402 |
checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1); |
|
| 1403 |
checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1); |
|
| 1404 |
checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2); |
|
| 1405 |
checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1); |
|
| 1406 |
checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1); |
|
| 1407 |
checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1); |
|
| 1408 |
checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0); |
|
| 1409 |
checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1); |
|
| 1410 |
|
|
| 1411 |
checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1); |
|
| 1412 |
checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1); |
|
| 1413 |
checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1); |
|
| 1414 |
checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0); |
|
| 1415 |
checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1); |
|
| 1416 |
checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1); |
|
| 1417 |
checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1); |
|
| 1418 |
checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2); |
|
| 1419 |
|
|
| 1420 |
checkNodeIds(adaptor); |
|
| 1421 |
checkArcIds(adaptor); |
|
| 1422 |
|
|
| 1423 |
checkGraphNodeMap(adaptor); |
|
| 1424 |
checkGraphArcMap(adaptor); |
|
| 1425 |
|
|
| 1426 |
// Check uadaptor |
|
| 1427 |
checkGraphNodeList(uadaptor, 8); |
|
| 1428 |
checkGraphEdgeList(uadaptor, 8); |
|
| 1429 |
checkGraphArcList(uadaptor, 16); |
|
| 1430 |
checkGraphConEdgeList(uadaptor, 8); |
|
| 1431 |
checkGraphConArcList(uadaptor, 16); |
|
| 1432 |
|
|
| 1433 |
checkNodeIds(uadaptor); |
|
| 1434 |
checkEdgeIds(uadaptor); |
|
| 1435 |
checkArcIds(uadaptor); |
|
| 1436 |
|
|
| 1437 |
checkGraphNodeMap(uadaptor); |
|
| 1438 |
checkGraphEdgeMap(uadaptor); |
|
| 1439 |
checkGraphArcMap(uadaptor); |
|
| 1440 |
|
|
| 1441 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2); |
|
| 1442 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2); |
|
| 1443 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3); |
|
| 1444 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1); |
|
| 1445 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2); |
|
| 1446 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2); |
|
| 1447 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1); |
|
| 1448 |
checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3); |
|
| 1449 |
|
|
| 1450 |
// Check uuadaptor |
|
| 1451 |
checkGraphNodeList(uuadaptor, 8); |
|
| 1452 |
checkGraphEdgeList(uuadaptor, 16); |
|
| 1453 |
checkGraphArcList(uuadaptor, 32); |
|
| 1454 |
checkGraphConEdgeList(uuadaptor, 16); |
|
| 1455 |
checkGraphConArcList(uuadaptor, 32); |
|
| 1456 |
|
|
| 1457 |
checkNodeIds(uuadaptor); |
|
| 1458 |
checkEdgeIds(uuadaptor); |
|
| 1459 |
checkArcIds(uuadaptor); |
|
| 1460 |
|
|
| 1461 |
checkGraphNodeMap(uuadaptor); |
|
| 1462 |
checkGraphEdgeMap(uuadaptor); |
|
| 1463 |
checkGraphArcMap(uuadaptor); |
|
| 1464 |
} |
|
| 967 | 1465 |
|
| 968 | 1466 |
int main(int, const char **) {
|
| 969 |
|
|
| 1467 |
// Check the digraph adaptors (using ListDigraph) |
|
| 970 | 1468 |
checkReverseDigraph(); |
| ... | ... |
@@ -974,5 +1472,6 @@ |
| 974 | 1472 |
checkUndirector(); |
| 975 |
|
|
| 1473 |
checkResidualDigraph(); |
|
| 976 | 1474 |
checkSplitNodes(); |
| 977 | 1475 |
|
| 1476 |
// Check the graph adaptors (using ListGraph) |
|
| 978 | 1477 |
checkSubGraph(); |
| ... | ... |
@@ -982,2 +1481,5 @@ |
| 982 | 1481 |
|
| 1482 |
// Combine adaptors (using GridGraph) |
|
| 1483 |
checkCombiningAdaptors(); |
|
| 1484 |
|
|
| 983 | 1485 |
return 0; |
| ... | ... |
@@ -94,2 +94,26 @@ |
| 94 | 94 |
-e "s/\<readNauty\>/readNautyGraph/g"\ |
| 95 |
-e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\ |
|
| 96 |
-e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\ |
|
| 97 |
-e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\ |
|
| 98 |
-e "s/\<subDigraphAdaptor\>/subDigraph/g"\ |
|
| 99 |
-e "s/\<SubGraphAdaptor\>/SubGraph/g"\ |
|
| 100 |
-e "s/\<subGraphAdaptor\>/subGraph/g"\ |
|
| 101 |
-e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\ |
|
| 102 |
-e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\ |
|
| 103 |
-e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\ |
|
| 104 |
-e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\ |
|
| 105 |
-e "s/\<UndirDigraphAdaptor\>/Undirector/g"\ |
|
| 106 |
-e "s/\<undirDigraphAdaptor\>/undirector/g"\ |
|
| 107 |
-e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\ |
|
| 108 |
-e "s/\<resDigraphAdaptor\>/residualDigraph/g"\ |
|
| 109 |
-e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\ |
|
| 110 |
-e "s/\<splitDigraphAdaptor\>/splitNodes/g"\ |
|
| 111 |
-e "s/\<SubGraphAdaptor\>/SubGraph/g"\ |
|
| 112 |
-e "s/\<subGraphAdaptor\>/subGraph/g"\ |
|
| 113 |
-e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\ |
|
| 114 |
-e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\ |
|
| 115 |
-e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\ |
|
| 116 |
-e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\ |
|
| 117 |
-e "s/\<DirGraphAdaptor\>/Orienter/g"\ |
|
| 118 |
-e "s/\<dirGraphAdaptor\>/orienter/g"\ |
|
| 95 | 119 |
<$i > $TMP |
0 comments (0 inline)