Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 225)
+++ test/CMakeLists.txt	(revision 522)
@@ -14,7 +14,10 @@
   graph_test
   graph_utils_test
+  hao_orlin_test
   heap_test
   kruskal_test
   maps_test
+  max_matching_test
+  min_cost_arborescence_test
   random_test
   path_test
Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 228)
+++ test/Makefile.am	(revision 522)
@@ -1,4 +1,6 @@
 EXTRA_DIST += \
-	test/CMakeLists.txt
+	test/CMakeLists.txt \
+        test/min_cost_flow_test.lgf \
+        test/preflow_graph.lgf
 
 noinst_HEADERS += \
@@ -8,4 +10,5 @@
 check_PROGRAMS += \
 	test/bfs_test \
+        test/circulation_test \
         test/counter_test \
 	test/dfs_test \
@@ -14,4 +17,5 @@
         test/dim_test \
 	test/error_test \
+	test/graph_adaptor_test \
 	test/graph_copy_test \
 	test/graph_test \
@@ -19,7 +23,12 @@
 	test/heap_test \
 	test/kruskal_test \
+	test/hao_orlin_test \
         test/maps_test \
+	test/max_matching_test \
+	test/min_cost_arborescence_test \
         test/random_test \
         test/path_test \
+        test/preflow_test \
+        test/suurballe_test \
         test/test_tools_fail \
         test/test_tools_pass \
@@ -31,4 +40,5 @@
 
 test_bfs_test_SOURCES = test/bfs_test.cc
+test_circulation_test_SOURCES = test/circulation_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
 test_dfs_test_SOURCES = test/dfs_test.cc
@@ -37,4 +47,5 @@
 test_dim_test_SOURCES = test/dim_test.cc
 test_error_test_SOURCES = test/error_test.cc
+test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
@@ -42,6 +53,11 @@
 test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
+test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
+test_max_matching_test_SOURCES = test/max_matching_test.cc
+test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_path_test_SOURCES = test/path_test.cc
+test_preflow_test_SOURCES = test/preflow_test.cc
+test_suurballe_test_SOURCES = test/suurballe_test.cc
 test_random_test_SOURCES = test/random_test.cc
 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
Index: test/circulation_test.cc
===================================================================
--- test/circulation_test.cc	(revision 418)
+++ test/circulation_test.cc	(revision 418)
@@ -0,0 +1,156 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 "test_tools.h"
+#include <lemon/list_graph.h>
+#include <lemon/circulation.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concepts/maps.h>
+
+using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "@arcs\n"
+  "     lcap  ucap\n"
+  "0 1  2  10\n"
+  "0 2  2  6\n"
+  "1 3  4  7\n"
+  "1 4  0  5\n"
+  "2 4  1  3\n"
+  "3 5  3  8\n"
+  "4 5  3  7\n"
+  "@attributes\n"
+  "source 0\n"
+  "sink   5\n";
+
+void checkCirculationCompile()
+{
+  typedef int VType;
+  typedef concepts::Digraph Digraph;
+
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
+  typedef concepts::ReadMap<Arc,VType> CapMap;
+  typedef concepts::ReadMap<Node,VType> DeltaMap;
+  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
+  typedef concepts::WriteMap<Node,bool> BarrierMap;
+
+  typedef Elevator<Digraph, Digraph::Node> Elev;
+  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
+
+  Digraph g;
+  Node n;
+  Arc a;
+  CapMap lcap, ucap;
+  DeltaMap delta;
+  FlowMap flow;
+  BarrierMap bar;
+
+  Circulation<Digraph, CapMap, CapMap, DeltaMap>
+    ::SetFlowMap<FlowMap>
+    ::SetElevator<Elev>
+    ::SetStandardElevator<LinkedElev>
+    ::Create circ_test(g,lcap,ucap,delta);
+
+  circ_test.lowerCapMap(lcap);
+  circ_test.upperCapMap(ucap);
+  circ_test.deltaMap(delta);
+  flow = circ_test.flowMap();
+  circ_test.flowMap(flow);
+
+  circ_test.init();
+  circ_test.greedyInit();
+  circ_test.start();
+  circ_test.run();
+
+  circ_test.barrier(n);
+  circ_test.barrierMap(bar);
+  circ_test.flow(a);
+}
+
+template <class G, class LM, class UM, class DM>
+void checkCirculation(const G& g, const LM& lm, const UM& um,
+                      const DM& dm, bool find)
+{
+  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
+  bool ret = circ.run();
+  if (find) {
+    check(ret, "A feasible solution should have been found.");
+    check(circ.checkFlow(), "The found flow is corrupt.");
+    check(!circ.checkBarrier(), "A barrier should not have been found.");
+  } else {
+    check(!ret, "A feasible solution should not have been found.");
+    check(circ.checkBarrier(), "The found barrier is corrupt.");
+  }
+}
+
+int main (int, char*[])
+{
+  typedef ListDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph g;
+  IntArcMap lo(g), up(g);
+  IntNodeMap delta(g, 0);
+  Node s, t;
+
+  std::istringstream input(test_lgf);
+  DigraphReader<Digraph>(g,input).
+    arcMap("lcap", lo).
+    arcMap("ucap", up).
+    node("source",s).
+    node("sink",t).
+    run();
+
+  delta[s] = 7; delta[t] = -7;
+  checkCirculation(g, lo, up, delta, true);
+
+  delta[s] = 13; delta[t] = -13;
+  checkCirculation(g, lo, up, delta, true);
+
+  delta[s] = 6; delta[t] = -6;
+  checkCirculation(g, lo, up, delta, false);
+
+  delta[s] = 14; delta[t] = -14;
+  checkCirculation(g, lo, up, delta, false);
+
+  delta[s] = 7; delta[t] = -13;
+  checkCirculation(g, lo, up, delta, true);
+
+  delta[s] = 5; delta[t] = -15;
+  checkCirculation(g, lo, up, delta, true);
+
+  delta[s] = 10; delta[t] = -11;
+  checkCirculation(g, lo, up, delta, true);
+
+  delta[s] = 11; delta[t] = -10;
+  checkCirculation(g, lo, up, delta, false);
+
+  return 0;
+}
Index: test/digraph_test.cc
===================================================================
--- test/digraph_test.cc	(revision 387)
+++ test/digraph_test.cc	(revision 388)
@@ -20,6 +20,5 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-//#include <lemon/full_graph.h>
-//#include <lemon/hypercube_graph.h>
+#include <lemon/full_graph.h>
 
 #include "test_tools.h"
@@ -319,10 +318,7 @@
     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   }
-//  { // Checking FullDigraph
-//    checkConcept<Digraph, FullDigraph>();
-//  }
-//  { // Checking HyperCubeDigraph
-//    checkConcept<Digraph, HyperCubeDigraph>();
-//  }
+  { // Checking FullDigraph
+    checkConcept<Digraph, FullDigraph>();
+  }
 }
 
