williamr@2: //======================================================================= williamr@2: // Copyright 2002 Indiana University. williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: williamr@2: #ifndef BOOST_CREATE_CONDENSATION_GRAPH_HPP williamr@2: #define BOOST_CREATE_CONDENSATION_GRAPH_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: template williamr@2: void create_condensation_graph(const Graph& g, williamr@2: const ComponentLists& components, williamr@2: ComponentNumberMap component_number, williamr@2: CondensationGraph& cg, williamr@2: EdgeMultiplicityMap edge_mult_map) williamr@2: { williamr@2: typedef typename graph_traits::vertex_descriptor vertex; williamr@2: typedef typename graph_traits::vertices_size_type size_type; williamr@2: typedef typename graph_traits::vertex_descriptor williamr@2: cg_vertex; williamr@2: std::vector to_cg_vertex(components.size()); williamr@2: for (size_type s = 0; s < components.size(); ++s) williamr@2: to_cg_vertex[s] = add_vertex(cg); williamr@2: williamr@2: for (size_type si = 0; si < components.size(); ++si) { williamr@2: cg_vertex s = to_cg_vertex[si]; williamr@2: std::vector adj; williamr@2: for (size_type i = 0; i < components[si].size(); ++i) { williamr@2: vertex u = components[s][i]; williamr@2: typename graph_traits::adjacency_iterator v, v_end; williamr@2: for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) { williamr@2: cg_vertex t = to_cg_vertex[component_number[*v]]; williamr@2: if (s != t) // Avoid loops in the condensation graph williamr@2: adj.push_back(t); williamr@2: } williamr@2: } williamr@2: std::sort(adj.begin(), adj.end()); williamr@2: if (! adj.empty()) { williamr@2: size_type i = 0; williamr@2: cg_vertex t = adj[i]; williamr@2: typename graph_traits::edge_descriptor e; williamr@2: bool inserted; williamr@2: tie(e, inserted) = add_edge(s, t, cg); williamr@2: put(edge_mult_map, e, 1); williamr@2: ++i; williamr@2: while (i < adj.size()) { williamr@2: if (adj[i] == t) williamr@2: put(edge_mult_map, e, get(edge_mult_map, e) + 1); williamr@2: else { williamr@2: t = adj[i]; williamr@2: tie(e, inserted) = add_edge(s, t, cg); williamr@2: put(edge_mult_map, e, 1); williamr@2: } williamr@2: ++i; williamr@2: } williamr@2: } williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void create_condensation_graph(const Graph& g, williamr@2: const ComponentLists& components, williamr@2: ComponentNumberMap component_number, williamr@2: CondensationGraph& cg) williamr@2: { williamr@2: create_condensation_graph(g, components, component_number, cg, williamr@2: dummy_property_map()); williamr@2: } williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP