test/bfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:52:51 +0100
changeset 813 25804ef35064
parent 440 88ed40ad0d4f
child 877 141f9c0db4a3
child 1007 7e368d9b67f7
permissions -rw-r--r--
Add citations to the scaling MCF algorithms (#180, #184)
and improve the doc of their group.
     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, n;
    62   Arc e;
    63   int l, i;
    64   bool b;
    65   BType::DistMap d(G);
    66   BType::PredMap p(G);
    67   Path<Digraph> pp;
    68   concepts::ReadMap<Node,bool> nm;
    69 
    70   {
    71     BType bfs_test(G);
    72     const BType& const_bfs_test = bfs_test;
    73 
    74     bfs_test.run(s);
    75     bfs_test.run(s,t);
    76     bfs_test.run();
    77 
    78     bfs_test.init();
    79     bfs_test.addSource(s);
    80     n = bfs_test.processNextNode();
    81     n = bfs_test.processNextNode(t, b);
    82     n = bfs_test.processNextNode(nm, n);
    83     n = const_bfs_test.nextNode();
    84     b = const_bfs_test.emptyQueue();
    85     i = const_bfs_test.queueSize();
    86     
    87     bfs_test.start();
    88     bfs_test.start(t);
    89     bfs_test.start(nm);
    90 
    91     l  = const_bfs_test.dist(t);
    92     e  = const_bfs_test.predArc(t);
    93     s  = const_bfs_test.predNode(t);
    94     b  = const_bfs_test.reached(t);
    95     d  = const_bfs_test.distMap();
    96     p  = const_bfs_test.predMap();
    97     pp = const_bfs_test.path(t);
    98   }
    99   {
   100     BType
   101       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
   102       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
   103       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
   104       ::SetStandardProcessedMap
   105       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
   106       ::Create bfs_test(G);
   107       
   108     concepts::ReadWriteMap<Node,Arc> pred_map;
   109     concepts::ReadWriteMap<Node,int> dist_map;
   110     concepts::ReadWriteMap<Node,bool> reached_map;
   111     concepts::WriteMap<Node,bool> processed_map;
   112     
   113     bfs_test
   114       .predMap(pred_map)
   115       .distMap(dist_map)
   116       .reachedMap(reached_map)
   117       .processedMap(processed_map);
   118 
   119     bfs_test.run(s);
   120     bfs_test.run(s,t);
   121     bfs_test.run();
   122     
   123     bfs_test.init();
   124     bfs_test.addSource(s);
   125     n = bfs_test.processNextNode();
   126     n = bfs_test.processNextNode(t, b);
   127     n = bfs_test.processNextNode(nm, n);
   128     n = bfs_test.nextNode();
   129     b = bfs_test.emptyQueue();
   130     i = bfs_test.queueSize();
   131     
   132     bfs_test.start();
   133     bfs_test.start(t);
   134     bfs_test.start(nm);
   135 
   136     l  = bfs_test.dist(t);
   137     e  = bfs_test.predArc(t);
   138     s  = bfs_test.predNode(t);
   139     b  = bfs_test.reached(t);
   140     pp = bfs_test.path(t);
   141   }
   142 }
   143 
   144 void checkBfsFunctionCompile()
   145 {
   146   typedef int VType;
   147   typedef concepts::Digraph Digraph;
   148   typedef Digraph::Arc Arc;
   149   typedef Digraph::Node Node;
   150 
   151   Digraph g;
   152   bool b;
   153   bfs(g).run(Node());
   154   b=bfs(g).run(Node(),Node());
   155   bfs(g).run();
   156   bfs(g)
   157     .predMap(concepts::ReadWriteMap<Node,Arc>())
   158     .distMap(concepts::ReadWriteMap<Node,VType>())
   159     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   160     .processedMap(concepts::WriteMap<Node,bool>())
   161     .run(Node());
   162   b=bfs(g)
   163     .predMap(concepts::ReadWriteMap<Node,Arc>())
   164     .distMap(concepts::ReadWriteMap<Node,VType>())
   165     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   166     .processedMap(concepts::WriteMap<Node,bool>())
   167     .path(concepts::Path<Digraph>())
   168     .dist(VType())
   169     .run(Node(),Node());
   170   bfs(g)
   171     .predMap(concepts::ReadWriteMap<Node,Arc>())
   172     .distMap(concepts::ReadWriteMap<Node,VType>())
   173     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   174     .processedMap(concepts::WriteMap<Node,bool>())
   175     .run();
   176 }
   177 
   178 template <class Digraph>
   179 void checkBfs() {
   180   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   181 
   182   Digraph G;
   183   Node s, t;
   184 
   185   std::istringstream input(test_lgf);
   186   digraphReader(G, input).
   187     node("source", s).
   188     node("target", t).
   189     run();
   190 
   191   Bfs<Digraph> bfs_test(G);
   192   bfs_test.run(s);
   193 
   194   check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
   195 
   196   Path<Digraph> p = bfs_test.path(t);
   197   check(p.length()==2,"path() found a wrong path.");
   198   check(checkPath(G, p),"path() found a wrong path.");
   199   check(pathSource(G, p) == s,"path() found a wrong path.");
   200   check(pathTarget(G, p) == t,"path() found a wrong path.");
   201 
   202 
   203   for(ArcIt a(G); a!=INVALID; ++a) {
   204     Node u=G.source(a);
   205     Node v=G.target(a);
   206     check( !bfs_test.reached(u) ||
   207            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
   208            "Wrong output. " << G.id(u) << "->" << G.id(v));
   209   }
   210 
   211   for(NodeIt v(G); v!=INVALID; ++v) {
   212     if (bfs_test.reached(v)) {
   213       check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
   214       if (bfs_test.predArc(v)!=INVALID ) {
   215         Arc a=bfs_test.predArc(v);
   216         Node u=G.source(a);
   217         check(u==bfs_test.predNode(v),"Wrong tree.");
   218         check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   219               "Wrong distance. Difference: "
   220               << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
   221       }
   222     }
   223   }
   224 
   225   {
   226     NullMap<Node,Arc> myPredMap;
   227     bfs(G).predMap(myPredMap).run(s);
   228   }
   229 }
   230 
   231 int main()
   232 {
   233   checkBfs<ListDigraph>();
   234   checkBfs<SmartDigraph>();
   235   return 0;
   236 }