COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/graph_utils_test.h @ 145:95d905b6e33d

Last change on this file since 145:95d905b6e33d was 139:701c529ba737, checked in by Balazs Dezso <deba@…>, 11 years ago

Renamings in the graph_utils.h + graph_utils_test added

File size: 2.5 KB
Line 
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.
30namespace 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
Note: See TracBrowser for help on using the repository browser.