test/dfs_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/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 }