/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <iostream>

#include <limits>

#include <lemon/list_graph.h>

#include <lemon/grid_graph.h>

#include <lemon/bfs.h>

#include <lemon/path.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/graph.h>

#include <lemon/concepts/graph_components.h>

#include <lemon/concepts/maps.h>

#include <lemon/concept_check.h>

#include <lemon/adaptors.h>

#include "test/test_tools.h"

#include "test/graph_test.h"

using namespace lemon;

void checkReverseDigraph() {

  // Check concepts

  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();

  checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();

  checkConcept<concepts::AlterableDigraphComponent<>,

               ReverseDigraph<ListDigraph> >();

  checkConcept<concepts::ExtendableDigraphComponent<>,

               ReverseDigraph<ListDigraph> >();

  checkConcept<concepts::ErasableDigraphComponent<>,

               ReverseDigraph<ListDigraph> >();

  checkConcept<concepts::ClearableDigraphComponent<>,

               ReverseDigraph<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef ReverseDigraph<Digraph> Adaptor;

  Digraph digraph;

  Adaptor adaptor(digraph);

  // Add nodes and arcs to the original digraph

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n2, n3);

  // Check the adaptor

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 0);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 2);

  checkGraphInArcList(adaptor, n1, 2);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check the orientation of the arcs

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");

    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");

  }

  // Add and erase nodes and arcs in the digraph through the adaptor

  Adaptor::Node n4 = adaptor.addNode();

  Adaptor::Arc a4 = adaptor.addArc(n4, n3);

  Adaptor::Arc a5 = adaptor.addArc(n2, n4);

  Adaptor::Arc a6 = adaptor.addArc(n2, n4);

  Adaptor::Arc a7 = adaptor.addArc(n1, n4);

  Adaptor::Arc a8 = adaptor.addArc(n1, n2);

  adaptor.erase(a1);

  adaptor.erase(n3);

  // Check the adaptor

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 4);

  checkGraphConArcList(adaptor, 4);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 2);

  checkGraphOutArcList(adaptor, n4, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n4, 3);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check the digraph

  checkGraphNodeList(digraph, 3);

  checkGraphArcList(digraph, 4);

  checkGraphConArcList(digraph, 4);

  checkGraphOutArcList(digraph, n1, 0);

  checkGraphOutArcList(digraph, n2, 1);

  checkGraphOutArcList(digraph, n4, 3);

  checkGraphInArcList(digraph, n1, 2);

  checkGraphInArcList(digraph, n2, 2);

  checkGraphInArcList(digraph, n4, 0);

  checkNodeIds(digraph);

  checkArcIds(digraph);

  checkGraphNodeMap(digraph);

  checkGraphArcMap(digraph);

  // Check the conversion of nodes and arcs

  Digraph::Node nd = n4;

  nd = n4;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = a4;

  ad = a5;

  Adaptor::Arc aa = a1;

  aa = a2;

}