@@ -375,4 +371,36 @@
   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
+}
+
+void checkFullDigraph(int num) {
+  typedef FullDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G(num);
+
+  checkGraphNodeList(G, num);
+  checkGraphArcList(G, num * num);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num);
+    checkGraphInArcList(G, n, num);
+  }
+
+  checkGraphConArcList(G, num * num);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt s(G); s != INVALID; ++s) {
+    for (NodeIt t(G); t != INVALID; ++t) {
+      Arc a = G.arc(s, t);
+      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
+    }
+  }
 }
 
@@ -392,4 +420,7 @@
     checkDigraphValidity<SmartDigraph>();
   }
+  { // Checking FullDigraph
+    checkFullDigraph(8);
+  }
 }
 
Index: test/graph_adaptor_test.cc
===================================================================
--- test/graph_adaptor_test.cc	(revision 432)
+++ test/graph_adaptor_test.cc	(revision 432)
@@ -0,0 +1,984 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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<lemon/concept_check.h>
+
+#include<lemon/list_graph.h>
+#include<lemon/smart_graph.h>
+
+#include<lemon/concepts/digraph.h>
+#include<lemon/concepts/graph.h>
+
+#include<lemon/adaptors.h>
+
+#include <limits>
+#include <lemon/bfs.h>
+#include <lemon/path.h>
+
+#include"test/test_tools.h"
+#include"test/graph_test.h"
+
+using namespace lemon;
+
+void checkReverseDigraph() {
+  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
+
+  typedef ListDigraph Digraph;
+  typedef ReverseDigraph<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, 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);
+
+  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");
+  }
+}
+
+void checkSubDigraph() {
+  checkConcept<concepts::Digraph,
+    SubDigraph<concepts::Digraph,
+    concepts::Digraph::NodeMap<bool>,
+    concepts::Digraph::ArcMap<bool> > >();
+
+  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);
+
+  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);
+
+  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
+  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);
+
+  arc_filter[a2] = false;
+
+  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);
+
+  node_filter[n1] = false;
+
+  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);
+
+  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);
+}
+
+void checkFilterNodes1() {
+  checkConcept<concepts::Digraph,
+    FilterNodes<concepts::Digraph,
+      concepts::Digraph::NodeMap<bool> > >();
+
+  typedef ListDigraph Digraph;
+  typedef Digraph::NodeMap<bool> NodeFilter;
+  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
+
+  Digraph digraph;
+  NodeFilter node_filter(digraph);
+  Adaptor adaptor(digraph, node_filter);
+
+  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);
+
+  node_filter[n1] = node_filter[n2] = node_filter[n3] = 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);
+
+  node_filter[n1] = false;
+
+  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);
+
+  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);
+}
+
+void checkFilterArcs() {
+  checkConcept<concepts::Digraph,
+    FilterArcs<concepts::Digraph,
+    concepts::Digraph::ArcMap<bool> > >();
+
+  typedef ListDigraph Digraph;
+  typedef Digraph::ArcMap<bool> ArcFilter;
+  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
+
+  Digraph digraph;
+  ArcFilter arc_filter(digraph);
+  Adaptor adaptor(digraph, arc_filter);
+
+  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);
+
+  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);
+
+  arc_filter[a2] = false;
+
+  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);
+
+  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);
+}
+
+void checkUndirector() {
+  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
+
+  typedef ListDigraph Digraph;
+  typedef Undirector<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, 3);
+  checkGraphArcList(adaptor, 6);
+  checkGraphEdgeList(adaptor, 3);
+  checkGraphConArcList(adaptor, 6);
+  checkGraphConEdgeList(adaptor, 3);
+
+  checkGraphOutArcList(adaptor, n1, 2);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 2);
+
+  checkGraphInArcList(adaptor, n1, 2);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 2);
+
+  checkGraphIncEdgeList(adaptor, n1, 2);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 2);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(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");
+  }
+
+}
+
+void checkResidual() {
+  checkConcept<concepts::Digraph,
+    Residual<concepts::Digraph,
+    concepts::Digraph::ArcMap<int>,
+    concepts::Digraph::ArcMap<int> > >();
+
+  typedef ListDigraph Digraph;
+  typedef Digraph::ArcMap<int> IntArcMap;
+  typedef Residual<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;
+
+  for (Adaptor::ArcIt a(adaptor); 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 (Adaptor::ArcIt a(adaptor); 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 (Adaptor::ArcIt a(adaptor); 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);
+
+  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
+    flow[a] = 0;
+  }
+
+  int flow_value = 0;
+  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 (adaptor.residualCapacity(a) < min)
+        min = adaptor.residualCapacity(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");
+
+}
+
+void checkSplitNodes() {
+  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
+
+  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);
+
+  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");
+    }
+  }
+}
+
+void checkSubGraph() {
+  checkConcept<concepts::Graph,
+    SubGraph<concepts::Graph,
+    concepts::Graph::NodeMap<bool>,
+    concepts::Graph::EdgeMap<bool> > >();
+
+  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);
+
+  Graph::Node n1 = graph.addNode();
+  Graph::Node n2 = graph.addNode();
+  Graph::Node n3 = graph.addNode();
+  Graph::Node n4 = graph.addNode();
+
+  Graph::Edge e1 = graph.addEdge(n1, n2);
+  Graph::Edge e2 = graph.addEdge(n1, n3);
+  Graph::Edge e3 = graph.addEdge(n2, n3);
+  Graph::Edge e4 = graph.addEdge(n3, n4);
+
+  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
+  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);
+
+  checkGraphOutArcList(adaptor, n1, 2);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 3);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n1, 2);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 3);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n1, 2);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 3);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  edge_filter[e2] = false;
+
+  checkGraphNodeList(adaptor, 4);
+  checkGraphArcList(adaptor, 6);
+  checkGraphEdgeList(adaptor, 3);
+  checkGraphConArcList(adaptor, 6);
+  checkGraphConEdgeList(adaptor, 3);
+
+  checkGraphOutArcList(adaptor, n1, 1);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 2);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n1, 1);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 2);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n1, 1);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 2);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  node_filter[n1] = false;
+
+  checkGraphNodeList(adaptor, 3);
+  checkGraphArcList(adaptor, 4);
+  checkGraphEdgeList(adaptor, 2);
+  checkGraphConArcList(adaptor, 4);
+  checkGraphConEdgeList(adaptor, 2);
+
+  checkGraphOutArcList(adaptor, n2, 1);
+  checkGraphOutArcList(adaptor, n3, 2);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n2, 1);
+  checkGraphInArcList(adaptor, n3, 2);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n2, 1);
+  checkGraphIncEdgeList(adaptor, n3, 2);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  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);
+}
+
+void checkFilterNodes2() {
+  checkConcept<concepts::Graph,
+    FilterNodes<concepts::Graph,
+      concepts::Graph::NodeMap<bool> > >();
+
+  typedef ListGraph Graph;
+  typedef Graph::NodeMap<bool> NodeFilter;
+  typedef FilterNodes<Graph, NodeFilter> Adaptor;
+
+  Graph graph;
+  NodeFilter node_filter(graph);
+  Adaptor adaptor(graph, node_filter);
+
+  Graph::Node n1 = graph.addNode();
+  Graph::Node n2 = graph.addNode();
+  Graph::Node n3 = graph.addNode();
+  Graph::Node n4 = graph.addNode();
+
+  Graph::Edge e1 = graph.addEdge(n1, n2);
+  Graph::Edge e2 = graph.addEdge(n1, n3);
+  Graph::Edge e3 = graph.addEdge(n2, n3);
+  Graph::Edge e4 = graph.addEdge(n3, n4);
+
+  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
+  
+  checkGraphNodeList(adaptor, 4);
+  checkGraphArcList(adaptor, 8);
+  checkGraphEdgeList(adaptor, 4);
+  checkGraphConArcList(adaptor, 8);
+  checkGraphConEdgeList(adaptor, 4);
+
+  checkGraphOutArcList(adaptor, n1, 2);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 3);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n1, 2);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 3);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n1, 2);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 3);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  node_filter[n1] = false;
+
+  checkGraphNodeList(adaptor, 3);
+  checkGraphArcList(adaptor, 4);
+  checkGraphEdgeList(adaptor, 2);
+  checkGraphConArcList(adaptor, 4);
+  checkGraphConEdgeList(adaptor, 2);
+
+  checkGraphOutArcList(adaptor, n2, 1);
+  checkGraphOutArcList(adaptor, n3, 2);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n2, 1);
+  checkGraphInArcList(adaptor, n3, 2);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n2, 1);
+  checkGraphIncEdgeList(adaptor, n3, 2);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = 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);
+}
+
+void checkFilterEdges() {
+  checkConcept<concepts::Graph,
+    FilterEdges<concepts::Graph,
+    concepts::Graph::EdgeMap<bool> > >();
+
+  typedef ListGraph Graph;
+  typedef Graph::EdgeMap<bool> EdgeFilter;
+  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
+
+  Graph graph;
+  EdgeFilter edge_filter(graph);
+  Adaptor adaptor(graph, edge_filter);
+
+  Graph::Node n1 = graph.addNode();
+  Graph::Node n2 = graph.addNode();
+  Graph::Node n3 = graph.addNode();
+  Graph::Node n4 = graph.addNode();
+
+  Graph::Edge e1 = graph.addEdge(n1, n2);
+  Graph::Edge e2 = graph.addEdge(n1, n3);
+  Graph::Edge e3 = graph.addEdge(n2, n3);
+  Graph::Edge e4 = graph.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);
+
+  checkGraphOutArcList(adaptor, n1, 2);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 3);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n1, 2);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 3);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n1, 2);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 3);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  edge_filter[e2] = false;
+
+  checkGraphNodeList(adaptor, 4);
+  checkGraphArcList(adaptor, 6);
+  checkGraphEdgeList(adaptor, 3);
+  checkGraphConArcList(adaptor, 6);
+  checkGraphConEdgeList(adaptor, 3);
+
+  checkGraphOutArcList(adaptor, n1, 1);
+  checkGraphOutArcList(adaptor, n2, 2);
+  checkGraphOutArcList(adaptor, n3, 2);
+  checkGraphOutArcList(adaptor, n4, 1);
+
+  checkGraphInArcList(adaptor, n1, 1);
+  checkGraphInArcList(adaptor, n2, 2);
+  checkGraphInArcList(adaptor, n3, 2);
+  checkGraphInArcList(adaptor, n4, 1);
+
+  checkGraphIncEdgeList(adaptor, n1, 1);
+  checkGraphIncEdgeList(adaptor, n2, 2);
+  checkGraphIncEdgeList(adaptor, n3, 2);
+  checkGraphIncEdgeList(adaptor, n4, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+
+  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
+
+  checkGraphNodeList(adaptor, 4);
+  checkGraphArcList(adaptor, 0);
+  checkGraphEdgeList(adaptor, 0);
+  checkGraphConArcList(adaptor, 0);
+  checkGraphConEdgeList(adaptor, 0);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+  checkEdgeIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+  checkGraphEdgeMap(adaptor);
+}
+
+void checkOrienter() {
+  checkConcept<concepts::Digraph,
+    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
+
+  typedef ListGraph Graph;
+  typedef ListGraph::EdgeMap<bool> DirMap;
+  typedef Orienter<Graph> Adaptor;
+
+  Graph graph;
+  DirMap dir(graph, true);
+  Adaptor adaptor(graph, dir);
+
+  Graph::Node n1 = graph.addNode();
+  Graph::Node n2 = graph.addNode();
+  Graph::Node n3 = graph.addNode();
+
+  Graph::Edge e1 = graph.addEdge(n1, n2);
+  Graph::Edge e2 = graph.addEdge(n1, n3);
+  Graph::Edge e3 = graph.addEdge(n2, n3);
+
+  checkGraphNodeList(adaptor, 3);
+  checkGraphArcList(adaptor, 3);
+  checkGraphConArcList(adaptor, 3);
+
+  {
+    dir[e1] = true;
+    Adaptor::Node u = adaptor.source(e1);
+    Adaptor::Node v = adaptor.target(e1);
+
+    dir[e1] = false;
+    check (u == adaptor.target(e1), "Wrong dir");
+    check (v == adaptor.source(e1), "Wrong dir");
+
+    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
+    dir[e1] = n1 == u;
+  }
+
+  {
+    dir[e2] = true;
+    Adaptor::Node u = adaptor.source(e2);
+    Adaptor::Node v = adaptor.target(e2);
+
+    dir[e2] = false;
+    check (u == adaptor.target(e2), "Wrong dir");
+    check (v == adaptor.source(e2), "Wrong dir");
+
+    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
+    dir[e2] = n3 == u;
+  }
+
+  {
+    dir[e3] = true;
+    Adaptor::Node u = adaptor.source(e3);
+    Adaptor::Node v = adaptor.target(e3);
+
+    dir[e3] = false;
+    check (u == adaptor.target(e3), "Wrong dir");
+    check (v == adaptor.source(e3), "Wrong dir");
+
+    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
+    dir[e3] = n2 == u;
+  }
+
+  checkGraphOutArcList(adaptor, n1, 1);
+  checkGraphOutArcList(adaptor, n2, 1);
+  checkGraphOutArcList(adaptor, n3, 1);
+
+  checkGraphInArcList(adaptor, n1, 1);
+  checkGraphInArcList(adaptor, n2, 1);
+  checkGraphInArcList(adaptor, n3, 1);
+
+  checkNodeIds(adaptor);
+  checkArcIds(adaptor);
+
+  checkGraphNodeMap(adaptor);
+  checkGraphArcMap(adaptor);
+
+}
+
+
+int main(int, const char **) {
+
+  checkReverseDigraph();
+  checkSubDigraph();
+  checkFilterNodes1();
+  checkFilterArcs();
+  checkUndirector();
+  checkResidual();
+  checkSplitNodes();
+
+  checkSubGraph();
+  checkFilterNodes2();
+  checkFilterEdges();
+  checkOrienter();
+
+  return 0;
+}
Index: test/graph_test.cc
===================================================================
--- test/graph_test.cc	(revision 387)
+++ test/graph_test.cc	(revision 388)
@@ -20,6 +20,7 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-// #include <lemon/full_graph.h>
-// #include <lemon/grid_graph.h>
+#include <lemon/full_graph.h>
+#include <lemon/grid_graph.h>
+#include <lemon/hypercube_graph.h>
 
 #include "test_tools.h"
