ceph/src/boost/libs/graph/include/boost/graph/create_condensation_graph.hpp

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #ifndef BOOST_CREATE_CONDENSATION_GRAPH_HPP
  11 #define BOOST_CREATE_CONDENSATION_GRAPH_HPP
  12
  13 #include <boost/graph/graph_traits.hpp>
  14 #include <boost/property_map/property_map.hpp>
  15
  16 namespace boost {
  17
  18   template <typename Graph, typename ComponentLists,
  19     typename ComponentNumberMap,
  20     typename CondensationGraph, typename EdgeMultiplicityMap>
  21   void create_condensation_graph(const Graph& g,
  22                                  const ComponentLists& components,
  23                                  ComponentNumberMap component_number,
  24                                  CondensationGraph& cg,
  25                                  EdgeMultiplicityMap edge_mult_map)
  26   {
  27     typedef typename graph_traits<Graph>::vertex_descriptor vertex;
  28     typedef typename graph_traits<Graph>::vertices_size_type size_type;
  29     typedef typename graph_traits<CondensationGraph>::vertex_descriptor
  30       cg_vertex;
  31     std::vector<cg_vertex> to_cg_vertex(components.size());
  32     for (size_type s = 0; s < components.size(); ++s)
  33       to_cg_vertex[s] = add_vertex(cg);
  34
  35     for (size_type si = 0; si < components.size(); ++si) {
  36       cg_vertex s = to_cg_vertex[si];
  37       std::vector<cg_vertex> adj;
  38       for (size_type i = 0; i < components[si].size(); ++i) {
  39         vertex u = components[s][i];
  40         typename graph_traits<Graph>::adjacency_iterator v, v_end;
  41         for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) {
  42           cg_vertex t = to_cg_vertex[component_number[*v]];
  43           if (s != t) // Avoid loops in the condensation graph
  44             adj.push_back(t);
  45         }
  46       }
  47       std::sort(adj.begin(), adj.end());
  48       if (! adj.empty()) {
  49         size_type i = 0;
  50         cg_vertex t = adj[i];
  51         typename graph_traits<CondensationGraph>::edge_descriptor e;
  52         bool inserted;
  53         boost::tie(e, inserted) = add_edge(s, t, cg);
  54         put(edge_mult_map, e, 1);
  55         ++i;
  56         while (i < adj.size()) {
  57           if (adj[i] == t)
  58             put(edge_mult_map, e, get(edge_mult_map, e) + 1);
  59           else {
  60             t = adj[i];
  61             boost::tie(e, inserted) = add_edge(s, t, cg);
  62             put(edge_mult_map, e, 1);
  63           }
  64           ++i;
  65         }
  66       }
  67     }
  68   }
  69
  70   template <typename Graph, typename ComponentLists,
  71     typename ComponentNumberMap, typename CondensationGraph>
  72   void create_condensation_graph(const Graph& g,
  73                                  const ComponentLists& components,
  74                                  ComponentNumberMap component_number,
  75                                  CondensationGraph& cg)
  76   {
  77     create_condensation_graph(g, components, component_number, cg,
  78                               dummy_property_map());
  79   }
  80
  81 } // namespace boost
  82
  83 #endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP