|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r84641 - in branches/release: boost/graph boost/graph/detail libs/graph/src
From: jewillco_at_[hidden]
Date: 2013-06-04 16:53:20
Author: jewillco
Date: 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
New Revision: 84641
URL: http://svn.boost.org/trac/boost/changeset/84641
Log:
Merged more Boost.Graph bug fixes from trunk
Properties modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp (contents, props changed)
branches/release/boost/graph/detail/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp (contents, props changed)
branches/release/boost/graph/detail/histogram_sort.hpp (contents, props changed)
branches/release/boost/graph/max_cardinality_matching.hpp (contents, props changed)
branches/release/boost/graph/maximum_adjacency_search.hpp (contents, props changed)
branches/release/boost/graph/stoer_wagner_min_cut.hpp (contents, props changed)
branches/release/libs/graph/src/read_graphviz_new.cpp (contents, props changed)
Text files modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 6 ------
branches/release/boost/graph/detail/adjacency_list.hpp | 4 ----
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp | 4 ----
branches/release/boost/graph/detail/histogram_sort.hpp | 20 ++++++++++----------
branches/release/boost/graph/max_cardinality_matching.hpp | 29 +++++++++++++++++++++++------
branches/release/boost/graph/maximum_adjacency_search.hpp | 2 +-
branches/release/boost/graph/stoer_wagner_min_cut.hpp | 6 +++---
branches/release/libs/graph/src/read_graphviz_new.cpp | 1 -
8 files changed, 37 insertions(+), 35 deletions(-)
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -642,8 +642,6 @@
const GlobalToLocal& global_to_local) {
typedef compressed_sparse_row_graph Graph;
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
- typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
edge_vector_t new_edges(first, last);
if (new_edges.empty()) return;
@@ -666,8 +664,6 @@
const GlobalToLocal& global_to_local) {
typedef compressed_sparse_row_graph Graph;
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
- typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
typedef std::pair<vertex_t, vertex_t> vertex_pair;
typedef std::vector<
boost::tuple<vertex_pair,
@@ -1164,7 +1160,6 @@
typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
{
- typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::edge_descriptor ed;
typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
@@ -1368,7 +1363,6 @@
typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k,
typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::type val) {
typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
- typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm;
lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::lookup(get(all_tag(), g, k), tag) = val;
}
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp (original)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -635,7 +635,6 @@
directed_graph_helper<Config>& g_)
{
typedef typename Config::graph_type graph_type;
- typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
g.out_edge_list(u).clear();
// clear() should be a req of Sequence and AssociativeContainer,
@@ -782,7 +781,6 @@
typedef typename Graph::global_edgelist_selector EdgeListS;
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
- typedef typename EdgeList::value_type StoredEdge;
typename EdgeList::iterator i = el.begin(), end = el.end();
for (; i != end; ++i) {
if ((*i).get_target() == v) {
@@ -987,7 +985,6 @@
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
typedef typename Config::graph_type graph_type;
- typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
while (true) {
typename Config::out_edge_iterator ei, ei_end;
@@ -1589,7 +1586,6 @@
typedef typename Config::graph_type Graph;
typedef typename Config::StoredEdge StoredEdge;
const Graph& cg = static_cast<const Graph&>(g_);
- typedef typename Config::out_edge_iterator out_edge_iterator;
const typename Config::OutEdgeList& el = cg.out_edge_list(u);
typename Config::OutEdgeList::const_iterator it = graph_detail::
find(el, StoredEdge(v));
Modified: branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp (original)
+++ branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -218,8 +218,6 @@
// the user has supplied the number of edges.
edges_size_type numedges = numedges_or_zero;
if (numedges == 0) {
- typedef typename std::iterator_traits<InputIterator>::iterator_category
- category;
numedges = boost::graph::detail::reserve_count_for_single_pass(edge_begin, edge_end);
}
m_column.clear();
@@ -313,7 +311,6 @@
inherited_edge_properties::resize(numedges);
EdgeIndex current_edge = 0;
typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
- typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;
typedef typename boost::graph_traits<Graph>::out_edge_iterator
g_out_edge_iter;
@@ -347,7 +344,6 @@
// Flip sequence
BidirectionalIterator first(last_sorted);
BidirectionalIterator last(first_sorted);
- typedef Vertex vertex_t;
typedef Vertex vertex_num;
typedef EdgeIndex edge_num;
edge_num new_edge_count = std::distance(first, last);
Modified: branches/release/boost/graph/detail/histogram_sort.hpp
==============================================================================
--- branches/release/boost/graph/detail/histogram_sort.hpp (original)
+++ branches/release/boost/graph/detail/histogram_sort.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -54,7 +54,6 @@
KeyFilter key_filter,
KeyTransform key_transform) {
- typedef VerticesSize vertices_size_type;
typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
// Put the degree of each vertex v into m_rowstart[v + 1]
@@ -69,7 +68,7 @@
// m_rowstart
EdgeIndex start_of_this_row = 0;
starts[0] = start_of_this_row;
- for (vertices_size_type i = 1; i < numkeys + 1; ++i) {
+ for (VerticesSize i = 1; i < numkeys + 1; ++i) {
start_of_this_row += starts[i];
starts[i] = start_of_this_row;
}
@@ -88,7 +87,6 @@
KeyFilter key_filter,
KeyTransform key_transform) {
- typedef NumKeys vertices_size_type;
typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
// Histogram sort the edges by their source vertices, putting the targets
@@ -99,7 +97,7 @@
Value1InputIter v1i = values1_begin;
for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i) {
if (key_filter(*i)) {
- vertices_size_type source = key_transform(*i);
+ NumKeys source = key_transform(*i);
BOOST_ASSERT (source < numkeys);
EdgeIndex insert_pos = current_insert_positions[source];
++current_insert_positions[source];
@@ -126,7 +124,6 @@
KeyFilter key_filter,
KeyTransform key_transform) {
- typedef NumKeys vertices_size_type;
typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
// Histogram sort the edges by their source vertices, putting the targets
@@ -138,7 +135,7 @@
Value2InputIter v2i = values2_begin;
for (KeyIterator i = key_begin; i != key_end; ++i, ++v1i, ++v2i) {
if (key_filter(*i)) {
- vertices_size_type source = key_transform(*i);
+ NumKeys source = key_transform(*i);
BOOST_ASSERT (source < numkeys);
EdgeIndex insert_pos = current_insert_positions[source];
++current_insert_positions[source];
@@ -159,7 +156,6 @@
Value1Iter values1,
KeyTransform key_transform) {
- typedef NumKeys vertices_size_type;
typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
// 1. Copy m_rowstart (except last element) to get insert positions
@@ -194,7 +190,6 @@
Value2Iter values2,
KeyTransform key_transform) {
- typedef NumKeys vertices_size_type;
typedef typename std::iterator_traits<RowstartIterator>::value_type EdgeIndex;
// 1. Copy m_rowstart (except last element) to get insert positions
@@ -274,16 +269,21 @@
}
}
+// The versions of operator()() here can't return by reference because the
+// actual type passed in may not match Pair, in which case the reference
+// parameter is bound to a temporary that could end up dangling after the
+// operator returns.
+
template <typename Pair>
struct project1st {
typedef typename Pair::first_type result_type;
- const result_type& operator()(const Pair& p) const {return p.first;}
+ result_type operator()(const Pair& p) const {return p.first;}
};
template <typename Pair>
struct project2nd {
typedef typename Pair::second_type result_type;
- const result_type& operator()(const Pair& p) const {return p.second;}
+ result_type operator()(const Pair& p) const {return p.second;}
};
}
Modified: branches/release/boost/graph/max_cardinality_matching.hpp
==============================================================================
--- branches/release/boost/graph/max_cardinality_matching.hpp (original)
+++ branches/release/boost/graph/max_cardinality_matching.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -219,7 +219,12 @@
vertex_state[u] = graph::detail::V_EVEN;
out_edge_iterator_t ei, ei_end;
for(boost::tie(ei,ei_end) = out_edges(u,g); ei != ei_end; ++ei)
- even_edges.push_back( *ei );
+ {
+ if (target(*ei,g) != u)
+ {
+ even_edges.push_back( *ei );
+ }
+ }
}
else
vertex_state[u] = graph::detail::V_UNREACHED;
@@ -258,10 +263,16 @@
if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
{
vertex_state[w_prime] = graph::detail::V_ODD;
- vertex_state[mate[w_prime]] = graph::detail::V_EVEN;
+ vertex_descriptor_t w_prime_mate = mate[w_prime];
+ vertex_state[w_prime_mate] = graph::detail::V_EVEN;
out_edge_iterator_t ei, ei_end;
- for( boost::tie(ei,ei_end) = out_edges(mate[w_prime], g); ei != ei_end; ++ei)
- even_edges.push_back(*ei);
+ for( boost::tie(ei,ei_end) = out_edges(w_prime_mate, g); ei != ei_end; ++ei)
+ {
+ if (target(*ei,g) != w_prime_mate)
+ {
+ even_edges.push_back(*ei);
+ }
+ }
pred[w_prime] = v;
}
@@ -403,7 +414,12 @@
bridge[v] = the_bridge;
out_edge_iterator_t oei, oei_end;
for(boost::tie(oei, oei_end) = out_edges(v,g); oei != oei_end; ++oei)
- even_edges.push_back(*oei);
+ {
+ if (target(*oei,g) != v)
+ {
+ even_edges.push_back(*oei);
+ }
+ }
}
}
}
@@ -529,7 +545,7 @@
vertex_descriptor_t u = source(e,g);
vertex_descriptor_t v = target(e,g);
- if (get(mate,u) == get(mate,v))
+ if (u != v && get(mate,u) == get(mate,v))
//only way equality can hold is if
// mate[u] == mate[v] == null_vertex
{
@@ -606,6 +622,7 @@
edge_descriptor_t e = *ei;
vertex_descriptor_t u = source(e,g);
vertex_descriptor_t v = target(e,g);
+ if (u == v) continue;
edge_list.push_back(std::make_pair(u,v));
edge_list.push_back(std::make_pair(v,u));
}
Modified: branches/release/boost/graph/maximum_adjacency_search.hpp
==============================================================================
--- branches/release/boost/graph/maximum_adjacency_search.hpp (original)
+++ branches/release/boost/graph/maximum_adjacency_search.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -304,7 +304,7 @@
template <typename ArgPack>
void
- operator() (const Graph& g, const ArgPack arg_pack) const {
+ operator() (const Graph& g, const ArgPack& arg_pack) const {
// call the function that does the dispatching
typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
Modified: branches/release/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- branches/release/boost/graph/stoer_wagner_min_cut.hpp (original)
+++ branches/release/boost/graph/stoer_wagner_min_cut.hpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -36,7 +36,7 @@
mas_min_cut_visitor(const Graph& g,
ParityMap parity,
weight_type& cutweight,
- WeightMap weight_map,
+ const WeightMap& weight_map,
IndexMap index_map)
: m_bestParity(parity),
m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
@@ -140,7 +140,7 @@
weight_type bestW = (std::numeric_limits<weight_type>::max)();
weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
- vertex_descriptor bestStart;
+ vertex_descriptor bestStart = boost::graph_traits<UndirectedGraph>::null_vertex();
detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
vis(g, parities, bestThisTime, weights, index_map);
@@ -213,7 +213,7 @@
typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
typedef typename boost::property_traits<WeightMap>::value_type weight_type;
- typedef typename boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
+ typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
Modified: branches/release/libs/graph/src/read_graphviz_new.cpp
==============================================================================
--- branches/release/libs/graph/src/read_graphviz_new.cpp (original)
+++ branches/release/libs/graph/src/read_graphviz_new.cpp 2013-06-04 16:53:19 EDT (Tue, 04 Jun 2013)
@@ -762,7 +762,6 @@
}
void translate_results_to_graph(const parser_result& r, ::boost::detail::graph::mutate_graph* mg) {
- typedef boost::detail::graph::node_t vertex;
typedef boost::detail::graph::edge_t edge;
for (std::map<node_name, properties>::const_iterator i = r.nodes.begin(); i != r.nodes.end(); ++i) {
// std::cerr << i->first << " " << props_to_string(i->second) << std::endl;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk