test/euler_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 522 22f932bbb305
child 592 2ebfdb89ec66
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/euler.h>
    20 #include <lemon/list_graph.h>
    21 #include <test/test_tools.h>
    22 
    23 using namespace lemon;
    24 
    25 template <typename Digraph>
    26 void checkDiEulerIt(const Digraph& g)
    27 {
    28   typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    29 
    30   DiEulerIt<Digraph> e(g);
    31   typename Digraph::Node firstNode = g.source(e);
    32   typename Digraph::Node lastNode = g.target(e);
    33 
    34   for (; e != INVALID; ++e)
    35   {
    36     if (e != INVALID)
    37     {
    38       lastNode = g.target(e);
    39     }
    40     ++visitationNumber[e];
    41   }
    42 
    43   check(firstNode == lastNode,
    44       "checkDiEulerIt: first and last node are not the same");
    45 
    46   for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    47   {
    48     check(visitationNumber[a] == 1,
    49         "checkDiEulerIt: not visited or multiple times visited arc found");
    50   }
    51 }
    52 
    53 template <typename Graph>
    54 void checkEulerIt(const Graph& g)
    55 {
    56   typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    57 
    58   EulerIt<Graph> e(g);
    59   typename Graph::Node firstNode = g.u(e);
    60   typename Graph::Node lastNode = g.v(e);
    61 
    62   for (; e != INVALID; ++e)
    63   {
    64     if (e != INVALID)
    65     {
    66       lastNode = g.v(e);
    67     }
    68     ++visitationNumber[e];
    69   }
    70 
    71   check(firstNode == lastNode,
    72       "checkEulerIt: first and last node are not the same");
    73 
    74   for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    75   {
    76     check(visitationNumber[e] == 1,
    77         "checkEulerIt: not visited or multiple times visited edge found");
    78   }
    79 }
    80 
    81 int main()
    82 {
    83   typedef ListDigraph Digraph;
    84   typedef ListGraph Graph;
    85 
    86   Digraph digraphWithEulerianCircuit;
    87   {
    88     Digraph& g = digraphWithEulerianCircuit;
    89 
    90     Digraph::Node n0 = g.addNode();
    91     Digraph::Node n1 = g.addNode();
    92     Digraph::Node n2 = g.addNode();
    93 
    94     g.addArc(n0, n1);
    95     g.addArc(n1, n0);
    96     g.addArc(n1, n2);
    97     g.addArc(n2, n1);
    98   }
    99 
   100   Digraph digraphWithoutEulerianCircuit;
   101   {
   102     Digraph& g = digraphWithoutEulerianCircuit;
   103 
   104     Digraph::Node n0 = g.addNode();
   105     Digraph::Node n1 = g.addNode();
   106     Digraph::Node n2 = g.addNode();
   107 
   108     g.addArc(n0, n1);
   109     g.addArc(n1, n0);
   110     g.addArc(n1, n2);
   111   }
   112 
   113   Graph graphWithEulerianCircuit;
   114   {
   115     Graph& g = graphWithEulerianCircuit;
   116 
   117     Graph::Node n0 = g.addNode();
   118     Graph::Node n1 = g.addNode();
   119     Graph::Node n2 = g.addNode();
   120 
   121     g.addEdge(n0, n1);
   122     g.addEdge(n1, n2);
   123     g.addEdge(n2, n0);
   124   }
   125 
   126   Graph graphWithoutEulerianCircuit;
   127   {
   128     Graph& g = graphWithoutEulerianCircuit;
   129 
   130     Graph::Node n0 = g.addNode();
   131     Graph::Node n1 = g.addNode();
   132     Graph::Node n2 = g.addNode();
   133 
   134     g.addEdge(n0, n1);
   135     g.addEdge(n1, n2);
   136   }
   137 
   138   checkDiEulerIt(digraphWithEulerianCircuit);
   139 
   140   checkEulerIt(graphWithEulerianCircuit);
   141 
   142   check(eulerian(digraphWithEulerianCircuit),
   143       "this graph should have an Eulerian circuit");
   144   check(!eulerian(digraphWithoutEulerianCircuit),
   145       "this graph should not have an Eulerian circuit");
   146 
   147   check(eulerian(graphWithEulerianCircuit),
   148       "this graph should have an Eulerian circuit");
   149   check(!eulerian(graphWithoutEulerianCircuit),
   150       "this graph should have an Eulerian circuit");
   151 
   152   return 0;
   153 }