void checkSubDigraph() {

  // Check concepts

  checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();

  checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();

  checkConcept<concepts::AlterableDigraphComponent<>,

               SubDigraph<ListDigraph> >();

  checkConcept<concepts::ExtendableDigraphComponent<>,

               SubDigraph<ListDigraph> >();

  checkConcept<concepts::ErasableDigraphComponent<>,

               SubDigraph<ListDigraph> >();

  checkConcept<concepts::ClearableDigraphComponent<>,

               SubDigraph<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Digraph::NodeMap<bool> NodeFilter;

  typedef Digraph::ArcMap<bool> ArcFilter;

  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;

  Digraph digraph;

  NodeFilter node_filter(digraph);

  ArcFilter arc_filter(digraph);

  Adaptor adaptor(digraph, node_filter, arc_filter);

  // Add nodes and arcs to the original digraph and the adaptor

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Adaptor::Node n3 = adaptor.addNode();

  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Adaptor::Arc a3 = adaptor.addArc(n2, n3);

  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide an arc

  adaptor.status(a2, false);

  adaptor.disable(a3);

  if (!adaptor.status(a3)) adaptor.enable(a3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 2);

  checkGraphConArcList(adaptor, 2);

  checkGraphOutArcList(adaptor, n1, 1);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide a node

  adaptor.status(n1, false);

  adaptor.disable(n3);

  if (!adaptor.status(n3)) adaptor.enable(n3);

  checkGraphNodeList(adaptor, 2);

  checkGraphArcList(adaptor, 1);

  checkGraphConArcList(adaptor, 1);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n2, 0);

  checkGraphInArcList(adaptor, n3, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide all nodes and arcs

  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

  checkGraphNodeList(adaptor, 0);

  checkGraphArcList(adaptor, 0);

  checkGraphConArcList(adaptor, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check the conversion of nodes and arcs

  Digraph::Node nd = n3;

  nd = n3;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = a3;

  ad = a3;

  Adaptor::Arc aa = a1;

  aa = a2;

}

void checkFilterNodes1() {

  // Check concepts

  checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();

  checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();

  checkConcept<concepts::AlterableDigraphComponent<>,

               FilterNodes<ListDigraph> >();

  checkConcept<concepts::ExtendableDigraphComponent<>,

               FilterNodes<ListDigraph> >();

  checkConcept<concepts::ErasableDigraphComponent<>,

               FilterNodes<ListDigraph> >();

  checkConcept<concepts::ClearableDigraphComponent<>,

               FilterNodes<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Digraph::NodeMap<bool> NodeFilter;

  typedef FilterNodes<Digraph, NodeFilter> Adaptor;

  Digraph digraph;

  NodeFilter node_filter(digraph);

  Adaptor adaptor(digraph, node_filter);

  // Add nodes and arcs to the original digraph and the adaptor

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Adaptor::Node n3 = adaptor.addNode();

  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Adaptor::Arc a3 = adaptor.addArc(n2, n3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide a node

  adaptor.status(n1, false);

  adaptor.disable(n3);

  if (!adaptor.status(n3)) adaptor.enable(n3);

  checkGraphNodeList(adaptor, 2);

  checkGraphArcList(adaptor, 1);

  checkGraphConArcList(adaptor, 1);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n2, 0);

  checkGraphInArcList(adaptor, n3, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide all nodes

  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

  checkGraphNodeList(adaptor, 0);

  checkGraphArcList(adaptor, 0);

  checkGraphConArcList(adaptor, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check the conversion of nodes and arcs

  Digraph::Node nd = n3;

  nd = n3;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = a3;

  ad = a3;

  Adaptor::Arc aa = a1;

  aa = a2;

}

void checkFilterArcs() {

  // Check concepts

  checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();

  checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();

  checkConcept<concepts::AlterableDigraphComponent<>,

               FilterArcs<ListDigraph> >();

  checkConcept<concepts::ExtendableDigraphComponent<>,

               FilterArcs<ListDigraph> >();

  checkConcept<concepts::ErasableDigraphComponent<>,

               FilterArcs<ListDigraph> >();

  checkConcept<concepts::ClearableDigraphComponent<>,

               FilterArcs<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Digraph::ArcMap<bool> ArcFilter;

  typedef FilterArcs<Digraph, ArcFilter> Adaptor;

  Digraph digraph;

  ArcFilter arc_filter(digraph);

  Adaptor adaptor(digraph, arc_filter);

  // Add nodes and arcs to the original digraph and the adaptor

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Adaptor::Node n3 = adaptor.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Adaptor::Arc a3 = adaptor.addArc(n2, n3);

  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide an arc

  adaptor.status(a2, false);

  adaptor.disable(a3);

  if (!adaptor.status(a3)) adaptor.enable(a3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 2);

  checkGraphConArcList(adaptor, 2);

  checkGraphOutArcList(adaptor, n1, 1);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Hide all arcs

  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 0);

  checkGraphConArcList(adaptor, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check the conversion of nodes and arcs

  Digraph::Node nd = n3;

  nd = n3;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = a3;

  ad = a3;

  Adaptor::Arc aa = a1;

  aa = a2;

}

void checkUndirector() {

  // Check concepts

  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();

  checkConcept<concepts::Graph, Undirector<ListDigraph> >();

  checkConcept<concepts::AlterableGraphComponent<>,

               Undirector<ListDigraph> >();

  checkConcept<concepts::ExtendableGraphComponent<>,

               Undirector<ListDigraph> >();

  checkConcept<concepts::ErasableGraphComponent<>,

               Undirector<ListDigraph> >();

  checkConcept<concepts::ClearableGraphComponent<>,

               Undirector<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Undirector<Digraph> Adaptor;

  Digraph digraph;

  Adaptor adaptor(digraph);

  // Add nodes and arcs/edges to the original digraph and the adaptor

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Adaptor::Node n3 = adaptor.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  // Check the original digraph

  checkGraphNodeList(digraph, 3);

  checkGraphArcList(digraph, 3);

  checkGraphConArcList(digraph, 3);

  checkGraphOutArcList(digraph, n1, 2);

  checkGraphOutArcList(digraph, n2, 1);

  checkGraphOutArcList(digraph, n3, 0);

  checkGraphInArcList(digraph, n1, 0);

  checkGraphInArcList(digraph, n2, 1);

  checkGraphInArcList(digraph, n3, 2);

  checkNodeIds(digraph);

  checkArcIds(digraph);

  checkGraphNodeMap(digraph);

  checkGraphArcMap(digraph);

  // Check the adaptor

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 6);

  checkGraphEdgeList(adaptor, 3);

  checkGraphConArcList(adaptor, 6);

  checkGraphConEdgeList(adaptor, 3);

  checkGraphIncEdgeArcLists(adaptor, n1, 2);

  checkGraphIncEdgeArcLists(adaptor, n2, 2);

  checkGraphIncEdgeArcLists(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

  // Check the edges of the adaptor

  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {

    check(adaptor.u(e) == digraph.source(e), "Wrong undir");

    check(adaptor.v(e) == digraph.target(e), "Wrong undir");

  }

  // Check CombinedArcMap

  typedef Adaptor::CombinedArcMap

    <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;

  typedef Adaptor::CombinedArcMap

    <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;

  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

    IntCombinedMap>();

  checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

    BoolCombinedMap>();

  Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    fw_map[a] = digraph.id(a);

    bk_map[a] = -digraph.id(a);

  }

  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >

    comb_map(fw_map, bk_map);

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    if (adaptor.source(a) == digraph.source(a)) {

      check(comb_map[a] == fw_map[a], "Wrong combined map");

    } else {

      check(comb_map[a] == bk_map[a], "Wrong combined map");

    }

  }

  // Check the conversion of nodes and arcs/edges

  Digraph::Node nd = n3;

  nd = n3;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = e3;

  ad = e3;

  Adaptor::Edge ea = a1;

  ea = a2;

}

void checkResidualDigraph() {

  // Check concepts

  checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();

  checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Digraph::ArcMap<int> IntArcMap;

  typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;

  Digraph digraph;

  IntArcMap capacity(digraph), flow(digraph);

  Adaptor adaptor(digraph, capacity, flow);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Node n4 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n1, n4);

  Digraph::Arc a4 = digraph.addArc(n2, n3);

  Digraph::Arc a5 = digraph.addArc(n2, n4);

  Digraph::Arc a6 = digraph.addArc(n3, n4);

  capacity[a1] = 8;

  capacity[a2] = 6;

  capacity[a3] = 4;

  capacity[a4] = 4;

  capacity[a5] = 6;

  capacity[a6] = 10;

  // Check the adaptor with various flow values

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    flow[a] = 0;

  }

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 6);

  checkGraphConArcList(adaptor, 6);

  checkGraphOutArcList(adaptor, n1, 3);

  checkGraphOutArcList(adaptor, n2, 2);

  checkGraphOutArcList(adaptor, n3, 1);

  checkGraphOutArcList(adaptor, n4, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkGraphInArcList(adaptor, n4, 3);

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    flow[a] = capacity[a] / 2;

  }

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 12);

  checkGraphConArcList(adaptor, 12);

  checkGraphOutArcList(adaptor, n1, 3);

  checkGraphOutArcList(adaptor, n2, 3);

  checkGraphOutArcList(adaptor, n3, 3);

  checkGraphOutArcList(adaptor, n4, 3);

  checkGraphInArcList(adaptor, n1, 3);

  checkGraphInArcList(adaptor, n2, 3);

  checkGraphInArcList(adaptor, n3, 3);

  checkGraphInArcList(adaptor, n4, 3);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    flow[a] = capacity[a];

  }

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 6);

  checkGraphConArcList(adaptor, 6);

  checkGraphOutArcList(adaptor, n1, 0);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 2);

  checkGraphOutArcList(adaptor, n4, 3);

  checkGraphInArcList(adaptor, n1, 3);

  checkGraphInArcList(adaptor, n2, 2);

  checkGraphInArcList(adaptor, n3, 1);

  checkGraphInArcList(adaptor, n4, 0);

  // Saturate all backward arcs

  // (set the flow to zero on all forward arcs)

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    if (adaptor.backward(a))

      adaptor.augment(a, adaptor.residualCapacity(a));

  }

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 6);

  checkGraphConArcList(adaptor, 6);

  checkGraphOutArcList(adaptor, n1, 3);

  checkGraphOutArcList(adaptor, n2, 2);

  checkGraphOutArcList(adaptor, n3, 1);

  checkGraphOutArcList(adaptor, n4, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkGraphInArcList(adaptor, n4, 3);

  // Find maximum flow by augmenting along shortest paths

  int flow_value = 0;

  Adaptor::ResidualCapacity res_cap(adaptor);

  while (true) {

    Bfs<Adaptor> bfs(adaptor);

    bfs.run(n1, n4);

    if (!bfs.reached(n4)) break;

    Path<Adaptor> p = bfs.path(n4);

    int min = std::numeric_limits<int>::max();

    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

      if (res_cap[a] < min) min = res_cap[a];

    }

    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

      adaptor.augment(a, min);

    }

    flow_value += min;

  }

  check(flow_value == 18, "Wrong flow with res graph adaptor");

  // Check forward() and backward()

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    check(adaptor.forward(a) != adaptor.backward(a),

          "Wrong forward() or backward()");

    check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||

          (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),

          "Wrong forward() or backward()");

  }

  // Check the conversion of nodes and arcs

  Digraph::Node nd = Adaptor::NodeIt(adaptor);

  nd = ++Adaptor::NodeIt(adaptor);

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = Adaptor::ArcIt(adaptor);

  ad = ++Adaptor::ArcIt(adaptor);

}

