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