diff --git a/test/adaptors_test.cc b/test/adaptors_test.cc new file mode 100644 --- /dev/null +++ b/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 +#include + +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +#include + +#include "test/test_tools.h" +#include "test/graph_test.h" + +using namespace lemon; + +void checkReverseDigraph() { + // Check concepts + checkConcept >(); + checkConcept >(); + checkConcept, + ReverseDigraph >(); + checkConcept, + ReverseDigraph >(); + checkConcept, + ReverseDigraph >(); + checkConcept, + ReverseDigraph >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef ReverseDigraph 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 >(); + checkConcept >(); + checkConcept, + SubDigraph >(); + checkConcept, + SubDigraph >(); + checkConcept, + SubDigraph >(); + checkConcept, + SubDigraph >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::NodeMap NodeFilter; + typedef Digraph::ArcMap ArcFilter; + typedef SubDigraph 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 >(); + checkConcept >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::NodeMap NodeFilter; + typedef FilterNodes 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 >(); + checkConcept >(); + checkConcept, + FilterArcs >(); + checkConcept, + FilterArcs >(); + checkConcept, + FilterArcs >(); + checkConcept, + FilterArcs >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::ArcMap ArcFilter; + typedef FilterArcs 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 >(); + checkConcept >(); + checkConcept, + Undirector >(); + checkConcept, + Undirector >(); + checkConcept, + Undirector >(); + checkConcept, + Undirector >(); + + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Undirector 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 > IntCombinedMap; + typedef Adaptor::CombinedArcMap + , Digraph::ArcMap > BoolCombinedMap; + checkConcept, + IntCombinedMap>(); + checkConcept, + BoolCombinedMap>(); + + Digraph::ArcMap 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 > + 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 >(); + checkConcept >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef Digraph::ArcMap IntArcMap; + typedef ResidualDigraph 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 bfs(adaptor); + bfs.run(n1, n4); + + if (!bfs.reached(n4)) break; + + Path p = bfs.path(n4); + + int min = std::numeric_limits::max(); + for (Path::ArcIt a(p); a != INVALID; ++a) { + if (res_cap[a] < min) min = res_cap[a]; + } + + for (Path::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 >(); + checkConcept >(); + + // Create a digraph and an adaptor + typedef ListDigraph Digraph; + typedef SplitNodes 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 > IntCombinedNodeMap; + typedef Adaptor::CombinedNodeMap + , Digraph::NodeMap > BoolCombinedNodeMap; + checkConcept, + IntCombinedNodeMap>(); +//checkConcept, +// BoolCombinedNodeMap>(); + checkConcept, + BoolCombinedNodeMap>(); + + Digraph::NodeMap 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 > + 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::NodeMap > IntCombinedArcMap; + typedef Adaptor::CombinedArcMap + , Digraph::NodeMap > BoolCombinedArcMap; + checkConcept, + IntCombinedArcMap>(); +//checkConcept, +// BoolCombinedArcMap>(); + checkConcept, + BoolCombinedArcMap>(); + + Digraph::ArcMap a_map(digraph); + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) { + a_map[a] = digraph.id(a); + } + + Adaptor::CombinedArcMap, Digraph::NodeMap > + 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 >(); + checkConcept >(); + checkConcept, + SubGraph >(); + checkConcept, + SubGraph >(); + checkConcept, + SubGraph >(); + checkConcept, + SubGraph >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::NodeMap NodeFilter; + typedef Graph::EdgeMap EdgeFilter; + typedef SubGraph 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 >(); + checkConcept >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + checkConcept, + FilterNodes >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::NodeMap NodeFilter; + typedef FilterNodes 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 >(); + checkConcept >(); + checkConcept, + FilterEdges >(); + checkConcept, + FilterEdges >(); + checkConcept, + FilterEdges >(); + checkConcept, + FilterEdges >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef Graph::EdgeMap EdgeFilter; + typedef FilterEdges 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 >(); + checkConcept >(); + checkConcept, + Orienter >(); + checkConcept, + Orienter >(); + checkConcept, + Orienter >(); + checkConcept, + Orienter >(); + + // Create a graph and an adaptor + typedef ListGraph Graph; + typedef ListGraph::EdgeMap DirMap; + typedef Orienter 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 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 > > + SplitGridGraph; + typedef Undirector USplitGridGraph; + checkConcept(); + checkConcept(); + + 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; +}