// Copyright (c) Jeremy Siek 2001 | |
// Copyright (c) Douglas Gregor 2004 | |
// | |
// 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) | |
// NOTE: this final is generated by libs/graph/doc/biconnected_components.w | |
#ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
#define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
#include <stack> | |
#include <vector> | |
#include <algorithm> // for std::min and std::max | |
#include <boost/config.hpp> | |
#include <boost/limits.hpp> | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/graph_concepts.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/graph/depth_first_search.hpp> | |
#include <boost/graph/graph_utility.hpp> | |
namespace boost | |
{ | |
namespace detail | |
{ | |
template<typename ComponentMap, typename DiscoverTimeMap, | |
typename LowPointMap, typename PredecessorMap, | |
typename OutputIterator, typename Stack, | |
typename DFSVisitor> | |
struct biconnected_components_visitor : public dfs_visitor<> | |
{ | |
biconnected_components_visitor | |
(ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm, | |
std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, | |
OutputIterator out, Stack& S, DFSVisitor vis) | |
: comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt), | |
pred(pred), out(out), S(S), vis(vis) { } | |
template <typename Vertex, typename Graph> | |
void initialize_vertex(const Vertex& u, Graph& g) | |
{ | |
vis.initialize_vertex(u, g); | |
} | |
template <typename Vertex, typename Graph> | |
void start_vertex(const Vertex& u, Graph& g) | |
{ | |
put(pred, u, u); | |
vis.start_vertex(u, g); | |
} | |
template <typename Vertex, typename Graph> | |
void discover_vertex(const Vertex& u, Graph& g) | |
{ | |
put(dtm, u, ++dfs_time); | |
put(lowpt, u, get(dtm, u)); | |
vis.discover_vertex(u, g); | |
} | |
template <typename Edge, typename Graph> | |
void examine_edge(const Edge& e, Graph& g) | |
{ | |
vis.examine_edge(e, g); | |
} | |
template <typename Edge, typename Graph> | |
void tree_edge(const Edge& e, Graph& g) | |
{ | |
S.push(e); | |
put(pred, target(e, g), source(e, g)); | |
vis.tree_edge(e, g); | |
} | |
template <typename Edge, typename Graph> | |
void back_edge(const Edge& e, Graph& g) | |
{ | |
BOOST_USING_STD_MIN(); | |
if ( target(e, g) != get(pred, source(e, g)) ) { | |
S.push(e); | |
put(lowpt, source(e, g), | |
min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, source(e, g)), | |
get(dtm, target(e, g)))); | |
} | |
vis.back_edge(e, g); | |
} | |
template <typename Edge, typename Graph> | |
void forward_or_cross_edge(const Edge& e, Graph& g) | |
{ | |
vis.forward_or_cross_edge(e, g); | |
} | |
template <typename Vertex, typename Graph> | |
void finish_vertex(const Vertex& u, Graph& g) | |
{ | |
BOOST_USING_STD_MIN(); | |
Vertex parent = get(pred, u); | |
const std::size_t dtm_of_dubious_parent = get(dtm, parent); | |
bool is_art_point = false; | |
if ( dtm_of_dubious_parent > get(dtm, u) ) { | |
parent = get(pred, parent); | |
is_art_point = true; | |
put(pred, get(pred, u), u); | |
put(pred, u, parent); | |
} | |
if ( parent == u ) { // at top | |
if ( get(dtm, u) + 1 == dtm_of_dubious_parent ) | |
is_art_point = false; | |
} else { | |
put(lowpt, parent, | |
min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent), | |
get(lowpt, u))); | |
if (get(lowpt, u) >= get(dtm, parent)) { | |
if ( get(dtm, parent) > get(dtm, get(pred, parent)) ) { | |
put(pred, u, get(pred, parent)); | |
put(pred, parent, u); | |
} | |
while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) { | |
put(comp, S.top(), c); | |
S.pop(); | |
} | |
put(comp, S.top(), c); | |
S.pop(); | |
++c; | |
if ( S.empty() ) { | |
put(pred, u, parent); | |
put(pred, parent, u); | |
} | |
} | |
} | |
if ( is_art_point ) | |
*out++ = u; | |
vis.finish_vertex(u, g); | |
} | |
ComponentMap comp; | |
std::size_t& c; | |
DiscoverTimeMap dtm; | |
std::size_t& dfs_time; | |
LowPointMap lowpt; | |
PredecessorMap pred; | |
OutputIterator out; | |
Stack& S; | |
DFSVisitor vis; | |
}; | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, | |
typename PredecessorMap, typename DFSVisitor> | |
std::pair<std::size_t, OutputIterator> | |
biconnected_components_impl(const Graph & g, ComponentMap comp, | |
OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, | |
LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
function_requires<VertexListGraphConcept<Graph> >(); | |
function_requires<IncidenceGraphConcept<Graph> >(); | |
function_requires<WritablePropertyMapConcept<ComponentMap, edge_t> >(); | |
function_requires<ReadWritePropertyMapConcept<DiscoverTimeMap, | |
vertex_t> >(); | |
function_requires<ReadWritePropertyMapConcept<LowPointMap, vertex_t > >(); | |
function_requires<ReadWritePropertyMapConcept<PredecessorMap, | |
vertex_t> >(); | |
std::size_t num_components = 0; | |
std::size_t dfs_time = 0; | |
std::stack<edge_t> S; | |
biconnected_components_visitor<ComponentMap, DiscoverTimeMap, | |
LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t>, | |
DFSVisitor> | |
vis(comp, num_components, dtm, dfs_time, lowpt, pred, out, | |
S, dfs_vis); | |
depth_first_search(g, visitor(vis).vertex_index_map(index_map)); | |
return std::pair<std::size_t, OutputIterator>(num_components, vis.out); | |
} | |
template <typename PredecessorMap> | |
struct bicomp_dispatch3 | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, typename DiscoverTimeMap, | |
typename LowPointMap, class P, class T, class R> | |
static std::pair<std::size_t, OutputIterator> apply (const Graph & g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
DiscoverTimeMap dtm, LowPointMap lowpt, | |
const bgl_named_params<P, T, R>& params, PredecessorMap pred) | |
{ | |
return biconnected_components_impl | |
(g, comp, out, index_map, dtm, lowpt, pred, | |
choose_param(get_param(params, graph_visitor), | |
make_dfs_visitor(null_visitor()))); | |
} | |
}; | |
template <> | |
struct bicomp_dispatch3<error_property_not_found> | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, typename DiscoverTimeMap, | |
typename LowPointMap, class P, class T, class R> | |
static std::pair<std::size_t, OutputIterator> apply (const Graph & g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
DiscoverTimeMap dtm, LowPointMap lowpt, | |
const bgl_named_params<P, T, R>& params, | |
error_property_not_found) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
std::vector<vertex_t> pred(num_vertices(g)); | |
vertex_t vert = graph_traits<Graph>::null_vertex(); | |
return biconnected_components_impl | |
(g, comp, out, index_map, dtm, lowpt, | |
make_iterator_property_map(pred.begin(), index_map, vert), | |
choose_param(get_param(params, graph_visitor), | |
make_dfs_visitor(null_visitor()))); | |
} | |
}; | |
template <typename LowPointMap> | |
struct bicomp_dispatch2 | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, typename DiscoverTimeMap, | |
typename P, typename T, typename R> | |
static std::pair<std::size_t, OutputIterator> apply (const Graph& g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, | |
LowPointMap lowpt) | |
{ | |
typedef typename property_value< bgl_named_params<P,T,R>, | |
vertex_predecessor_t>::type dispatch_type; | |
return bicomp_dispatch3<dispatch_type>::apply | |
(g, comp, out, index_map, dtm, lowpt, params, | |
get_param(params, vertex_predecessor)); | |
} | |
}; | |
template <> | |
struct bicomp_dispatch2<error_property_not_found> | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, typename DiscoverTimeMap, | |
typename P, typename T, typename R> | |
static std::pair<std::size_t, OutputIterator> apply (const Graph& g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
DiscoverTimeMap dtm, const bgl_named_params<P, T, R>& params, | |
error_property_not_found) | |
{ | |
typedef typename graph_traits<Graph>::vertices_size_type | |
vertices_size_type; | |
std::vector<vertices_size_type> lowpt(num_vertices(g)); | |
vertices_size_type vst(0); | |
typedef typename property_value< bgl_named_params<P,T,R>, | |
vertex_predecessor_t>::type dispatch_type; | |
return bicomp_dispatch3<dispatch_type>::apply | |
(g, comp, out, index_map, dtm, | |
make_iterator_property_map(lowpt.begin(), index_map, vst), | |
params, get_param(params, vertex_predecessor)); | |
} | |
}; | |
template <typename DiscoverTimeMap> | |
struct bicomp_dispatch1 | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, class P, class T, class R> | |
static std::pair<std::size_t, OutputIterator> apply(const Graph& g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
const bgl_named_params<P, T, R>& params, DiscoverTimeMap dtm) | |
{ | |
typedef typename property_value< bgl_named_params<P,T,R>, | |
vertex_lowpoint_t>::type dispatch_type; | |
return bicomp_dispatch2<dispatch_type>::apply | |
(g, comp, out, index_map, dtm, params, | |
get_param(params, vertex_lowpoint)); | |
} | |
}; | |
template <> | |
struct bicomp_dispatch1<error_property_not_found> | |
{ | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename VertexIndexMap, class P, class T, class R> | |
static std::pair<std::size_t, OutputIterator> apply(const Graph& g, | |
ComponentMap comp, OutputIterator out, VertexIndexMap index_map, | |
const bgl_named_params<P, T, R>& params, error_property_not_found) | |
{ | |
typedef typename graph_traits<Graph>::vertices_size_type | |
vertices_size_type; | |
std::vector<vertices_size_type> discover_time(num_vertices(g)); | |
vertices_size_type vst(0); | |
typedef typename property_value< bgl_named_params<P,T,R>, | |
vertex_lowpoint_t>::type dispatch_type; | |
return bicomp_dispatch2<dispatch_type>::apply | |
(g, comp, out, index_map, | |
make_iterator_property_map(discover_time.begin(), index_map, vst), | |
params, get_param(params, vertex_lowpoint)); | |
} | |
}; | |
} | |
template<typename Graph, typename ComponentMap, typename OutputIterator, | |
typename DiscoverTimeMap, typename LowPointMap> | |
std::pair<std::size_t, OutputIterator> | |
biconnected_components(const Graph& g, ComponentMap comp, | |
OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) | |
{ | |
typedef detail::error_property_not_found dispatch_type; | |
return detail::bicomp_dispatch3<dispatch_type>::apply | |
(g, comp, out, | |
get(vertex_index, g), | |
dtm, lowpt, | |
bgl_named_params<int, buffer_param_t>(0), | |
detail::error_property_not_found()); | |
} | |
template <typename Graph, typename ComponentMap, typename OutputIterator, | |
typename P, typename T, typename R> | |
std::pair<std::size_t, OutputIterator> | |
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, | |
const bgl_named_params<P, T, R>& params) | |
{ | |
typedef typename property_value< bgl_named_params<P,T,R>, | |
vertex_discover_time_t>::type dispatch_type; | |
return detail::bicomp_dispatch1<dispatch_type>::apply(g, comp, out, | |
choose_const_pmap(get_param(params, vertex_index), g, vertex_index), | |
params, get_param(params, vertex_discover_time)); | |
} | |
template < typename Graph, typename ComponentMap, typename OutputIterator> | |
std::pair<std::size_t, OutputIterator> | |
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out) | |
{ | |
return biconnected_components(g, comp, out, | |
bgl_named_params<int, buffer_param_t>(0)); | |
} | |
namespace graph_detail { | |
struct dummy_output_iterator | |
{ | |
typedef std::output_iterator_tag iterator_category; | |
typedef void value_type; | |
typedef void pointer; | |
typedef void difference_type; | |
struct reference { | |
template<typename T> | |
reference& operator=(const T&) { return *this; } | |
}; | |
reference operator*() const { return reference(); } | |
dummy_output_iterator& operator++() { return *this; } | |
dummy_output_iterator operator++(int) { return *this; } | |
}; | |
} // end namespace graph_detail | |
template <typename Graph, typename ComponentMap, | |
typename P, typename T, typename R> | |
std::size_t | |
biconnected_components(const Graph& g, ComponentMap comp, | |
const bgl_named_params<P, T, R>& params) | |
{ | |
return biconnected_components(g, comp, | |
graph_detail::dummy_output_iterator(), params).first; | |
} | |
template <typename Graph, typename ComponentMap> | |
std::size_t | |
biconnected_components(const Graph& g, ComponentMap comp) | |
{ | |
return biconnected_components(g, comp, | |
graph_detail::dummy_output_iterator()).first; | |
} | |
template<typename Graph, typename OutputIterator, | |
typename P, typename T, typename R> | |
OutputIterator | |
articulation_points(const Graph& g, OutputIterator out, | |
const bgl_named_params<P, T, R>& params) | |
{ | |
return biconnected_components(g, dummy_property_map(), out, | |
params).second; | |
} | |
template<typename Graph, typename OutputIterator> | |
OutputIterator | |
articulation_points(const Graph& g, OutputIterator out) | |
{ | |
return biconnected_components(g, dummy_property_map(), out, | |
bgl_named_params<int, buffer_param_t>(0)).second; | |
} | |
} // namespace boost | |
#endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */ |