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