test/bfs_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 07 Aug 2013 07:09:31 +0200
branch1.2
changeset 985 b9887ae63df0
parent 970 d216e1c8b3fa
parent 982 3e711ee55d31
permissions -rw-r--r--
Merge #294 to branch 1.2
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     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 <lemon/concepts/digraph.h>
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/list_graph.h>
    22 #include <lemon/lgf_reader.h>
    23 #include <lemon/bfs.h>
    24 #include <lemon/path.h>
    25 
    26 #include "graph_test.h"
    27 #include "test_tools.h"
    28 
    29 using namespace lemon;
    30 
    31 char test_lgf[] =
    32   "@nodes\n"
    33   "label\n"
    34   "0\n"
    35   "1\n"
    36   "2\n"
    37   "3\n"
    38   "4\n"
    39   "5\n"
    40   "@arcs\n"
    41   "     label\n"
    42   "0 1  0\n"
    43   "1 2  1\n"
    44   "2 3  2\n"
    45   "3 4  3\n"
    46   "0 3  4\n"
    47   "0 3  5\n"
    48   "5 2  6\n"
    49   "@attributes\n"
    50   "source 0\n"
    51   "target 4\n";
    52 
    53 void checkBfsCompile()
    54 {
    55   typedef concepts::Digraph Digraph;
    56   typedef Bfs<Digraph> BType;
    57   typedef Digraph::Node Node;
    58   typedef Digraph::Arc Arc;
    59 
    60   Digraph G;
    61   Node s, t, n;
    62   Arc e;
    63   int l, i;
    64   ::lemon::ignore_unused_variable_warning(l,i);
    65   bool b;
    66   BType::DistMap d(G);
    67   BType::PredMap p(G);
    68   Path<Digraph> pp;
    69   concepts::ReadMap<Node,bool> nm;
    70 
    71   {
    72     BType bfs_test(G);
    73     const BType& const_bfs_test = bfs_test;
    74 
    75     bfs_test.run(s);
    76     bfs_test.run(s,t);
    77     bfs_test.run();
    78 
    79     bfs_test.init();
    80     bfs_test.addSource(s);
    81     n = bfs_test.processNextNode();
    82     n = bfs_test.processNextNode(t, b);
    83     n = bfs_test.processNextNode(nm, n);
    84     n = const_bfs_test.nextNode();
    85     b = const_bfs_test.emptyQueue();
    86     i = const_bfs_test.queueSize();
    87 
    88     bfs_test.start();
    89     bfs_test.start(t);
    90     bfs_test.start(nm);
    91 
    92     l  = const_bfs_test.dist(t);
    93     e  = const_bfs_test.predArc(t);
    94     s  = const_bfs_test.predNode(t);
    95     b  = const_bfs_test.reached(t);
    96     d  = const_bfs_test.distMap();
    97     p  = const_bfs_test.predMap();
    98     pp = const_bfs_test.path(t);
    99   }
   100   {
   101     BType
   102       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   103       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
   104       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
   105       ::SetStandardProcessedMap
   106       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
   107       ::Create bfs_test(G);
   108 
   109     concepts::ReadWriteMap<Node,Arc> pred_map;
   110     concepts::ReadWriteMap<Node,int> dist_map;
   111     concepts::ReadWriteMap<Node,bool> reached_map;
   112     concepts::WriteMap<Node,bool> processed_map;
   113 
   114     bfs_test
   115       .predMap(pred_map)
   116       .distMap(dist_map)
   117       .reachedMap(reached_map)
   118       .processedMap(processed_map);
   119 
   120     bfs_test.run(s);
   121     bfs_test.run(s,t);
   122     bfs_test.run();
   123 
   124     bfs_test.init();
   125     bfs_test.addSource(s);
   126     n = bfs_test.processNextNode();
   127     n = bfs_test.processNextNode(t, b);
   128     n = bfs_test.processNextNode(nm, n);
   129     n = bfs_test.nextNode();
   130     b = bfs_test.emptyQueue();
   131     i = bfs_test.queueSize();
   132 
   133     bfs_test.start();
   134     bfs_test.start(t);
   135     bfs_test.start(nm);
   136 
   137     l  = bfs_test.dist(t);
   138     e  = bfs_test.predArc(t);
   139     s  = bfs_test.predNode(t);
   140     b  = bfs_test.reached(t);
   141     pp = bfs_test.path(t);
   142   }
   143 }
   144 
   145 void checkBfsFunctionCompile()
   146 {
   147   typedef int VType;
   148   typedef concepts::Digraph Digraph;
   149   typedef Digraph::Arc Arc;
   150   typedef Digraph::Node Node;
   151 
   152   Digraph g;
   153   bool b;
   154   ::lemon::ignore_unused_variable_warning(b);
   155 
   156   bfs(g).run(Node());
   157   b=bfs(g).run(Node(),Node());
   158   bfs(g).run();
   159   bfs(g)
   160     .predMap(concepts::ReadWriteMap<Node,Arc>())
   161     .distMap(concepts::ReadWriteMap<Node,VType>())
   162     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   163     .processedMap(concepts::WriteMap<Node,bool>())
   164     .run(Node());
   165   b=bfs(g)
   166     .predMap(concepts::ReadWriteMap<Node,Arc>())
   167     .distMap(concepts::ReadWriteMap<Node,VType>())
   168     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   169     .processedMap(concepts::WriteMap<Node,bool>())
   170     .path(concepts::Path<Digraph>())
   171     .dist(VType())
   172     .run(Node(),Node());
   173   bfs(g)
   174     .predMap(concepts::ReadWriteMap<Node,Arc>())
   175     .distMap(concepts::ReadWriteMap<Node,VType>())
   176     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   177     .processedMap(concepts::WriteMap<Node,bool>())
   178     .run();
   179 }
   180 
   181 template <class Digraph>
   182 void checkBfs() {
   183   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   184 
   185   Digraph G;
   186   Node s, t;
   187 
   188   std::istringstream input(test_lgf);
   189   digraphReader(G, input).
   190     node("source", s).
   191     node("target", t).
   192     run();
   193 
   194   Bfs<Digraph> bfs_test(G);
   195   bfs_test.run(s);
   196 
   197   check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
   198 
   199   Path<Digraph> p = bfs_test.path(t);
   200   check(p.length()==2,"path() found a wrong path.");
   201   check(checkPath(G, p),"path() found a wrong path.");
   202   check(pathSource(G, p) == s,"path() found a wrong path.");
   203   check(pathTarget(G, p) == t,"path() found a wrong path.");
   204 
   205 
   206   for(ArcIt a(G); a!=INVALID; ++a) {
   207     Node u=G.source(a);
   208     Node v=G.target(a);
   209     check( !bfs_test.reached(u) ||
   210            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
   211            "Wrong output. " << G.id(u) << "->" << G.id(v));
   212   }
   213 
   214   for(NodeIt v(G); v!=INVALID; ++v) {
   215     if (bfs_test.reached(v)) {
   216       check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
   217       if (bfs_test.predArc(v)!=INVALID ) {
   218         Arc a=bfs_test.predArc(v);
   219         Node u=G.source(a);
   220         check(u==bfs_test.predNode(v),"Wrong tree.");
   221         check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   222               "Wrong distance. Difference: "
   223               << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
   224       }
   225     }
   226   }
   227 
   228   {
   229     NullMap<Node,Arc> myPredMap;
   230     bfs(G).predMap(myPredMap).run(s);
   231   }
   232 }
   233 
   234 int main()
   235 {
   236   checkBfs<ListDigraph>();
   237   checkBfs<SmartDigraph>();
   238   return 0;
   239 }