void checkSplitNodes() {

  // Check concepts

  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();

  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef SplitNodes<Digraph> Adaptor;

  Digraph digraph;

  Adaptor adaptor(digraph);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n2, n3);

  checkGraphNodeList(adaptor, 6);

  checkGraphArcList(adaptor, 6);

  checkGraphConArcList(adaptor, 6);

  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);

  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);

  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);

  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);

  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);

  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);

  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);

  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);

  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);

  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);

  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);

  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  // Check split

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    if (adaptor.origArc(a)) {

      Digraph::Arc oa = a;

      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),

            "Wrong split");

      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),

            "Wrong split");

    } else {

      Digraph::Node on = a;

      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");

      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");

    }

  }

  // Check combined node map

  typedef Adaptor::CombinedNodeMap

    <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;

  typedef Adaptor::CombinedNodeMap

    <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;

  checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,

    IntCombinedNodeMap>();

//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,

//  BoolCombinedNodeMap>();

  checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,

    BoolCombinedNodeMap>();

  Digraph::NodeMap<int> in_map(digraph), out_map(digraph);

  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

    in_map[n] = digraph.id(n);

    out_map[n] = -digraph.id(n);

  }

  Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >

    node_map(in_map, out_map);

  for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {

    if (adaptor.inNode(n)) {

      check(node_map[n] == in_map[n], "Wrong combined node map");

    } else {

      check(node_map[n] == out_map[n], "Wrong combined node map");

    }

  }

  // Check combined arc map

  typedef Adaptor::CombinedArcMap

    <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;

  typedef Adaptor::CombinedArcMap

    <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;

  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

    IntCombinedArcMap>();

