ceph/src/boost/libs/graph/test/core_numbers_test.cpp

   1 // (C) Copyright David Gleich 2007
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <vector>
   8 #include <boost/graph/adjacency_list.hpp>
   9 #include <boost/graph/core_numbers.hpp>
  10 #include <boost/property_map/property_map.hpp>
  11 #include <stdio.h>
  12
  13 using namespace boost;
  14
  15 const char* errstr = "";
  16
  17 int test_1()
  18 {
  19     // core numbers of sample graph
  20     typedef adjacency_list< vecS, vecS, undirectedS > Graph;
  21
  22     Graph G(21);
  23     add_edge(0, 1, G);
  24     add_edge(1, 2, G);
  25     add_edge(1, 3, G);
  26     add_edge(2, 3, G);
  27     add_edge(1, 4, G);
  28     add_edge(3, 4, G);
  29     add_edge(4, 5, G);
  30     add_edge(4, 6, G);
  31     add_edge(5, 6, G);
  32     add_edge(4, 7, G);
  33     add_edge(5, 7, G);
  34     add_edge(6, 7, G);
  35     add_edge(7, 8, G);
  36     add_edge(3, 9, G);
  37     add_edge(8, 9, G);
  38     add_edge(8, 10, G);
  39     add_edge(9, 10, G);
  40     add_edge(10, 11, G);
  41     add_edge(10, 12, G);
  42     add_edge(3, 13, G);
  43     add_edge(9, 13, G);
  44     add_edge(3, 14, G);
  45     add_edge(9, 14, G);
  46     add_edge(13, 14, G);
  47     add_edge(16, 17, G);
  48     add_edge(16, 18, G);
  49     add_edge(17, 19, G);
  50     add_edge(18, 19, G);
  51     add_edge(19, 20, G);
  52
  53     std::vector< int > core_nums(num_vertices(G));
  54     core_numbers(
  55         G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
  56
  57     for (size_t i = 0; i < num_vertices(G); ++i)
  58     {
  59         printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
  60     }
  61
  62     int correct[21]
  63         = { 1, 2, 2, 3, 3, 3, 3, 3, 2, 3, 2, 1, 1, 3, 3, 0, 2, 2, 2, 2, 1 };
  64     for (size_t i = 0; i < num_vertices(G); ++i)
  65     {
  66         if (core_nums[i] != correct[i])
  67         {
  68             return 1; // error!
  69         }
  70     }
  71     return 0;
  72 }
  73
  74 int test_2()
  75 {
  76     // core numbers of sample graph
  77     typedef adjacency_list< listS, vecS, undirectedS, no_property,
  78         property< edge_weight_t, int > >
  79         graph_t;
  80     int num_nodes = 3;
  81     typedef std::pair< int, int > Edge;
  82
  83     Edge edge_array[] = { Edge(0, 1), Edge(0, 2), Edge(1, 2) };
  84     int weights[] = { -1, -2, -2 };
  85     int num_arcs = sizeof(edge_array) / sizeof(Edge);
  86
  87     graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
  88
  89     std::vector< int > core_nums(num_vertices(G));
  90     weighted_core_numbers(
  91         G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
  92
  93     for (size_t i = 0; i < num_vertices(G); ++i)
  94     {
  95         printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
  96     }
  97
  98     int correct[3] = { -1, -1, -4 };
  99     for (size_t i = 0; i < num_vertices(G); ++i)
 100     {
 101         if (core_nums[i] != correct[i])
 102         {
 103             return 1; // error!
 104         }
 105     }
 106     return 0;
 107 }
 108
 109 int test_3()
 110 {
 111     // core numbers of a directed graph, the core numbers of a directed
 112     // cycle are always one
 113     typedef adjacency_list< vecS, vecS, directedS > graph_t;
 114     int num_nodes = 5;
 115     typedef std::pair< int, int > Edge;
 116
 117     Edge edge_array[]
 118         = { Edge(0, 1), Edge(1, 2), Edge(2, 3), Edge(3, 4), Edge(4, 0) };
 119     int num_arcs = sizeof(edge_array) / sizeof(Edge);
 120
 121     graph_t G(edge_array, edge_array + num_arcs, num_nodes);
 122
 123     std::vector< int > core_nums(num_vertices(G));
 124     core_numbers(
 125         G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
 126
 127     for (size_t i = 0; i < num_vertices(G); ++i)
 128     {
 129         printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
 130     }
 131
 132     int correct[5] = { 1, 1, 1, 1, 1 };
 133     for (size_t i = 0; i < num_vertices(G); ++i)
 134     {
 135         if (core_nums[i] != correct[i])
 136         {
 137             return 1; // error!
 138         }
 139     }
 140     return 0;
 141 }
 142
 143 int main(int, char**)
 144 {
 145     int nfail = 0, ntotal = 0;
 146     int rval;
 147
 148     const char* name;
 149
 150     name = "core_numbers";
 151     rval = test_1();
 152     ntotal++;
 153     if (rval != 0)
 154     {
 155         nfail++;
 156         printf("%20s  %50s\n", name, errstr);
 157     }
 158     else
 159     {
 160         printf("%20s  success\n", name);
 161     }
 162
 163     name = "weighted_core_numbers";
 164     rval = test_2();
 165     ntotal++;
 166     if (rval != 0)
 167     {
 168         nfail++;
 169         printf("%20s  %50s\n", name, errstr);
 170     }
 171     else
 172     {
 173         printf("%20s  success\n", name);
 174     }
 175
 176     name = "directed_corenums";
 177     rval = test_3();
 178     ntotal++;
 179     if (rval != 0)
 180     {
 181         nfail++;
 182         printf("%20s  %50s\n", name, errstr);
 183     }
 184     else
 185     {
 186         printf("%20s  success\n", name);
 187     }
 188
 189     printf("\n");
 190     printf("Total tests  : %3i\n", ntotal);
 191     printf("Total failed : %3i\n", nfail);
 192
 193     return nfail != 0;
 194 }