]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/doc/eg1-iso.cpp
1 // Boost.Graph library isomorphism test
3 // Copyright (C) 2001 Douglas Gregor (gregod@cs.rpi.edu)
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 // For more information, see http://www.boost.org
13 // 29 Nov 2001 Jeremy Siek
14 // Changed to use Boost.Random.
15 // 29 Nov 2001 Doug Gregor
18 #define BOOST_INCLUDE_MAIN
19 #include <boost/test/test_tools.hpp>
20 #include <boost/graph/adjacency_list.hpp>
21 #include <boost/graph/isomorphism.hpp>
22 //#include "isomorphism-v3.hpp"
23 #include <boost/property_map/property_map.hpp>
31 using namespace boost
;
34 enum { a
, b
, c
, d
, e
, f
, g
, h
};
35 enum { _1
, _2
, _3
, _4
, _5
, _6
, _7
, _8
};
37 void test_isomorphism()
39 typedef adjacency_list
<vecS
, vecS
, bidirectionalS
> GraphA
;
40 typedef adjacency_list
<vecS
, vecS
, bidirectionalS
> GraphB
;
42 char a_names
[] = "abcdefgh";
43 char b_names
[] = "12345678";
78 std::vector
<std::size_t> in_degree_A(num_vertices(Ga
));
79 boost::detail::compute_in_degree(Ga
, &in_degree_A
[0]);
81 std::vector
<std::size_t> in_degree_B(num_vertices(Gb
));
82 boost::detail::compute_in_degree(Gb
, &in_degree_B
[0]);
84 degree_vertex_invariant
<std::size_t*, GraphA
>
85 invariantA(&in_degree_A
[0], Ga
);
86 degree_vertex_invariant
<std::size_t*, GraphB
>
87 invariantB(&in_degree_B
[0], Gb
);
89 std::vector
<graph_traits
<GraphB
>::vertex_descriptor
> f(num_vertices(Ga
));
91 bool ret
= isomorphism(Ga
, Gb
, &f
[0], invariantA
, invariantB
,
93 get(vertex_index
, Ga
), get(vertex_index
, Gb
));
96 for (std::size_t i
= 0; i
< num_vertices(Ga
); ++i
)
97 std::cout
<< "f(" << a_names
[i
] << ")=" << b_names
[f
[i
]] << std::endl
;
99 BOOST_TEST(verify_isomorphism(Ga
, Gb
, &f
[0]));
102 int test_main(int, char* [])
105 return boost::report_errors();