COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/graph_utils_test.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 2.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 Graph>
33  void checkGraphCounters() {
34    const int num = 5;
35    Graph graph;
36    addPetersen(graph, num);
37    bidirGraph(graph);
38    check(countNodes(graph) == 2*num, "Wrong node number.");
39    check(countEdges(graph) == 6*num, "Wrong edge number.");   
40    for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
41      check(countOutEdges(graph, it) == 3, "Wrong out degree number.");
42      check(countInEdges(graph, it) == 3, "Wrong in degree number.");
43    }
44  }
45
46  template <typename Graph>
47  void checkFindEdge() {
48    typedef typename Graph::Node Node;
49    typedef typename Graph::Edge Edge;
50    typedef typename Graph::NodeIt NodeIt;
51    typedef typename Graph::EdgeIt EdgeIt;
52    Graph graph;
53    srand(time(0));
54    for (int i = 0; i < 10; ++i) {
55      graph.addNode();
56    }
57    DescriptorMap<Graph, Node> nodes(graph);
58    typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
59    for (int i = 0; i < 100; ++i) {
60      int src = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
61      int trg = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
62      graph.addEdge(invNodes[src], invNodes[trg]);
63    }
64    typename Graph::template EdgeMap<bool> found(graph, false);
65    DescriptorMap<Graph, Edge> edges(graph);
66    for (NodeIt src(graph); src != INVALID; ++src) {
67      for (NodeIt trg(graph); trg != INVALID; ++trg) {
68        for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
69          check(graph.source(con) == src, "Wrong source.");
70          check(graph.target(con) == trg, "Wrong target.");
71          check(found[con] == false, "The edge found already.");
72          found[con] = true;
73        }
74      }
75    }
76    for (EdgeIt it(graph); it != INVALID; ++it) {
77      check(found[it] == true, "The edge is not found.");
78    }
79  }
80 
81} //namespace lemon
82
83
84#endif
Note: See TracBrowser for help on using the repository browser.