diff options
Diffstat (limited to 'lemon/test/adaptors_test.cc')
| -rw-r--r-- | lemon/test/adaptors_test.cc | 1463 |
1 files changed, 1463 insertions, 0 deletions
diff --git a/lemon/test/adaptors_test.cc b/lemon/test/adaptors_test.cc new file mode 100644 index 0000000..9c625f2 --- /dev/null +++ b/lemon/test/adaptors_test.cc @@ -0,0 +1,1463 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include <iostream> +#include <limits> + +#include <lemon/list_graph.h> +#include <lemon/grid_graph.h> +#include <lemon/bfs.h> +#include <lemon/path.h> + +#include <lemon/concepts/digraph.h> +#include <lemon/concepts/graph.h> +#include <lemon/concepts/graph_components.h> +#include <lemon/concepts/maps.h> +#include <lemon/concept_check.h> + +#include <lemon/adaptors.h> + +#include "test/test_tools.h" +#include "test/graph_test.h" + +using namespace lemon; + +void checkReverseDigraph() { + // Check concepts + checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); + checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >(); + checkConcept<concepts::AlterableDigraphComponent<>, + ReverseDigraph<ListDigraph> >(); + checkConcept<concepts::ExtendableDigraphComponent<>, + ReverseDigraph<ListDigraph> >(); + checkConcept<concepts::ErasableDigraphComponent<>, + ReverseDigraph<ListDigraph> >(); + checkConcept<concepts::ClearableDigraphComponent<>, + ReverseDigraph<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef ReverseDigraph<Digraph> Adaptor; + + Digraph digraph; + Adaptor adaptor(digraph); + + // Add nodes and arcs to the original digraph + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Digraph::Node n3 = digraph.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Digraph::Arc a3 = digraph.addArc(n2, n3); + + // Check the adaptor + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 0); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 2); + + checkGraphInArcList(adaptor, n1, 2); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check the orientation of the arcs + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { + check(adaptor.source(a) == digraph.target(a), "Wrong reverse"); + check(adaptor.target(a) == digraph.source(a), "Wrong reverse"); + } + + // Add and erase nodes and arcs in the digraph through the adaptor + Adaptor::Node n4 = adaptor.addNode(); + + Adaptor::Arc a4 = adaptor.addArc(n4, n3); + Adaptor::Arc a5 = adaptor.addArc(n2, n4); + Adaptor::Arc a6 = adaptor.addArc(n2, n4); + Adaptor::Arc a7 = adaptor.addArc(n1, n4); + Adaptor::Arc a8 = adaptor.addArc(n1, n2); + + adaptor.erase(a1); + adaptor.erase(n3); + + // Check the adaptor + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 4); + checkGraphConArcList(adaptor, 4); + + checkGraphOutArcList(adaptor, n1, 2); + checkGraphOutArcList(adaptor, n2, 2); + checkGraphOutArcList(adaptor, n4, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n4, 3); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check the digraph + checkGraphNodeList(digraph, 3); + checkGraphArcList(digraph, 4); + checkGraphConArcList(digraph, 4); + + checkGraphOutArcList(digraph, n1, 0); + checkGraphOutArcList(digraph, n2, 1); + checkGraphOutArcList(digraph, n4, 3); + + checkGraphInArcList(digraph, n1, 2); + checkGraphInArcList(digraph, n2, 2); + checkGraphInArcList(digraph, n4, 0); + + checkNodeIds(digraph); + checkArcIds(digraph); + + checkGraphNodeMap(digraph); + checkGraphArcMap(digraph); + + // Check the conversion of nodes and arcs + Digraph::Node nd = n4; + nd = n4; + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = a4; + ad = a5; + Adaptor::Arc aa = a1; + aa = a2; +} + +void checkSubDigraph() { + // Check concepts + checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >(); + checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >(); + checkConcept<concepts::AlterableDigraphComponent<>, + SubDigraph<ListDigraph> >(); + checkConcept<concepts::ExtendableDigraphComponent<>, + SubDigraph<ListDigraph> >(); + checkConcept<concepts::ErasableDigraphComponent<>, + SubDigraph<ListDigraph> >(); + checkConcept<concepts::ClearableDigraphComponent<>, + SubDigraph<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::NodeMap<bool> NodeFilter; + typedef Digraph::ArcMap<bool> ArcFilter; + typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor; + + Digraph digraph; + NodeFilter node_filter(digraph); + ArcFilter arc_filter(digraph); + Adaptor adaptor(digraph, node_filter, arc_filter); + + // Add nodes and arcs to the original digraph and the adaptor + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + + node_filter[n1] = node_filter[n2] = node_filter[n3] = true; + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Adaptor::Arc a3 = adaptor.addArc(n2, n3); + + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 2); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide an arc + adaptor.status(a2, false); + adaptor.disable(a3); + if (!adaptor.status(a3)) adaptor.enable(a3); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 2); + checkGraphConArcList(adaptor, 2); + + checkGraphOutArcList(adaptor, n1, 1); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide a node + adaptor.status(n1, false); + adaptor.disable(n3); + if (!adaptor.status(n3)) adaptor.enable(n3); + + checkGraphNodeList(adaptor, 2); + checkGraphArcList(adaptor, 1); + checkGraphConArcList(adaptor, 1); + + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n2, 0); + checkGraphInArcList(adaptor, n3, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide all nodes and arcs + node_filter[n1] = node_filter[n2] = node_filter[n3] = false; + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; + + checkGraphNodeList(adaptor, 0); + checkGraphArcList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check the conversion of nodes and arcs + Digraph::Node nd = n3; + nd = n3; + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = a3; + ad = a3; + Adaptor::Arc aa = a1; + aa = a2; +} + +void checkFilterNodes1() { + // Check concepts + checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >(); + checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >(); + checkConcept<concepts::AlterableDigraphComponent<>, + FilterNodes<ListDigraph> >(); + checkConcept<concepts::ExtendableDigraphComponent<>, + FilterNodes<ListDigraph> >(); + checkConcept<concepts::ErasableDigraphComponent<>, + FilterNodes<ListDigraph> >(); + checkConcept<concepts::ClearableDigraphComponent<>, + FilterNodes<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::NodeMap<bool> NodeFilter; + typedef FilterNodes<Digraph, NodeFilter> Adaptor; + + Digraph digraph; + NodeFilter node_filter(digraph); + Adaptor adaptor(digraph, node_filter); + + // Add nodes and arcs to the original digraph and the adaptor + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + + node_filter[n1] = node_filter[n2] = node_filter[n3] = true; + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Adaptor::Arc a3 = adaptor.addArc(n2, n3); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 2); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide a node + adaptor.status(n1, false); + adaptor.disable(n3); + if (!adaptor.status(n3)) adaptor.enable(n3); + + checkGraphNodeList(adaptor, 2); + checkGraphArcList(adaptor, 1); + checkGraphConArcList(adaptor, 1); + + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n2, 0); + checkGraphInArcList(adaptor, n3, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide all nodes + node_filter[n1] = node_filter[n2] = node_filter[n3] = false; + + checkGraphNodeList(adaptor, 0); + checkGraphArcList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check the conversion of nodes and arcs + Digraph::Node nd = n3; + nd = n3; + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = a3; + ad = a3; + Adaptor::Arc aa = a1; + aa = a2; +} + +void checkFilterArcs() { + // Check concepts + checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >(); + checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >(); + checkConcept<concepts::AlterableDigraphComponent<>, + FilterArcs<ListDigraph> >(); + checkConcept<concepts::ExtendableDigraphComponent<>, + FilterArcs<ListDigraph> >(); + checkConcept<concepts::ErasableDigraphComponent<>, + FilterArcs<ListDigraph> >(); + checkConcept<concepts::ClearableDigraphComponent<>, + FilterArcs<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::ArcMap<bool> ArcFilter; + typedef FilterArcs<Digraph, ArcFilter> Adaptor; + + Digraph digraph; + ArcFilter arc_filter(digraph); + Adaptor adaptor(digraph, arc_filter); + + // Add nodes and arcs to the original digraph and the adaptor + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Adaptor::Arc a3 = adaptor.addArc(n2, n3); + + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 2); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide an arc + adaptor.status(a2, false); + adaptor.disable(a3); + if (!adaptor.status(a3)) adaptor.enable(a3); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 2); + checkGraphConArcList(adaptor, 2); + + checkGraphOutArcList(adaptor, n1, 1); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Hide all arcs + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check the conversion of nodes and arcs + Digraph::Node nd = n3; + nd = n3; + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = a3; + ad = a3; + Adaptor::Arc aa = a1; + aa = a2; +} + +void checkUndirector() { + // Check concepts + checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); + checkConcept<concepts::Graph, Undirector<ListDigraph> >(); + checkConcept<concepts::AlterableGraphComponent<>, + Undirector<ListDigraph> >(); + checkConcept<concepts::ExtendableGraphComponent<>, + Undirector<ListDigraph> >(); + checkConcept<concepts::ErasableGraphComponent<>, + Undirector<ListDigraph> >(); + checkConcept<concepts::ClearableGraphComponent<>, + Undirector<ListDigraph> >(); + + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Undirector<Digraph> Adaptor; + + Digraph digraph; + Adaptor adaptor(digraph); + + // Add nodes and arcs/edges to the original digraph and the adaptor + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Adaptor::Edge e3 = adaptor.addEdge(n2, n3); + + // Check the original digraph + checkGraphNodeList(digraph, 3); + checkGraphArcList(digraph, 3); + checkGraphConArcList(digraph, 3); + + checkGraphOutArcList(digraph, n1, 2); + checkGraphOutArcList(digraph, n2, 1); + checkGraphOutArcList(digraph, n3, 0); + + checkGraphInArcList(digraph, n1, 0); + checkGraphInArcList(digraph, n2, 1); + checkGraphInArcList(digraph, n3, 2); + + checkNodeIds(digraph); + checkArcIds(digraph); + + checkGraphNodeMap(digraph); + checkGraphArcMap(digraph); + + // Check the adaptor + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 6); + checkGraphEdgeList(adaptor, 3); + checkGraphConArcList(adaptor, 6); + checkGraphConEdgeList(adaptor, 3); + + checkGraphIncEdgeArcLists(adaptor, n1, 2); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 2); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Check the edges of the adaptor + for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) { + check(adaptor.u(e) == digraph.source(e), "Wrong undir"); + check(adaptor.v(e) == digraph.target(e), "Wrong undir"); + } + + // Check CombinedArcMap + typedef Adaptor::CombinedArcMap + <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap; + typedef Adaptor::CombinedArcMap + <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap; + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>, + IntCombinedMap>(); + checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>, + BoolCombinedMap>(); + + Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph); + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + fw_map[a] = digraph.id(a); + bk_map[a] = -digraph.id(a); + } + + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> > + comb_map(fw_map, bk_map); + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { + if (adaptor.source(a) == digraph.source(a)) { + check(comb_map[a] == fw_map[a], "Wrong combined map"); + } else { + check(comb_map[a] == bk_map[a], "Wrong combined map"); + } + } + + // Check the conversion of nodes and arcs/edges + Digraph::Node nd = n3; + nd = n3; + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = e3; + ad = e3; + Adaptor::Edge ea = a1; + ea = a2; +} + +void checkResidualDigraph() { + // Check concepts + checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >(); + checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::ArcMap<int> IntArcMap; + typedef ResidualDigraph<Digraph, IntArcMap> Adaptor; + + Digraph digraph; + IntArcMap capacity(digraph), flow(digraph); + Adaptor adaptor(digraph, capacity, flow); + + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Digraph::Node n3 = digraph.addNode(); + Digraph::Node n4 = digraph.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Digraph::Arc a3 = digraph.addArc(n1, n4); + Digraph::Arc a4 = digraph.addArc(n2, n3); + Digraph::Arc a5 = digraph.addArc(n2, n4); + Digraph::Arc a6 = digraph.addArc(n3, n4); + + capacity[a1] = 8; + capacity[a2] = 6; + capacity[a3] = 4; + capacity[a4] = 4; + capacity[a5] = 6; + capacity[a6] = 10; + + // Check the adaptor with various flow values + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + flow[a] = 0; + } + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 6); + checkGraphConArcList(adaptor, 6); + + checkGraphOutArcList(adaptor, n1, 3); + checkGraphOutArcList(adaptor, n2, 2); + checkGraphOutArcList(adaptor, n3, 1); + checkGraphOutArcList(adaptor, n4, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + checkGraphInArcList(adaptor, n4, 3); + + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + flow[a] = capacity[a] / 2; + } + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 12); + checkGraphConArcList(adaptor, 12); + + checkGraphOutArcList(adaptor, n1, 3); + checkGraphOutArcList(adaptor, n2, 3); + checkGraphOutArcList(adaptor, n3, 3); + checkGraphOutArcList(adaptor, n4, 3); + + checkGraphInArcList(adaptor, n1, 3); + checkGraphInArcList(adaptor, n2, 3); + checkGraphInArcList(adaptor, n3, 3); + checkGraphInArcList(adaptor, n4, 3); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + flow[a] = capacity[a]; + } + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 6); + checkGraphConArcList(adaptor, 6); + + checkGraphOutArcList(adaptor, n1, 0); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 2); + checkGraphOutArcList(adaptor, n4, 3); + + checkGraphInArcList(adaptor, n1, 3); + checkGraphInArcList(adaptor, n2, 2); + checkGraphInArcList(adaptor, n3, 1); + checkGraphInArcList(adaptor, n4, 0); + + // Saturate all backward arcs + // (set the flow to zero on all forward arcs) + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { + if (adaptor.backward(a)) + adaptor.augment(a, adaptor.residualCapacity(a)); + } + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 6); + checkGraphConArcList(adaptor, 6); + + checkGraphOutArcList(adaptor, n1, 3); + checkGraphOutArcList(adaptor, n2, 2); + checkGraphOutArcList(adaptor, n3, 1); + checkGraphOutArcList(adaptor, n4, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + checkGraphInArcList(adaptor, n4, 3); + + // Find maximum flow by augmenting along shortest paths + int flow_value = 0; + Adaptor::ResidualCapacity res_cap(adaptor); + while (true) { + + Bfs<Adaptor> bfs(adaptor); + bfs.run(n1, n4); + + if (!bfs.reached(n4)) break; + + Path<Adaptor> p = bfs.path(n4); + + int min = std::numeric_limits<int>::max(); + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { + if (res_cap[a] < min) min = res_cap[a]; + } + + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { + adaptor.augment(a, min); + } + flow_value += min; + } + + check(flow_value == 18, "Wrong flow with res graph adaptor"); + + // Check forward() and backward() + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { + check(adaptor.forward(a) != adaptor.backward(a), + "Wrong forward() or backward()"); + check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) || + (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a), + "Wrong forward() or backward()"); + } + + // Check the conversion of nodes and arcs + Digraph::Node nd = Adaptor::NodeIt(adaptor); + nd = ++Adaptor::NodeIt(adaptor); + Adaptor::Node na = n1; + na = n2; + Digraph::Arc ad = Adaptor::ArcIt(adaptor); + ad = ++Adaptor::ArcIt(adaptor); +} + +void checkSplitNodes() { + // Check concepts + checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); + checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef SplitNodes<Digraph> Adaptor; + + Digraph digraph; + Adaptor adaptor(digraph); + + Digraph::Node n1 = digraph.addNode(); + Digraph::Node n2 = digraph.addNode(); + Digraph::Node n3 = digraph.addNode(); + + Digraph::Arc a1 = digraph.addArc(n1, n2); + Digraph::Arc a2 = digraph.addArc(n1, n3); + Digraph::Arc a3 = digraph.addArc(n2, n3); + + checkGraphNodeList(adaptor, 6); + checkGraphArcList(adaptor, 6); + checkGraphConArcList(adaptor, 6); + + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2); + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1); + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0); + + checkGraphInArcList(adaptor, adaptor.inNode(n1), 0); + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n2), 1); + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n3), 2); + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check split + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { + if (adaptor.origArc(a)) { + Digraph::Arc oa = a; + check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), + "Wrong split"); + check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), + "Wrong split"); + } else { + Digraph::Node on = a; + check(adaptor.source(a) == adaptor.inNode(on), "Wrong split"); + check(adaptor.target(a) == adaptor.outNode(on), "Wrong split"); + } + } + + // Check combined node map + typedef Adaptor::CombinedNodeMap + <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap; + typedef Adaptor::CombinedNodeMap + <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap; + checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>, + IntCombinedNodeMap>(); +//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>, +// BoolCombinedNodeMap>(); + checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>, + BoolCombinedNodeMap>(); + + Digraph::NodeMap<int> in_map(digraph), out_map(digraph); + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) { + in_map[n] = digraph.id(n); + out_map[n] = -digraph.id(n); + } + + Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> > + node_map(in_map, out_map); + for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) { + if (adaptor.inNode(n)) { + check(node_map[n] == in_map[n], "Wrong combined node map"); + } else { + check(node_map[n] == out_map[n], "Wrong combined node map"); + } + } + + // Check combined arc map + typedef Adaptor::CombinedArcMap + <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap; + typedef Adaptor::CombinedArcMap + <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap; + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>, + IntCombinedArcMap>(); +//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>, +// BoolCombinedArcMap>(); + checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>, + BoolCombinedArcMap>(); + + Digraph::ArcMap<int> a_map(digraph); + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + a_map[a] = digraph.id(a); + } + + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> > + arc_map(a_map, out_map); + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map"); + } + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) { + check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map"); + } + + // Check the conversion of nodes + Digraph::Node nd = adaptor.inNode(n1); + check (nd == n1, "Wrong node conversion"); + nd = adaptor.outNode(n2); + check (nd == n2, "Wrong node conversion"); +} + +void checkSubGraph() { + // Check concepts + checkConcept<concepts::Graph, SubGraph<concepts::Graph> >(); + checkConcept<concepts::Graph, SubGraph<ListGraph> >(); + checkConcept<concepts::AlterableGraphComponent<>, + SubGraph<ListGraph> >(); + checkConcept<concepts::ExtendableGraphComponent<>, + SubGraph<ListGraph> >(); + checkConcept<concepts::ErasableGraphComponent<>, + SubGraph<ListGraph> >(); + checkConcept<concepts::ClearableGraphComponent<>, + SubGraph<ListGraph> >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::NodeMap<bool> NodeFilter; + typedef Graph::EdgeMap<bool> EdgeFilter; + typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor; + + Graph graph; + NodeFilter node_filter(graph); + EdgeFilter edge_filter(graph); + Adaptor adaptor(graph, node_filter, edge_filter); + + // Add nodes and edges to the original graph and the adaptor + Graph::Node n1 = graph.addNode(); + Graph::Node n2 = graph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + Adaptor::Node n4 = adaptor.addNode(); + + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; + + Graph::Edge e1 = graph.addEdge(n1, n2); + Graph::Edge e2 = graph.addEdge(n1, n3); + Adaptor::Edge e3 = adaptor.addEdge(n2, n3); + Adaptor::Edge e4 = adaptor.addEdge(n3, n4); + + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 8); + checkGraphEdgeList(adaptor, 4); + checkGraphConArcList(adaptor, 8); + checkGraphConEdgeList(adaptor, 4); + + checkGraphIncEdgeArcLists(adaptor, n1, 2); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 3); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide an edge + adaptor.status(e2, false); + adaptor.disable(e3); + if (!adaptor.status(e3)) adaptor.enable(e3); + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 6); + checkGraphEdgeList(adaptor, 3); + checkGraphConArcList(adaptor, 6); + checkGraphConEdgeList(adaptor, 3); + + checkGraphIncEdgeArcLists(adaptor, n1, 1); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 2); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide a node + adaptor.status(n1, false); + adaptor.disable(n3); + if (!adaptor.status(n3)) adaptor.enable(n3); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 4); + checkGraphEdgeList(adaptor, 2); + checkGraphConArcList(adaptor, 4); + checkGraphConEdgeList(adaptor, 2); + + checkGraphIncEdgeArcLists(adaptor, n2, 1); + checkGraphIncEdgeArcLists(adaptor, n3, 2); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide all nodes and edges + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; + + checkGraphNodeList(adaptor, 0); + checkGraphArcList(adaptor, 0); + checkGraphEdgeList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + checkGraphConEdgeList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Check the conversion of nodes and edges + Graph::Node ng = n3; + ng = n4; + Adaptor::Node na = n1; + na = n2; + Graph::Edge eg = e3; + eg = e4; + Adaptor::Edge ea = e1; + ea = e2; +} + +void checkFilterNodes2() { + // Check concepts + checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >(); + checkConcept<concepts::Graph, FilterNodes<ListGraph> >(); + checkConcept<concepts::AlterableGraphComponent<>, + FilterNodes<ListGraph> >(); + checkConcept<concepts::ExtendableGraphComponent<>, + FilterNodes<ListGraph> >(); + checkConcept<concepts::ErasableGraphComponent<>, + FilterNodes<ListGraph> >(); + checkConcept<concepts::ClearableGraphComponent<>, + FilterNodes<ListGraph> >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::NodeMap<bool> NodeFilter; + typedef FilterNodes<Graph, NodeFilter> Adaptor; + + // Add nodes and edges to the original graph and the adaptor + Graph graph; + NodeFilter node_filter(graph); + Adaptor adaptor(graph, node_filter); + + Graph::Node n1 = graph.addNode(); + Graph::Node n2 = graph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + Adaptor::Node n4 = adaptor.addNode(); + + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; + + Graph::Edge e1 = graph.addEdge(n1, n2); + Graph::Edge e2 = graph.addEdge(n1, n3); + Adaptor::Edge e3 = adaptor.addEdge(n2, n3); + Adaptor::Edge e4 = adaptor.addEdge(n3, n4); + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 8); + checkGraphEdgeList(adaptor, 4); + checkGraphConArcList(adaptor, 8); + checkGraphConEdgeList(adaptor, 4); + + checkGraphIncEdgeArcLists(adaptor, n1, 2); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 3); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide a node + adaptor.status(n1, false); + adaptor.disable(n3); + if (!adaptor.status(n3)) adaptor.enable(n3); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 4); + checkGraphEdgeList(adaptor, 2); + checkGraphConArcList(adaptor, 4); + checkGraphConEdgeList(adaptor, 2); + + checkGraphIncEdgeArcLists(adaptor, n2, 1); + checkGraphIncEdgeArcLists(adaptor, n3, 2); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide all nodes + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; + + checkGraphNodeList(adaptor, 0); + checkGraphArcList(adaptor, 0); + checkGraphEdgeList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + checkGraphConEdgeList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Check the conversion of nodes and edges + Graph::Node ng = n3; + ng = n4; + Adaptor::Node na = n1; + na = n2; + Graph::Edge eg = e3; + eg = e4; + Adaptor::Edge ea = e1; + ea = e2; +} + +void checkFilterEdges() { + // Check concepts + checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >(); + checkConcept<concepts::Graph, FilterEdges<ListGraph> >(); + checkConcept<concepts::AlterableGraphComponent<>, + FilterEdges<ListGraph> >(); + checkConcept<concepts::ExtendableGraphComponent<>, + FilterEdges<ListGraph> >(); + checkConcept<concepts::ErasableGraphComponent<>, + FilterEdges<ListGraph> >(); + checkConcept<concepts::ClearableGraphComponent<>, + FilterEdges<ListGraph> >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::EdgeMap<bool> EdgeFilter; + typedef FilterEdges<Graph, EdgeFilter> Adaptor; + + Graph graph; + EdgeFilter edge_filter(graph); + Adaptor adaptor(graph, edge_filter); + + // Add nodes and edges to the original graph and the adaptor + Graph::Node n1 = graph.addNode(); + Graph::Node n2 = graph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + Adaptor::Node n4 = adaptor.addNode(); + + Graph::Edge e1 = graph.addEdge(n1, n2); + Graph::Edge e2 = graph.addEdge(n1, n3); + Adaptor::Edge e3 = adaptor.addEdge(n2, n3); + Adaptor::Edge e4 = adaptor.addEdge(n3, n4); + + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 8); + checkGraphEdgeList(adaptor, 4); + checkGraphConArcList(adaptor, 8); + checkGraphConEdgeList(adaptor, 4); + + checkGraphIncEdgeArcLists(adaptor, n1, 2); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 3); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide an edge + adaptor.status(e2, false); + adaptor.disable(e3); + if (!adaptor.status(e3)) adaptor.enable(e3); + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 6); + checkGraphEdgeList(adaptor, 3); + checkGraphConArcList(adaptor, 6); + checkGraphConEdgeList(adaptor, 3); + + checkGraphIncEdgeArcLists(adaptor, n1, 1); + checkGraphIncEdgeArcLists(adaptor, n2, 2); + checkGraphIncEdgeArcLists(adaptor, n3, 2); + checkGraphIncEdgeArcLists(adaptor, n4, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Hide all edges + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; + + checkGraphNodeList(adaptor, 4); + checkGraphArcList(adaptor, 0); + checkGraphEdgeList(adaptor, 0); + checkGraphConArcList(adaptor, 0); + checkGraphConEdgeList(adaptor, 0); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + checkEdgeIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + checkGraphEdgeMap(adaptor); + + // Check the conversion of nodes and edges + Graph::Node ng = n3; + ng = n4; + Adaptor::Node na = n1; + na = n2; + Graph::Edge eg = e3; + eg = e4; + Adaptor::Edge ea = e1; + ea = e2; +} + +void checkOrienter() { + // Check concepts + checkConcept<concepts::Digraph, Orienter<concepts::Graph> >(); + checkConcept<concepts::Digraph, Orienter<ListGraph> >(); + checkConcept<concepts::AlterableDigraphComponent<>, + Orienter<ListGraph> >(); + checkConcept<concepts::ExtendableDigraphComponent<>, + Orienter<ListGraph> >(); + checkConcept<concepts::ErasableDigraphComponent<>, + Orienter<ListGraph> >(); + checkConcept<concepts::ClearableDigraphComponent<>, + Orienter<ListGraph> >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef ListGraph::EdgeMap<bool> DirMap; + typedef Orienter<Graph> Adaptor; + + Graph graph; + DirMap dir(graph); + Adaptor adaptor(graph, dir); + + // Add nodes and edges to the original graph and the adaptor + Graph::Node n1 = graph.addNode(); + Graph::Node n2 = graph.addNode(); + Adaptor::Node n3 = adaptor.addNode(); + + Graph::Edge e1 = graph.addEdge(n1, n2); + Graph::Edge e2 = graph.addEdge(n1, n3); + Adaptor::Arc e3 = adaptor.addArc(n2, n3); + + dir[e1] = dir[e2] = dir[e3] = true; + + // Check the original graph + checkGraphNodeList(graph, 3); + checkGraphArcList(graph, 6); + checkGraphConArcList(graph, 6); + checkGraphEdgeList(graph, 3); + checkGraphConEdgeList(graph, 3); + + checkGraphIncEdgeArcLists(graph, n1, 2); + checkGraphIncEdgeArcLists(graph, n2, 2); + checkGraphIncEdgeArcLists(graph, n3, 2); + + checkNodeIds(graph); + checkArcIds(graph); + checkEdgeIds(graph); + + checkGraphNodeMap(graph); + checkGraphArcMap(graph); + checkGraphEdgeMap(graph); + + // Check the adaptor + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 2); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 0); + + checkGraphInArcList(adaptor, n1, 0); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 2); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check direction changing + { + dir[e1] = true; + Adaptor::Node u = adaptor.source(e1); + Adaptor::Node v = adaptor.target(e1); + + dir[e1] = false; + check (u == adaptor.target(e1), "Wrong dir"); + check (v == adaptor.source(e1), "Wrong dir"); + + check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir"); + dir[e1] = n1 == u; + } + + { + dir[e2] = true; + Adaptor::Node u = adaptor.source(e2); + Adaptor::Node v = adaptor.target(e2); + + dir[e2] = false; + check (u == adaptor.target(e2), "Wrong dir"); + check (v == adaptor.source(e2), "Wrong dir"); + + check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir"); + dir[e2] = n3 == u; + } + + { + dir[e3] = true; + Adaptor::Node u = adaptor.source(e3); + Adaptor::Node v = adaptor.target(e3); + + dir[e3] = false; + check (u == adaptor.target(e3), "Wrong dir"); + check (v == adaptor.source(e3), "Wrong dir"); + + check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir"); + dir[e3] = n2 == u; + } + + // Check the adaptor again + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 1); + checkGraphOutArcList(adaptor, n2, 1); + checkGraphOutArcList(adaptor, n3, 1); + + checkGraphInArcList(adaptor, n1, 1); + checkGraphInArcList(adaptor, n2, 1); + checkGraphInArcList(adaptor, n3, 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check reverseArc() + adaptor.reverseArc(e2); + adaptor.reverseArc(e3); + adaptor.reverseArc(e2); + + checkGraphNodeList(adaptor, 3); + checkGraphArcList(adaptor, 3); + checkGraphConArcList(adaptor, 3); + + checkGraphOutArcList(adaptor, n1, 1); + checkGraphOutArcList(adaptor, n2, 0); + checkGraphOutArcList(adaptor, n3, 2); + + checkGraphInArcList(adaptor, n1, 1); + checkGraphInArcList(adaptor, n2, 2); + checkGraphInArcList(adaptor, n3, 0); + + // Check the conversion of nodes and arcs/edges + Graph::Node ng = n3; + ng = n3; + Adaptor::Node na = n1; + na = n2; + Graph::Edge eg = e3; + eg = e3; + Adaptor::Arc aa = e1; + aa = e2; +} + +void checkCombiningAdaptors() { + // Create a grid graph + GridGraph graph(2,2); + GridGraph::Node n1 = graph(0,0); + GridGraph::Node n2 = graph(0,1); + GridGraph::Node n3 = graph(1,0); + GridGraph::Node n4 = graph(1,1); + + GridGraph::EdgeMap<bool> dir_map(graph); + dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1; + dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1; + dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4; + dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4; + + // Apply several adaptors on the grid graph + typedef SplitNodes<Orienter< const GridGraph, GridGraph::EdgeMap<bool> > > + SplitGridGraph; + typedef Undirector<const SplitGridGraph> USplitGridGraph; + checkConcept<concepts::Digraph, SplitGridGraph>(); + checkConcept<concepts::Graph, USplitGridGraph>(); + + SplitGridGraph adaptor = splitNodes(orienter(graph, dir_map)); + USplitGridGraph uadaptor = undirector(adaptor); + + // Check adaptor + checkGraphNodeList(adaptor, 8); + checkGraphArcList(adaptor, 8); + checkGraphConArcList(adaptor, 8); + + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1); + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0); + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1); + checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1); + checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2); + + checkGraphInArcList(adaptor, adaptor.inNode(n1), 1); + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n2), 2); + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n3), 1); + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); + checkGraphInArcList(adaptor, adaptor.inNode(n4), 0); + checkGraphInArcList(adaptor, adaptor.outNode(n4), 1); + + checkNodeIds(adaptor); + checkArcIds(adaptor); + + checkGraphNodeMap(adaptor); + checkGraphArcMap(adaptor); + + // Check uadaptor + checkGraphNodeList(uadaptor, 8); + checkGraphEdgeList(uadaptor, 8); + checkGraphArcList(uadaptor, 16); + checkGraphConEdgeList(uadaptor, 8); + checkGraphConArcList(uadaptor, 16); + + checkNodeIds(uadaptor); + checkEdgeIds(uadaptor); + checkArcIds(uadaptor); + + checkGraphNodeMap(uadaptor); + checkGraphEdgeMap(uadaptor); + checkGraphArcMap(uadaptor); + + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2); + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1); + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3); +} + +int main(int, const char **) { + // Check the digraph adaptors (using ListDigraph) + checkReverseDigraph(); + checkSubDigraph(); + checkFilterNodes1(); + checkFilterArcs(); + checkUndirector(); + checkResidualDigraph(); + checkSplitNodes(); + + // Check the graph adaptors (using ListGraph) + checkSubGraph(); + checkFilterNodes2(); + checkFilterEdges(); + checkOrienter(); + + // Combine adaptors (using GridGraph) + checkCombiningAdaptors(); + + return 0; +} |