src/test/dfs_test.cc
author jacint
Mon, 13 Sep 2004 10:50:28 +0000
changeset 833 512e5fd7d38b
parent 780 e06d0d16595f
child 880 9d0bfd35b97c
permissions -rw-r--r--
preflow test
alpar@780
     1
#include "test_tools.h"
alpar@780
     2
#include <hugo/smart_graph.h>
alpar@780
     3
#include <hugo/dfs.h>
alpar@793
     4
#include<hugo/skeletons/graph.h>
alpar@780
     5
alpar@780
     6
using namespace hugo;
alpar@780
     7
alpar@780
     8
const int PET_SIZE =5;
alpar@780
     9
alpar@780
    10
alpar@780
    11
void check_Dfs_SmartGraph_Compile() 
alpar@780
    12
{
alpar@793
    13
  typedef skeleton::StaticGraphSkeleton Graph;
alpar@780
    14
alpar@780
    15
  typedef Graph::Edge Edge;
alpar@780
    16
  typedef Graph::Node Node;
alpar@780
    17
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    18
  typedef Graph::NodeIt NodeIt;
alpar@780
    19
 
alpar@793
    20
  typedef Dfs<Graph> DType;
alpar@780
    21
  
alpar@780
    22
  Graph G;
alpar@780
    23
  Node n;
alpar@780
    24
  Edge e;
alpar@793
    25
  int l;
alpar@780
    26
  bool b;
alpar@793
    27
  DType::DistMap d(G);
alpar@793
    28
  DType::PredMap p(G);
alpar@793
    29
  DType::PredNodeMap pn(G);
alpar@780
    30
  
alpar@793
    31
  DType dfs_test(G);
alpar@780
    32
  
alpar@780
    33
  dfs_test.run(n);
alpar@780
    34
  
alpar@780
    35
  l  = dfs_test.dist(n);
alpar@780
    36
  e  = dfs_test.pred(n);
alpar@780
    37
  n  = dfs_test.predNode(n);
alpar@780
    38
  d  = dfs_test.distMap();
alpar@780
    39
  p  = dfs_test.predMap();
alpar@780
    40
  pn = dfs_test.predNodeMap();
alpar@780
    41
  b  = dfs_test.reached(n);
alpar@780
    42
alpar@780
    43
}
alpar@780
    44
alpar@780
    45
int main()
alpar@780
    46
{
alpar@780
    47
    
alpar@780
    48
  typedef SmartGraph Graph;
alpar@780
    49
alpar@780
    50
  typedef Graph::Edge Edge;
alpar@780
    51
  typedef Graph::Node Node;
alpar@780
    52
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    53
  typedef Graph::NodeIt NodeIt;
alpar@780
    54
  typedef Graph::EdgeMap<int> LengthMap;
alpar@780
    55
alpar@780
    56
  Graph G;
alpar@780
    57
  Node s, t;
alpar@780
    58
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@780
    59
   
alpar@780
    60
  s=ps.outer[2];
alpar@780
    61
  t=ps.inner[0];
alpar@780
    62
  
alpar@780
    63
  Dfs<Graph> dfs_test(G);
alpar@780
    64
  dfs_test.run(s);  
alpar@780
    65
  
alpar@780
    66
  for(NodeIt v(G); v!=INVALID; ++v) {
alpar@780
    67
    check(dfs_test.reached(v),"Each node should be reached.");
alpar@780
    68
    if ( dfs_test.pred(v)!=INVALID ) {
alpar@780
    69
      Edge e=dfs_test.pred(v);
alpar@780
    70
      Node u=G.tail(e);
alpar@780
    71
      check(u==dfs_test.predNode(v),"Wrong tree.");
alpar@780
    72
      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
alpar@780
    73
	    "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
alpar@780
    74
    }
alpar@780
    75
  }
alpar@780
    76
}
alpar@780
    77