test/bfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 596 8c3112a66878
parent 293 47fbc814aa31
child 577 65fbcf2f978a
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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 }