src/test/dfs_test.cc
author ladanyi
Fri, 11 Feb 2005 14:56:40 +0000
changeset 1145 99c1aa395a58
parent 959 c80ef5912903
child 1164 80bb73097736
permissions -rw-r--r--
more docs
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/test/dfs_test.cc - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@906
     4
 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
alpar@780
    17
#include "test_tools.h"
alpar@921
    18
#include <lemon/smart_graph.h>
alpar@921
    19
#include <lemon/dfs.h>
klao@959
    20
#include <lemon/concept/graph.h>
alpar@780
    21
alpar@921
    22
using namespace lemon;
alpar@780
    23
alpar@780
    24
const int PET_SIZE =5;
alpar@780
    25
alpar@780
    26
alpar@780
    27
void check_Dfs_SmartGraph_Compile() 
alpar@780
    28
{
klao@959
    29
  typedef concept::StaticGraph Graph;
alpar@780
    30
alpar@780
    31
  typedef Graph::Edge Edge;
alpar@780
    32
  typedef Graph::Node Node;
alpar@780
    33
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    34
  typedef Graph::NodeIt NodeIt;
alpar@780
    35
 
alpar@793
    36
  typedef Dfs<Graph> DType;
alpar@780
    37
  
alpar@780
    38
  Graph G;
alpar@780
    39
  Node n;
alpar@780
    40
  Edge e;
alpar@793
    41
  int l;
alpar@780
    42
  bool b;
alpar@793
    43
  DType::DistMap d(G);
alpar@793
    44
  DType::PredMap p(G);
alpar@793
    45
  DType::PredNodeMap pn(G);
alpar@780
    46
  
alpar@793
    47
  DType dfs_test(G);
alpar@780
    48
  
alpar@780
    49
  dfs_test.run(n);
alpar@780
    50
  
alpar@780
    51
  l  = dfs_test.dist(n);
alpar@780
    52
  e  = dfs_test.pred(n);
alpar@780
    53
  n  = dfs_test.predNode(n);
alpar@780
    54
  d  = dfs_test.distMap();
alpar@780
    55
  p  = dfs_test.predMap();
alpar@780
    56
  pn = dfs_test.predNodeMap();
alpar@780
    57
  b  = dfs_test.reached(n);
alpar@780
    58
alpar@780
    59
}
alpar@780
    60
alpar@780
    61
int main()
alpar@780
    62
{
alpar@780
    63
    
alpar@780
    64
  typedef SmartGraph Graph;
alpar@780
    65
alpar@780
    66
  typedef Graph::Edge Edge;
alpar@780
    67
  typedef Graph::Node Node;
alpar@780
    68
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    69
  typedef Graph::NodeIt NodeIt;
alpar@780
    70
  typedef Graph::EdgeMap<int> LengthMap;
alpar@780
    71
alpar@780
    72
  Graph G;
alpar@780
    73
  Node s, t;
alpar@780
    74
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@780
    75
   
alpar@780
    76
  s=ps.outer[2];
alpar@780
    77
  t=ps.inner[0];
alpar@780
    78
  
alpar@780
    79
  Dfs<Graph> dfs_test(G);
alpar@780
    80
  dfs_test.run(s);  
alpar@780
    81
  
alpar@780
    82
  for(NodeIt v(G); v!=INVALID; ++v) {
alpar@780
    83
    check(dfs_test.reached(v),"Each node should be reached.");
alpar@780
    84
    if ( dfs_test.pred(v)!=INVALID ) {
alpar@780
    85
      Edge e=dfs_test.pred(v);
alpar@986
    86
      Node u=G.source(e);
alpar@780
    87
      check(u==dfs_test.predNode(v),"Wrong tree.");
alpar@780
    88
      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
alpar@780
    89
	    "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
alpar@780
    90
    }
alpar@780
    91
  }
alpar@780
    92
}
alpar@780
    93