Edit: /usr/include/boost/graph/bipartite.hpp (13492B)
/**
*
* 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)
*
*/
#ifndef BOOST_GRAPH_BIPARTITE_HPP
#define BOOST_GRAPH_BIPARTITE_HPP
#include
#include
#include
#include
#include
#include
#include
namespace boost
{
namespace detail
{
/**
* The bipartite_visitor_error is thrown if an edge cannot be colored.
* The witnesses are the edges incident vertices.
*/
template < typename Vertex >
struct BOOST_SYMBOL_VISIBLE bipartite_visitor_error : std::exception
{
std::pair< Vertex, Vertex > witnesses;
bipartite_visitor_error(Vertex a, Vertex b) : witnesses(a, b) {}
const char* what() const throw() { return "Graph is not bipartite."; }
};
/**
* Functor which colors edges to be non-monochromatic.
*/
template < typename PartitionMap > struct bipartition_colorize
{
typedef on_tree_edge event_filter;
bipartition_colorize(PartitionMap partition_map)
: partition_map_(partition_map)
{
}
template < typename Edge, typename Graph >
void operator()(Edge e, const Graph& g)
{
typedef typename graph_traits< Graph >::vertex_descriptor
vertex_descriptor_t;
typedef color_traits<
typename property_traits< PartitionMap >::value_type >
color_traits;
vertex_descriptor_t source_vertex = source(e, g);
vertex_descriptor_t target_vertex = target(e, g);
if (get(partition_map_, source_vertex) == color_traits::white())
put(partition_map_, target_vertex, color_traits::black());
else
put(partition_map_, target_vertex, color_traits::white());
}
private:
PartitionMap partition_map_;
};
/**
* Creates a bipartition_colorize functor which colors edges
* to be non-monochromatic.
*
* @param partition_map Color map for the bipartition
* @return The functor.
*/
template < typename PartitionMap >
inline bipartition_colorize< PartitionMap > colorize_bipartition(
PartitionMap partition_map)
{
return bipartition_colorize< PartitionMap >(partition_map);
}
/**
* Functor which tests an edge to be monochromatic.
*/
template < typename PartitionMap > struct bipartition_check
{
typedef on_back_edge event_filter;
bipartition_check(PartitionMap partition_map)
: partition_map_(partition_map)
{
}
template < typename Edge, typename Graph >
void operator()(Edge e, const Graph& g)
{
typedef typename graph_traits< Graph >::vertex_descriptor
vertex_descriptor_t;
vertex_descriptor_t source_vertex = source(e, g);
vertex_descriptor_t target_vertex = target(e, g);
if (get(partition_map_, source_vertex)
== get(partition_map_, target_vertex))
throw bipartite_visitor_error< vertex_descriptor_t >(
source_vertex, target_vertex);
}
private:
PartitionMap partition_map_;
};
/**
* Creates a bipartition_check functor which raises an error if a
* monochromatic edge is found.
*
* @param partition_map The map for a bipartition.
* @return The functor.
*/
template < typename PartitionMap >
inline bipartition_check< PartitionMap > check_bipartition(
PartitionMap partition_map)
{
return bipartition_check< PartitionMap >(partition_map);
}
/**
* Find the beginning of a common suffix of two sequences
*
* @param sequence1 Pair of bidirectional iterators defining the first
* sequence.
* @param sequence2 Pair of bidirectional iterators defining the second
* sequence.
* @return Pair of iterators pointing to the beginning of the common suffix.
*/
template < typename BiDirectionalIterator1,
typename BiDirectionalIterator2 >
inline std::pair< BiDirectionalIterator1, BiDirectionalIterator2 >
reverse_mismatch(
std::pair< BiDirectionalIterator1, BiDirectionalIterator1 > sequence1,
std::pair< BiDirectionalIterator2, BiDirectionalIterator2 > sequence2)
{
if (sequence1.first == sequence1.second
|| sequence2.first == sequence2.second)
return std::make_pair(sequence1.first, sequence2.first);
BiDirectionalIterator1 iter1 = sequence1.second;
BiDirectionalIterator2 iter2 = sequence2.second;
while (true)
{
--iter1;
--iter2;
if (*iter1 != *iter2)
{
++iter1;
++iter2;
break;
}
if (iter1 == sequence1.first)
break;
if (iter2 == sequence2.first)
break;
}
return std::make_pair(iter1, iter2);
}
}
/**
* Checks a given graph for bipartiteness and fills the given color map with
* white and black according to the bipartition. If the graph is not
* bipartite, the contents of the color map are undefined. Runs in linear
* time in the size of the graph, if access to the property maps is in
* constant time.
*
* @param graph The given graph.
* @param index_map An index map associating vertices with an index.
* @param partition_map A color map to fill with the bipartition.
* @return true if and only if the given graph is bipartite.
*/
template < typename Graph, typename IndexMap, typename PartitionMap >
bool is_bipartite(
const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
{
/// General types and variables
typedef
typename property_traits< PartitionMap >::value_type partition_color_t;
typedef
typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
/// Declare dfs visitor
// detail::empty_recorder recorder;
// typedef detail::bipartite_visitor dfs_visitor_t; dfs_visitor_t dfs_visitor
// (partition_map, recorder);
/// Call dfs
try
{
depth_first_search(graph,
vertex_index_map(index_map).visitor(make_dfs_visitor(
std::make_pair(detail::colorize_bipartition(partition_map),
std::make_pair(detail::check_bipartition(partition_map),
put_property(partition_map,
color_traits< partition_color_t >::white(),
on_start_vertex()))))));
}
catch (const detail::bipartite_visitor_error< vertex_descriptor_t >&)
{
return false;
}
return true;
}
/**
* Checks a given graph for bipartiteness.
*
* @param graph The given graph.
* @param index_map An index map associating vertices with an index.
* @return true if and only if the given graph is bipartite.
*/
template < typename Graph, typename IndexMap >
bool is_bipartite(const Graph& graph, const IndexMap index_map)
{
typedef one_bit_color_map< IndexMap > partition_map_t;
partition_map_t partition_map(num_vertices(graph), index_map);
return is_bipartite(graph, index_map, partition_map);
}
/**
* Checks a given graph for bipartiteness. The graph must
* have an internal vertex_index property. Runs in linear time in the
* size of the graph, if access to the property maps is in constant time.
*
* @param graph The given graph.
* @return true if and only if the given graph is bipartite.
*/
template < typename Graph > bool is_bipartite(const Graph& graph)
{
return is_bipartite(graph, get(vertex_index, graph));
}
/**
* Checks a given graph for bipartiteness and fills a given color map with
* white and black according to the bipartition. If the graph is not
* bipartite, a sequence of vertices, producing an odd-cycle, is written to
* the output iterator. The final iterator value is returned. Runs in linear
* time in the size of the graph, if access to the property maps is in
* constant time.
*
* @param graph The given graph.
* @param index_map An index map associating vertices with an index.
* @param partition_map A color map to fill with the bipartition.
* @param result An iterator to write the odd-cycle vertices to.
* @return The final iterator value after writing.
*/
template < typename Graph, typename IndexMap, typename PartitionMap,
typename OutputIterator >
OutputIterator find_odd_cycle(const Graph& graph, const IndexMap index_map,
PartitionMap partition_map, OutputIterator result)
{
/// General types and variables
typedef
typename property_traits< PartitionMap >::value_type partition_color_t;
typedef
typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
vertex_iterator_t vertex_iter, vertex_end;
/// Declare predecessor map
typedef std::vector< vertex_descriptor_t > predecessors_t;
typedef iterator_property_map< typename predecessors_t::iterator, IndexMap,
vertex_descriptor_t, vertex_descriptor_t& >
predecessor_map_t;
predecessors_t predecessors(
num_vertices(graph), graph_traits< Graph >::null_vertex());
predecessor_map_t predecessor_map(predecessors.begin(), index_map);
/// Initialize predecessor map
for (boost::tie(vertex_iter, vertex_end) = vertices(graph);
vertex_iter != vertex_end; ++vertex_iter)
{
put(predecessor_map, *vertex_iter, *vertex_iter);
}
/// Call dfs
try
{
depth_first_search(graph,
vertex_index_map(index_map).visitor(make_dfs_visitor(
std::make_pair(detail::colorize_bipartition(partition_map),
std::make_pair(detail::check_bipartition(partition_map),
std::make_pair(
put_property(partition_map,
color_traits< partition_color_t >::white(),
on_start_vertex()),
record_predecessors(
predecessor_map, on_tree_edge())))))));
}
catch (const detail::bipartite_visitor_error< vertex_descriptor_t >& error)
{
typedef std::vector< vertex_descriptor_t > path_t;
path_t path1, path2;
vertex_descriptor_t next, current;
/// First path
next = error.witnesses.first;
do
{
current = next;
path1.push_back(current);
next = predecessor_map[current];
} while (current != next);
/// Second path
next = error.witnesses.second;
do
{
current = next;
path2.push_back(current);
next = predecessor_map[current];
} while (current != next);
/// Find beginning of common suffix
std::pair< typename path_t::iterator, typename path_t::iterator >
mismatch = detail::reverse_mismatch(
std::make_pair(path1.begin(), path1.end()),
std::make_pair(path2.begin(), path2.end()));
/// Copy the odd-length cycle
result = std::copy(path1.begin(), mismatch.first + 1, result);
return std::reverse_copy(path2.begin(), mismatch.second, result);
}
return result;
}
/**
* Checks a given graph for bipartiteness. If the graph is not bipartite, a
* sequence of vertices, producing an odd-cycle, is written to the output
* iterator. The final iterator value is returned. Runs in linear time in the
* size of the graph, if access to the property maps is in constant time.
*
* @param graph The given graph.
* @param index_map An index map associating vertices with an index.
* @param result An iterator to write the odd-cycle vertices to.
* @return The final iterator value after writing.
*/
template < typename Graph, typename IndexMap, typename OutputIterator >
OutputIterator find_odd_cycle(
const Graph& graph, const IndexMap index_map, OutputIterator result)
{
typedef one_bit_color_map< IndexMap > partition_map_t;
partition_map_t partition_map(num_vertices(graph), index_map);
return find_odd_cycle(graph, index_map, partition_map, result);
}
/**
* Checks a given graph for bipartiteness. If the graph is not bipartite, a
* sequence of vertices, producing an odd-cycle, is written to the output
* iterator. The final iterator value is returned. The graph must have an
* internal vertex_index property. Runs in linear time in the size of the
* graph, if access to the property maps is in constant time.
*
* @param graph The given graph.
* @param result An iterator to write the odd-cycle vertices to.
* @return The final iterator value after writing.
*/
template < typename Graph, typename OutputIterator >
OutputIterator find_odd_cycle(const Graph& graph, OutputIterator result)
{
return find_odd_cycle(graph, get(vertex_index, graph), result);
}
}
#endif /// BOOST_GRAPH_BIPARTITE_HPP