@@ -262,4 +263,51 @@
 }
 
+void checkFullGraph(int num) {
+  typedef FullGraph Graph;
+  GRAPH_TYPEDEFS(Graph);
+
+  Graph G(num);
+  checkGraphNodeList(G, num);
+  checkGraphEdgeList(G, num * (num - 1) / 2);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num - 1);
+    checkGraphInArcList(G, n, num - 1);
+    checkGraphIncEdgeList(G, n, num - 1);
+  }
+
+  checkGraphConArcList(G, num * (num - 1));
+  checkGraphConEdgeList(G, num * (num - 1) / 2);
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt u(G); u != INVALID; ++u) {
+    for (NodeIt v(G); v != INVALID; ++v) {
+      Edge e = G.edge(u, v);
+      Arc a = G.arc(u, v);
+      if (u == v) {
+        check(e == INVALID, "Wrong edge lookup");
+        check(a == INVALID, "Wrong arc lookup");
+      } else {
+        check((G.u(e) == u && G.v(e) == v) ||
+              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
+        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
+      }
+    }
+  }
+}
+
 void checkConcepts() {
   { // Checking graph components
@@ -291,12 +339,13 @@
     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   }
-//  { // Checking FullGraph
-//    checkConcept<Graph, FullGraph>();
-//    checkGraphIterators<FullGraph>();
-//  }
-//  { // Checking GridGraph
-//    checkConcept<Graph, GridGraph>();
-//    checkGraphIterators<GridGraph>();
-//  }
+  { // Checking FullGraph
+    checkConcept<Graph, FullGraph>();
+  }
+  { // Checking GridGraph
+    checkConcept<Graph, GridGraph>();
+  }
+  { // Checking HypercubeGraph
+    checkConcept<Graph, HypercubeGraph>();
+  }
 }
 
