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