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