1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/create_condensation_graph.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,83 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 2002 Indiana University.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +
    1.13 +#ifndef BOOST_CREATE_CONDENSATION_GRAPH_HPP
    1.14 +#define BOOST_CREATE_CONDENSATION_GRAPH_HPP
    1.15 +
    1.16 +#include <boost/graph/graph_traits.hpp>
    1.17 +#include <boost/property_map.hpp>
    1.18 +
    1.19 +namespace boost {
    1.20 +
    1.21 +  template <typename Graph, typename ComponentLists, 
    1.22 +    typename ComponentNumberMap,
    1.23 +    typename CondensationGraph, typename EdgeMultiplicityMap>
    1.24 +  void create_condensation_graph(const Graph& g, 
    1.25 +                                 const ComponentLists& components,
    1.26 +                                 ComponentNumberMap component_number,
    1.27 +                                 CondensationGraph& cg,
    1.28 +                                 EdgeMultiplicityMap edge_mult_map)
    1.29 +  {
    1.30 +    typedef typename graph_traits<Graph>::vertex_descriptor vertex;
    1.31 +    typedef typename graph_traits<Graph>::vertices_size_type size_type;
    1.32 +    typedef typename graph_traits<CondensationGraph>::vertex_descriptor 
    1.33 +      cg_vertex;
    1.34 +    std::vector<cg_vertex> to_cg_vertex(components.size());
    1.35 +    for (size_type s = 0; s < components.size(); ++s)
    1.36 +      to_cg_vertex[s] = add_vertex(cg);
    1.37 +
    1.38 +    for (size_type si = 0; si < components.size(); ++si) {
    1.39 +      cg_vertex s = to_cg_vertex[si];
    1.40 +      std::vector<cg_vertex> adj;
    1.41 +      for (size_type i = 0; i < components[si].size(); ++i) {
    1.42 +        vertex u = components[s][i];
    1.43 +        typename graph_traits<Graph>::adjacency_iterator v, v_end;
    1.44 +        for (tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
    1.45 +          cg_vertex t = to_cg_vertex[component_number[*v]];
    1.46 +          if (s != t) // Avoid loops in the condensation graph
    1.47 +            adj.push_back(t);
    1.48 +        }
    1.49 +      }
    1.50 +      std::sort(adj.begin(), adj.end());
    1.51 +      if (! adj.empty()) {
    1.52 +        size_type i = 0;
    1.53 +        cg_vertex t = adj[i];
    1.54 +        typename graph_traits<CondensationGraph>::edge_descriptor e;
    1.55 +        bool inserted;
    1.56 +        tie(e, inserted) = add_edge(s, t, cg);
    1.57 +        put(edge_mult_map, e, 1);
    1.58 +        ++i;
    1.59 +        while (i < adj.size()) {
    1.60 +          if (adj[i] == t)
    1.61 +            put(edge_mult_map, e, get(edge_mult_map, e) + 1);
    1.62 +          else {
    1.63 +            t = adj[i];
    1.64 +            tie(e, inserted) = add_edge(s, t, cg);
    1.65 +            put(edge_mult_map, e, 1);
    1.66 +          }
    1.67 +          ++i;
    1.68 +        }
    1.69 +      }
    1.70 +    }
    1.71 +  }
    1.72 +  
    1.73 +  template <typename Graph, typename ComponentLists, 
    1.74 +    typename ComponentNumberMap, typename CondensationGraph>
    1.75 +  void create_condensation_graph(const Graph& g, 
    1.76 +                                 const ComponentLists& components,
    1.77 +                                 ComponentNumberMap component_number,
    1.78 +                                 CondensationGraph& cg)
    1.79 +  {
    1.80 +    create_condensation_graph(g, components, component_number, cg, 
    1.81 +                              dummy_property_map());
    1.82 +  }
    1.83 +
    1.84 +} // namespace boost
    1.85 +
    1.86 +#endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP