test/dfs_test.cc
author deba
Mon, 20 Feb 2006 09:40:07 +0000
changeset 1975 64db671eda28
parent 1875 98698b69a902
child 2111 ea1fa1bc3f6d
permissions -rw-r--r--
Second renaming of min cut

Minimum => Min
Work => Aux
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@780
    19
#include "test_tools.h"
alpar@921
    20
#include <lemon/smart_graph.h>
alpar@921
    21
#include <lemon/dfs.h>
alpar@1283
    22
#include <lemon/path.h>
klao@959
    23
#include <lemon/concept/graph.h>
alpar@780
    24
alpar@921
    25
using namespace lemon;
alpar@780
    26
alpar@780
    27
const int PET_SIZE =5;
alpar@780
    28
alpar@780
    29
alpar@780
    30
void check_Dfs_SmartGraph_Compile() 
alpar@780
    31
{
klao@959
    32
  typedef concept::StaticGraph Graph;
alpar@780
    33
alpar@780
    34
  typedef Graph::Edge Edge;
alpar@780
    35
  typedef Graph::Node Node;
alpar@780
    36
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    37
  typedef Graph::NodeIt NodeIt;
alpar@780
    38
 
alpar@793
    39
  typedef Dfs<Graph> DType;
alpar@780
    40
  
alpar@780
    41
  Graph G;
alpar@780
    42
  Node n;
alpar@780
    43
  Edge e;
alpar@793
    44
  int l;
alpar@780
    45
  bool b;
alpar@793
    46
  DType::DistMap d(G);
alpar@793
    47
  DType::PredMap p(G);
alpar@1218
    48
  //  DType::PredNodeMap pn(G);
alpar@780
    49
  
alpar@793
    50
  DType dfs_test(G);
alpar@780
    51
  
alpar@780
    52
  dfs_test.run(n);
alpar@780
    53
  
alpar@780
    54
  l  = dfs_test.dist(n);
deba@1763
    55
  e  = dfs_test.predEdge(n);
alpar@780
    56
  n  = dfs_test.predNode(n);
alpar@780
    57
  d  = dfs_test.distMap();
alpar@780
    58
  p  = dfs_test.predMap();
alpar@1218
    59
  //  pn = dfs_test.predNodeMap();
alpar@780
    60
  b  = dfs_test.reached(n);
alpar@780
    61
alpar@1283
    62
  DirPath<Graph> pp(G);
alpar@1283
    63
  dfs_test.getPath(pp,n);
alpar@780
    64
}
alpar@780
    65
alpar@1220
    66
alpar@1220
    67
void check_Dfs_Function_Compile() 
alpar@1220
    68
{
alpar@1220
    69
  typedef int VType;
alpar@1220
    70
  typedef concept::StaticGraph Graph;
alpar@1220
    71
alpar@1220
    72
  typedef Graph::Edge Edge;
alpar@1220
    73
  typedef Graph::Node Node;
alpar@1220
    74
  typedef Graph::EdgeIt EdgeIt;
alpar@1220
    75
  typedef Graph::NodeIt NodeIt;
alpar@1220
    76
  typedef concept::ReadMap<Edge,VType> LengthMap;
alpar@1220
    77
   
alpar@1220
    78
  dfs(Graph(),Node()).run();
alpar@1220
    79
  dfs(Graph()).source(Node()).run();
alpar@1220
    80
  dfs(Graph())
alpar@1220
    81
    .predMap(concept::WriteMap<Node,Edge>())
alpar@1220
    82
    .distMap(concept::WriteMap<Node,VType>())
alpar@1220
    83
    .reachedMap(concept::ReadWriteMap<Node,bool>())
alpar@1220
    84
    .processedMap(concept::WriteMap<Node,bool>())
alpar@1220
    85
    .run(Node());
alpar@1220
    86
  
alpar@1220
    87
}
alpar@1220
    88
alpar@780
    89
int main()
alpar@780
    90
{
alpar@780
    91
    
alpar@780
    92
  typedef SmartGraph Graph;
alpar@780
    93
alpar@780
    94
  typedef Graph::Edge Edge;
alpar@780
    95
  typedef Graph::Node Node;
alpar@780
    96
  typedef Graph::EdgeIt EdgeIt;
alpar@780
    97
  typedef Graph::NodeIt NodeIt;
alpar@780
    98
  typedef Graph::EdgeMap<int> LengthMap;
alpar@780
    99
alpar@780
   100
  Graph G;
alpar@780
   101
  Node s, t;
alpar@780
   102
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@780
   103
   
alpar@780
   104
  s=ps.outer[2];
alpar@780
   105
  t=ps.inner[0];
alpar@780
   106
  
alpar@780
   107
  Dfs<Graph> dfs_test(G);
alpar@780
   108
  dfs_test.run(s);  
alpar@780
   109
  
alpar@1283
   110
  DirPath<Graph> p(G);
alpar@1283
   111
  check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
alpar@1283
   112
  check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
alpar@1283
   113
  
alpar@780
   114
  for(NodeIt v(G); v!=INVALID; ++v) {
alpar@780
   115
    check(dfs_test.reached(v),"Each node should be reached.");
deba@1763
   116
    if ( dfs_test.predEdge(v)!=INVALID ) {
deba@1763
   117
      Edge e=dfs_test.predEdge(v);
alpar@986
   118
      Node u=G.source(e);
alpar@780
   119
      check(u==dfs_test.predNode(v),"Wrong tree.");
alpar@780
   120
      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
alpar@1233
   121
	    "Wrong distance. (" << dfs_test.dist(u) << "->" 
alpar@1233
   122
	    <<dfs_test.dist(v) << ')');
alpar@780
   123
    }
alpar@780
   124
  }
alpar@780
   125
}
alpar@780
   126