123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154 |
- // (C) Copyright David Gleich 2007
- //
- // Use, modification and distribution are subject to the
- // Boost Software License, Version 1.0 (See accompanying file
- // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
- #include <vector>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/core_numbers.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <stdio.h>
- using namespace boost;
- const char* errstr = "";
- int test_1() {
- // core numbers of sample graph
- typedef adjacency_list<vecS,vecS,undirectedS> Graph;
- Graph G(21);
- add_edge(0,1,G);
- add_edge(1,2,G);
- add_edge(1,3,G);
- add_edge(2,3,G);
- add_edge(1,4,G);
- add_edge(3,4,G);
- add_edge(4,5,G);
- add_edge(4,6,G);
- add_edge(5,6,G);
- add_edge(4,7,G);
- add_edge(5,7,G);
- add_edge(6,7,G);
- add_edge(7,8,G);
- add_edge(3,9,G);
- add_edge(8,9,G);
- add_edge(8,10,G);
- add_edge(9,10,G);
- add_edge(10,11,G);
- add_edge(10,12,G);
- add_edge(3,13,G);
- add_edge(9,13,G);
- add_edge(3,14,G);
- add_edge(9,14,G);
- add_edge(13,14,G);
- add_edge(16,17,G);
- add_edge(16,18,G);
- add_edge(17,19,G);
- add_edge(18,19,G);
- add_edge(19,20,G);
- std::vector<int> core_nums(num_vertices(G));
- core_numbers(G,
- make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
- for (size_t i=0; i<num_vertices(G); ++i) {
- printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
- }
- int correct[21]={1,2,2,3,3,3,3,3,2,3,2,1,1,3,3,0,2,2,2,2,1};
- for (size_t i=0; i<num_vertices(G); ++i) {
- if (core_nums[i] != correct[i]) {
- return 1; // error!
- }
- }
- return 0;
- }
- int test_2() {
- // core numbers of sample graph
- typedef adjacency_list < listS, vecS, undirectedS,
- no_property, property < edge_weight_t, int > > graph_t;
- int num_nodes = 3;
- typedef std::pair<int,int> Edge;
- Edge edge_array[] = { Edge(0,1), Edge(0,2), Edge(1,2) };
- int weights[] = {-1, -2, -2};
- int num_arcs = sizeof(edge_array) / sizeof(Edge);
- graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
- std::vector<int> core_nums(num_vertices(G));
- weighted_core_numbers(G,
- make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
- for (size_t i=0; i<num_vertices(G); ++i) {
- printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
- }
- int correct[3]={-1,-1,-4};
- for (size_t i=0; i<num_vertices(G); ++i) {
- if (core_nums[i] != correct[i]) {
- return 1; // error!
- }
- }
- return 0;
- }
- int test_3() {
- // core numbers of a directed graph, the core numbers of a directed
- // cycle are always one
- typedef adjacency_list < vecS, vecS, directedS > graph_t;
- int num_nodes = 5;
- typedef std::pair<int,int> Edge;
- Edge edge_array[] = { Edge(0,1),Edge(1,2),Edge(2,3),Edge(3,4),Edge(4,0) };
- int num_arcs = sizeof(edge_array) / sizeof(Edge);
- graph_t G(edge_array, edge_array + num_arcs, num_nodes);
- std::vector<int> core_nums(num_vertices(G));
- core_numbers(G,
- make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
- for (size_t i=0; i<num_vertices(G); ++i) {
- printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
- }
- int correct[5]={1,1,1,1,1};
- for (size_t i=0; i<num_vertices(G); ++i) {
- if (core_nums[i] != correct[i]) {
- return 1; // error!
- }
- }
- return 0;
- }
- int main(int, char **) {
- int nfail = 0, ntotal = 0;
- int rval;
- const char* name;
- name= "core_numbers";
- rval= test_1(); ntotal++;
- if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
- else { printf("%20s success\n", name); }
- name= "weighted_core_numbers";
- rval= test_2(); ntotal++;
- if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
- else { printf("%20s success\n", name); }
- name= "directed_corenums";
- rval= test_3(); ntotal++;
- if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
- else { printf("%20s success\n", name); }
- printf("\n");
- printf("Total tests : %3i\n", ntotal);
- printf("Total failed : %3i\n", nfail);
- return nfail!=0;
- }
|