test/graph_utils_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 220 a5d8c039f218
child 572 be6646ac5d89
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 <cstdlib>
    20 #include <ctime>
    21 
    22 #include <lemon/random.h>
    23 #include <lemon/list_graph.h>
    24 #include <lemon/smart_graph.h>
    25 #include <lemon/maps.h>
    26 
    27 #include "graph_test.h"
    28 #include "test_tools.h"
    29 
    30 using namespace lemon;
    31 
    32 template <typename Digraph>
    33 void checkFindArcs() {
    34   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    35 
    36   {
    37     Digraph digraph;
    38     for (int i = 0; i < 10; ++i) {
    39       digraph.addNode();
    40     }
    41     DescriptorMap<Digraph, Node> nodes(digraph);
    42     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
    43     for (int i = 0; i < 100; ++i) {
    44       int src = rnd[invNodes.size()];
    45       int trg = rnd[invNodes.size()];
    46       digraph.addArc(invNodes[src], invNodes[trg]);
    47     }
    48     typename Digraph::template ArcMap<bool> found(digraph, false);
    49     DescriptorMap<Digraph, Arc> arcs(digraph);
    50     for (NodeIt src(digraph); src != INVALID; ++src) {
    51       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
    52         for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
    53           check(digraph.source(con) == src, "Wrong source.");
    54           check(digraph.target(con) == trg, "Wrong target.");
    55           check(found[con] == false, "The arc found already.");
    56           found[con] = true;
    57         }
    58       }
    59     }
    60     for (ArcIt it(digraph); it != INVALID; ++it) {
    61       check(found[it] == true, "The arc is not found.");
    62     }
    63   }
    64 
    65   {
    66     int num = 5;
    67     Digraph fg;
    68     std::vector<Node> nodes;
    69     for (int i = 0; i < num; ++i) {
    70       nodes.push_back(fg.addNode());
    71     }
    72     for (int i = 0; i < num * num; ++i) {
    73       fg.addArc(nodes[i / num], nodes[i % num]);
    74     }
    75     check(countNodes(fg) == num, "Wrong node number.");
    76     check(countArcs(fg) == num*num, "Wrong arc number.");
    77     for (NodeIt src(fg); src != INVALID; ++src) {
    78       for (NodeIt trg(fg); trg != INVALID; ++trg) {
    79         ConArcIt<Digraph> con(fg, src, trg);
    80         check(con != INVALID, "There is no connecting arc.");
    81         check(fg.source(con) == src, "Wrong source.");
    82         check(fg.target(con) == trg, "Wrong target.");
    83         check(++con == INVALID, "There is more connecting arc.");
    84       }
    85     }
    86     ArcLookUp<Digraph> al1(fg);
    87     DynArcLookUp<Digraph> al2(fg);
    88     AllArcLookUp<Digraph> al3(fg);
    89     for (NodeIt src(fg); src != INVALID; ++src) {
    90       for (NodeIt trg(fg); trg != INVALID; ++trg) {
    91         Arc con1 = al1(src, trg);
    92         Arc con2 = al2(src, trg);
    93         Arc con3 = al3(src, trg);
    94         Arc con4 = findArc(fg, src, trg);
    95         check(con1 == con2 && con2 == con3 && con3 == con4,
    96               "Different results.")
    97         check(con1 != INVALID, "There is no connecting arc.");
    98         check(fg.source(con1) == src, "Wrong source.");
    99         check(fg.target(con1) == trg, "Wrong target.");
   100         check(al3(src, trg, con3) == INVALID,
   101               "There is more connecting arc.");
   102         check(findArc(fg, src, trg, con4) == INVALID,
   103               "There is more connecting arc.");
   104       }
   105     }
   106   }
   107 }
   108 
   109 template <typename Graph>
   110 void checkFindEdges() {
   111   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   112   Graph graph;
   113   for (int i = 0; i < 10; ++i) {
   114     graph.addNode();
   115   }
   116   DescriptorMap<Graph, Node> nodes(graph);
   117   typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
   118   for (int i = 0; i < 100; ++i) {
   119     int src = rnd[invNodes.size()];
   120     int trg = rnd[invNodes.size()];
   121     graph.addEdge(invNodes[src], invNodes[trg]);
   122   }
   123   typename Graph::template EdgeMap<int> found(graph, 0);
   124   DescriptorMap<Graph, Edge> edges(graph);
   125   for (NodeIt src(graph); src != INVALID; ++src) {
   126     for (NodeIt trg(graph); trg != INVALID; ++trg) {
   127       for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
   128         check( (graph.u(con) == src && graph.v(con) == trg) ||
   129                (graph.v(con) == src && graph.u(con) == trg),
   130                "Wrong end nodes.");
   131         ++found[con];
   132         check(found[con] <= 2, "The edge found more than twice.");
   133       }
   134     }
   135   }
   136   for (EdgeIt it(graph); it != INVALID; ++it) {
   137     check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
   138            (graph.u(it) == graph.v(it) && found[it] == 1),
   139            "The edge is not found correctly.");
   140   }
   141 }
   142 
   143 template <class Digraph>
   144 void checkDeg()
   145 {
   146   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   147 
   148   const int nodeNum = 10;
   149   const int arcNum = 100;
   150   Digraph digraph;
   151   InDegMap<Digraph> inDeg(digraph);
   152   OutDegMap<Digraph> outDeg(digraph);
   153   std::vector<Node> nodes(nodeNum);
   154   for (int i = 0; i < nodeNum; ++i) {
   155     nodes[i] = digraph.addNode();
   156   }
   157   std::vector<Arc> arcs(arcNum);
   158   for (int i = 0; i < arcNum; ++i) {
   159     arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
   160   }
   161   for (int i = 0; i < nodeNum; ++i) {
   162     check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
   163           "Wrong in degree map");
   164   }
   165   for (int i = 0; i < nodeNum; ++i) {
   166     check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
   167           "Wrong out degree map");
   168   }
   169 }
   170 
   171 template <class Digraph>
   172 void checkSnapDeg()
   173 {
   174   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   175 
   176   Digraph g;
   177   Node n1=g.addNode();
   178   Node n2=g.addNode();
   179 
   180   InDegMap<Digraph> ind(g);
   181 
   182   g.addArc(n1,n2);
   183 
   184   typename Digraph::Snapshot snap(g);
   185 
   186   OutDegMap<Digraph> outd(g);
   187 
   188   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
   189   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
   190 
   191   g.addArc(n1,n2);
   192   g.addArc(n2,n1);
   193 
   194   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
   195   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
   196 
   197   snap.restore();
   198 
   199   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
   200   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
   201 }
   202 
   203 int main() {
   204   // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
   205   checkFindArcs<ListDigraph>();
   206   checkFindArcs<SmartDigraph>();
   207   checkFindEdges<ListGraph>();
   208   checkFindEdges<SmartGraph>();
   209 
   210   // Checking In/OutDegMap (and Snapshot feature)
   211   checkDeg<ListDigraph>();
   212   checkDeg<SmartDigraph>();
   213   checkSnapDeg<ListDigraph>();
   214   checkSnapDeg<SmartDigraph>();
   215 
   216   return 0;
   217 }