GeezerVison is showing github.com — boost_graph/example/bipartite_example.cpp at develop · stdgraph/boost_graph

Expand file tree

bipartite_example.cpp

Copy path

More file actions

Latest commit

History

125 lines (102 loc) · 3.59 KB

bipartite_example.cpp

Copy path

File metadata and controls

125 lines (102 loc) · 3.59 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* 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)

{

using traits = graph_traits< Graph >;

typename traits::vertex_iterator vertex_iter, vertex_end;

/// Most simple interface just tests for bipartiteness.

bool bipartite = is_bipartite(g);

if (bipartite)

{

using partition_t = std::vector< default_color_type >;

using index_map_t =

typename property_map< Graph, vertex_index_t >::type;

using partition_map_t

= iterator_property_map< partition_t::iterator, index_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

{

using vertex_vector_t

= std::vector< typename traits::vertex_descriptor >;

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)

{

using vector_graph_t = adjacency_list< vecS, vecS, undirectedS >;

using E = std::pair< int, int >;

/**

* 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;

}