diff options
Diffstat (limited to 'boost/graph')
22 files changed, 198 insertions, 117 deletions
diff --git a/boost/graph/astar_search.hpp b/boost/graph/astar_search.hpp index 2d4f264fef..02f4b1cb49 100644 --- a/boost/graph/astar_search.hpp +++ b/boost/graph/astar_search.hpp @@ -328,7 +328,6 @@ inline void astar_search_no_init_tree(const VertexListGraph& g, BOOST_THROW_EXCEPTION(negative_edge()); bool decreased = relax(e, g, weight, predecessor, distance, combine, compare); - combine(get(distance, v), e_weight); if (decreased) { vis.edge_relaxed(e, g); diff --git a/boost/graph/boykov_kolmogorov_max_flow.hpp b/boost/graph/boykov_kolmogorov_max_flow.hpp index 7c74f338f9..eb0189eb5f 100644 --- a/boost/graph/boykov_kolmogorov_max_flow.hpp +++ b/boost/graph/boykov_kolmogorov_max_flow.hpp @@ -977,7 +977,7 @@ boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap, } /** - * non-named-parameter version, given capacity, residucal_capacity, + * non-named-parameter version, given capacity, residual_capacity, * reverse_edges, and an index map. */ template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, @@ -1029,8 +1029,7 @@ boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap, * named-parameter version, some given */ template < class Graph, class P, class T, class R > -typename property_traits< - typename property_map< Graph, edge_capacity_t >::const_type >::value_type +typename detail::edge_capacity_value< Graph, P, T, R >::type boykov_kolmogorov_max_flow(Graph& g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink, diff --git a/boost/graph/detail/adjacency_list.hpp b/boost/graph/detail/adjacency_list.hpp index c1a2ada237..7fb2c49361 100644 --- a/boost/graph/detail/adjacency_list.hpp +++ b/boost/graph/detail/adjacency_list.hpp @@ -2069,15 +2069,20 @@ namespace detail inline void reindex_edge_list( EdgeList& el, vertex_descriptor u, boost::disallow_parallel_edge_tag) { - for (typename EdgeList::iterator ei = el.begin(); ei != el.end(); ++ei) + typename EdgeList::iterator ei = el.begin(), e_end = el.end(); + while (ei != e_end) { if (ei->get_target() > u) { typename EdgeList::value_type ce = *ei; + ++ei; el.erase(ce); --ce.get_target(); el.insert(ce); } + else { + ++ei; + } } } } // namespace detail diff --git a/boost/graph/detail/d_ary_heap.hpp b/boost/graph/detail/d_ary_heap.hpp index e7dc4b91f7..7c423dcac2 100644 --- a/boost/graph/detail/d_ary_heap.hpp +++ b/boost/graph/detail/d_ary_heap.hpp @@ -204,10 +204,10 @@ private: // Get the parent of a given node in the heap static size_type parent(size_type index) { return (index - 1) / Arity; } - // Get the child_idx'th child of a given node; 0 <= child_idx < Arity - static size_type child(size_type index, std::size_t child_idx) + // Get the first child of a given node + static size_type first_child(size_type index) { - return index * Arity + child_idx + 1; + return index * Arity + 1; } // Swap two elements in the heap by index, updating index_in_heap @@ -304,7 +304,7 @@ private: Value* data_ptr = &data[0]; for (;;) { - size_type first_child_index = child(index, 0); + size_type first_child_index = first_child(index); if (first_child_index >= heap_size) break; /* No children */ Value* child_base_ptr = data_ptr + first_child_index; diff --git a/boost/graph/detail/geodesic.hpp b/boost/graph/detail/geodesic.hpp index 40b3cefc4a..84805fb647 100644 --- a/boost/graph/detail/geodesic.hpp +++ b/boost/graph/detail/geodesic.hpp @@ -55,8 +55,9 @@ namespace detail (ReadablePropertyMapConcept< DistanceMap, Vertex >)); BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >)); typedef numeric_values< Distance > DistanceNumbers; - BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance, - Distance, Distance >)); +// NOTE: Disabled until this concept assert is fixed in Boost.ConceptCheck. +// BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance, +// Distance, Distance >)); // If there's ever an infinite distance, then we simply return // infinity. Note that this /will/ include the a non-zero diff --git a/boost/graph/distributed/adjacency_list.hpp b/boost/graph/distributed/adjacency_list.hpp index e22276aebb..1d7d20b506 100644 --- a/boost/graph/distributed/adjacency_list.hpp +++ b/boost/graph/distributed/adjacency_list.hpp @@ -23,6 +23,7 @@ #include <boost/graph/distributed/concepts.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/adjacency_iterator.hpp> #include <boost/property_map/parallel/distributed_property_map.hpp> #include <boost/property_map/parallel/local_property_map.hpp> diff --git a/boost/graph/distributed/boman_et_al_graph_coloring.hpp b/boost/graph/distributed/boman_et_al_graph_coloring.hpp index 4bdd9c2a32..e7350d7f02 100644 --- a/boost/graph/distributed/boman_et_al_graph_coloring.hpp +++ b/boost/graph/distributed/boman_et_al_graph_coloring.hpp @@ -16,6 +16,7 @@ #include <boost/graph/graph_traits.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/parallel/process_group.hpp> #include <functional> #include <vector> diff --git a/boost/graph/distributed/connected_components.hpp b/boost/graph/distributed/connected_components.hpp index 3650efb451..01c940015e 100644 --- a/boost/graph/distributed/connected_components.hpp +++ b/boost/graph/distributed/connected_components.hpp @@ -17,6 +17,7 @@ #include <boost/detail/is_sorted.hpp> #include <boost/assert.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/property_map/parallel/caching_property_map.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <boost/pending/indirect_cmp.hpp> diff --git a/boost/graph/distributed/connected_components_parallel_search.hpp b/boost/graph/distributed/connected_components_parallel_search.hpp index f3ebf05688..0dfd546ebf 100644 --- a/boost/graph/distributed/connected_components_parallel_search.hpp +++ b/boost/graph/distributed/connected_components_parallel_search.hpp @@ -16,6 +16,7 @@ #include <boost/assert.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/graph/graph_traits.hpp> diff --git a/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp b/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp index 0e7c1cf23b..07a8074259 100644 --- a/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp +++ b/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp @@ -29,6 +29,7 @@ #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <vector> #include <boost/graph/parallel/algorithm.hpp> #include <boost/limits.hpp> diff --git a/boost/graph/distributed/delta_stepping_shortest_paths.hpp b/boost/graph/distributed/delta_stepping_shortest_paths.hpp index 97a04e6916..07ad50e84e 100644 --- a/boost/graph/distributed/delta_stepping_shortest_paths.hpp +++ b/boost/graph/distributed/delta_stepping_shortest_paths.hpp @@ -46,6 +46,7 @@ #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/iteration_macros.hpp> #include <limits> #include <list> diff --git a/boost/graph/distributed/depth_first_search.hpp b/boost/graph/distributed/depth_first_search.hpp index 032902f4f1..49df5b3a56 100644 --- a/boost/graph/distributed/depth_first_search.hpp +++ b/boost/graph/distributed/depth_first_search.hpp @@ -15,6 +15,7 @@ #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/overloading.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/distributed/concepts.hpp> diff --git a/boost/graph/distributed/detail/dijkstra_shortest_paths.hpp b/boost/graph/distributed/detail/dijkstra_shortest_paths.hpp index 0597689167..cd955f5b24 100644 --- a/boost/graph/distributed/detail/dijkstra_shortest_paths.hpp +++ b/boost/graph/distributed/detail/dijkstra_shortest_paths.hpp @@ -14,6 +14,7 @@ #endif #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> namespace boost { namespace graph { namespace distributed { namespace detail { diff --git a/boost/graph/distributed/detail/mpi_process_group.ipp b/boost/graph/distributed/detail/mpi_process_group.ipp index 94050da9c2..cdd5c972c4 100644 --- a/boost/graph/distributed/detail/mpi_process_group.ipp +++ b/boost/graph/distributed/detail/mpi_process_group.ipp @@ -28,6 +28,7 @@ #include <queue> #include <stack> #include <list> +#include <map> #include <boost/graph/distributed/detail/tag_allocator.hpp> #include <stdio.h> diff --git a/boost/graph/distributed/graphviz.hpp b/boost/graph/distributed/graphviz.hpp index fa843fd70c..45641f0340 100644 --- a/boost/graph/distributed/graphviz.hpp +++ b/boost/graph/distributed/graphviz.hpp @@ -16,6 +16,7 @@ #include <boost/graph/graph_traits.hpp> #include <boost/graph/distributed/concepts.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/graphviz.hpp> #include <boost/type_traits/is_base_and_derived.hpp> #include <boost/type_traits/is_same.hpp> diff --git a/boost/graph/distributed/st_connected.hpp b/boost/graph/distributed/st_connected.hpp index b007442615..2fcfd1016e 100644 --- a/boost/graph/distributed/st_connected.hpp +++ b/boost/graph/distributed/st_connected.hpp @@ -20,6 +20,7 @@ #include <boost/graph/iteration_macros.hpp> #include <boost/graph/parallel/container_traits.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <utility> #include <boost/optional.hpp> diff --git a/boost/graph/distributed/strong_components.hpp b/boost/graph/distributed/strong_components.hpp index 5c9307f0ce..139f39d5d5 100644 --- a/boost/graph/distributed/strong_components.hpp +++ b/boost/graph/distributed/strong_components.hpp @@ -18,6 +18,7 @@ #include <boost/assert.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/property_map/parallel/distributed_property_map.hpp> #include <boost/property_map/parallel/caching_property_map.hpp> #include <boost/graph/parallel/algorithm.hpp> diff --git a/boost/graph/distributed/vertex_list_adaptor.hpp b/boost/graph/distributed/vertex_list_adaptor.hpp index 8928479a7a..42e547b877 100644 --- a/boost/graph/distributed/vertex_list_adaptor.hpp +++ b/boost/graph/distributed/vertex_list_adaptor.hpp @@ -18,6 +18,7 @@ #include <vector> #include <boost/shared_ptr.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <boost/graph/parallel/container_traits.hpp> #include <boost/property_map/vector_property_map.hpp> diff --git a/boost/graph/geodesic_distance.hpp b/boost/graph/geodesic_distance.hpp index 0da9666b5d..5675406a08 100644 --- a/boost/graph/geodesic_distance.hpp +++ b/boost/graph/geodesic_distance.hpp @@ -27,8 +27,9 @@ struct mean_geodesic_measure BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >)); BOOST_CONCEPT_ASSERT((NumericValueConcept< DistanceType >)); BOOST_CONCEPT_ASSERT((NumericValueConcept< ResultType >)); - BOOST_CONCEPT_ASSERT((AdaptableBinaryFunctionConcept< Divides, - ResultType, ResultType, ResultType >)); +// NOTE: Disabled until this concept assert is fixed in Boost.ConceptCheck. +// BOOST_CONCEPT_ASSERT((AdaptableBinaryFunctionConcept< Divides, +// ResultType, ResultType, ResultType >)); return (d == base_type::infinite_distance()) ? base_type::infinite_result() diff --git a/boost/graph/parallel/detail/property_holders.hpp b/boost/graph/parallel/detail/property_holders.hpp index bbdbeba6c9..48b044aa40 100644 --- a/boost/graph/parallel/detail/property_holders.hpp +++ b/boost/graph/parallel/detail/property_holders.hpp @@ -15,6 +15,7 @@ #include <boost/mpi/datatype.hpp> #include <boost/property_map/property_map.hpp> +#include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/serialization/base_object.hpp> #include <boost/mpl/and.hpp> #include <boost/graph/parallel/detail/untracked_pair.hpp> diff --git a/boost/graph/stoer_wagner_min_cut.hpp b/boost/graph/stoer_wagner_min_cut.hpp index 0ae15fbfc0..33ef6e9693 100644 --- a/boost/graph/stoer_wagner_min_cut.hpp +++ b/boost/graph/stoer_wagner_min_cut.hpp @@ -29,94 +29,130 @@ namespace boost namespace detail { - template < typename ParityMap, typename WeightMap, typename IndexMap > - class mas_min_cut_visitor : public boost::default_mas_visitor + /** + * \brief Performs a phase of the Stoer-Wagner min-cut algorithm + * + * Performs a phase of the Stoer-Wagner min-cut algorithm. + * + * As described by Stoer & Wagner (1997), a phase is simply a maximum + * adjacency search (also called a maximum cardinality search), which + * results in the selection of two vertices \em s and \em t, and, as a side + * product, a minimum <em>s</em>-<em>t</em> cut of the input graph. Here, + * the input graph is basically \p g, but some vertices are virtually + * assigned to others as a way of viewing \p g as a graph with some sets of + * vertices merged together. + * + * This implementation is a translation of pseudocode by Professor Uri + * Zwick, School of Computer Science, Tel Aviv University. + * + * \pre \p g is a connected, undirected graph + * \param[in] g the input graph + * \param[in] assignments a read/write property map from each vertex to the + * vertex that it is assigned to + * \param[in] assignedVertices a list of vertices that are assigned to + * others + * \param[in] weights a readable property map from each edge to its + * weight (a non-negative value) + * \param[out] pq a keyed, updatable max-priority queue + * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and + * "<em>t</em>" of the minimum <em>s</em>-<em>t</em> cut and the + * cut weight \em w of the minimum <em>s</em>-<em>t</em> cut. + * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf + * + * \author Daniel Trebbien + * \date 2010-09-11 + */ + template < class UndirectedGraph, class VertexAssignmentMap, + class WeightMap, class KeyedUpdatablePriorityQueue > + boost::tuple< + typename boost::graph_traits< UndirectedGraph >::vertex_descriptor, + typename boost::graph_traits< UndirectedGraph >::vertex_descriptor, + typename boost::property_traits< WeightMap >::value_type > + stoer_wagner_phase(const UndirectedGraph& g, + VertexAssignmentMap assignments, + const std::set< typename boost::graph_traits< + UndirectedGraph >::vertex_descriptor >& assignedVertices, + WeightMap weights, KeyedUpdatablePriorityQueue& pq) { - typedef one_bit_color_map< IndexMap > InternalParityMap; + typedef + typename boost::graph_traits< UndirectedGraph >::vertex_descriptor + vertex_descriptor; typedef typename boost::property_traits< WeightMap >::value_type weight_type; - public: - template < typename Graph > - mas_min_cut_visitor(const Graph& g, ParityMap parity, - weight_type& cutweight, const WeightMap& weight_map, - IndexMap index_map) - : m_bestParity(parity) - , m_parity(make_one_bit_color_map(num_vertices(g), index_map)) - , m_bestWeight(cutweight) - , m_cutweight(0) - , m_visited(0) - , m_weightMap(weight_map) - { - // set here since the init list sets the reference - m_bestWeight = (std::numeric_limits< weight_type >::max)(); - } - - template < typename Vertex, typename Graph > - void initialize_vertex(Vertex u, const Graph& g) - { - typedef typename boost::property_traits< ParityMap >::value_type - parity_type; - typedef - typename boost::property_traits< InternalParityMap >::value_type - internal_parity_type; - - put(m_parity, u, internal_parity_type(0)); - put(m_bestParity, u, parity_type(0)); - } + BOOST_ASSERT(pq.empty()); + typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys(); - template < typename Edge, typename Graph > - void examine_edge(Edge e, const Graph& g) + BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { - weight_type w = get(m_weightMap, e); + if (v == get(assignments, v)) + { // foreach u \in V do + put(keys, v, weight_type(0)); - // if the target of e is already marked then decrease cutweight - // otherwise, increase it - if (get(m_parity, boost::target(e, g))) - { - m_cutweight -= w; - } - else - { - m_cutweight += w; + pq.push(v); } } - template < typename Vertex, typename Graph > - void finish_vertex(Vertex u, const Graph& g) - { - typedef - typename boost::property_traits< InternalParityMap >::value_type - internal_parity_type; + BOOST_ASSERT(pq.size() >= 2); - ++m_visited; - put(m_parity, u, internal_parity_type(1)); + vertex_descriptor s + = boost::graph_traits< UndirectedGraph >::null_vertex(); + vertex_descriptor t + = boost::graph_traits< UndirectedGraph >::null_vertex(); + weight_type w; + while (!pq.empty()) + { // while PQ \neq {} do + const vertex_descriptor u = pq.top(); // u = extractmax(PQ) + w = get(keys, u); + pq.pop(); + + s = t; + t = u; + + BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) + { // foreach (u, v) \in E do + const vertex_descriptor v = get(assignments, target(e, g)); + + if (pq.contains(v)) + { // if v \in PQ then + put(keys, v, + get(keys, v) + + get(weights, + e)); // increasekey(PQ, v, wA(v) + w(u, v)) + pq.update(v); + } + } - if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) + typename std::set< vertex_descriptor >::const_iterator + assignedVertexIt, + assignedVertexEnd = assignedVertices.end(); + for (assignedVertexIt = assignedVertices.begin(); + assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) { - m_bestWeight = m_cutweight; - BGL_FORALL_VERTICES_T(i, g, Graph) + const vertex_descriptor uPrime = *assignedVertexIt; + + if (get(assignments, uPrime) == u) { - put(m_bestParity, i, get(m_parity, i)); + BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph) + { // foreach (u, v) \in E do + const vertex_descriptor v + = get(assignments, target(e, g)); + + if (pq.contains(v)) + { // if v \in PQ then + put(keys, v, + get(keys, v) + + get(weights, e)); // increasekey(PQ, v, + // wA(v) + w(u, v)) + pq.update(v); + } + } } } } - inline void clear() - { - m_bestWeight = (std::numeric_limits< weight_type >::max)(); - m_visited = 0; - m_cutweight = 0; - } - - private: - ParityMap m_bestParity; - InternalParityMap m_parity; - weight_type& m_bestWeight; - weight_type m_cutweight; - unsigned m_visited; - const WeightMap& m_weightMap; - }; + return boost::make_tuple(s, t, w); + } /** * \brief Computes a min-cut of the input graph @@ -156,44 +192,71 @@ namespace detail vertex_descriptor; typedef typename boost::property_traits< WeightMap >::value_type weight_type; + typedef + typename boost::graph_traits< UndirectedGraph >::vertices_size_type + vertices_size_type; + typedef typename boost::property_traits< ParityMap >::value_type + parity_type; - typename graph_traits< UndirectedGraph >::vertex_iterator u_iter, u_end; + vertices_size_type n = num_vertices(g); - weight_type bestW = (std::numeric_limits< weight_type >::max)(); - weight_type bestThisTime = (std::numeric_limits< weight_type >::max)(); - vertex_descriptor bestStart - = boost::graph_traits< UndirectedGraph >::null_vertex(); + std::set< vertex_descriptor > assignedVertices; + + // initialize `assignments` (all vertices are initially assigned to + // themselves) + BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { put(assignments, v, v); } - detail::mas_min_cut_visitor< ParityMap, WeightMap, IndexMap > vis( - g, parities, bestThisTime, weights, index_map); + vertex_descriptor s, t; + weight_type bestW; - // for each node in the graph, - for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) + boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase( + g, assignments, assignedVertices, weights, pq); + BOOST_ASSERT(s != t); + BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { - // run the MAS and find the min cut - vis.clear(); - boost::maximum_adjacency_search(g, - boost::weight_map(weights) - .visitor(vis) - .root_vertex(*u_iter) - .vertex_assignment_map(assignments) - .max_priority_queue(pq)); - if (bestThisTime < bestW) + put(parities, v, parity_type(v == t ? 1 : 0)); + } + put(assignments, t, s); + assignedVertices.insert(t); + --n; + + for (; n >= 2; --n) + { + weight_type w; + boost::tie(s, t, w) = boost::detail::stoer_wagner_phase( + g, assignments, assignedVertices, weights, pq); + BOOST_ASSERT(s != t); + + if (w < bestW) + { + BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) + { + put(parities, v, + parity_type(get(assignments, v) == t ? 1 : 0)); + + if (get(assignments, v) + == t) // all vertices that were assigned to t are now + // assigned to s + put(assignments, v, s); + } + + bestW = w; + } + else { - bestW = bestThisTime; - bestStart = *u_iter; + BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) + { + if (get(assignments, v) + == t) // all vertices that were assigned to t are now + // assigned to s + put(assignments, v, s); + } } + put(assignments, t, s); + assignedVertices.insert(t); } - // Run one more time, starting from the best start location, to - // ensure the visitor has the best values. - vis.clear(); - boost::maximum_adjacency_search(g, - boost::vertex_assignment_map(assignments) - .weight_map(weights) - .visitor(vis) - .root_vertex(bestStart) - .max_priority_queue(pq)); + BOOST_ASSERT(pq.empty()); return bestW; } diff --git a/boost/graph/transitive_closure.hpp b/boost/graph/transitive_closure.hpp index cac02ff916..fa8a7cd9e7 100644 --- a/boost/graph/transitive_closure.hpp +++ b/boost/graph/transitive_closure.hpp @@ -82,7 +82,7 @@ void transitive_closure(const Graph& g, GraphTC& tc, iterator_property_map< cg_vertex*, VertexIndexMap, cg_vertex, cg_vertex& > component_number(&component_number_vec[0], index_map); - int num_scc + const cg_vertex num_scc = strong_components(g, component_number, vertex_index_map(index_map)); std::vector< std::vector< vertex > > components; @@ -107,12 +107,11 @@ void transitive_closure(const Graph& g, GraphTC& tc, } } std::sort(adj.begin(), adj.end()); - typename std::vector< cg_vertex >::iterator di + const typename std::vector< cg_vertex >::iterator di = std::unique(adj.begin(), adj.end()); - if (di != adj.end()) - adj.erase(di, adj.end()); + for (typename std::vector< cg_vertex >::const_iterator i = adj.begin(); - i != adj.end(); ++i) + i != di; ++i) { add_edge(s, *i, CG); } |