File indexing completed on 2025-01-30 09:42:54
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef BOOST_CREATE_CONDENSATION_GRAPH_HPP
0011 #define BOOST_CREATE_CONDENSATION_GRAPH_HPP
0012
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/property_map/property_map.hpp>
0015
0016 namespace boost
0017 {
0018
0019 template < typename Graph, typename ComponentLists, typename ComponentNumberMap,
0020 typename CondensationGraph, typename EdgeMultiplicityMap >
0021 void create_condensation_graph(const Graph& g, const ComponentLists& components,
0022 ComponentNumberMap component_number, CondensationGraph& cg,
0023 EdgeMultiplicityMap edge_mult_map)
0024 {
0025 typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0026 typedef typename graph_traits< Graph >::vertices_size_type size_type;
0027 typedef
0028 typename graph_traits< CondensationGraph >::vertex_descriptor cg_vertex;
0029 std::vector< cg_vertex > to_cg_vertex(components.size());
0030 for (size_type s = 0; s < components.size(); ++s)
0031 to_cg_vertex[s] = add_vertex(cg);
0032
0033 for (size_type si = 0; si < components.size(); ++si)
0034 {
0035 cg_vertex s = to_cg_vertex[si];
0036 std::vector< cg_vertex > adj;
0037 for (size_type i = 0; i < components[si].size(); ++i)
0038 {
0039 vertex u = components[s][i];
0040 typename graph_traits< Graph >::adjacency_iterator v, v_end;
0041 for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end;
0042 ++v)
0043 {
0044 cg_vertex t = to_cg_vertex[component_number[*v]];
0045 if (s != t)
0046 adj.push_back(t);
0047 }
0048 }
0049 std::sort(adj.begin(), adj.end());
0050 if (!adj.empty())
0051 {
0052 size_type i = 0;
0053 cg_vertex t = adj[i];
0054 typename graph_traits< CondensationGraph >::edge_descriptor e;
0055 bool inserted;
0056 boost::tie(e, inserted) = add_edge(s, t, cg);
0057 put(edge_mult_map, e, 1);
0058 ++i;
0059 while (i < adj.size())
0060 {
0061 if (adj[i] == t)
0062 put(edge_mult_map, e, get(edge_mult_map, e) + 1);
0063 else
0064 {
0065 t = adj[i];
0066 boost::tie(e, inserted) = add_edge(s, t, cg);
0067 put(edge_mult_map, e, 1);
0068 }
0069 ++i;
0070 }
0071 }
0072 }
0073 }
0074
0075 template < typename Graph, typename ComponentLists, typename ComponentNumberMap,
0076 typename CondensationGraph >
0077 void create_condensation_graph(const Graph& g, const ComponentLists& components,
0078 ComponentNumberMap component_number, CondensationGraph& cg)
0079 {
0080 create_condensation_graph(
0081 g, components, component_number, cg, dummy_property_map());
0082 }
0083
0084 }
0085
0086 #endif