test/dfs_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 08 Aug 2011 00:00:00 +0200
branch1.0
changeset 429 351009ebb624
parent 420 e24922c56bc2
permissions -rw-r--r--
Release series 1.0.x has reached its end of life.
     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-2011
     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/dfs.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   "6\n"
    41   "@arcs\n"
    42   "     label\n"
    43   "0 1  0\n"
    44   "1 2  1\n"
    45   "2 3  2\n"
    46   "1 4  3\n"
    47   "4 2  4\n"
    48   "4 5  5\n"
    49   "5 0  6\n"
    50   "6 3  7\n"
    51   "@attributes\n"
    52   "source 0\n"
    53   "target 5\n"
    54   "source1 6\n"
    55   "target1 3\n";
    56 
    57 
    58 void checkDfsCompile()
    59 {
    60   typedef concepts::Digraph Digraph;
    61   typedef Dfs<Digraph> DType;
    62   typedef Digraph::Node Node;
    63   typedef Digraph::Arc Arc;
    64 
    65   Digraph G;
    66   Node s, t;
    67   Arc e;
    68   int l;
    69   bool b;
    70   DType::DistMap d(G);
    71   DType::PredMap p(G);
    72   Path<Digraph> pp;
    73 
    74   {
    75     DType dfs_test(G);
    76 
    77     dfs_test.run(s);
    78     dfs_test.run(s,t);
    79     dfs_test.run();
    80 
    81     l  = dfs_test.dist(t);
    82     e  = dfs_test.predArc(t);
    83     s  = dfs_test.predNode(t);
    84     b  = dfs_test.reached(t);
    85     d  = dfs_test.distMap();
    86     p  = dfs_test.predMap();
    87     pp = dfs_test.path(t);
    88   }
    89   {
    90     DType
    91       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    92       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    93       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
    94       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    95       ::SetStandardProcessedMap
    96       ::Create dfs_test(G);
    97 
    98     dfs_test.run(s);
    99     dfs_test.run(s,t);
   100     dfs_test.run();
   101 
   102     l  = dfs_test.dist(t);
   103     e  = dfs_test.predArc(t);
   104     s  = dfs_test.predNode(t);
   105     b  = dfs_test.reached(t);
   106     pp = dfs_test.path(t);
   107   }
   108 }
   109 
   110 void checkDfsFunctionCompile()
   111 {
   112   typedef int VType;
   113   typedef concepts::Digraph Digraph;
   114   typedef Digraph::Arc Arc;
   115   typedef Digraph::Node Node;
   116 
   117   Digraph g;
   118   bool b;
   119   dfs(g).run(Node());
   120   b=dfs(g).run(Node(),Node());
   121   dfs(g).run();
   122   dfs(g)
   123     .predMap(concepts::ReadWriteMap<Node,Arc>())
   124     .distMap(concepts::ReadWriteMap<Node,VType>())
   125     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   126     .processedMap(concepts::WriteMap<Node,bool>())
   127     .run(Node());
   128   b=dfs(g)
   129     .predMap(concepts::ReadWriteMap<Node,Arc>())
   130     .distMap(concepts::ReadWriteMap<Node,VType>())
   131     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   132     .processedMap(concepts::WriteMap<Node,bool>())
   133     .path(concepts::Path<Digraph>())
   134     .dist(VType())
   135     .run(Node(),Node());
   136   dfs(g)
   137     .predMap(concepts::ReadWriteMap<Node,Arc>())
   138     .distMap(concepts::ReadWriteMap<Node,VType>())
   139     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   140     .processedMap(concepts::WriteMap<Node,bool>())
   141     .run();
   142 }
   143 
   144 template <class Digraph>
   145 void checkDfs() {
   146   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   147 
   148   Digraph G;
   149   Node s, t;
   150   Node s1, t1;
   151 
   152   std::istringstream input(test_lgf);
   153   digraphReader(G, input).
   154     node("source", s).
   155     node("target", t).
   156     node("source1", s1).
   157     node("target1", t1).
   158     run();
   159 
   160   Dfs<Digraph> dfs_test(G);
   161   dfs_test.run(s);
   162 
   163   Path<Digraph> p = dfs_test.path(t);
   164   check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
   165   check(checkPath(G, p),"path() found a wrong path.");
   166   check(pathSource(G, p) == s,"path() found a wrong path.");
   167   check(pathTarget(G, p) == t,"path() found a wrong path.");
   168 
   169   for(NodeIt v(G); v!=INVALID; ++v) {
   170     if (dfs_test.reached(v)) {
   171       check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
   172       if (dfs_test.predArc(v)!=INVALID ) {
   173         Arc e=dfs_test.predArc(v);
   174         Node u=G.source(e);
   175         check(u==dfs_test.predNode(v),"Wrong tree.");
   176         check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
   177               "Wrong distance. (" << dfs_test.dist(u) << "->"
   178               << dfs_test.dist(v) << ")");
   179       }
   180     }
   181   }
   182 
   183   {
   184   Dfs<Digraph> dfs(G);
   185   check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
   186   }
   187 
   188   {
   189     NullMap<Node,Arc> myPredMap;
   190     dfs(G).predMap(myPredMap).run(s);
   191   }
   192 }
   193 
   194 int main()
   195 {
   196   checkDfs<ListDigraph>();
   197   checkDfs<SmartDigraph>();
   198   return 0;
   199 }