deba@432: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@430:  *
deba@432:  * This file is a part of LEMON, a generic C++ optimization library.
deba@430:  *
deba@430:  * Copyright (C) 2003-2008
deba@430:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@430:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@430:  *
deba@430:  * Permission to use, modify and distribute this software is granted
deba@430:  * provided that this copyright notice appears in all copies. For
deba@430:  * precise terms see the accompanying LICENSE file.
deba@430:  *
deba@430:  * This software is provided "AS IS" with no warranty of any kind,
deba@430:  * express or implied, and with no claim as to its suitability for any
deba@430:  * purpose.
deba@430:  *
deba@430:  */
deba@430: 
deba@430: #include<iostream>
deba@430: #include<lemon/concept_check.h>
deba@430: 
deba@430: #include<lemon/list_graph.h>
deba@430: #include<lemon/smart_graph.h>
deba@430: 
deba@430: #include<lemon/concepts/digraph.h>
deba@430: #include<lemon/concepts/graph.h>
deba@430: 
deba@432: #include<lemon/adaptors.h>
deba@430: 
deba@430: #include <limits>
deba@430: #include <lemon/bfs.h>
deba@430: #include <lemon/path.h>
deba@430: 
deba@430: #include"test/test_tools.h"
deba@430: #include"test/graph_test.h"
deba@430: 
deba@430: using namespace lemon;
deba@430: 
deba@432: void checkReverseDigraph() {
deba@432:   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@432:   typedef ReverseDigraph<Digraph> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   Adaptor adaptor(digraph);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 0);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 2);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
deba@430:     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
deba@430:   }
deba@430: }
deba@430: 
deba@432: void checkSubDigraph() {
deba@432:   checkConcept<concepts::Digraph,
deba@432:     SubDigraph<concepts::Digraph,
deba@430:     concepts::Digraph::NodeMap<bool>,
deba@430:     concepts::Digraph::ArcMap<bool> > >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@430:   typedef Digraph::NodeMap<bool> NodeFilter;
deba@430:   typedef Digraph::ArcMap<bool> ArcFilter;
deba@432:   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   NodeFilter node_filter(digraph);
deba@430:   ArcFilter arc_filter(digraph);
deba@430:   Adaptor adaptor(digraph, node_filter, arc_filter);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@430:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@432:   arc_filter[a2] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 2);
deba@430:   checkGraphConArcList(adaptor, 2);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 1);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@432:   node_filter[n1] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 2);
deba@430:   checkGraphArcList(adaptor, 1);
deba@430:   checkGraphConArcList(adaptor, 1);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n2, 0);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@430:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 0);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkFilterNodes1() {
deba@432:   checkConcept<concepts::Digraph,
deba@432:     FilterNodes<concepts::Digraph,
deba@430:       concepts::Digraph::NodeMap<bool> > >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@430:   typedef Digraph::NodeMap<bool> NodeFilter;
deba@432:   typedef FilterNodes<Digraph, NodeFilter> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   NodeFilter node_filter(digraph);
deba@430:   Adaptor adaptor(digraph, node_filter);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@432:   node_filter[n1] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 2);
deba@430:   checkGraphArcList(adaptor, 1);
deba@430:   checkGraphConArcList(adaptor, 1);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n2, 0);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 0);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkFilterArcs() {
deba@432:   checkConcept<concepts::Digraph,
deba@432:     FilterArcs<concepts::Digraph,
deba@430:     concepts::Digraph::ArcMap<bool> > >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@430:   typedef Digraph::ArcMap<bool> ArcFilter;
deba@432:   typedef FilterArcs<Digraph, ArcFilter> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   ArcFilter arc_filter(digraph);
deba@430:   Adaptor adaptor(digraph, arc_filter);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@430: 
deba@430:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@432:   arc_filter[a2] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 2);
deba@430:   checkGraphConArcList(adaptor, 2);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 1);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkUndirector() {
deba@432:   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@432:   typedef Undirector<Digraph> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   Adaptor adaptor(digraph);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphEdgeList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430:   checkGraphConEdgeList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 2);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@430:   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
deba@430:     check(adaptor.u(e) == digraph.source(e), "Wrong undir");
deba@430:     check(adaptor.v(e) == digraph.target(e), "Wrong undir");
deba@430:   }
deba@430: 
deba@430: }
deba@430: 
deba@432: void checkResidual() {
deba@432:   checkConcept<concepts::Digraph,
deba@432:     Residual<concepts::Digraph,
deba@432:     concepts::Digraph::ArcMap<int>,
deba@430:     concepts::Digraph::ArcMap<int> > >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@430:   typedef Digraph::ArcMap<int> IntArcMap;
deba@432:   typedef Residual<Digraph, IntArcMap> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   IntArcMap capacity(digraph), flow(digraph);
deba@430:   Adaptor adaptor(digraph, capacity, flow);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430:   Digraph::Node n4 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n1, n4);
deba@430:   Digraph::Arc a4 = digraph.addArc(n2, n3);
deba@430:   Digraph::Arc a5 = digraph.addArc(n2, n4);
deba@430:   Digraph::Arc a6 = digraph.addArc(n3, n4);
deba@430: 
deba@430:   capacity[a1] = 8;
deba@430:   capacity[a2] = 6;
deba@430:   capacity[a3] = 4;
deba@430:   capacity[a4] = 4;
deba@430:   capacity[a5] = 6;
deba@430:   capacity[a6] = 10;
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     flow[a] = 0;
deba@430:   }
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 3);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 1);
deba@430:   checkGraphOutArcList(adaptor, n4, 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 0);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430:   checkGraphInArcList(adaptor, n4, 3);
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     flow[a] = capacity[a] / 2;
deba@430:   }
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 12);
deba@430:   checkGraphConArcList(adaptor, 12);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 3);
deba@430:   checkGraphOutArcList(adaptor, n2, 3);
deba@430:   checkGraphOutArcList(adaptor, n3, 3);
deba@430:   checkGraphOutArcList(adaptor, n4, 3);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 3);
deba@430:   checkGraphInArcList(adaptor, n2, 3);
deba@430:   checkGraphInArcList(adaptor, n3, 3);
deba@430:   checkGraphInArcList(adaptor, n4, 3);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     flow[a] = capacity[a];
deba@430:   }
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 0);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430:   checkGraphOutArcList(adaptor, n4, 3);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 3);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430:   checkGraphInArcList(adaptor, n4, 0);
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     flow[a] = 0;
deba@430:   }
deba@430: 
deba@430:   int flow_value = 0;
deba@430:   while (true) {
deba@432: 
deba@430:     Bfs<Adaptor> bfs(adaptor);
deba@430:     bfs.run(n1, n4);
deba@432: 
deba@430:     if (!bfs.reached(n4)) break;
deba@430: 
deba@430:     Path<Adaptor> p = bfs.path(n4);
deba@432: 
deba@430:     int min = std::numeric_limits<int>::max();
deba@430:     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@432:       if (adaptor.residualCapacity(a) < min)
deba@432:         min = adaptor.residualCapacity(a);
deba@430:     }
deba@430: 
deba@430:     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@430:       adaptor.augment(a, min);
deba@430:     }
deba@430:     flow_value += min;
deba@430:   }
deba@430: 
deba@430:   check(flow_value == 18, "Wrong flow with res graph adaptor");
deba@430: 
deba@430: }
deba@430: 
deba@432: void checkSplitNodes() {
deba@432:   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
deba@430: 
deba@430:   typedef ListDigraph Digraph;
deba@432:   typedef SplitNodes<Digraph> Adaptor;
deba@430: 
deba@430:   Digraph digraph;
deba@430:   Adaptor adaptor(digraph);
deba@430: 
deba@430:   Digraph::Node n1 = digraph.addNode();
deba@430:   Digraph::Node n2 = digraph.addNode();
deba@430:   Digraph::Node n3 = digraph.addNode();
deba@430: 
deba@430:   Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@430:   Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@430:   Digraph::Arc a3 = digraph.addArc(n2, n3);
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 6);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
deba@430:   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
deba@430:   checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
deba@430:   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
deba@430:   checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
deba@430:   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
deba@430:   checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
deba@430:   checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
deba@430:   checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
deba@430:   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
deba@430:   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@432: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430:   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@430:     if (adaptor.origArc(a)) {
deba@430:       Digraph::Arc oa = a;
deba@432:       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
deba@432:             "Wrong split");
deba@432:       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
deba@432:             "Wrong split");
deba@430:     } else {
deba@430:       Digraph::Node on = a;
deba@430:       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
deba@430:       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
deba@430:     }
deba@430:   }
deba@430: }
deba@430: 
deba@432: void checkSubGraph() {
deba@432:   checkConcept<concepts::Graph,
deba@432:     SubGraph<concepts::Graph,
deba@430:     concepts::Graph::NodeMap<bool>,
deba@430:     concepts::Graph::EdgeMap<bool> > >();
deba@430: 
deba@430:   typedef ListGraph Graph;
deba@430:   typedef Graph::NodeMap<bool> NodeFilter;
deba@430:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@432:   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
deba@430: 
deba@430:   Graph graph;
deba@430:   NodeFilter node_filter(graph);
deba@430:   EdgeFilter edge_filter(graph);
deba@430:   Adaptor adaptor(graph, node_filter, edge_filter);
deba@430: 
deba@430:   Graph::Node n1 = graph.addNode();
deba@430:   Graph::Node n2 = graph.addNode();
deba@430:   Graph::Node n3 = graph.addNode();
deba@430:   Graph::Node n4 = graph.addNode();
deba@430: 
deba@430:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@430:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@430:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@430:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@430:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 8);
deba@430:   checkGraphEdgeList(adaptor, 4);
deba@430:   checkGraphConArcList(adaptor, 8);
deba@430:   checkGraphConEdgeList(adaptor, 4);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 3);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 2);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 3);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@432:   edge_filter[e2] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphEdgeList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430:   checkGraphConEdgeList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 1);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 1);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 1);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@432:   node_filter[n1] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 4);
deba@430:   checkGraphEdgeList(adaptor, 2);
deba@430:   checkGraphConArcList(adaptor, 4);
deba@430:   checkGraphConEdgeList(adaptor, 2);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n2, 1);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@430:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 0);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphEdgeList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430:   checkGraphConEdgeList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkFilterNodes2() {
deba@432:   checkConcept<concepts::Graph,
deba@432:     FilterNodes<concepts::Graph,
deba@430:       concepts::Graph::NodeMap<bool> > >();
deba@430: 
deba@430:   typedef ListGraph Graph;
deba@430:   typedef Graph::NodeMap<bool> NodeFilter;
deba@432:   typedef FilterNodes<Graph, NodeFilter> Adaptor;
deba@430: 
deba@430:   Graph graph;
deba@430:   NodeFilter node_filter(graph);
deba@430:   Adaptor adaptor(graph, node_filter);
deba@430: 
deba@430:   Graph::Node n1 = graph.addNode();
deba@430:   Graph::Node n2 = graph.addNode();
deba@430:   Graph::Node n3 = graph.addNode();
deba@430:   Graph::Node n4 = graph.addNode();
deba@430: 
deba@430:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@430:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@430:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@430:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 8);
deba@430:   checkGraphEdgeList(adaptor, 4);
deba@430:   checkGraphConArcList(adaptor, 8);
deba@430:   checkGraphConEdgeList(adaptor, 4);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 3);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 2);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 3);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@432:   node_filter[n1] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 4);
deba@430:   checkGraphEdgeList(adaptor, 2);
deba@430:   checkGraphConArcList(adaptor, 4);
deba@430:   checkGraphConEdgeList(adaptor, 2);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n2, 1);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@430:   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 0);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphEdgeList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430:   checkGraphConEdgeList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkFilterEdges() {
deba@432:   checkConcept<concepts::Graph,
deba@432:     FilterEdges<concepts::Graph,
deba@430:     concepts::Graph::EdgeMap<bool> > >();
deba@430: 
deba@430:   typedef ListGraph Graph;
deba@430:   typedef Graph::EdgeMap<bool> EdgeFilter;
deba@432:   typedef FilterEdges<Graph, EdgeFilter> Adaptor;
deba@430: 
deba@430:   Graph graph;
deba@430:   EdgeFilter edge_filter(graph);
deba@430:   Adaptor adaptor(graph, edge_filter);
deba@430: 
deba@430:   Graph::Node n1 = graph.addNode();
deba@430:   Graph::Node n2 = graph.addNode();
deba@430:   Graph::Node n3 = graph.addNode();
deba@430:   Graph::Node n4 = graph.addNode();
deba@430: 
deba@430:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@430:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@430:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@430:   Graph::Edge e4 = graph.addEdge(n3, n4);
deba@430: 
deba@430:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
deba@430:   
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 8);
deba@430:   checkGraphEdgeList(adaptor, 4);
deba@430:   checkGraphConArcList(adaptor, 8);
deba@430:   checkGraphConEdgeList(adaptor, 4);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 2);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 3);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 2);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 3);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 3);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@432:   edge_filter[e2] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 6);
deba@430:   checkGraphEdgeList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 6);
deba@430:   checkGraphConEdgeList(adaptor, 3);
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 1);
deba@430:   checkGraphOutArcList(adaptor, n2, 2);
deba@430:   checkGraphOutArcList(adaptor, n3, 2);
deba@430:   checkGraphOutArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 1);
deba@430:   checkGraphInArcList(adaptor, n2, 2);
deba@430:   checkGraphInArcList(adaptor, n3, 2);
deba@430:   checkGraphInArcList(adaptor, n4, 1);
deba@430: 
deba@430:   checkGraphIncEdgeList(adaptor, n1, 1);
deba@430:   checkGraphIncEdgeList(adaptor, n2, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n3, 2);
deba@430:   checkGraphIncEdgeList(adaptor, n4, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: 
deba@430:   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@430: 
deba@430:   checkGraphNodeList(adaptor, 4);
deba@430:   checkGraphArcList(adaptor, 0);
deba@430:   checkGraphEdgeList(adaptor, 0);
deba@430:   checkGraphConArcList(adaptor, 0);
deba@430:   checkGraphConEdgeList(adaptor, 0);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430:   checkEdgeIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430:   checkGraphEdgeMap(adaptor);
deba@430: }
deba@430: 
deba@432: void checkOrienter() {
deba@432:   checkConcept<concepts::Digraph,
deba@432:     Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
deba@430: 
deba@430:   typedef ListGraph Graph;
deba@430:   typedef ListGraph::EdgeMap<bool> DirMap;
deba@432:   typedef Orienter<Graph> Adaptor;
deba@430: 
deba@430:   Graph graph;
deba@430:   DirMap dir(graph, true);
deba@430:   Adaptor adaptor(graph, dir);
deba@430: 
deba@430:   Graph::Node n1 = graph.addNode();
deba@430:   Graph::Node n2 = graph.addNode();
deba@430:   Graph::Node n3 = graph.addNode();
deba@430: 
deba@430:   Graph::Edge e1 = graph.addEdge(n1, n2);
deba@430:   Graph::Edge e2 = graph.addEdge(n1, n3);
deba@430:   Graph::Edge e3 = graph.addEdge(n2, n3);
deba@432: 
deba@430:   checkGraphNodeList(adaptor, 3);
deba@430:   checkGraphArcList(adaptor, 3);
deba@430:   checkGraphConArcList(adaptor, 3);
deba@432: 
deba@430:   {
deba@430:     dir[e1] = true;
deba@430:     Adaptor::Node u = adaptor.source(e1);
deba@430:     Adaptor::Node v = adaptor.target(e1);
deba@432: 
deba@430:     dir[e1] = false;
deba@430:     check (u == adaptor.target(e1), "Wrong dir");
deba@430:     check (v == adaptor.source(e1), "Wrong dir");
deba@430: 
deba@430:     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
deba@430:     dir[e1] = n1 == u;
deba@430:   }
deba@430: 
deba@430:   {
deba@430:     dir[e2] = true;
deba@430:     Adaptor::Node u = adaptor.source(e2);
deba@430:     Adaptor::Node v = adaptor.target(e2);
deba@432: 
deba@430:     dir[e2] = false;
deba@430:     check (u == adaptor.target(e2), "Wrong dir");
deba@430:     check (v == adaptor.source(e2), "Wrong dir");
deba@430: 
deba@430:     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
deba@430:     dir[e2] = n3 == u;
deba@430:   }
deba@430: 
deba@430:   {
deba@430:     dir[e3] = true;
deba@430:     Adaptor::Node u = adaptor.source(e3);
deba@430:     Adaptor::Node v = adaptor.target(e3);
deba@432: 
deba@430:     dir[e3] = false;
deba@430:     check (u == adaptor.target(e3), "Wrong dir");
deba@430:     check (v == adaptor.source(e3), "Wrong dir");
deba@430: 
deba@430:     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
deba@430:     dir[e3] = n2 == u;
deba@430:   }
deba@430: 
deba@430:   checkGraphOutArcList(adaptor, n1, 1);
deba@430:   checkGraphOutArcList(adaptor, n2, 1);
deba@430:   checkGraphOutArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkGraphInArcList(adaptor, n1, 1);
deba@430:   checkGraphInArcList(adaptor, n2, 1);
deba@430:   checkGraphInArcList(adaptor, n3, 1);
deba@430: 
deba@430:   checkNodeIds(adaptor);
deba@430:   checkArcIds(adaptor);
deba@430: 
deba@430:   checkGraphNodeMap(adaptor);
deba@430:   checkGraphArcMap(adaptor);
deba@430: 
deba@430: }
deba@430: 
deba@430: 
deba@430: int main(int, const char **) {
deba@430: 
deba@432:   checkReverseDigraph();
deba@432:   checkSubDigraph();
deba@432:   checkFilterNodes1();
deba@432:   checkFilterArcs();
deba@432:   checkUndirector();
deba@432:   checkResidual();
deba@432:   checkSplitNodes();
deba@430: 
deba@432:   checkSubGraph();
deba@432:   checkFilterNodes2();
deba@432:   checkFilterEdges();
deba@432:   checkOrienter();
deba@430: 
deba@430:   return 0;
deba@430: }