test/dfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 293 47fbc814aa31
child 585 65fbcf2f978a
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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/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 
    55 void checkDfsCompile()
    56 {
    57   typedef concepts::Digraph Digraph;
    58   typedef Dfs<Digraph> DType;
    59   typedef Digraph::Node Node;
    60   typedef Digraph::Arc Arc;
    61 
    62   Digraph G;
    63   Node s, t;
    64   Arc e;
    65   int l;
    66   bool b;
    67   DType::DistMap d(G);
    68   DType::PredMap p(G);
    69   Path<Digraph> pp;
    70 
    71   {
    72     DType dfs_test(G);
    73 
    74     dfs_test.run(s);
    75     dfs_test.run(s,t);
    76     dfs_test.run();
    77 
    78     l  = dfs_test.dist(t);
    79     e  = dfs_test.predArc(t);
    80     s  = dfs_test.predNode(t);
    81     b  = dfs_test.reached(t);
    82     d  = dfs_test.distMap();
    83     p  = dfs_test.predMap();
    84     pp = dfs_test.path(t);
    85   }
    86   {
    87     DType
    88       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    89       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    90       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
    91       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    92       ::SetStandardProcessedMap
    93       ::Create dfs_test(G);
    94 
    95     dfs_test.run(s);
    96     dfs_test.run(s,t);
    97     dfs_test.run();
    98 
    99     l  = dfs_test.dist(t);
   100     e  = dfs_test.predArc(t);
   101     s  = dfs_test.predNode(t);
   102     b  = dfs_test.reached(t);
   103     pp = dfs_test.path(t);
   104   }
   105 }
   106 
   107 void checkDfsFunctionCompile()
   108 {
   109   typedef int VType;
   110   typedef concepts::Digraph Digraph;
   111   typedef Digraph::Arc Arc;
   112   typedef Digraph::Node Node;
   113 
   114   Digraph g;
   115   bool b;
   116   dfs(g).run(Node());
   117   b=dfs(g).run(Node(),Node());
   118   dfs(g).run();
   119   dfs(g)
   120     .predMap(concepts::ReadWriteMap<Node,Arc>())
   121     .distMap(concepts::ReadWriteMap<Node,VType>())
   122     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   123     .processedMap(concepts::WriteMap<Node,bool>())
   124     .run(Node());
   125   b=dfs(g)
   126     .predMap(concepts::ReadWriteMap<Node,Arc>())
   127     .distMap(concepts::ReadWriteMap<Node,VType>())
   128     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   129     .processedMap(concepts::WriteMap<Node,bool>())
   130     .path(concepts::Path<Digraph>())
   131     .dist(VType())
   132     .run(Node(),Node());
   133   dfs(g)
   134     .predMap(concepts::ReadWriteMap<Node,Arc>())
   135     .distMap(concepts::ReadWriteMap<Node,VType>())
   136     .reachedMap(concepts::ReadWriteMap<Node,bool>())
   137     .processedMap(concepts::WriteMap<Node,bool>())
   138     .run();
   139 }
   140 
   141 template <class Digraph>
   142 void checkDfs() {
   143   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   144 
   145   Digraph G;
   146   Node s, t;
   147 
   148   std::istringstream input(test_lgf);
   149   digraphReader(G, input).
   150     node("source", s).
   151     node("target", t).
   152     run();
   153 
   154   Dfs<Digraph> dfs_test(G);
   155   dfs_test.run(s);
   156 
   157   Path<Digraph> p = dfs_test.path(t);
   158   check(p.length() == dfs_test.dist(t),"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   for(NodeIt v(G); v!=INVALID; ++v) {
   164     if (dfs_test.reached(v)) {
   165       check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
   166       if (dfs_test.predArc(v)!=INVALID ) {
   167         Arc e=dfs_test.predArc(v);
   168         Node u=G.source(e);
   169         check(u==dfs_test.predNode(v),"Wrong tree.");
   170         check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
   171               "Wrong distance. (" << dfs_test.dist(u) << "->"
   172               << dfs_test.dist(v) << ")");
   173       }
   174     }
   175   }
   176 
   177   {
   178     NullMap<Node,Arc> myPredMap;
   179     dfs(G).predMap(myPredMap).run(s);
   180   }
   181 }
   182 
   183 int main()
   184 {
   185   checkDfs<ListDigraph>();
   186   checkDfs<SmartDigraph>();
   187   return 0;
   188 }