test/graph_utils_test.h
changeset 145 95d905b6e33d
equal deleted inserted replaced
-1:000000000000 0:a5df799d4d30
       
     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 #ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
       
    20 #define LEMON_TEST_GRAPH_UTILS_TEST_H
       
    21 
       
    22 
       
    23 #include "test_tools.h"
       
    24 #include <cstdlib>
       
    25 #include <ctime>
       
    26 
       
    27 //! \ingroup misc
       
    28 //! \file
       
    29 //! \brief Test cases for graph utils.
       
    30 namespace lemon {
       
    31   
       
    32   template <typename Digraph>
       
    33   void checkDigraphCounters() {
       
    34     const int num = 5;
       
    35     Digraph digraph;
       
    36     addPetersen(digraph, num);
       
    37     bidirDigraph(digraph);
       
    38     check(countNodes(digraph) == 2*num, "Wrong node number.");
       
    39     check(countArcs(digraph) == 6*num, "Wrong arc number.");    
       
    40     for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
       
    41       check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
       
    42       check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
       
    43     }
       
    44   }
       
    45 
       
    46   template <typename Digraph>
       
    47   void checkFindArc() {
       
    48     typedef typename Digraph::Node Node;
       
    49     typedef typename Digraph::Arc Arc;
       
    50     typedef typename Digraph::NodeIt NodeIt;
       
    51     typedef typename Digraph::ArcIt ArcIt;
       
    52     Digraph digraph;
       
    53     for (int i = 0; i < 10; ++i) {
       
    54       digraph.addNode();
       
    55     }
       
    56     DescriptorMap<Digraph, Node> nodes(digraph);
       
    57     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
       
    58     for (int i = 0; i < 100; ++i) {
       
    59       int src = rnd[invNodes.size()];
       
    60       int trg = rnd[invNodes.size()];
       
    61       digraph.addArc(invNodes[src], invNodes[trg]);
       
    62     }
       
    63     typename Digraph::template ArcMap<bool> found(digraph, false);
       
    64     DescriptorMap<Digraph, Arc> arcs(digraph);
       
    65     for (NodeIt src(digraph); src != INVALID; ++src) {
       
    66       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
       
    67 	for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
       
    68 	  check(digraph.source(con) == src, "Wrong source.");
       
    69 	  check(digraph.target(con) == trg, "Wrong target.");
       
    70 	  check(found[con] == false, "The arc found already.");
       
    71 	  found[con] = true;
       
    72 	}
       
    73       }
       
    74     }
       
    75     for (ArcIt it(digraph); it != INVALID; ++it) {
       
    76       check(found[it] == true, "The arc is not found.");
       
    77     }
       
    78   }
       
    79   
       
    80 } //namespace lemon
       
    81 
       
    82 
       
    83 #endif