Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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.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 (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         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             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