@@ -355,47 +404,130 @@
 }
 
-// void checkGridGraph(const GridGraph& g, int w, int h) {
-//   check(g.width() == w, "Wrong width");
-//   check(g.height() == h, "Wrong height");
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 0; j < h; ++j) {
-//       check(g.col(g(i, j)) == i, "Wrong col");
-//       check(g.row(g(i, j)) == j, "Wrong row");
-//     }
-//   }
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 0; j < h - 1; ++j) {
-//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
-//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
-//     }
-//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
-//   }
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 1; j < h; ++j) {
-//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
-//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
-//     }
-//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
-//   }
-
-//   for (int j = 0; j < h; ++j) {
-//     for (int i = 0; i < w - 1; ++i) {
-//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
-//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
-//     }
-//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
-//   }
-
-//   for (int j = 0; j < h; ++j) {
-//     for (int i = 1; i < w; ++i) {
-//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
-//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
-//     }
-//     check(g.left(g(0, j)) == INVALID, "Wrong left");
-//   }
-// }
+void checkGridGraph(int width, int height) {
+  typedef GridGraph Graph;
+  GRAPH_TYPEDEFS(Graph);
+  Graph G(width, height);
+
+  check(G.width() == width, "Wrong column number");
+  check(G.height() == height, "Wrong row number");
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 0; j < height; ++j) {
+      check(G.col(G(i, j)) == i, "Wrong column");
+      check(G.row(G(i, j)) == j, "Wrong row");
+      check(G.pos(G(i, j)).x == i, "Wrong column");
+      check(G.pos(G(i, j)).y == j, "Wrong row");
+    }
+  }
+
+  for (int j = 0; j < height; ++j) {
+    for (int i = 0; i < width - 1; ++i) {
+      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
+      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
+    }
+    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
+  }
+
+  for (int j = 0; j < height; ++j) {
+    for (int i = 1; i < width; ++i) {
+      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
+      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
+    }
+    check(G.left(G(0, j)) == INVALID, "Wrong left");
+  }
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 0; j < height - 1; ++j) {
+      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
+      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
+    }
+    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
+  }
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 1; j < height; ++j) {
+      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
+      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
+    }
+    check(G.down(G(i, 0)) == INVALID, "Wrong down");
+  }
+
+  checkGraphNodeList(G, width * height);
+  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
+  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    int nb = 4;
+    if (G.col(n) == 0) --nb;
+    if (G.col(n) == width - 1) --nb;
+    if (G.row(n) == 0) --nb;
+    if (G.row(n) == height - 1) --nb;
+
+    checkGraphOutArcList(G, n, nb);
+    checkGraphInArcList(G, n, nb);
+    checkGraphIncEdgeList(G, n, nb);
+  }
+
+  checkArcDirections(G);
+
+  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
+  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+
+}
+
+void checkHypercubeGraph(int dim) {
+  GRAPH_TYPEDEFS(HypercubeGraph);
+
+  HypercubeGraph G(dim);
+  checkGraphNodeList(G, 1 << dim);
+  checkGraphEdgeList(G, dim * (1 << (dim-1)));
+  checkGraphArcList(G, dim * (1 << dim));
+
+  Node n = G.nodeFromId(dim);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphIncEdgeList(G, n, dim);
+    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
+      check( (G.u(e) == n &&
+              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
+             (G.v(e) == n &&
+              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
+             "Wrong edge or wrong dimension");
+    }
+
+    checkGraphOutArcList(G, n, dim);
+    for (OutArcIt a(G, n); a != INVALID; ++a) {
+      check(G.source(a) == n &&
+            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
+            "Wrong arc or wrong dimension");
+    }
+
+    checkGraphInArcList(G, n, dim);
+    for (InArcIt a(G, n); a != INVALID; ++a) {
+      check(G.target(a) == n &&
+            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
+            "Wrong arc or wrong dimension");
+    }
+  }
+
+  checkGraphConArcList(G, (1 << dim) * dim);
+  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+}
 
 void checkGraphs() {
@@ -412,15 +544,21 @@
     checkGraphValidity<SmartGraph>();
   }
