test/dfs_test.cc
author alpar
Thu, 23 Oct 2008 16:49:06 +0000
changeset 2626 324cfbf66a12
parent 2391 14a343be7a5a
permissions -rw-r--r--
Adapt the doc generation to the hg repo
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include "test_tools.h"
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/dfs.h>
    22 #include <lemon/path.h>
    23 #include <lemon/concepts/graph.h>
    24 
    25 using namespace lemon;
    26 
    27 const int PET_SIZE =5;
    28 
    29 
    30 void check_Dfs_SmartGraph_Compile() 
    31 {
    32   typedef concepts::Graph Graph;
    33 
    34   typedef Graph::Edge Edge;
    35   typedef Graph::Node Node;
    36   typedef Graph::EdgeIt EdgeIt;
    37   typedef Graph::NodeIt NodeIt;
    38  
    39   typedef Dfs<Graph> DType;
    40   
    41   Graph G;
    42   Node n;
    43   Edge e;
    44   int l;
    45   bool b;
    46   DType::DistMap d(G);
    47   DType::PredMap p(G);
    48   //  DType::PredNodeMap pn(G);
    49   
    50   DType dfs_test(G);
    51   
    52   dfs_test.run(n);
    53   
    54   l  = dfs_test.dist(n);
    55   e  = dfs_test.predEdge(n);
    56   n  = dfs_test.predNode(n);
    57   d  = dfs_test.distMap();
    58   p  = dfs_test.predMap();
    59   //  pn = dfs_test.predNodeMap();
    60   b  = dfs_test.reached(n);
    61 
    62   Path<Graph> pp = dfs_test.path(n);
    63 }
    64 
    65 
    66 void check_Dfs_Function_Compile() 
    67 {
    68   typedef int VType;
    69   typedef concepts::Graph Graph;
    70 
    71   typedef Graph::Edge Edge;
    72   typedef Graph::Node Node;
    73   typedef Graph::EdgeIt EdgeIt;
    74   typedef Graph::NodeIt NodeIt;
    75   typedef concepts::ReadMap<Edge,VType> LengthMap;
    76    
    77   Graph g;
    78   dfs(g,Node()).run();
    79   dfs(g).source(Node()).run();
    80   dfs(g)
    81     .predMap(concepts::WriteMap<Node,Edge>())
    82     .distMap(concepts::WriteMap<Node,VType>())
    83     .reachedMap(concepts::ReadWriteMap<Node,bool>())
    84     .processedMap(concepts::WriteMap<Node,bool>())
    85     .run(Node());
    86   
    87 }
    88 
    89 int main()
    90 {
    91     
    92   typedef SmartGraph Graph;
    93 
    94   typedef Graph::Edge Edge;
    95   typedef Graph::Node Node;
    96   typedef Graph::EdgeIt EdgeIt;
    97   typedef Graph::NodeIt NodeIt;
    98   typedef Graph::EdgeMap<int> LengthMap;
    99 
   100   Graph G;
   101   Node s, t;
   102   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
   103    
   104   s=ps.outer[2];
   105   t=ps.inner[0];
   106   
   107   Dfs<Graph> dfs_test(G);
   108   dfs_test.run(s);  
   109   
   110   Path<Graph> p = dfs_test.path(t);
   111   check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
   112   check(checkPath(G, p),"path() found a wrong path.");
   113   check(pathSource(G, p) == s,"path() found a wrong path.");
   114   check(pathTarget(G, p) == t,"path() found a wrong path.");
   115   
   116   for(NodeIt v(G); v!=INVALID; ++v) {
   117     check(dfs_test.reached(v),"Each node should be reached.");
   118     if ( dfs_test.predEdge(v)!=INVALID ) {
   119       Edge e=dfs_test.predEdge(v);
   120       Node u=G.source(e);
   121       check(u==dfs_test.predNode(v),"Wrong tree.");
   122       check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
   123 	    "Wrong distance. (" << dfs_test.dist(u) << "->" 
   124 	    <<dfs_test.dist(v) << ')');
   125     }
   126   }
   127 }
   128