test/graph_utils_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 17 May 2008 06:30:02 +0100
changeset 156 e561aa7675de
child 171 02f4d5d9bfd7
permissions -rw-r--r--
More flexible header names in .lgf + largely improved doc
deba@139
     1
/* -*- C++ -*-
deba@139
     2
 *
deba@139
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@139
     4
 *
deba@139
     5
 * Copyright (C) 2003-2008
deba@139
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@139
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@139
     8
 *
deba@139
     9
 * Permission to use, modify and distribute this software is granted
deba@139
    10
 * provided that this copyright notice appears in all copies. For
deba@139
    11
 * precise terms see the accompanying LICENSE file.
deba@139
    12
 *
deba@139
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@139
    14
 * express or implied, and with no claim as to its suitability for any
deba@139
    15
 * purpose.
deba@139
    16
 *
deba@139
    17
 */
deba@139
    18
deba@139
    19
#include <iostream>
deba@139
    20
#include <vector>
deba@139
    21
deba@139
    22
#include <lemon/graph_utils.h>
deba@139
    23
deba@139
    24
#include <lemon/list_graph.h>
deba@139
    25
#include <lemon/smart_graph.h>
deba@139
    26
deba@139
    27
#include "test_tools.h"
deba@139
    28
#include "graph_utils_test.h"
deba@139
    29
deba@139
    30
deba@139
    31
using namespace lemon;
deba@139
    32
deba@139
    33
template <class Graph>
deba@139
    34
void checkSnapDeg() 
deba@139
    35
{
deba@139
    36
  Graph g;
deba@139
    37
  typename Graph::Node n1=g.addNode();
deba@139
    38
  typename Graph::Node n2=g.addNode();
deba@139
    39
   
deba@139
    40
  InDegMap<Graph> ind(g);
deba@139
    41
 
deba@139
    42
  g.addArc(n1,n2);
deba@139
    43
  
deba@139
    44
  typename Graph::Snapshot snap(g);
deba@139
    45
  
deba@139
    46
  OutDegMap<Graph> outd(g);
deba@139
    47
  
deba@139
    48
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139
    49
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139
    50
deba@139
    51
  g.addArc(n1,n2);
deba@139
    52
  g.addArc(n2,n1);
deba@139
    53
 
deba@139
    54
  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
deba@139
    55
  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
deba@139
    56
deba@139
    57
  snap.restore();
deba@139
    58
deba@139
    59
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139
    60
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139
    61
  
deba@139
    62
}
deba@139
    63
deba@139
    64
int main() {
deba@139
    65
  ///\file
deba@139
    66
  { // checking list graph
deba@139
    67
    checkDigraphCounters<ListDigraph>();
deba@139
    68
    checkFindArc<ListDigraph>();
deba@139
    69
  }
deba@139
    70
  { // checking smart graph
deba@139
    71
    checkDigraphCounters<SmartDigraph>();
deba@139
    72
    checkFindArc<SmartDigraph>();
deba@139
    73
  }
deba@139
    74
  {
deba@139
    75
    int num = 5;
deba@139
    76
    SmartDigraph fg;
deba@139
    77
    std::vector<SmartDigraph::Node> nodes;
deba@139
    78
    for (int i = 0; i < num; ++i) {
deba@139
    79
      nodes.push_back(fg.addNode());
deba@139
    80
    }
deba@139
    81
    for (int i = 0; i < num * num; ++i) {
deba@139
    82
      fg.addArc(nodes[i / num], nodes[i % num]);
deba@139
    83
    }
deba@139
    84
    check(countNodes(fg) == num, "FullGraph: wrong node number.");
deba@139
    85
    check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
deba@139
    86
    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
deba@139
    87
      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
deba@139
    88
	ConArcIt<SmartDigraph> con(fg, src, trg);
deba@139
    89
	check(con != INVALID, "There is no connecting arc.");
deba@139
    90
	check(fg.source(con) == src, "Wrong source.");
deba@139
    91
	check(fg.target(con) == trg, "Wrong target.");
deba@139
    92
	check(++con == INVALID, "There is more connecting arc.");
deba@139
    93
      }
deba@139
    94
    }
deba@139
    95
    AllArcLookUp<SmartDigraph> el(fg);
deba@139
    96
    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
deba@139
    97
      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
deba@139
    98
	SmartDigraph::Arc con = el(src, trg);
deba@139
    99
	check(con != INVALID, "There is no connecting arc.");
deba@139
   100
	check(fg.source(con) == src, "Wrong source.");
deba@139
   101
	check(fg.target(con) == trg, "Wrong target.");
deba@139
   102
	check(el(src,trg,con) == INVALID, "There is more connecting arc.");
deba@139
   103
      }
deba@139
   104
    }
deba@139
   105
  }
deba@139
   106
deba@139
   107
  //check In/OutDegMap (and Snapshot feature)
deba@139
   108
deba@139
   109
  checkSnapDeg<ListDigraph>();
deba@139
   110
  checkSnapDeg<SmartDigraph>();
deba@139
   111
  
deba@139
   112
  {
deba@139
   113
    const int nodeNum = 10;
deba@139
   114
    const int arcNum = 100;
deba@139
   115
    ListDigraph digraph;
deba@139
   116
    InDegMap<ListDigraph> inDeg(digraph);
deba@139
   117
    OutDegMap<ListDigraph> outDeg(digraph);
deba@139
   118
    std::vector<ListDigraph::Node> nodes(nodeNum);
deba@139
   119
    for (int i = 0; i < nodeNum; ++i) {
deba@139
   120
      nodes[i] = digraph.addNode();
deba@139
   121
    }
deba@139
   122
    std::vector<ListDigraph::Arc> arcs(arcNum);
deba@139
   123
    for (int i = 0; i < arcNum; ++i) {
deba@139
   124
      arcs[i] = 
deba@139
   125
	digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
deba@139
   126
    }
deba@139
   127
    for (int i = 0; i < nodeNum; ++i) {
deba@139
   128
      check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
deba@139
   129
	    "Wrong in degree map");
deba@139
   130
    }
deba@139
   131
    for (int i = 0; i < nodeNum; ++i) {
deba@139
   132
      check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
deba@139
   133
	    "Wrong in degree map");
deba@139
   134
    }
deba@139
   135
  }
deba@139
   136
deba@139
   137
  ///Everything is OK
deba@139
   138
  std::cout << __FILE__ ": All tests passed.\n";
deba@139
   139
deba@139
   140
  return 0;
deba@139
   141
}