test/graph_utils_test.cc
author deba
Tue, 24 Jan 2006 16:07:38 +0000
changeset 1901 723b2b81d900
parent 1729 06f939455cb1
child 1956 a055123339d5
permissions -rw-r--r--
Lemon Graph Format uses label instead of id named map.
     1 // -*- c++ -*-
     2 
     3 #include <iostream>
     4 #include <vector>
     5 
     6 #include <lemon/graph_utils.h>
     7 
     8 #include <lemon/list_graph.h>
     9 #include <lemon/smart_graph.h>
    10 #include <lemon/full_graph.h>
    11 
    12 #include "test_tools.h"
    13 #include "graph_utils_test.h"
    14 
    15 
    16 using namespace lemon;
    17 
    18 template<class Graph>
    19 void checkSnapDeg() 
    20 {
    21   Graph g;
    22   typename Graph::Node n1=g.addNode();
    23   typename Graph::Node n2=g.addNode();
    24    
    25   InDegMap<Graph> ind(g);
    26  
    27   g.addEdge(n1,n2);
    28   
    29   typename Graph::Snapshot snap(g);
    30   
    31   OutDegMap<Graph> outd(g);
    32   
    33   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    34   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    35 
    36   g.addEdge(n1,n2);
    37   g.addEdge(n2,n1);
    38  
    39   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
    40   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
    41 
    42   snap.restore();
    43 
    44   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    45   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    46   
    47 }
    48 
    49 int main() {
    50   ///\file
    51   { // checking list graph
    52     checkGraphCounters<ListGraph>();
    53     checkFindEdge<ListGraph>();
    54   }
    55   { // checking smart graph
    56     checkGraphCounters<SmartGraph>();
    57     checkFindEdge<SmartGraph>();
    58   }
    59   {
    60     int num = 5;
    61     FullGraph fg(num);
    62     check(countNodes(fg) == num, "FullGraph: wrong node number.");
    63     check(countEdges(fg) == num*num, "FullGraph: wrong edge number.");
    64     for (FullGraph::NodeIt src(fg); src != INVALID; ++src) {
    65       for (FullGraph::NodeIt trg(fg); trg != INVALID; ++trg) {
    66 	ConEdgeIt<FullGraph> con(fg, src, trg);
    67 	check(con != INVALID, "There is no connecting edge.");
    68 	check(fg.source(con) == src, "Wrong source.");
    69 	check(fg.target(con) == trg, "Wrong target.");
    70 	check(++con == INVALID, "There is more connecting edge.");
    71       }
    72     }
    73   }
    74 
    75   //check In/OutDegMap (and Snapshot feature)
    76 
    77   checkSnapDeg<ListGraph>();
    78   checkSnapDeg<SmartGraph>();
    79   
    80   {
    81     const int nodeNum = 10;
    82     const int edgeNum = 100;
    83     ListGraph graph;
    84     InDegMap<ListGraph> inDeg(graph);
    85     OutDegMap<ListGraph> outDeg(graph);
    86     std::vector<ListGraph::Node> nodes(nodeNum);
    87     for (int i = 0; i < nodeNum; ++i) {
    88       nodes[i] = graph.addNode();
    89     }
    90     std::vector<ListGraph::Edge> edges(edgeNum);
    91     for (int i = 0; i < edgeNum; ++i) {
    92       edges[i] = 
    93 	graph.addEdge(nodes[urandom(nodeNum)], nodes[urandom(nodeNum)]);
    94     }
    95     for (int i = 0; i < nodeNum; ++i) {
    96       check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
    97 	    "Wrong in degree map");
    98     }
    99     for (int i = 0; i < nodeNum; ++i) {
   100       check(outDeg[nodes[i]] == countOutEdges(graph, nodes[i]), 
   101 	    "Wrong in degree map");
   102     }
   103   }
   104 
   105   ///Everything is OK
   106   std::cout << __FILE__ ": All tests passed.\n";
   107 
   108   return 0;
   109 }