]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |