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