-//   { // Checking FullGraph
-//     FullGraph g(5);
-//     checkGraphNodeList(g, 5);
-//     checkGraphEdgeList(g, 10);
-//   }
-//   { // Checking GridGraph
-//     GridGraph g(5, 6);
-//     checkGraphNodeList(g, 30);
-//     checkGraphEdgeList(g, 49);
-//     checkGridGraph(g, 5, 6);
-//   }
+  { // Checking FullGraph
+    checkFullGraph(7);
+    checkFullGraph(8);
+  }
+  { // Checking GridGraph
+    checkGridGraph(5, 8);
+    checkGridGraph(8, 5);
+    checkGridGraph(5, 5);
+    checkGridGraph(0, 0);
+    checkGridGraph(1, 1);
+  }
+  { // Checking HypercubeGraph
+    checkHypercubeGraph(1);
+    checkHypercubeGraph(2);
+    checkHypercubeGraph(3);
+    checkHypercubeGraph(4);
+  }
 }
 
Index: test/graph_utils_test.cc
===================================================================
--- test/graph_utils_test.cc	(revision 324)
+++ test/graph_utils_test.cc	(revision 220)
@@ -36,10 +36,9 @@
   {
     Digraph digraph;
-    typename Digraph::template NodeMap<int> nodes(digraph);
-    std::vector<Node> invNodes;
     for (int i = 0; i < 10; ++i) {
-      invNodes.push_back(digraph.addNode());
-      nodes[invNodes.back()]=invNodes.size()-1;
-    }
+      digraph.addNode();
+    }
+    DescriptorMap<Digraph, Node> nodes(digraph);
+    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     for (int i = 0; i < 100; ++i) {
       int src = rnd[invNodes.size()];
@@ -48,4 +47,5 @@
     }
     typename Digraph::template ArcMap<bool> found(digraph, false);
+    DescriptorMap<Digraph, Arc> arcs(digraph);
     for (NodeIt src(digraph); src != INVALID; ++src) {
       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
@@ -111,10 +111,9 @@
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph graph;
-  typename Graph::template NodeMap<int> nodes(graph);
-  std::vector<Node> invNodes;
   for (int i = 0; i < 10; ++i) {
-    invNodes.push_back(graph.addNode());
-    nodes[invNodes.back()]=invNodes.size()-1;
-  }
+    graph.addNode();
+  }
+  DescriptorMap<Graph, Node> nodes(graph);
+  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
   for (int i = 0; i < 100; ++i) {
     int src = rnd[invNodes.size()];
@@ -123,4 +122,5 @@
   }
   typename Graph::template EdgeMap<int> found(graph, 0);
