test/bfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 293 47fbc814aa31
child 585 65fbcf2f978a
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
     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 }