test/bfs_test.cc
author ladanyi
Tue, 04 Jul 2006 18:53:24 +0000
changeset 2118 54350d5c316a
parent 1956 a055123339d5
child 2135 15355b98fb84
permissions -rw-r--r--
Distribute Doxyfile.in and lemon.pc.in.
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@1956
     5
 * Copyright (C) 2003-2006
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
alpar@774
    19
#include "test_tools.h"
alpar@921
    20
#include <lemon/smart_graph.h>
alpar@921
    21
#include <lemon/bfs.h>
alpar@1283
    22
#include <lemon/path.h>
klao@959
    23
#include<lemon/concept/graph.h>
alpar@774
    24
alpar@921
    25
using namespace lemon;
alpar@774
    26
alpar@774
    27
const int PET_SIZE =5;
alpar@774
    28
alpar@774
    29
alpar@793
    30
void check_Bfs_Compile() 
alpar@774
    31
{
deba@2111
    32
  typedef concept::Graph Graph;
alpar@774
    33
alpar@774
    34
  typedef Graph::Edge Edge;
alpar@774
    35
  typedef Graph::Node Node;
alpar@774
    36
  typedef Graph::EdgeIt EdgeIt;
alpar@774
    37
  typedef Graph::NodeIt NodeIt;
alpar@774
    38
 
alpar@774
    39
  typedef Bfs<Graph> BType;
alpar@774
    40
  
alpar@774
    41
  Graph G;
alpar@774
    42
  Node n;
alpar@774
    43
  Edge e;
alpar@793
    44
  int l;
alpar@774
    45
  bool b;
alpar@774
    46
  BType::DistMap d(G);
alpar@774
    47
  BType::PredMap p(G);
alpar@1218
    48
  //  BType::PredNodeMap pn(G);
alpar@774
    49
  
alpar@774
    50
  BType bfs_test(G);
alpar@774
    51
  
alpar@774
    52
  bfs_test.run(n);
alpar@774
    53
  
alpar@774
    54
  l  = bfs_test.dist(n);
deba@1763
    55
  e  = bfs_test.predEdge(n);
alpar@774
    56
  n  = bfs_test.predNode(n);
alpar@774
    57
  d  = bfs_test.distMap();
alpar@774
    58
  p  = bfs_test.predMap();
alpar@1218
    59
  //  pn = bfs_test.predNodeMap();
alpar@774
    60
  b  = bfs_test.reached(n);
alpar@774
    61
alpar@1283
    62
  DirPath<Graph> pp(G);
alpar@1283
    63
  bfs_test.getPath(pp,n);
alpar@774
    64
}
alpar@774
    65
alpar@1220
    66
void check_Bfs_Function_Compile() 
alpar@1220
    67
{
alpar@1220
    68
  typedef int VType;
deba@2111
    69
  typedef concept::Graph Graph;
alpar@1220
    70
alpar@1220
    71
  typedef Graph::Edge Edge;
alpar@1220
    72
  typedef Graph::Node Node;
alpar@1220
    73
  typedef Graph::EdgeIt EdgeIt;
alpar@1220
    74
  typedef Graph::NodeIt NodeIt;
alpar@1220
    75
  typedef concept::ReadMap<Edge,VType> LengthMap;
alpar@1220
    76
   
alpar@1220
    77
  bfs(Graph(),Node()).run();
alpar@1220
    78
  bfs(Graph()).source(Node()).run();
alpar@1220
    79
  bfs(Graph())
alpar@1220
    80
    .predMap(concept::WriteMap<Node,Edge>())
alpar@1220
    81
    .distMap(concept::WriteMap<Node,VType>())
alpar@1220
    82
    .reachedMap(concept::ReadWriteMap<Node,bool>())
alpar@1220
    83
    .processedMap(concept::WriteMap<Node,bool>())
alpar@1220
    84
    .run(Node());
alpar@1220
    85
  
alpar@1220
    86
}
alpar@1220
    87
alpar@774
    88
int main()
alpar@774
    89
{
alpar@774
    90
    
alpar@774
    91
  typedef SmartGraph Graph;
alpar@774
    92
alpar@774
    93
  typedef Graph::Edge Edge;
alpar@774
    94
  typedef Graph::Node Node;
alpar@774
    95
  typedef Graph::EdgeIt EdgeIt;
alpar@774
    96
  typedef Graph::NodeIt NodeIt;
alpar@774
    97
  typedef Graph::EdgeMap<int> LengthMap;
alpar@774
    98
alpar@774
    99
  Graph G;
alpar@774
   100
  Node s, t;
alpar@774
   101
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@774
   102
   
alpar@774
   103
  s=ps.outer[2];
alpar@774
   104
  t=ps.inner[0];
alpar@774
   105
  
alpar@774
   106
  Bfs<Graph> bfs_test(G);
alpar@774
   107
  bfs_test.run(s);
alpar@774
   108
  
alpar@774
   109
  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
alpar@774
   110
alpar@1283
   111
  DirPath<Graph> p(G);
alpar@1283
   112
  check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
alpar@1283
   113
  check(p.length()==3,"getPath() found a wrong path.");
alpar@1283
   114
  
alpar@774
   115
alpar@774
   116
  for(EdgeIt e(G); e==INVALID; ++e) {
alpar@986
   117
    Node u=G.source(e);
alpar@986
   118
    Node v=G.target(e);
alpar@774
   119
    check( !bfs_test.reached(u) ||
alpar@774
   120
	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
alpar@774
   121
	   "Wrong output.");
alpar@774
   122
  }
alpar@774
   123
alpar@780
   124
  for(NodeIt v(G); v==INVALID; ++v) {
alpar@780
   125
    check(bfs_test.reached(v),"Each node should be reached.");
deba@1763
   126
    if ( bfs_test.predEdge(v)!=INVALID ) {
deba@1763
   127
      Edge e=bfs_test.predEdge(v);
alpar@986
   128
      Node u=G.source(e);
alpar@780
   129
      check(u==bfs_test.predNode(v),"Wrong tree.");
alpar@774
   130
      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
alpar@780
   131
	    "Wrong distance. Difference: " 
alpar@774
   132
	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
alpar@774
   133
			- 1));
alpar@774
   134
    }
alpar@780
   135
  }
alpar@774
   136
}
alpar@780
   137