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