test/graph_adaptor_test.cc
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2529 93de38566e6c
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
alpar@906
     1
/* -*- C++ -*-
alpar@906
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906
     8
 *
alpar@906
     9
 * Permission to use, modify and distribute this software is granted
alpar@906
    10
 * provided that this copyright notice appears in all copies. For
alpar@906
    11
 * precise terms see the accompanying LICENSE file.
alpar@906
    12
 *
alpar@906
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    14
 * express or implied, and with no claim as to its suitability for any
alpar@906
    15
 * purpose.
alpar@906
    16
 *
alpar@906
    17
 */
alpar@906
    18
marci@849
    19
#include<iostream>
klao@946
    20
#include<lemon/concept_check.h>
klao@946
    21
alpar@921
    22
#include<lemon/smart_graph.h>
alpar@2260
    23
#include<lemon/concepts/graph.h>
alpar@2260
    24
#include<lemon/concepts/ugraph.h>
alpar@2260
    25
#include<lemon/concepts/bpugraph.h>
klao@946
    26
alpar@921
    27
#include<lemon/list_graph.h>
alpar@921
    28
#include<lemon/full_graph.h>
alpar@1401
    29
#include<lemon/graph_adaptor.h>
deba@1980
    30
#include<lemon/ugraph_adaptor.h>
deba@2231
    31
#include<lemon/bpugraph_adaptor.h>
marci@849
    32
marci@870
    33
#include"test/test_tools.h"
marci@870
    34
#include"test/graph_test.h"
marci@849
    35
marci@849
    36
/**
marci@849
    37
\file
alpar@1401
    38
This test makes consistency checks of graph adaptors.
marci@849
    39
alpar@878
    40
\todo More extensive tests are needed 
marci@849
    41
*/
marci@849
    42
alpar@921
    43
using namespace lemon;
alpar@2260
    44
using namespace lemon::concepts;
marci@849
    45
marci@849
    46
marci@849
    47
marci@849
    48
int main() 
marci@849
    49
{
klao@946
    50
  {
deba@2111
    51
    typedef Graph Graph;
deba@2111
    52
    checkConcept<Graph, GraphAdaptor<Graph> >();
klao@946
    53
deba@2111
    54
    checkConcept<Graph, RevGraphAdaptor<Graph> >();
klao@946
    55
deba@2111
    56
    checkConcept<Graph, SubGraphAdaptor<Graph, 
marci@998
    57
      Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
deba@2111
    58
    checkConcept<Graph, NodeSubGraphAdaptor<Graph, 
marci@998
    59
      Graph::NodeMap<bool> > >();
deba@2111
    60
    checkConcept<Graph, EdgeSubGraphAdaptor<Graph, 
marci@998
    61
      Graph::EdgeMap<bool> > >();
marci@992
    62
    
deba@2111
    63
    checkConcept<Graph, ResGraphAdaptor<Graph, int, 
marci@998
    64
      Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
klao@946
    65
deba@2111
    66
    checkConcept<Graph, ErasingFirstGraphAdaptor<Graph, 
marci@998
    67
      Graph::NodeMap<Graph::Edge> > >(); 
marci@1383
    68
deba@2529
    69
    checkConcept<Graph, SplitGraphAdaptor<Graph> >(); 
deba@2529
    70
deba@1980
    71
    checkConcept<UGraph, UndirGraphAdaptor<Graph> >();
deba@1980
    72
deba@1980
    73
    checkConcept<UGraph, SubUGraphAdaptor<UGraph, 
deba@1980
    74
      UGraph::NodeMap<bool> , UGraph::UEdgeMap<bool> > >();
deba@1980
    75
    checkConcept<UGraph, NodeSubUGraphAdaptor<UGraph, 
deba@1980
    76
      UGraph::NodeMap<bool> > >();
deba@1980
    77
    checkConcept<UGraph, EdgeSubUGraphAdaptor<UGraph, 
deba@1980
    78
      UGraph::UEdgeMap<bool> > >();
deba@1980
    79
deba@2111
    80
    checkConcept<Graph, DirUGraphAdaptor<UGraph, 
deba@1980
    81
      UGraph::UEdgeMap<bool> > >();
deba@2231
    82
deba@2231
    83
    checkConcept<BpUGraph, BpUGraphAdaptor<BpUGraph> >();
deba@2231
    84
deba@2231
    85
    checkConcept<BpUGraph, SwapBpUGraphAdaptor<BpUGraph> >();
deba@2231
    86
klao@946
    87
  }
marci@849
    88
  std::cout << __FILE__ ": All tests passed.\n";
marci@849
    89
marci@849
    90
  return 0;
marci@849
    91
}