1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/graph_utils_test.h Tue Apr 22 15:04:00 2008 +0200
1.3 @@ -0,0 +1,83 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
1.23 +#define LEMON_TEST_GRAPH_UTILS_TEST_H
1.24 +
1.25 +
1.26 +#include "test_tools.h"
1.27 +#include <cstdlib>
1.28 +#include <ctime>
1.29 +
1.30 +//! \ingroup misc
1.31 +//! \file
1.32 +//! \brief Test cases for graph utils.
1.33 +namespace lemon {
1.34 +
1.35 + template <typename Digraph>
1.36 + void checkDigraphCounters() {
1.37 + const int num = 5;
1.38 + Digraph digraph;
1.39 + addPetersen(digraph, num);
1.40 + bidirDigraph(digraph);
1.41 + check(countNodes(digraph) == 2*num, "Wrong node number.");
1.42 + check(countArcs(digraph) == 6*num, "Wrong arc number.");
1.43 + for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.44 + check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
1.45 + check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
1.46 + }
1.47 + }
1.48 +
1.49 + template <typename Digraph>
1.50 + void checkFindArc() {
1.51 + typedef typename Digraph::Node Node;
1.52 + typedef typename Digraph::Arc Arc;
1.53 + typedef typename Digraph::NodeIt NodeIt;
1.54 + typedef typename Digraph::ArcIt ArcIt;
1.55 + Digraph digraph;
1.56 + for (int i = 0; i < 10; ++i) {
1.57 + digraph.addNode();
1.58 + }
1.59 + DescriptorMap<Digraph, Node> nodes(digraph);
1.60 + typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
1.61 + for (int i = 0; i < 100; ++i) {
1.62 + int src = rnd[invNodes.size()];
1.63 + int trg = rnd[invNodes.size()];
1.64 + digraph.addArc(invNodes[src], invNodes[trg]);
1.65 + }
1.66 + typename Digraph::template ArcMap<bool> found(digraph, false);
1.67 + DescriptorMap<Digraph, Arc> arcs(digraph);
1.68 + for (NodeIt src(digraph); src != INVALID; ++src) {
1.69 + for (NodeIt trg(digraph); trg != INVALID; ++trg) {
1.70 + for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
1.71 + check(digraph.source(con) == src, "Wrong source.");
1.72 + check(digraph.target(con) == trg, "Wrong target.");
1.73 + check(found[con] == false, "The arc found already.");
1.74 + found[con] = true;
1.75 + }
1.76 + }
1.77 + }
1.78 + for (ArcIt it(digraph); it != INVALID; ++it) {
1.79 + check(found[it] == true, "The arc is not found.");
1.80 + }
1.81 + }
1.82 +
1.83 +} //namespace lemon
1.84 +
1.85 +
1.86 +#endif