test/graph_utils_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
parent 440 88ed40ad0d4f
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     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     RangeIdMap<Digraph, Node> nodes(digraph);
    42     typename RangeIdMap<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     RangeIdMap<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   RangeIdMap<Graph, Node> nodes(graph);
   117   typename RangeIdMap<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   RangeIdMap<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 }