+  DescriptorMap<Graph, Edge> edges(graph);
   for (NodeIt src(graph); src != INVALID; ++src) {
     for (NodeIt trg(graph); trg != INVALID; ++trg) {
Index: test/hao_orlin_test.cc
===================================================================
--- test/hao_orlin_test.cc	(revision 426)
+++ test/hao_orlin_test.cc	(revision 426)
@@ -0,0 +1,63 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 <sstream>
+
+#include <lemon/smart_graph.h>
+#include <lemon/hao_orlin.h>
+
+#include <lemon/lgf_reader.h>
+#include "test_tools.h"
+
+using namespace lemon;
+using namespace std;
+
+const std::string lgf =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "@edges\n"
+  "     label  capacity\n"
+  "0 1  0      2\n"
+  "1 2  1      2\n"
+  "2 0  2      2\n"
+  "3 4  3      2\n"
+  "4 5  4      2\n"
+  "5 3  5      2\n"
+  "2 3  6      3\n";
+
+int main() {
+  SmartGraph graph;
+  SmartGraph::EdgeMap<int> capacity(graph);
+
+  istringstream lgfs(lgf);
+  graphReader(graph, lgfs).
+    edgeMap("capacity", capacity).run();
+
+  HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
+  ho.run();
+
+  check(ho.minCutValue() == 3, "Wrong cut value");
+
+  return 0;
+}
Index: test/maps_test.cc
===================================================================
--- test/maps_test.cc	(revision 500)
+++ test/maps_test.cc	(revision 210)
@@ -171,5 +171,5 @@
     typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
     checkConcept<ReadMap<B,double>, CompMap>();
-    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
+    CompMap map1(DoubleMap(),ReadMap<B,A>());
     CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
 
@@ -184,5 +184,5 @@
     typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
     checkConcept<ReadMap<A,double>, CombMap>();
-    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
+    CombMap map1(DoubleMap(), DoubleMap());
     CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
 
@@ -196,9 +196,9 @@
     checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
     FunctorToMap<F> map1;
-    FunctorToMap<F> map2 = FunctorToMap<F>(F());
+    FunctorToMap<F> map2(F());
     B b = functorToMap(F())[A()];
 
     checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
-    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
+    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
 
     check(functorToMap(&func)[A()] == 3,
Index: test/max_matching_test.cc
===================================================================
--- test/max_matching_test.cc	(revision 339)
+++ test/max_matching_test.cc	(revision 339)
@@ -0,0 +1,310 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 <sstream>
+#include <vector>
+#include <queue>
+#include <lemon/math.h>
+#include <cstdlib>
+
+#include <lemon/max_matching.h>
+#include <lemon/smart_graph.h>
+#include <lemon/lgf_reader.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+GRAPH_TYPEDEFS(SmartGraph);
+
+
+const int lgfn = 3;
+const std::string lgf[lgfn] = {
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@edges\n"
+  "     label  weight\n"
+  "7 4  0      984\n"
+  "0 7  1      73\n"
+  "7 1  2      204\n"
+  "2 3  3      583\n"
+  "2 7  4      565\n"
+  "2 1  5      582\n"
+  "0 4  6      551\n"
+  "2 5  7      385\n"
+  "1 5  8      561\n"
+  "5 3  9      484\n"
+  "7 5  10     904\n"
+  "3 6  11     47\n"
+  "7 6  12     888\n"
+  "3 0  13     747\n"
+  "6 1  14     310\n",
+
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@edges\n"
+  "     label  weight\n"
+  "2 5  0      710\n"
+  "0 5  1      241\n"
+  "2 4  2      856\n"
+  "2 6  3      762\n"
+  "4 1  4      747\n"
+  "6 1  5      962\n"
+  "4 7  6      723\n"
+  "1 7  7      661\n"
+  "2 3  8      376\n"
+  "1 0  9      416\n"
+  "6 7  10     391\n",
+
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@edges\n"
+  "     label  weight\n"
+  "6 2  0      553\n"
+  "0 7  1      653\n"
+  "6 3  2      22\n"
+  "4 7  3      846\n"
+  "7 2  4      981\n"
+  "7 6  5      250\n"
+  "5 2  6      539\n",
+};
+
+void checkMatching(const SmartGraph& graph,
+                   const MaxMatching<SmartGraph>& mm) {
+  int num = 0;
+
+  IntNodeMap comp_index(graph);
+  UnionFind<IntNodeMap> comp(comp_index);
+
+  int barrier_num = 0;
+
+  for (NodeIt n(graph); n != INVALID; ++n) {
+    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
+          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
+    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
+      ++barrier_num;
+    } else {
+      comp.insert(n);
+    }
+  }
+
+  for (EdgeIt e(graph); e != INVALID; ++e) {
+    if (mm.matching(e)) {
+      check(e == mm.matching(graph.u(e)), "Wrong matching");
+      check(e == mm.matching(graph.v(e)), "Wrong matching");
+      ++num;
+    }
+    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
+          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
+          "Wrong Gallai-Edmonds decomposition");
+
+    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
+          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
+          "Wrong Gallai-Edmonds decomposition");
+
+    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
+        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
+      comp.join(graph.u(e), graph.v(e));
+    }
+  }
+
+  std::set<int> comp_root;
+  int odd_comp_num = 0;
+  for (NodeIt n(graph); n != INVALID; ++n) {
+    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
+      int root = comp.find(n);
+      if (comp_root.find(root) == comp_root.end()) {
+        comp_root.insert(root);
+        if (comp.size(n) % 2 == 1) {
+          ++odd_comp_num;
+        }
+      }
+    }
+  }
+
+  check(mm.matchingSize() == num, "Wrong matching");
+  check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
+         "Wrong matching");
+  return;
+}
+
+void checkWeightedMatching(const SmartGraph& graph,
+                   const SmartGraph::EdgeMap<int>& weight,
+                   const MaxWeightedMatching<SmartGraph>& mwm) {
+  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+    if (graph.u(e) == graph.v(e)) continue;
+    int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
+
+    for (int i = 0; i < mwm.blossomNum(); ++i) {
+      bool s = false, t = false;
+      for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
+           n != INVALID; ++n) {
+        if (graph.u(e) == n) s = true;
+        if (graph.v(e) == n) t = true;
+      }
+      if (s == true && t == true) {
+        rw += mwm.blossomValue(i);
+      }
+    }
+    rw -= weight[e] * mwm.dualScale;
+
+    check(rw >= 0, "Negative reduced weight");
+    check(rw == 0 || !mwm.matching(e),
+          "Non-zero reduced weight on matching edge");
+  }
+
+  int pv = 0;
+  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
+    if (mwm.matching(n) != INVALID) {
+      check(mwm.nodeValue(n) >= 0, "Invalid node value");
+      pv += weight[mwm.matching(n)];
+      SmartGraph::Node o = graph.target(mwm.matching(n));
+      check(mwm.mate(n) == o, "Invalid matching");
+      check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
+            "Invalid matching");
+    } else {
+      check(mwm.mate(n) == INVALID, "Invalid matching");
+      check(mwm.nodeValue(n) == 0, "Invalid matching");
+    }
+  }
+
+  int dv = 0;
+  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
+    dv += mwm.nodeValue(n);
+  }
+
+  for (int i = 0; i < mwm.blossomNum(); ++i) {
+    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
+    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
+    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
+  }
+
+  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
+
+  return;
+}
+
+void checkWeightedPerfectMatching(const SmartGraph& graph,
+                          const SmartGraph::EdgeMap<int>& weight,
+                          const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
+  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+    if (graph.u(e) == graph.v(e)) continue;
+    int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
+
+    for (int i = 0; i < mwpm.blossomNum(); ++i) {
+      bool s = false, t = false;
+      for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
+           n != INVALID; ++n) {
+        if (graph.u(e) == n) s = true;
+        if (graph.v(e) == n) t = true;
+      }
+      if (s == true && t == true) {
+        rw += mwpm.blossomValue(i);
+      }
+    }
+    rw -= weight[e] * mwpm.dualScale;
+
+    check(rw >= 0, "Negative reduced weight");
+    check(rw == 0 || !mwpm.matching(e),
+          "Non-zero reduced weight on matching edge");
+  }
+
+  int pv = 0;
+  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
+    check(mwpm.matching(n) != INVALID, "Non perfect");
+    pv += weight[mwpm.matching(n)];
+    SmartGraph::Node o = graph.target(mwpm.matching(n));
+    check(mwpm.mate(n) == o, "Invalid matching");
+    check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
+          "Invalid matching");
+  }
+
+  int dv = 0;
+  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
+    dv += mwpm.nodeValue(n);
+  }
+
+  for (int i = 0; i < mwpm.blossomNum(); ++i) {
+    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
+    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
+    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
+  }
+
+  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
+
+  return;
+}
+
+
+int main() {
+
+  for (int i = 0; i < lgfn; ++i) {
+    SmartGraph graph;
+    SmartGraph::EdgeMap<int> weight(graph);
+
+    istringstream lgfs(lgf[i]);
+    graphReader(graph, lgfs).
+      edgeMap("weight", weight).run();
+
+    MaxMatching<SmartGraph> mm(graph);
+    mm.run();
+    checkMatching(graph, mm);
+
+    MaxWeightedMatching<SmartGraph> mwm(graph, weight);
+    mwm.run();
+    checkWeightedMatching(graph, weight, mwm);
+
+    MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
+    bool perfect = mwpm.run();
+
+    check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
+          "Perfect matching found");
+
+    if (perfect) {
+      checkWeightedPerfectMatching(graph, weight, mwpm);
+    }
+  }
+
+  return 0;
+}
Index: test/min_cost_arborescence_test.cc
===================================================================
--- test/min_cost_arborescence_test.cc	(revision 522)
+++ test/min_cost_arborescence_test.cc	(revision 522)
@@ -0,0 +1,146 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 <set>
+#include <vector>
+#include <iterator>
+
+#include <lemon/smart_graph.h>
+#include <lemon/min_cost_arborescence.h>
+#include <lemon/lgf_reader.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+using namespace std;
+
+const char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "8\n"
+  "9\n"
+  "@arcs\n"
+  "     label  cost\n"
+  "1 8  0      107\n"
+  "0 3  1      70\n"
+  "2 1  2      46\n"
+  "4 1  3      28\n"
+  "4 4  4      91\n"
+  "3 9  5      76\n"
+  "9 8  6      61\n"
+  "8 1  7      39\n"
+  "9 8  8      74\n"
+  "8 0  9      39\n"
+  "4 3  10     45\n"
+  "2 2  11     34\n"
+  "0 1  12     100\n"
+  "6 3  13     95\n"
+  "4 1  14     22\n"
+  "1 1  15     31\n"
+  "7 2  16     51\n"
+  "2 6  17     29\n"
+  "8 3  18     115\n"
+  "6 9  19     32\n"
+  "1 1  20     60\n"
+  "0 3  21     40\n"
+  "@attributes\n"
+  "source 0\n";
+
+int main() {
+  typedef SmartDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+
+  typedef Digraph::ArcMap<double> CostMap;
+
+  Digraph digraph;
+  CostMap cost(digraph);
+  Node source;
+
+  std::istringstream is(test_lgf);
+  digraphReader(digraph, is).
+    arcMap("cost", cost).
+    node("source", source).run();
+
+  MinCostArborescence<Digraph, CostMap> mca(digraph, cost);
+  mca.run(source);
+
+  vector<pair<double, set<Node> > > dualSolution(mca.dualNum());
+
+  for (int i = 0; i < mca.dualNum(); ++i) {
+    dualSolution[i].first = mca.dualValue(i);
+    for (MinCostArborescence<Digraph, CostMap>::DualIt it(mca, i);
+         it != INVALID; ++it) {
+      dualSolution[i].second.insert(it);
+    }
+  }
+
+  for (ArcIt it(digraph); it != INVALID; ++it) {
+    if (mca.reached(digraph.source(it))) {
+      double sum = 0.0;
+      for (int i = 0; i < int(dualSolution.size()); ++i) {
+        if (dualSolution[i].second.find(digraph.target(it))
+            != dualSolution[i].second.end() &&
+            dualSolution[i].second.find(digraph.source(it))
+            == dualSolution[i].second.end()) {
+          sum += dualSolution[i].first;
+        }
+      }
+      if (mca.arborescence(it)) {
+        check(sum == cost[it], "INVALID DUAL");
+      }
+      check(sum <= cost[it], "INVALID DUAL");
+    }
+  }
+
+
+  check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
+
+  check(mca.reached(source), "INVALID ARBORESCENCE");
+  for (ArcIt a(digraph); a != INVALID; ++a) {
+    check(!mca.reached(digraph.source(a)) ||
+          mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
+  }
+
+  for (NodeIt n(digraph); n != INVALID; ++n) {
+    if (!mca.reached(n)) continue;
+    int cnt = 0;
+    for (InArcIt a(digraph, n); a != INVALID; ++a) {
+      if (mca.arborescence(a)) {
+        check(mca.pred(n) == a, "INVALID ARBORESCENCE");
+        ++cnt;
+      }
+    }
+    check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
+  }
+
+  Digraph::ArcMap<bool> arborescence(digraph);
+  check(mca.arborescenceValue() ==
+        minCostArborescence(digraph, cost, source, arborescence),
+        "WRONG FUNCTION");
+
+  return 0;
+}
Index: test/min_cost_flow_test.lgf
===================================================================
--- test/min_cost_flow_test.lgf	(revision 357)
+++ test/min_cost_flow_test.lgf	(revision 357)
@@ -0,0 +1,44 @@
+@nodes
+label	supply1	supply2	supply3
+1	0	20	27	
+2	0	-4	0		
+3	0	0	0	
+4	0	0	0	
+5	0	9	0	
+6	0	-6	0	
+7	0	0	0	
+8	0	0	0	
+9	0	3	0	
+10	0	-2	0	
+11	0	0	0		
+12	0	-20	-27	
+               
+@arcs
+		cost	capacity	lower1	lower2
+1	2	70	11		0	8
+1	3	150	3		0	1
+1	4	80	15		0	2
+2	8	80	12		0	0
+3	5	140	5		0	3
+4	6	60	10		0	1
+4	7	80	2		0	0
+4	8	110	3		0	0
+5	7	60	14		0	0
+5	11	120	12		0	0
+6	3	0	3		0	0
+6	9	140	4		0	0
+6	10	90	8		0	0
+7	1	30	5		0	0
+8	12	60	16		0	4
+9	12	50	6		0	0
+10	12	70	13		0	5
+10	2	100	7		0	0
+10	7	60	10		0	0
+11	10	20	14		0	6
+12	11	30	10		0	0
+
+@attributes
+source	1
+target	12
+
+@end
Index: test/preflow_graph.lgf
===================================================================
--- test/preflow_graph.lgf	(revision 409)
+++ test/preflow_graph.lgf	(revision 409)
@@ -0,0 +1,34 @@
+@nodes
+label
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
+@arcs
+		label	capacity
+0	1	0	20
+0	2	1	0
+1	1	2	3
+1	2	3	8
+1	3	4	8
+2	5	5	5
+3	2	6	5
+3	5	7	5
+3	6	8	5
+4	3	9	3
+5	7	10	3
+5	6	11	10
+5	8	12	10
+6	8	13	8
+8	9	14	20
+8	1	15	5
+9	5	16	5
+@attributes
+source 1
+target 8
Index: test/preflow_test.cc
===================================================================
--- test/preflow_test.cc	(revision 409)
+++ test/preflow_test.cc	(revision 409)
@@ -0,0 +1,213 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * 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 <fstream>
+#include <string>
+
+#include "test_tools.h"
+#include <lemon/smart_graph.h>
+#include <lemon/preflow.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/elevator.h>
+
+using namespace lemon;
+
+void checkPreflowCompile()
+{
+  typedef int VType;
+  typedef concepts::Digraph Digraph;
+
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
+  typedef concepts::ReadMap<Arc,VType> CapMap;
+  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
+  typedef concepts::WriteMap<Node,bool> CutMap;
+
+  typedef Elevator<Digraph, Digraph::Node> Elev;
+  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
+
+  Digraph g;
+  Node n;
+  Arc e;
+  CapMap cap;
+  FlowMap flow;
+  CutMap cut;
+
+  Preflow<Digraph, CapMap>
+    ::SetFlowMap<FlowMap>
+    ::SetElevator<Elev>
+    ::SetStandardElevator<LinkedElev>
+    ::Create preflow_test(g,cap,n,n);
+
+  preflow_test.capacityMap(cap);
+  flow = preflow_test.flowMap();
+  preflow_test.flowMap(flow);
+  preflow_test.source(n);
+  preflow_test.target(n);
+
+  preflow_test.init();
+  preflow_test.init(cap);
+  preflow_test.startFirstPhase();
+  preflow_test.startSecondPhase();
+  preflow_test.run();
+  preflow_test.runMinCut();
+
+  preflow_test.flowValue();
+  preflow_test.minCut(n);
+  preflow_test.minCutMap(cut);
+  preflow_test.flow(e);
+
+}
+
+int cutValue (const SmartDigraph& g,
+              const SmartDigraph::NodeMap<bool>& cut,
+              const SmartDigraph::ArcMap<int>& cap) {
+
+  int c=0;
+  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
+    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
+  }
+  return c;
+}
+
+bool checkFlow(const SmartDigraph& g,
+               const SmartDigraph::ArcMap<int>& flow,
+               const SmartDigraph::ArcMap<int>& cap,
+               SmartDigraph::Node s, SmartDigraph::Node t) {
+
+  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
+    if (flow[e] < 0 || flow[e] > cap[e]) return false;
+  }
+
+  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
+    if (n == s || n == t) continue;
+    int sum = 0;
+    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
+      sum += flow[e];
+    }
+    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
+      sum -= flow[e];
+    }
+    if (sum != 0) return false;
+  }
+  return true;
+}
+
+int main() {
+
+  typedef SmartDigraph Digraph;
+
+  typedef Digraph::Node Node;
+  typedef Digraph::NodeIt NodeIt;
+  typedef Digraph::ArcIt ArcIt;
+  typedef Digraph::ArcMap<int> CapMap;
+  typedef Digraph::ArcMap<int> FlowMap;
+  typedef Digraph::NodeMap<bool> CutMap;
+
+  typedef Preflow<Digraph, CapMap> PType;
+
+  std::string f_name;
+  if( getenv("srcdir") )
+    f_name = std::string(getenv("srcdir"));
+  else f_name = ".";
+  f_name += "/test/preflow_graph.lgf";
+
+  std::ifstream file(f_name.c_str());
+
+  check(file, "Input file '" << f_name << "' not found.");
+
+  Digraph g;
+  Node s, t;
+  CapMap cap(g);
+  DigraphReader<Digraph>(g,file).
+    arcMap("capacity", cap).
+    node("source",s).
+    node("target",t).
+    run();
+
+  PType preflow_test(g, cap, s, t);
+  preflow_test.run();
+
+  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+        "The flow is not feasible.");
+
+  CutMap min_cut(g);
+  preflow_test.minCutMap(min_cut);
+  int min_cut_value=cutValue(g,min_cut,cap);
+
+  check(preflow_test.flowValue() == min_cut_value,
+        "The max flow value is not equal to the three min cut values.");
+
+  FlowMap flow(g);
+  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
+
+  int flow_value=preflow_test.flowValue();
+
+  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
+  preflow_test.init(flow);
+  preflow_test.startFirstPhase();
+
+  CutMap min_cut1(g);
+  preflow_test.minCutMap(min_cut1);
+  min_cut_value=cutValue(g,min_cut1,cap);
+
+  check(preflow_test.flowValue() == min_cut_value &&
+        min_cut_value == 2*flow_value,
+        "The max flow value or the min cut value is wrong.");
+
+  preflow_test.startSecondPhase();
+
+  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+        "The flow is not feasible.");
+
+  CutMap min_cut2(g);
+  preflow_test.minCutMap(min_cut2);
+  min_cut_value=cutValue(g,min_cut2,cap);
+
+  check(preflow_test.flowValue() == min_cut_value &&
+        min_cut_value == 2*flow_value,
+        "The max flow value or the three min cut values were not doubled");
+
+
+  preflow_test.flowMap(flow);
+
+  NodeIt tmp1(g,s);
+  ++tmp1;
+  if ( tmp1 != INVALID ) s=tmp1;
+
+  NodeIt tmp2(g,t);
+  ++tmp2;
+  if ( tmp2 != INVALID ) t=tmp2;
+
+  preflow_test.source(s);
+  preflow_test.target(t);
+
+  preflow_test.run();
+
+  CutMap min_cut3(g);
+  preflow_test.minCutMap(min_cut3);
+  min_cut_value=cutValue(g,min_cut3,cap);
+
+
+  check(preflow_test.flowValue() == min_cut_value,
+        "The max flow value or the three min cut values are incorrect.");
+
+  return 0;
+}
Index: test/suurballe_test.cc
===================================================================
--- test/suurballe_test.cc	(revision 358)
+++ test/suurballe_test.cc	(revision 358)
@@ -0,0 +1,160 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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 <fstream>
+
+#include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/path.h>
+#include <lemon/suurballe.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+// Check the feasibility of the flow
+template <typename Digraph, typename FlowMap>
+bool checkFlow( const Digraph& gr, const FlowMap& flow, 
+                typename Digraph::Node s, typename Digraph::Node t,
+                int value )
+{
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  for (ArcIt e(gr); e != INVALID; ++e)
+    if (!(flow[e] == 0 || flow[e] == 1)) return false;
+
+  for (NodeIt n(gr); n != INVALID; ++n) {
+    int sum = 0;
+    for (OutArcIt e(gr, n); e != INVALID; ++e)
+      sum += flow[e];
+    for (InArcIt e(gr, n); e != INVALID; ++e)
+      sum -= flow[e];
+    if (n == s && sum != value) return false;
+    if (n == t && sum != -value) return false;
+    if (n != s && n != t && sum != 0) return false;
+  }
+
+  return true;
+}
+
+// Check the optimalitiy of the flow
+template < typename Digraph, typename CostMap, 
+           typename FlowMap, typename PotentialMap >
+bool checkOptimality( const Digraph& gr, const CostMap& cost,
+                      const FlowMap& flow, const PotentialMap& pi )
+{
+  // Check the "Complementary Slackness" optimality condition
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  bool opt = true;
+  for (ArcIt e(gr); e != INVALID; ++e) {
+    typename CostMap::Value red_cost =
+      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
+    opt = (flow[e] == 0 && red_cost >= 0) ||
+          (flow[e] == 1 && red_cost <= 0);
+    if (!opt) break;
+  }
+  return opt;
+}
+
+// Check a path
+template <typename Digraph, typename Path>
+bool checkPath( const Digraph& gr, const Path& path,
+                typename Digraph::Node s, typename Digraph::Node t)
+{
+  // Check the "Complementary Slackness" optimality condition
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  Node n = s;
+  for (int i = 0; i < path.length(); ++i) {
+    if (gr.source(path.nth(i)) != n) return false;
+    n = gr.target(path.nth(i));
+  }
+  return n == t;
+}
+
+
+int main()
+{
+  DIGRAPH_TYPEDEFS(ListDigraph);
+
+  // Read the test digraph
+  ListDigraph digraph;
+  ListDigraph::ArcMap<int> length(digraph);
+  Node source, target;
+
+  std::string fname;
+  if(getenv("srcdir"))
+    fname = std::string(getenv("srcdir"));
+  else fname = ".";
+  fname += "/test/min_cost_flow_test.lgf";
+
+  std::ifstream input(fname.c_str());
+  check(input, "Input file '" << fname << "' not found");
+  DigraphReader<ListDigraph>(digraph, input).
+    arcMap("cost", length).
+    node("source", source).
+    node("target", target).
+    run();
+  input.close();
+  
+  // Find 2 paths
+  {
+    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+    check(suurballe.run(2) == 2, "Wrong number of paths");
+    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 510, "The flow is not optimal");
+    check(checkOptimality(digraph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(digraph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
+
+  // Find 3 paths
+  {
+    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+    check(suurballe.run(3) == 3, "Wrong number of paths");
+    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+    check(checkOptimality(digraph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(digraph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
+
+  // Find 5 paths (only 3 can be found)
+  {
+    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
+    check(suurballe.run(5) == 3, "Wrong number of paths");
+    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+    check(checkOptimality(digraph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(digraph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
+
+  return 0;
+}
