//======================================================================= | |
// Copyright 2002 Indiana University. | |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
// | |
// 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_CREATE_CONDENSATION_GRAPH_HPP | |
#define BOOST_CREATE_CONDENSATION_GRAPH_HPP | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/property_map/property_map.hpp> | |
namespace boost { | |
template <typename Graph, typename ComponentLists, | |
typename ComponentNumberMap, | |
typename CondensationGraph, typename EdgeMultiplicityMap> | |
void create_condensation_graph(const Graph& g, | |
const ComponentLists& components, | |
ComponentNumberMap component_number, | |
CondensationGraph& cg, | |
EdgeMultiplicityMap edge_mult_map) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex; | |
typedef typename graph_traits<Graph>::vertices_size_type size_type; | |
typedef typename graph_traits<CondensationGraph>::vertex_descriptor | |
cg_vertex; | |
std::vector<cg_vertex> to_cg_vertex(components.size()); | |
for (size_type s = 0; s < components.size(); ++s) | |
to_cg_vertex[s] = add_vertex(cg); | |
for (size_type si = 0; si < components.size(); ++si) { | |
cg_vertex s = to_cg_vertex[si]; | |
std::vector<cg_vertex> adj; | |
for (size_type i = 0; i < components[si].size(); ++i) { | |
vertex u = components[s][i]; | |
typename graph_traits<Graph>::adjacency_iterator v, v_end; | |
for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) { | |
cg_vertex t = to_cg_vertex[component_number[*v]]; | |
if (s != t) // Avoid loops in the condensation graph | |
adj.push_back(t); | |
} | |
} | |
std::sort(adj.begin(), adj.end()); | |
if (! adj.empty()) { | |
size_type i = 0; | |
cg_vertex t = adj[i]; | |
typename graph_traits<CondensationGraph>::edge_descriptor e; | |
bool inserted; | |
boost::tie(e, inserted) = add_edge(s, t, cg); | |
put(edge_mult_map, e, 1); | |
++i; | |
while (i < adj.size()) { | |
if (adj[i] == t) | |
put(edge_mult_map, e, get(edge_mult_map, e) + 1); | |
else { | |
t = adj[i]; | |
boost::tie(e, inserted) = add_edge(s, t, cg); | |
put(edge_mult_map, e, 1); | |
} | |
++i; | |
} | |
} | |
} | |
} | |
template <typename Graph, typename ComponentLists, | |
typename ComponentNumberMap, typename CondensationGraph> | |
void create_condensation_graph(const Graph& g, | |
const ComponentLists& components, | |
ComponentNumberMap component_number, | |
CondensationGraph& cg) | |
{ | |
create_condensation_graph(g, components, component_number, cg, | |
dummy_property_map()); | |
} | |
} // namespace boost | |
#endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP |