test/graph_utils_test.cc
changeset 158 500f3cbff9e4
child 171 02f4d5d9bfd7
equal deleted inserted replaced
-1:000000000000 0:e514dac31c31
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     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 <iostream>
       
    20 #include <vector>
       
    21 
       
    22 #include <lemon/graph_utils.h>
       
    23 
       
    24 #include <lemon/list_graph.h>
       
    25 #include <lemon/smart_graph.h>
       
    26 
       
    27 #include "test_tools.h"
       
    28 #include "graph_utils_test.h"
       
    29 
       
    30 
       
    31 using namespace lemon;
       
    32 
       
    33 template <class Graph>
       
    34 void checkSnapDeg() 
       
    35 {
       
    36   Graph g;
       
    37   typename Graph::Node n1=g.addNode();
       
    38   typename Graph::Node n2=g.addNode();
       
    39    
       
    40   InDegMap<Graph> ind(g);
       
    41  
       
    42   g.addArc(n1,n2);
       
    43   
       
    44   typename Graph::Snapshot snap(g);
       
    45   
       
    46   OutDegMap<Graph> outd(g);
       
    47   
       
    48   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
       
    49   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
       
    50 
       
    51   g.addArc(n1,n2);
       
    52   g.addArc(n2,n1);
       
    53  
       
    54   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
       
    55   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
       
    56 
       
    57   snap.restore();
       
    58 
       
    59   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
       
    60   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
       
    61   
       
    62 }
       
    63 
       
    64 int main() {
       
    65   ///\file
       
    66   { // checking list graph
       
    67     checkDigraphCounters<ListDigraph>();
       
    68     checkFindArc<ListDigraph>();
       
    69   }
       
    70   { // checking smart graph
       
    71     checkDigraphCounters<SmartDigraph>();
       
    72     checkFindArc<SmartDigraph>();
       
    73   }
       
    74   {
       
    75     int num = 5;
       
    76     SmartDigraph fg;
       
    77     std::vector<SmartDigraph::Node> nodes;
       
    78     for (int i = 0; i < num; ++i) {
       
    79       nodes.push_back(fg.addNode());
       
    80     }
       
    81     for (int i = 0; i < num * num; ++i) {
       
    82       fg.addArc(nodes[i / num], nodes[i % num]);
       
    83     }
       
    84     check(countNodes(fg) == num, "FullGraph: wrong node number.");
       
    85     check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
       
    86     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
       
    87       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
       
    88 	ConArcIt<SmartDigraph> con(fg, src, trg);
       
    89 	check(con != INVALID, "There is no connecting arc.");
       
    90 	check(fg.source(con) == src, "Wrong source.");
       
    91 	check(fg.target(con) == trg, "Wrong target.");
       
    92 	check(++con == INVALID, "There is more connecting arc.");
       
    93       }
       
    94     }
       
    95     AllArcLookUp<SmartDigraph> el(fg);
       
    96     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
       
    97       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
       
    98 	SmartDigraph::Arc con = el(src, trg);
       
    99 	check(con != INVALID, "There is no connecting arc.");
       
   100 	check(fg.source(con) == src, "Wrong source.");
       
   101 	check(fg.target(con) == trg, "Wrong target.");
       
   102 	check(el(src,trg,con) == INVALID, "There is more connecting arc.");
       
   103       }
       
   104     }
       
   105   }
       
   106 
       
   107   //check In/OutDegMap (and Snapshot feature)
       
   108 
       
   109   checkSnapDeg<ListDigraph>();
       
   110   checkSnapDeg<SmartDigraph>();
       
   111   
       
   112   {
       
   113     const int nodeNum = 10;
       
   114     const int arcNum = 100;
       
   115     ListDigraph digraph;
       
   116     InDegMap<ListDigraph> inDeg(digraph);
       
   117     OutDegMap<ListDigraph> outDeg(digraph);
       
   118     std::vector<ListDigraph::Node> nodes(nodeNum);
       
   119     for (int i = 0; i < nodeNum; ++i) {
       
   120       nodes[i] = digraph.addNode();
       
   121     }
       
   122     std::vector<ListDigraph::Arc> arcs(arcNum);
       
   123     for (int i = 0; i < arcNum; ++i) {
       
   124       arcs[i] = 
       
   125 	digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
       
   126     }
       
   127     for (int i = 0; i < nodeNum; ++i) {
       
   128       check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
       
   129 	    "Wrong in degree map");
       
   130     }
       
   131     for (int i = 0; i < nodeNum; ++i) {
       
   132       check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
       
   133 	    "Wrong in degree map");
       
   134     }
       
   135   }
       
   136 
       
   137   ///Everything is OK
       
   138   std::cout << __FILE__ ": All tests passed.\n";
       
   139 
       
   140   return 0;
       
   141 }