test/bfs_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 20 Feb 2009 21:37:19 +0000
changeset 517 2b6d5d22bb23
parent 293 47fbc814aa31
child 585 65fbcf2f978a
permissions -rw-r--r--
Merge
     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-2009
     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;
    62   Arc e;
    63   int l;
    64   bool b;
    65   BType::DistMap d(G);
    66   BType::PredMap p(G);
    67   Path<Digraph> pp;
    68 
    69   {
    70     BType bfs_test(G);
    71 
    72     bfs_test.run(s);
    73     bfs_test.run(s,t);
    74     bfs_test.run();
    75 
    76     l  = bfs_test.dist(t);
    77     e  = bfs_test.predArc(t);
    78     s  = bfs_test.predNode(t);
    79     b  = bfs_test.reached(t);
    80     d  = bfs_test.distMap();
    81     p  = bfs_test.predMap();
    82     pp = bfs_test.path(t);
    83   }
    84   {
    85     BType
    86       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    87       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    88       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
    89       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    90       ::SetStandardProcessedMap
    91       ::Create bfs_test(G);
    92 
    93     bfs_test.run(s);
    94     bfs_test.run(s,t);
    95     bfs_test.run();
    96 
    97     l  = bfs_test.dist(t);
    98     e  = bfs_test.predArc(t);
    99     s  = bfs_test.predNode(t);
   100     b  = bfs_test.reached(t);
   101     pp = bfs_test.path(t);
   102   }
   103 }
   104 
   105 void checkBfsFunctionCompile()
   106 {
   107   typedef int VType;
   108   typedef concepts::Digraph Digraph;
   109   typedef Digraph::Arc Arc;
   110   typedef Digraph::Node Node;
   111 
   112   Digraph g;
   113   bool b;
   114   bfs(g).run(Node());
   115   b=bfs(g).run(Node(),Node());
   116   bfs(g).run();
   117   bfs(g)
   118     .predMap(concepts::ReadWriteMap<Node,Arc>())
   119     .distMap(concepts::ReadWriteMap<Node,VType>())
   120     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   121     .processedMap(concepts::WriteMap<Node,bool>())
   122     .run(Node());
   123   b=bfs(g)
   124     .predMap(concepts::ReadWriteMap<Node,Arc>())
   125     .distMap(concepts::ReadWriteMap<Node,VType>())
   126     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   127     .processedMap(concepts::WriteMap<Node,bool>())
   128     .path(concepts::Path<Digraph>())
   129     .dist(VType())
   130     .run(Node(),Node());
   131   bfs(g)
   132     .predMap(concepts::ReadWriteMap<Node,Arc>())
   133     .distMap(concepts::ReadWriteMap<Node,VType>())
   134     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   135     .processedMap(concepts::WriteMap<Node,bool>())
   136     .run();
   137 }
   138 
   139 template <class Digraph>
   140 void checkBfs() {
   141   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   142 
   143   Digraph G;
   144   Node s, t;
   145 
   146   std::istringstream input(test_lgf);
   147   digraphReader(G, input).
   148     node("source", s).
   149     node("target", t).
   150     run();
   151 
   152   Bfs<Digraph> bfs_test(G);
   153   bfs_test.run(s);
   154 
   155   check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
   156 
   157   Path<Digraph> p = bfs_test.path(t);
   158   check(p.length()==2,"path() found a wrong path.");
   159   check(checkPath(G, p),"path() found a wrong path.");
   160   check(pathSource(G, p) == s,"path() found a wrong path.");
   161   check(pathTarget(G, p) == t,"path() found a wrong path.");
   162 
   163 
   164   for(ArcIt a(G); a!=INVALID; ++a) {
   165     Node u=G.source(a);
   166     Node v=G.target(a);
   167     check( !bfs_test.reached(u) ||
   168            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
   169            "Wrong output. " << G.id(u) << "->" << G.id(v));
   170   }
   171 
   172   for(NodeIt v(G); v!=INVALID; ++v) {
   173     if (bfs_test.reached(v)) {
   174       check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
   175       if (bfs_test.predArc(v)!=INVALID ) {
   176         Arc a=bfs_test.predArc(v);
   177         Node u=G.source(a);
   178         check(u==bfs_test.predNode(v),"Wrong tree.");
   179         check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   180               "Wrong distance. Difference: "
   181               << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
   182       }
   183     }
   184   }
   185 
   186   {
   187     NullMap<Node,Arc> myPredMap;
   188     bfs(G).predMap(myPredMap).run(s);
   189   }
   190 }
   191 
   192 int main()
   193 {
   194   checkBfs<ListDigraph>();
   195   checkBfs<SmartDigraph>();
   196   return 0;
   197 }