test/graph_utils_test.cc
author Balazs Dezso <deba@google.com>
Fri, 22 Jan 2021 10:55:32 +0100
changeset 1208 c6aa2cc1af04
parent 440 88ed40ad0d4f
permissions -rw-r--r--
Factor out recursion from weighted matching algorithms (#638)
     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 }