deba@414: /* -*- C++ -*-
deba@414:  *
deba@414:  * This file is a part of LEMON, a generic C++ optimization library
deba@414:  *
deba@414:  * Copyright (C) 2003-2008
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: 
deba@414: #include<iostream>
deba@414: #include<lemon/concept_check.h>
deba@414: 
deba@414: #include<lemon/list_graph.h>
deba@414: #include<lemon/smart_graph.h>
deba@414: 
deba@414: #include<lemon/concepts/digraph.h>
deba@414: #include<lemon/concepts/graph.h>
deba@414: 
deba@414: #include<lemon/digraph_adaptor.h>
deba@414: #include<lemon/graph_adaptor.h>
deba@414: 
deba@414: #include <limits>
deba@414: #include <lemon/bfs.h>
deba@414: #include <lemon/path.h>
deba@414: 
deba@414: #include"test/test_tools.h"
deba@414: #include"test/graph_test.h"
deba@414: 
deba@414: using namespace lemon;
deba@414: 
deba@414: void checkDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef DigraphAdaptor<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);
deba@414:   
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: }
deba@414: 
deba@414: void checkRevDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef RevDigraphAdaptor<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);
deba@414:   
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: 
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:   }
deba@414: }
deba@414: 
deba@414: void checkSubDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, 
deba@414:     SubDigraphAdaptor<concepts::Digraph, 
deba@414:     concepts::Digraph::NodeMap<bool>,
deba@414:     concepts::Digraph::ArcMap<bool> > >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::NodeMap<bool> NodeFilter;
deba@414:   typedef Digraph::ArcMap<bool> ArcFilter;
deba@414:   typedef SubDigraphAdaptor<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: 
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);
deba@414: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@414:   
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: 
deba@414:   arc_filter[a2] = false; 
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: 
deba@414:   node_filter[n1] = false; 
deba@414: 
deba@414:   checkGraphNodeList(adaptor, 2);
deba@414:   checkGraphArcList(adaptor, 1);
deba@414:   checkGraphConArcList(adaptor, 1);
deba@414: 
deba@414:   checkGraphOutArcList(adaptor, n2, 1);
deba@414:   checkGraphOutArcList(adaptor, n3, 0);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n2, 0);
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: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@414:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@414: 
deba@414:   checkGraphNodeList(adaptor, 0);
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);
deba@414: }
deba@414: 
deba@414: void checkNodeSubDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, 
deba@414:     NodeSubDigraphAdaptor<concepts::Digraph, 
deba@414:       concepts::Digraph::NodeMap<bool> > >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::NodeMap<bool> NodeFilter;
deba@414:   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
deba@414: 
deba@414:   Digraph digraph;
deba@414:   NodeFilter node_filter(digraph);
deba@414:   Adaptor adaptor(digraph, node_filter);
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);
deba@414: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414:   
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: 
deba@414:   node_filter[n1] = false; 
deba@414: 
deba@414:   checkGraphNodeList(adaptor, 2);
deba@414:   checkGraphArcList(adaptor, 1);
deba@414:   checkGraphConArcList(adaptor, 1);
deba@414: 
deba@414:   checkGraphOutArcList(adaptor, n2, 1);
deba@414:   checkGraphOutArcList(adaptor, n3, 0);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n2, 0);
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: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@414: 
deba@414:   checkGraphNodeList(adaptor, 0);
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);
deba@414: }
deba@414: 
deba@414: void checkArcSubDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, 
deba@414:     ArcSubDigraphAdaptor<concepts::Digraph, 
deba@414:     concepts::Digraph::ArcMap<bool> > >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::ArcMap<bool> ArcFilter;
deba@414:   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
deba@414: 
deba@414:   Digraph digraph;
deba@414:   ArcFilter arc_filter(digraph);
deba@414:   Adaptor adaptor(digraph, arc_filter);
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);
deba@414: 
deba@414:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@414:   
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: 
deba@414:   arc_filter[a2] = false; 
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: 
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);
deba@414: }
deba@414: 
deba@414: void checkUndirDigraphAdaptor() {
deba@414:   checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef UndirDigraphAdaptor<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);
deba@414:   
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 2);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 2);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 2);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 2);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(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: 
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: 
deba@414: }
deba@414: 
deba@414: void checkResDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, 
deba@414:     ResDigraphAdaptor<concepts::Digraph, 
deba@414:     concepts::Digraph::ArcMap<int>, 
deba@414:     concepts::Digraph::ArcMap<int> > >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef Digraph::ArcMap<int> IntArcMap;
deba@414:   typedef ResDigraphAdaptor<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: 
deba@414:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414:     flow[a] = 0;
deba@414:   }
deba@414:   
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: 
deba@414:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414:     flow[a] = capacity[a] / 2;
deba@414:   }
deba@414:   
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: 
deba@414:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414:     flow[a] = capacity[a];
deba@414:   }
deba@414:   
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: 
deba@414:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414:     flow[a] = 0;
deba@414:   }
deba@414: 
deba@414:   int flow_value = 0;
deba@414:   while (true) {
deba@414:     
deba@414:     Bfs<Adaptor> bfs(adaptor);
deba@414:     bfs.run(n1, n4);
deba@414:     
deba@414:     if (!bfs.reached(n4)) break;
deba@414: 
deba@414:     Path<Adaptor> p = bfs.path(n4);
deba@414:     
deba@414:     int min = std::numeric_limits<int>::max();
deba@414:     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@414:       if (adaptor.rescap(a) < min) min = adaptor.rescap(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: 
deba@414: }
deba@414: 
deba@414: void checkSplitDigraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
deba@414: 
deba@414:   typedef ListDigraph Digraph;
deba@414:   typedef SplitDigraphAdaptor<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);
deba@414:   
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@414:   
deba@414:   checkGraphNodeMap(adaptor);
deba@414:   checkGraphArcMap(adaptor);
deba@414: 
deba@414:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414:     if (adaptor.origArc(a)) {
deba@414:       Digraph::Arc oa = a;
deba@414:       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 
deba@414: 	    "Wrong split");
deba@414:       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 
deba@414: 	    "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:   }
deba@414: }
deba@414: 
deba@414: void checkGraphAdaptor() {
deba@414:   checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
deba@414: 
deba@414:   typedef ListGraph Graph;
deba@414:   typedef GraphAdaptor<Graph> Adaptor;
deba@414: 
deba@414:   Graph graph;
deba@414:   Adaptor adaptor(graph);
deba@414: 
deba@414:   Graph::Node n1 = graph.addNode();
deba@414:   Graph::Node n2 = graph.addNode();
deba@414:   Graph::Node n3 = graph.addNode();
deba@414:   Graph::Node n4 = graph.addNode();
deba@414: 
deba@414:   Graph::Edge a1 = graph.addEdge(n1, n2);
deba@414:   Graph::Edge a2 = graph.addEdge(n1, n3);
deba@414:   Graph::Edge a3 = graph.addEdge(n2, n3);
deba@414:   Graph::Edge a4 = graph.addEdge(n3, n4);
deba@414:   
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 2);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 3);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 2);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 3);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@414:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@414: 
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: }
deba@414: 
deba@414: void checkSubGraphAdaptor() {
deba@414:   checkConcept<concepts::Graph, 
deba@414:     SubGraphAdaptor<concepts::Graph, 
deba@414:     concepts::Graph::NodeMap<bool>,
deba@414:     concepts::Graph::EdgeMap<bool> > >();
deba@414: 
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::NodeMap<bool> NodeFilter;
deba@414:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@414:   typedef SubGraphAdaptor<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: 
deba@414:   Graph::Node n1 = graph.addNode();
deba@414:   Graph::Node n2 = graph.addNode();
deba@414:   Graph::Node n3 = graph.addNode();
deba@414:   Graph::Node n4 = graph.addNode();
deba@414: 
deba@414:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@414:   
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 2);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 3);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 2);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 3);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@414:   checkGraphIncEdgeList(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: 
deba@414:   edge_filter[e2] = false; 
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 1);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 2);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 1);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 2);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 1);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@414:   checkGraphIncEdgeList(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: 
deba@414:   node_filter[n1] = false; 
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: 
deba@414:   checkGraphOutArcList(adaptor, n2, 1);
deba@414:   checkGraphOutArcList(adaptor, n3, 2);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n2, 1);
deba@414:   checkGraphInArcList(adaptor, n3, 2);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n2, 1);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@414:   checkGraphIncEdgeList(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: 
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);
deba@414: }
deba@414: 
deba@414: void checkNodeSubGraphAdaptor() {
deba@414:   checkConcept<concepts::Graph, 
deba@414:     NodeSubGraphAdaptor<concepts::Graph, 
deba@414:       concepts::Graph::NodeMap<bool> > >();
deba@414: 
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::NodeMap<bool> NodeFilter;
deba@414:   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
deba@414: 
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();
deba@414:   Graph::Node n3 = graph.addNode();
deba@414:   Graph::Node n4 = graph.addNode();
deba@414: 
deba@414:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414: 
deba@414:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414:   
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 2);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 3);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 2);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 3);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@414:   checkGraphIncEdgeList(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: 
deba@414:   node_filter[n1] = false; 
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: 
deba@414:   checkGraphOutArcList(adaptor, n2, 1);
deba@414:   checkGraphOutArcList(adaptor, n3, 2);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n2, 1);
deba@414:   checkGraphInArcList(adaptor, n3, 2);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n2, 1);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@414:   checkGraphIncEdgeList(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: 
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);
deba@414: }
deba@414: 
deba@414: void checkEdgeSubGraphAdaptor() {
deba@414:   checkConcept<concepts::Graph, 
deba@414:     EdgeSubGraphAdaptor<concepts::Graph, 
deba@414:     concepts::Graph::EdgeMap<bool> > >();
deba@414: 
deba@414:   typedef ListGraph Graph;
deba@414:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@414:   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
deba@414: 
deba@414:   Graph graph;
deba@414:   EdgeFilter edge_filter(graph);
deba@414:   Adaptor adaptor(graph, edge_filter);
deba@414: 
deba@414:   Graph::Node n1 = graph.addNode();
deba@414:   Graph::Node n2 = graph.addNode();
deba@414:   Graph::Node n3 = graph.addNode();
deba@414:   Graph::Node n4 = graph.addNode();
deba@414: 
deba@414:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@414: 
deba@414:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@414:   
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 2);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 3);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 2);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 3);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@414:   checkGraphIncEdgeList(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: 
deba@414:   edge_filter[e2] = false; 
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: 
deba@414:   checkGraphOutArcList(adaptor, n1, 1);
deba@414:   checkGraphOutArcList(adaptor, n2, 2);
deba@414:   checkGraphOutArcList(adaptor, n3, 2);
deba@414:   checkGraphOutArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphInArcList(adaptor, n1, 1);
deba@414:   checkGraphInArcList(adaptor, n2, 2);
deba@414:   checkGraphInArcList(adaptor, n3, 2);
deba@414:   checkGraphInArcList(adaptor, n4, 1);
deba@414: 
deba@414:   checkGraphIncEdgeList(adaptor, n1, 1);
deba@414:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@414:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@414:   checkGraphIncEdgeList(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: 
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);
deba@414: }
deba@414: 
deba@414: void checkDirGraphAdaptor() {
deba@414:   checkConcept<concepts::Digraph, 
deba@414:     DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
deba@414: 
deba@414:   typedef ListGraph Graph;
deba@414:   typedef ListGraph::EdgeMap<bool> DirMap;
deba@414:   typedef DirGraphAdaptor<Graph> Adaptor;
deba@414: 
deba@414:   Graph graph;
deba@414:   DirMap dir(graph, true);
deba@414:   Adaptor adaptor(graph, dir);
deba@414: 
deba@414:   Graph::Node n1 = graph.addNode();
deba@414:   Graph::Node n2 = graph.addNode();
deba@414:   Graph::Node n3 = graph.addNode();
deba@414: 
deba@414:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@414:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@414:   
deba@414:   checkGraphNodeList(adaptor, 3);
deba@414:   checkGraphArcList(adaptor, 3);
deba@414:   checkGraphConArcList(adaptor, 3);
deba@414:   
deba@414:   {
deba@414:     dir[e1] = true;
deba@414:     Adaptor::Node u = adaptor.source(e1);
deba@414:     Adaptor::Node v = adaptor.target(e1);
deba@414:     
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@414:     
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@414:     
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: 
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: 
deba@414: }
deba@414: 
deba@414: 
deba@414: int main(int, const char **) {
deba@414: 
deba@414:   checkDigraphAdaptor();
deba@414:   checkRevDigraphAdaptor();
deba@414:   checkSubDigraphAdaptor();
deba@414:   checkNodeSubDigraphAdaptor();
deba@414:   checkArcSubDigraphAdaptor();
deba@414:   checkUndirDigraphAdaptor();
deba@414:   checkResDigraphAdaptor();
deba@414:   checkSplitDigraphAdaptor();
deba@414: 
deba@414:   checkGraphAdaptor();
deba@414:   checkSubGraphAdaptor();
deba@414:   checkNodeSubGraphAdaptor();
deba@414:   checkEdgeSubGraphAdaptor();
deba@414:   checkDirGraphAdaptor();
deba@414: 
deba@414:   return 0;
deba@414: }