src/test/bfs_test.cc
author marci
Thu, 02 Sep 2004 16:56:33 +0000
changeset 788 c3187cafcabf
parent 774 4297098d9677
child 793 9cd0aeea47b0
permissions -rw-r--r--
mincostflow_test is ok.
alpar@774
     1
#include "test_tools.h"
alpar@774
     2
#include <hugo/smart_graph.h>
alpar@774
     3
#include <hugo/bfs.h>
alpar@774
     4
alpar@774
     5
using namespace hugo;
alpar@774
     6
alpar@774
     7
const int PET_SIZE =5;
alpar@774
     8
alpar@774
     9
alpar@774
    10
void check_Bfs_SmartGraph_Compile() 
alpar@774
    11
{
alpar@774
    12
  typedef int VType;
alpar@774
    13
  typedef SmartGraph Graph;
alpar@774
    14
alpar@774
    15
  typedef Graph::Edge Edge;
alpar@774
    16
  typedef Graph::Node Node;
alpar@774
    17
  typedef Graph::EdgeIt EdgeIt;
alpar@774
    18
  typedef Graph::NodeIt NodeIt;
alpar@774
    19
  typedef Graph::EdgeMap<VType> LengthMap;
alpar@774
    20
 
alpar@774
    21
  typedef Bfs<Graph> BType;
alpar@774
    22
  
alpar@774
    23
  Graph G;
alpar@774
    24
  Node n;
alpar@774
    25
  Edge e;
alpar@774
    26
  VType l;
alpar@774
    27
  bool b;
alpar@774
    28
  BType::DistMap d(G);
alpar@774
    29
  BType::PredMap p(G);
alpar@774
    30
  BType::PredNodeMap pn(G);
alpar@774
    31
  LengthMap cap(G);
alpar@774
    32
  
alpar@774
    33
  BType bfs_test(G);
alpar@774
    34
  
alpar@774
    35
  bfs_test.run(n);
alpar@774
    36
  
alpar@774
    37
  l  = bfs_test.dist(n);
alpar@774
    38
  e  = bfs_test.pred(n);
alpar@774
    39
  n  = bfs_test.predNode(n);
alpar@774
    40
  d  = bfs_test.distMap();
alpar@774
    41
  p  = bfs_test.predMap();
alpar@774
    42
  pn = bfs_test.predNodeMap();
alpar@774
    43
  b  = bfs_test.reached(n);
alpar@774
    44
alpar@774
    45
}
alpar@774
    46
alpar@774
    47
int main()
alpar@774
    48
{
alpar@774
    49
    
alpar@774
    50
  typedef SmartGraph Graph;
alpar@774
    51
alpar@774
    52
  typedef Graph::Edge Edge;
alpar@774
    53
  typedef Graph::Node Node;
alpar@774
    54
  typedef Graph::EdgeIt EdgeIt;
alpar@774
    55
  typedef Graph::NodeIt NodeIt;
alpar@774
    56
  typedef Graph::EdgeMap<int> LengthMap;
alpar@774
    57
alpar@774
    58
  Graph G;
alpar@774
    59
  Node s, t;
alpar@774
    60
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@774
    61
   
alpar@774
    62
  s=ps.outer[2];
alpar@774
    63
  t=ps.inner[0];
alpar@774
    64
  
alpar@774
    65
  Bfs<Graph> bfs_test(G);
alpar@774
    66
  bfs_test.run(s);
alpar@774
    67
  
alpar@774
    68
  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
alpar@774
    69
alpar@774
    70
alpar@774
    71
  for(EdgeIt e(G); e==INVALID; ++e) {
alpar@774
    72
    Node u=G.tail(e);
alpar@774
    73
    Node v=G.head(e);
alpar@774
    74
    check( !bfs_test.reached(u) ||
alpar@774
    75
	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
alpar@774
    76
	   "Wrong output.");
alpar@774
    77
  }
alpar@774
    78
alpar@780
    79
  for(NodeIt v(G); v==INVALID; ++v) {
alpar@780
    80
    check(bfs_test.reached(v),"Each node should be reached.");
alpar@780
    81
    if ( bfs_test.pred(v)!=INVALID ) {
alpar@774
    82
      Edge e=bfs_test.pred(v);
alpar@774
    83
      Node u=G.tail(e);
alpar@780
    84
      check(u==bfs_test.predNode(v),"Wrong tree.");
alpar@774
    85
      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
alpar@780
    86
	    "Wrong distance. Difference: " 
alpar@774
    87
	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
alpar@774
    88
			- 1));
alpar@774
    89
    }
alpar@780
    90
  }
alpar@774
    91
}
alpar@780
    92