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 <iostream>
kpeter@463: #include <limits>
deba@414: 
kpeter@463: #include <lemon/list_graph.h>
kpeter@463: #include <lemon/grid_graph.h>
deba@414: #include <lemon/bfs.h>
deba@414: #include <lemon/path.h>
deba@414: 
kpeter@463: #include <lemon/concepts/digraph.h>
kpeter@463: #include <lemon/concepts/graph.h>
kpeter@463: #include <lemon/concepts/graph_components.h>
kpeter@463: #include <lemon/concepts/maps.h>
kpeter@463: #include <lemon/concept_check.h>
kpeter@463: 
kpeter@463: #include <lemon/adaptors.h>
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<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463:                ReverseDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463:                ReverseDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463:                ReverseDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463:                ReverseDigraph<ListDigraph> >();
deba@414: 
kpeter@463:   // Create a digraph and an adaptor
deba@414:   typedef ListDigraph Digraph;
deba@416:   typedef ReverseDigraph<Digraph> 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<concepts::Digraph, SubDigraph<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463:                SubDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463:                SubDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463:                SubDigraph<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463:                SubDigraph<ListDigraph> >();
deba@414: 
kpeter@463:   // Create a digraph and an adaptor
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::NodeMap<bool> NodeFilter;
deba@414:   typedef Digraph::ArcMap<bool> ArcFilter;
deba@416:   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> 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<concepts::Digraph, FilterNodes<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
kpeter@463:   checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463:                FilterNodes<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463:                FilterNodes<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463:                FilterNodes<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463:                FilterNodes<ListDigraph> >();
kpeter@463: 
kpeter@463:   // Create a digraph and an adaptor
kpeter@463:   typedef ListDigraph Digraph;
kpeter@463:   typedef Digraph::NodeMap<bool> NodeFilter;
kpeter@463:   typedef FilterNodes<Digraph, NodeFilter> 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<concepts::Digraph, FilterArcs<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
kpeter@463:   checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463:                FilterArcs<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463:                FilterArcs<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463:                FilterArcs<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463:                FilterArcs<ListDigraph> >();
kpeter@463: 
kpeter@463:   // Create a digraph and an adaptor
kpeter@463:   typedef ListDigraph Digraph;
kpeter@463:   typedef Digraph::ArcMap<bool> ArcFilter;
kpeter@463:   typedef FilterArcs<Digraph, ArcFilter> 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<concepts::Graph, Undirector<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Graph, Undirector<ListDigraph> >();
kpeter@463:   checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463:                Undirector<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463:                Undirector<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463:                Undirector<ListDigraph> >();
kpeter@463:   checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463:                Undirector<ListDigraph> >();
deba@414: 
kpeter@463: 
kpeter@463:   // Create a digraph and an adaptor
deba@414:   typedef ListDigraph Digraph;
deba@416:   typedef Undirector<Digraph> 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<int>, Digraph::ArcMap<int> > IntCombinedMap;
kpeter@463:   typedef Adaptor::CombinedArcMap
kpeter@463:     <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
kpeter@463:   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463:     IntCombinedMap>();
kpeter@463:   checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463:     BoolCombinedMap>();
kpeter@463: 
kpeter@463:   Digraph::ArcMap<int> 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<int>, Digraph::ArcMap<int> >
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<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
kpeter@464:   checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
deba@414: 
kpeter@463:   // Create a digraph and an adaptor
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::ArcMap<int> IntArcMap;
kpeter@464:   typedef ResidualDigraph<Digraph, IntArcMap> 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<Adaptor> bfs(adaptor);
deba@414:     bfs.run(n1, n4);
deba@416: 
deba@414:     if (!bfs.reached(n4)) break;
deba@414: 
deba@414:     Path<Adaptor> p = bfs.path(n4);
deba@416: 
deba@414:     int min = std::numeric_limits<int>::max();
deba@414:     for (Path<Adaptor>::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<Adaptor>::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<concepts::Digraph, SplitNodes<concepts::Digraph> >();
kpeter@463:   checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
deba@414: 
kpeter@463:   // Create a digraph and an adaptor
deba@414:   typedef ListDigraph Digraph;
deba@416:   typedef SplitNodes<Digraph> 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<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
kpeter@463:   typedef Adaptor::CombinedNodeMap
kpeter@463:     <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
kpeter@463:   checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
kpeter@463:     IntCombinedNodeMap>();
kpeter@463: //checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
kpeter@463: //  BoolCombinedNodeMap>();
kpeter@463:   checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
kpeter@463:     BoolCombinedNodeMap>();
kpeter@463: 
kpeter@463:   Digraph::NodeMap<int> 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<int>, Digraph::NodeMap<int> >
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::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
kpeter@463:   typedef Adaptor::CombinedArcMap
kpeter@463:     <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
kpeter@463:   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463:     IntCombinedArcMap>();
kpeter@463: //checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463: //  BoolCombinedArcMap>();
kpeter@463:   checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
kpeter@463:     BoolCombinedArcMap>();
kpeter@463: 
kpeter@463:   Digraph::ArcMap<int> 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::ArcMap<int>, Digraph::NodeMap<int> >
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<concepts::Graph, SubGraph<concepts::Graph> >();
kpeter@463:   checkConcept<concepts::Graph, SubGraph<ListGraph> >();
kpeter@463:   checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463:                SubGraph<ListGraph> >();
kpeter@463:   checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463:                SubGraph<ListGraph> >();
kpeter@463:   checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463:                SubGraph<ListGraph> >();
kpeter@463:   checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463:                SubGraph<ListGraph> >();
deba@414: 
kpeter@463:   // Create a graph and an adaptor
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::NodeMap<bool> NodeFilter;
deba@414:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416:   typedef SubGraph<Graph, NodeFilter, EdgeFilter> 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<concepts::Graph, FilterNodes<concepts::Graph> >();
kpeter@463:   checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
kpeter@463:   checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463:                FilterNodes<ListGraph> >();
kpeter@463:   checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463:                FilterNodes<ListGraph> >();
kpeter@463:   checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463:                FilterNodes<ListGraph> >();
kpeter@463:   checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463:                FilterNodes<ListGraph> >();
deba@414: 
kpeter@463:   // Create a graph and an adaptor
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::NodeMap<bool> NodeFilter;
deba@416:   typedef FilterNodes<Graph, NodeFilter> 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<concepts::Graph, FilterEdges<concepts::Graph> >();
kpeter@463:   checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
kpeter@463:   checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463:                FilterEdges<ListGraph> >();
kpeter@463:   checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463:                FilterEdges<ListGraph> >();
kpeter@463:   checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463:                FilterEdges<ListGraph> >();
kpeter@463:   checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463:                FilterEdges<ListGraph> >();
deba@414: 
kpeter@463:   // Create a graph and an adaptor
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416:   typedef FilterEdges<Graph, EdgeFilter> 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<concepts::Digraph, Orienter<concepts::Graph> >();
kpeter@463:   checkConcept<concepts::Digraph, Orienter<ListGraph> >();
kpeter@463:   checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463:                Orienter<ListGraph> >();
kpeter@463:   checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463:                Orienter<ListGraph> >();
kpeter@463:   checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463:                Orienter<ListGraph> >();
kpeter@463:   checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463:                Orienter<ListGraph> >();
deba@414: 
kpeter@463:   // Create a graph and an adaptor
deba@414:   typedef ListGraph Graph;
deba@414:   typedef ListGraph::EdgeMap<bool> DirMap;
deba@416:   typedef Orienter<Graph> 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<bool> 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
kpeter@463:   typedef SplitNodes< ReverseDigraph< const Orienter<
kpeter@463:             const GridGraph, GridGraph::EdgeMap<bool> > > >
kpeter@463:     RevSplitGridGraph;
kpeter@463:   typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
kpeter@463:   typedef Undirector<const SplitGridGraph> USplitGridGraph;
kpeter@463:   typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
kpeter@463:   checkConcept<concepts::Digraph, RevSplitGridGraph>();
kpeter@463:   checkConcept<concepts::Digraph, SplitGridGraph>();
kpeter@463:   checkConcept<concepts::Graph, USplitGridGraph>();
kpeter@463:   checkConcept<concepts::Graph, UUSplitGridGraph>();
kpeter@463: 
kpeter@463:   RevSplitGridGraph rev_adaptor =
kpeter@463:     splitNodes(reverseDigraph(orienter(graph, dir_map)));
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: }