COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dfs_test.cc @ 970:09f9abe22df2

Last change on this file since 970:09f9abe22df2 was 959:c80ef5912903, checked in by Mihaly Barasz, 19 years ago

skeleton(s) -> concept renaming

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