1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/graph_utils_test.cc Tue Apr 22 15:04:00 2008 +0200
1.3 @@ -0,0 +1,141 @@
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 +#include <iostream>
1.23 +#include <vector>
1.24 +
1.25 +#include <lemon/graph_utils.h>
1.26 +
1.27 +#include <lemon/list_graph.h>
1.28 +#include <lemon/smart_graph.h>
1.29 +
1.30 +#include "test_tools.h"
1.31 +#include "graph_utils_test.h"
1.32 +
1.33 +
1.34 +using namespace lemon;
1.35 +
1.36 +template <class Graph>
1.37 +void checkSnapDeg()
1.38 +{
1.39 + Graph g;
1.40 + typename Graph::Node n1=g.addNode();
1.41 + typename Graph::Node n2=g.addNode();
1.42 +
1.43 + InDegMap<Graph> ind(g);
1.44 +
1.45 + g.addArc(n1,n2);
1.46 +
1.47 + typename Graph::Snapshot snap(g);
1.48 +
1.49 + OutDegMap<Graph> outd(g);
1.50 +
1.51 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
1.52 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
1.53 +
1.54 + g.addArc(n1,n2);
1.55 + g.addArc(n2,n1);
1.56 +
1.57 + check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
1.58 + check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
1.59 +
1.60 + snap.restore();
1.61 +
1.62 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
1.63 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
1.64 +
1.65 +}
1.66 +
1.67 +int main() {
1.68 + ///\file
1.69 + { // checking list graph
1.70 + checkDigraphCounters<ListDigraph>();
1.71 + checkFindArc<ListDigraph>();
1.72 + }
1.73 + { // checking smart graph
1.74 + checkDigraphCounters<SmartDigraph>();
1.75 + checkFindArc<SmartDigraph>();
1.76 + }
1.77 + {
1.78 + int num = 5;
1.79 + SmartDigraph fg;
1.80 + std::vector<SmartDigraph::Node> nodes;
1.81 + for (int i = 0; i < num; ++i) {
1.82 + nodes.push_back(fg.addNode());
1.83 + }
1.84 + for (int i = 0; i < num * num; ++i) {
1.85 + fg.addArc(nodes[i / num], nodes[i % num]);
1.86 + }
1.87 + check(countNodes(fg) == num, "FullGraph: wrong node number.");
1.88 + check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
1.89 + for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
1.90 + for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
1.91 + ConArcIt<SmartDigraph> con(fg, src, trg);
1.92 + check(con != INVALID, "There is no connecting arc.");
1.93 + check(fg.source(con) == src, "Wrong source.");
1.94 + check(fg.target(con) == trg, "Wrong target.");
1.95 + check(++con == INVALID, "There is more connecting arc.");
1.96 + }
1.97 + }
1.98 + AllArcLookUp<SmartDigraph> el(fg);
1.99 + for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
1.100 + for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
1.101 + SmartDigraph::Arc con = el(src, trg);
1.102 + check(con != INVALID, "There is no connecting arc.");
1.103 + check(fg.source(con) == src, "Wrong source.");
1.104 + check(fg.target(con) == trg, "Wrong target.");
1.105 + check(el(src,trg,con) == INVALID, "There is more connecting arc.");
1.106 + }
1.107 + }
1.108 + }
1.109 +
1.110 + //check In/OutDegMap (and Snapshot feature)
1.111 +
1.112 + checkSnapDeg<ListDigraph>();
1.113 + checkSnapDeg<SmartDigraph>();
1.114 +
1.115 + {
1.116 + const int nodeNum = 10;
1.117 + const int arcNum = 100;
1.118 + ListDigraph digraph;
1.119 + InDegMap<ListDigraph> inDeg(digraph);
1.120 + OutDegMap<ListDigraph> outDeg(digraph);
1.121 + std::vector<ListDigraph::Node> nodes(nodeNum);
1.122 + for (int i = 0; i < nodeNum; ++i) {
1.123 + nodes[i] = digraph.addNode();
1.124 + }
1.125 + std::vector<ListDigraph::Arc> arcs(arcNum);
1.126 + for (int i = 0; i < arcNum; ++i) {
1.127 + arcs[i] =
1.128 + digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
1.129 + }
1.130 + for (int i = 0; i < nodeNum; ++i) {
1.131 + check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
1.132 + "Wrong in degree map");
1.133 + }
1.134 + for (int i = 0; i < nodeNum; ++i) {
1.135 + check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
1.136 + "Wrong in degree map");
1.137 + }
1.138 + }
1.139 +
1.140 + ///Everything is OK
1.141 + std::cout << __FILE__ ": All tests passed.\n";
1.142 +
1.143 + return 0;
1.144 +}