1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
/**
*
* Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net)
*
* Authors: Matthias Walter
*
* Distributed under the Boost Software License, Version 1.0. (See
* accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*
*/
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
using namespace boost;
/// Example to test for bipartiteness and print the certificates.
template < typename Graph > void print_bipartite(const Graph& g)
{
typedef graph_traits< Graph > traits;
typename traits::vertex_iterator vertex_iter, vertex_end;
/// Most simple interface just tests for bipartiteness.
bool bipartite = is_bipartite(g);
if (bipartite)
{
typedef std::vector< default_color_type > partition_t;
typedef
typename property_map< Graph, vertex_index_t >::type index_map_t;
typedef iterator_property_map< partition_t::iterator, index_map_t >
partition_map_t;
partition_t partition(num_vertices(g));
partition_map_t partition_map(partition.begin(), get(vertex_index, g));
/// A second interface yields a bipartition in a color map, if the graph
/// is bipartite.
is_bipartite(g, get(vertex_index, g), partition_map);
for (boost::tie(vertex_iter, vertex_end) = vertices(g);
vertex_iter != vertex_end; ++vertex_iter)
{
std::cout
<< "Vertex " << *vertex_iter << " has color "
<< (get(partition_map, *vertex_iter)
== color_traits< default_color_type >::white()
? "white"
: "black")
<< std::endl;
}
}
else
{
typedef std::vector< typename traits::vertex_descriptor >
vertex_vector_t;
vertex_vector_t odd_cycle;
/// A third interface yields an odd-cycle if the graph is not bipartite.
find_odd_cycle(g, get(vertex_index, g), std::back_inserter(odd_cycle));
std::cout << "Odd cycle consists of the vertices:";
for (size_t i = 0; i < odd_cycle.size(); ++i)
{
std::cout << " " << odd_cycle[i];
}
std::cout << std::endl;
}
}
int main(int argc, char** argv)
{
typedef adjacency_list< vecS, vecS, undirectedS > vector_graph_t;
typedef std::pair< int, int > E;
/**
* Create the graph drawn below.
*
* 0 - 1 - 2
* | |
* 3 - 4 - 5 - 6
* / \ /
* | 7
* | |
* 8 - 9 - 10
**/
E bipartite_edges[]
= { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 4), E(3, 8), E(4, 5),
E(4, 7), E(5, 6), E(6, 7), E(7, 10), E(8, 9), E(9, 10) };
vector_graph_t bipartite_vector_graph(&bipartite_edges[0],
&bipartite_edges[0] + sizeof(bipartite_edges) / sizeof(E), 11);
/**
* Create the graph drawn below.
*
* 2 - 1 - 0
* | |
* 3 - 6 - 5 - 4
* / \ /
* | 7
* | /
* 8 ---- 9
*
**/
E non_bipartite_edges[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 6), E(3, 6),
E(3, 8), E(4, 5), E(4, 7), E(5, 6), E(6, 7), E(7, 9), E(8, 9) };
vector_graph_t non_bipartite_vector_graph(&non_bipartite_edges[0],
&non_bipartite_edges[0] + sizeof(non_bipartite_edges) / sizeof(E), 10);
/// Call test routine for a bipartite and a non-bipartite graph.
print_bipartite(bipartite_vector_graph);
print_bipartite(non_bipartite_vector_graph);
return 0;
}
|