//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

//  BoolCombinedArcMap>();

  checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,

    BoolCombinedArcMap>();

  Digraph::ArcMap<int> a_map(digraph);

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    a_map[a] = digraph.id(a);

  }

  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >

    arc_map(a_map, out_map);

  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

    check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");

  }

  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

    check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");

  }

  // Check the conversion of nodes

  Digraph::Node nd = adaptor.inNode(n1);

  check (nd == n1, "Wrong node conversion");

  nd = adaptor.outNode(n2);

  check (nd == n2, "Wrong node conversion");

}

void checkSubGraph() {

  // Check concepts

  checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();

  checkConcept<concepts::Graph, SubGraph<ListGraph> >();

  checkConcept<concepts::AlterableGraphComponent<>,

               SubGraph<ListGraph> >();

  checkConcept<concepts::ExtendableGraphComponent<>,

               SubGraph<ListGraph> >();

  checkConcept<concepts::ErasableGraphComponent<>,

               SubGraph<ListGraph> >();

  checkConcept<concepts::ClearableGraphComponent<>,

               SubGraph<ListGraph> >();

  // Create a graph and an adaptor

  typedef ListGraph Graph;

  typedef Graph::NodeMap<bool> NodeFilter;

  typedef Graph::EdgeMap<bool> EdgeFilter;

  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;

  Graph graph;

  NodeFilter node_filter(graph);

  EdgeFilter edge_filter(graph);

  Adaptor adaptor(graph, node_filter, edge_filter);

  // Add nodes and edges to the original graph and the adaptor

  Graph::Node n1 = graph.addNode();

  Graph::Node n2 = graph.addNode();

  Adaptor::Node n3 = adaptor.addNode();

  Adaptor::Node n4 = adaptor.addNode();

  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;

  Graph::Edge e1 = graph.addEdge(n1, n2);

  Graph::Edge e2 = graph.addEdge(n1, n3);

  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 8);

  checkGraphEdgeList(adaptor, 4);

  checkGraphConArcList(adaptor, 8);

  checkGraphConEdgeList(adaptor, 4);

  checkGraphIncEdgeArcLists(adaptor, n1, 2);

  checkGraphIncEdgeArcLists(adaptor, n2, 2);

  checkGraphIncEdgeArcLists(adaptor, n3, 3);

  checkGraphIncEdgeArcLists(adaptor, n4, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

  // Hide an edge

  adaptor.status(e2, false);

  adaptor.disable(e3);

  if (!adaptor.status(e3)) adaptor.enable(e3);

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 6);

  checkGraphEdgeList(adaptor, 3);

  checkGraphConArcList(adaptor, 6);

  checkGraphConEdgeList(adaptor, 3);

  checkGraphIncEdgeArcLists(adaptor, n1, 1);

  checkGraphIncEdgeArcLists(adaptor, n2, 2);

  checkGraphIncEdgeArcLists(adaptor, n3, 2);

  checkGraphIncEdgeArcLists(adaptor, n4, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

  // Hide a node

  adaptor.status(n1, false);

  adaptor.disable(n3);

  if (!adaptor.status(n3)) adaptor.enable(n3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 4);

  checkGraphEdgeList(adaptor, 2);

  checkGraphConArcList(adaptor, 4);

  checkGraphConEdgeList(adaptor, 2);

  checkGraphIncEdgeArcLists(adaptor, n2, 1);

  checkGraphIncEdgeArcLists(adaptor, n3, 2);

  checkGraphIncEdgeArcLists(adaptor, n4, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

  // Hide all nodes and edges

  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;

  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;

  checkGraphNodeList(adaptor, 0);

  checkGraphArcList(adaptor, 0);

  checkGraphEdgeList(adaptor, 0);

  checkGraphConArcList(adaptor, 0);

  checkGraphConEdgeList(adaptor, 0);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

  // Check the conversion of nodes and edges

  Graph::Node ng = n3;

  ng = n4;

  Adaptor::Node na = n1;

  na = n2;

  Graph::Edge eg = e3;

  eg = e4;

  Adaptor::Edge ea = e1;