test/bfs_test.cc
author kpeter
Thu, 28 Feb 2008 02:55:23 +0000
changeset 2582 4f1ac622bb7a
parent 2391 14a343be7a5a
permissions -rw-r--r--
Avoid map copy in MinCostMaxFlow.
     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/bfs.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_Bfs_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 Bfs<Graph> BType;
    40   
    41   Graph G;
    42   Node n;
    43   Edge e;
    44   int l;
    45   bool b;
    46   BType::DistMap d(G);
    47   BType::PredMap p(G);
    48   //  BType::PredNodeMap pn(G);
    49   
    50   BType bfs_test(G);
    51   
    52   bfs_test.run(n);
    53   
    54   l  = bfs_test.dist(n);
    55   e  = bfs_test.predEdge(n);
    56   n  = bfs_test.predNode(n);
    57   d  = bfs_test.distMap();
    58   p  = bfs_test.predMap();
    59   //  pn = bfs_test.predNodeMap();
    60   b  = bfs_test.reached(n);
    61 
    62   Path<Graph> pp = bfs_test.path(n);
    63 }
    64 
    65 void check_Bfs_Function_Compile() 
    66 {
    67   typedef int VType;
    68   typedef concepts::Graph Graph;
    69 
    70   typedef Graph::Edge Edge;
    71   typedef Graph::Node Node;
    72   typedef Graph::EdgeIt EdgeIt;
    73   typedef Graph::NodeIt NodeIt;
    74   typedef concepts::ReadMap<Edge,VType> LengthMap;
    75    
    76   Graph g;
    77   bfs(g,Node()).run();
    78   bfs(g).source(Node()).run();
    79   bfs(g)
    80     .predMap(concepts::WriteMap<Node,Edge>())
    81     .distMap(concepts::WriteMap<Node,VType>())
    82     .reachedMap(concepts::ReadWriteMap<Node,bool>())
    83     .processedMap(concepts::WriteMap<Node,bool>())
    84     .run(Node());
    85   
    86 }
    87 
    88 int main()
    89 {
    90     
    91   typedef SmartGraph Graph;
    92 
    93   typedef Graph::Edge Edge;
    94   typedef Graph::Node Node;
    95   typedef Graph::EdgeIt EdgeIt;
    96   typedef Graph::NodeIt NodeIt;
    97   typedef Graph::EdgeMap<int> LengthMap;
    98 
    99   Graph G;
   100   Node s, t;
   101   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
   102    
   103   s=ps.outer[2];
   104   t=ps.inner[0];
   105   
   106   Bfs<Graph> bfs_test(G);
   107   bfs_test.run(s);
   108   
   109   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
   110 
   111   Path<Graph> p = bfs_test.path(t);
   112   check(p.length()==3,"getPath() found a wrong path.");
   113   check(checkPath(G, p),"path() found a wrong path.");
   114   check(pathSource(G, p) == s,"path() found a wrong path.");
   115   check(pathTarget(G, p) == t,"path() found a wrong path.");
   116   
   117 
   118   for(EdgeIt e(G); e==INVALID; ++e) {
   119     Node u=G.source(e);
   120     Node v=G.target(e);
   121     check( !bfs_test.reached(u) ||
   122 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
   123 	   "Wrong output.");
   124   }
   125 
   126   for(NodeIt v(G); v==INVALID; ++v) {
   127     check(bfs_test.reached(v),"Each node should be reached.");
   128     if ( bfs_test.predEdge(v)!=INVALID ) {
   129       Edge e=bfs_test.predEdge(v);
   130       Node u=G.source(e);
   131       check(u==bfs_test.predNode(v),"Wrong tree.");
   132       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   133 	    "Wrong distance. Difference: " 
   134 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
   135 			- 1));
   136     }
   137   }
   138 }
   139