|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r67705 - in trunk: boost/graph boost/graph/detail libs/graph/src
From: jewillco_at_[hidden]
Date: 2011-01-05 21:08:44
Author: jewillco
Date: 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
New Revision: 67705
URL: http://svn.boost.org/trac/boost/changeset/67705
Log:
Fixed assert inspection issues in sequential BGL
Text files modified:
trunk/boost/graph/adjacency_matrix.hpp | 8 +++---
trunk/boost/graph/boykov_kolmogorov_max_flow.hpp | 48 ++++++++++++++++++++--------------------
trunk/boost/graph/compressed_sparse_row_graph.hpp | 4 +-
trunk/boost/graph/detail/adjacency_list.hpp | 3 +
trunk/boost/graph/detail/compressed_sparse_row_struct.hpp | 8 +++---
trunk/boost/graph/detail/d_ary_heap.hpp | 4 +-
trunk/boost/graph/detail/histogram_sort.hpp | 6 +++-
trunk/boost/graph/dimacs.hpp | 15 ++++++-----
trunk/boost/graph/erdos_renyi_generator.hpp | 6 ++--
trunk/boost/graph/graph_stats.hpp | 3 +
trunk/boost/graph/graph_test.hpp | 2
trunk/boost/graph/gursoy_atun_layout.hpp | 3 +
trunk/boost/graph/kamada_kawai_spring_layout.hpp | 31 ++++++++++++++++++++-----
trunk/boost/graph/loop_erased_random_walk.hpp | 6 ++--
trunk/boost/graph/mesh_graph_generator.hpp | 4 +-
trunk/boost/graph/minimum_degree_ordering.hpp | 4 +-
trunk/boost/graph/one_bit_color_map.hpp | 7 +++--
trunk/boost/graph/properties.hpp | 4 +-
trunk/boost/graph/push_relabel_max_flow.hpp | 8 +++---
trunk/boost/graph/random.hpp | 4 +-
trunk/boost/graph/random_spanning_tree.hpp | 5 ++-
trunk/boost/graph/rmat_graph_generator.hpp | 9 ++++---
trunk/boost/graph/stoer_wagner_min_cut.hpp | 12 +++++-----
trunk/boost/graph/subgraph.hpp | 8 +++---
trunk/boost/graph/two_bit_color_map.hpp | 7 +++--
trunk/libs/graph/src/read_graphviz_new.cpp | 17 +++++++------
26 files changed, 132 insertions(+), 104 deletions(-)
Modified: trunk/boost/graph/adjacency_matrix.hpp
==============================================================================
--- trunk/boost/graph/adjacency_matrix.hpp (original)
+++ trunk/boost/graph/adjacency_matrix.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -14,7 +14,7 @@
#include <boost/config.hpp>
#include <vector>
#include <memory>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/limits.hpp>
#include <boost/iterator.hpp>
#include <boost/graph/graph_traits.hpp>
@@ -982,7 +982,7 @@
inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
// UNDER CONSTRUCTION
- assert(false);
+ BOOST_ASSERT(false);
return *vertices(g).first;
}
@@ -991,7 +991,7 @@
inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
add_vertex(const VP2& /*vp*/, adjacency_matrix<D,VP,EP,GP,A>& g) {
// UNDER CONSTRUCTION
- assert(false);
+ BOOST_ASSERT(false);
return *vertices(g).first;
}
@@ -1001,7 +1001,7 @@
adjacency_matrix<D,VP,EP,GP,A>& /*g*/)
{
// UNDER CONSTRUCTION
- assert(false);
+ BOOST_ASSERT(false);
}
// O(V)
Modified: trunk/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/boykov_kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/boykov_kolmogorov_max_flow.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -33,7 +33,7 @@
#define BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
#include <boost/config.hpp>
-#include <cassert>
+#include <boost/assert.hpp>
#include <vector>
#include <list>
#include <utility>
@@ -126,7 +126,7 @@
edge_iterator ei, e_end;
for(boost::tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
m_res_cap_map[*ei] = m_cap_map[*ei];
- assert(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
+ BOOST_ASSERT(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
}
//init the search trees with the two terminals
set_tree(m_source, tColorTraits::black());
@@ -235,13 +235,13 @@
* target(returnVal, m_g) is the beginning of the path found in the sink-tree
*/
std::pair<edge_descriptor, bool> grow(){
- assert(m_orphans.empty());
+ BOOST_ASSERT(m_orphans.empty());
vertex_descriptor current_node;
while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
- assert(get_tree(current_node) != tColorTraits::gray() &&
- (has_parent(current_node) ||
- current_node == m_source ||
- current_node == m_sink));
+ BOOST_ASSERT(get_tree(current_node) != tColorTraits::gray() &&
+ (has_parent(current_node) ||
+ current_node == m_source ||
+ current_node == m_sink));
if(get_tree(current_node) == tColorTraits::black()){
//source tree growing
@@ -269,7 +269,7 @@
m_time_map[other_node] = m_time_map[current_node];
}
} else{
- assert(get_tree(other_node)==tColorTraits::white());
+ BOOST_ASSERT(get_tree(other_node)==tColorTraits::white());
//kewl, found a path from one to the other search tree, return
// the connecting edge in src->sink dir
return std::make_pair(out_edge, true);
@@ -278,7 +278,7 @@
} //for all out-edges
} //source-tree-growing
else{
- assert(get_tree(current_node) == tColorTraits::white());
+ BOOST_ASSERT(get_tree(current_node) == tColorTraits::white());
out_edge_iterator ei, e_end;
if(current_node != m_last_grow_vertex){
m_last_grow_vertex = current_node;
@@ -302,7 +302,7 @@
m_time_map[other_node] = m_time_map[current_node];
}
} else{
- assert(get_tree(other_node)==tColorTraits::black());
+ BOOST_ASSERT(get_tree(other_node)==tColorTraits::black());
//kewl, found a path from one to the other search tree,
// return the connecting edge in src->sink dir
return std::make_pair(in_edge, true);
@@ -332,16 +332,16 @@
* and so we process the nearest verts to the terminals first
*/
void augment(edge_descriptor e) {
- assert(get_tree(target(e, m_g)) == tColorTraits::white());
- assert(get_tree(source(e, m_g)) == tColorTraits::black());
- assert(m_orphans.empty());
+ BOOST_ASSERT(get_tree(target(e, m_g)) == tColorTraits::white());
+ BOOST_ASSERT(get_tree(source(e, m_g)) == tColorTraits::black());
+ BOOST_ASSERT(m_orphans.empty());
const tEdgeVal bottleneck = find_bottleneck(e);
//now we push the found flow through the path
//for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
//now process the connecting edge
m_res_cap_map[e] -= bottleneck;
- assert(m_res_cap_map[e] >= 0);
+ BOOST_ASSERT(m_res_cap_map[e] >= 0);
m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
//now we follow the path back to the source
@@ -349,7 +349,7 @@
while(current_node != m_source){
edge_descriptor pred = get_edge_to_parent(current_node);
m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
+ BOOST_ASSERT(m_res_cap_map[pred] >= 0);
m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
if(m_res_cap_map[pred] == 0){
set_no_parent(current_node);
@@ -362,7 +362,7 @@
while(current_node != m_sink){
edge_descriptor pred = get_edge_to_parent(current_node);
m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
+ BOOST_ASSERT(m_res_cap_map[pred] >= 0);
m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
if(m_res_cap_map[pred] == 0){
set_no_parent(current_node);
@@ -421,7 +421,7 @@
out_edge_iterator ei, e_end;
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
const edge_descriptor in_edge = m_rev_edge_map[*ei];
- assert(target(in_edge, m_g) == current_node); //we should be the target of this edge
+ BOOST_ASSERT(target(in_edge, m_g) == current_node); //we should be the target of this edge
if(m_res_cap_map[in_edge] > 0){
vertex_descriptor other_node = source(in_edge, m_g);
if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
@@ -458,7 +458,7 @@
} //source-tree-adoption
else{
//now we should be in the sink-tree, check that...
- assert(get_tree(current_node) == tColorTraits::white());
+ BOOST_ASSERT(get_tree(current_node) == tColorTraits::white());
out_edge_iterator ei, e_end;
edge_descriptor new_parent_edge;
tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
@@ -513,7 +513,7 @@
m_active_nodes.pop();
m_in_active_list_map[v] = false;
} else{
- assert(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
+ BOOST_ASSERT(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
return v;
}
}
@@ -523,7 +523,7 @@
* adds v as an active vertex, but only if its not in the list already
*/
inline void add_active_node(vertex_descriptor v){
- assert(get_tree(v) != tColorTraits::gray());
+ BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
if(m_in_active_list_map[v]){
return;
} else{
@@ -536,7 +536,7 @@
* finish_node removes a node from the front of the active queue (its called in grow phase, if no more paths can be found using this node)
*/
inline void finish_node(vertex_descriptor v){
- assert(m_active_nodes.front() == v);
+ BOOST_ASSERT(m_active_nodes.front() == v);
m_active_nodes.pop();
m_in_active_list_map[v] = false;
m_last_grow_vertex = graph_traits<Graph>::null_vertex();
@@ -548,7 +548,7 @@
* being no more active)
*/
inline void remove_active_node(vertex_descriptor v){
- assert(!has_parent(v));
+ BOOST_ASSERT(!has_parent(v));
}
/**
@@ -585,7 +585,7 @@
* sets edge to parent vertex of v;
*/
inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
- assert(m_res_cap_map[f_edge_to_parent] > 0);
+ BOOST_ASSERT(m_res_cap_map[f_edge_to_parent] > 0);
m_pre_map[v] = f_edge_to_parent;
m_has_parent_map[v] = true;
}
@@ -750,7 +750,7 @@
function_requires<Mutable_LvaluePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
function_requires<Mutable_LvaluePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
- assert(num_vertices(g) >= 2 && src != sink);
+ BOOST_ASSERT(num_vertices(g) >= 2 && src != sink);
detail::bk_max_flow<
Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -17,7 +17,7 @@
#include <utility>
#include <algorithm>
#include <climits>
-#include <cassert>
+#include <boost/assert.hpp>
#include <iterator>
#if 0
#include <iostream> // For some debugging code below
@@ -1342,7 +1342,7 @@
edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
{
typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
- assert (idx < num_edges(g));
+ BOOST_ASSERT (idx < num_edges(g));
row_start_iter src_plus_1 =
std::upper_bound(g.m_forward.m_rowstart.begin(),
g.m_forward.m_rowstart.end(),
Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp (original)
+++ trunk/boost/graph/detail/adjacency_list.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -35,6 +35,7 @@
#include <boost/pending/property.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/static_assert.hpp>
+#include <boost/assert.hpp>
// Symbol truncation problems with MSVC, trying to shorten names.
#define stored_edge se_
@@ -1216,7 +1217,7 @@
std::pair<out_edge_iterator, out_edge_iterator> rng =
get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
rng.first = std::find(rng.first, rng.second, e);
- assert(rng.first != rng.second);
+ BOOST_ASSERT(rng.first != rng.second);
remove_edge(rng.first);
}
Modified: trunk/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- trunk/boost/graph/detail/compressed_sparse_row_struct.hpp (original)
+++ trunk/boost/graph/detail/compressed_sparse_row_struct.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -21,7 +21,7 @@
#include <utility>
#include <algorithm>
#include <climits>
-#include <cassert>
+#include <boost/assert.hpp>
#include <iterator>
#if 0
#include <iostream> // For some debugging code below
@@ -255,7 +255,7 @@
std::vector<vertex_descriptor>& targets,
vertices_size_type numverts,
GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
+ BOOST_ASSERT (sources.size() == targets.size());
// Do an in-place histogram sort (at least that's what I think it is) to
// sort sources and targets
m_rowstart.clear();
@@ -281,8 +281,8 @@
std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
vertices_size_type numverts,
GlobalToLocal global_to_local) {
- assert (sources.size() == targets.size());
- assert (sources.size() == edge_props.size());
+ BOOST_ASSERT (sources.size() == targets.size());
+ BOOST_ASSERT (sources.size() == edge_props.size());
// Do an in-place histogram sort (at least that's what I think it is) to
// sort sources and targets
m_rowstart.clear();
Modified: trunk/boost/graph/detail/d_ary_heap.hpp
==============================================================================
--- trunk/boost/graph/detail/d_ary_heap.hpp (original)
+++ trunk/boost/graph/detail/d_ary_heap.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -15,7 +15,7 @@
#include <cstddef>
#include <algorithm>
#include <utility>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/static_assert.hpp>
#include <boost/shared_array.hpp>
#include <boost/property_map/property_map.hpp>
@@ -213,7 +213,7 @@
#if 0
for (size_t i = 1; i < data.size(); ++i) {
if (compare_indirect(data[i], data[parent(i)])) {
- assert (!"Element is smaller than its parent");
+ BOOST_ASSERT (!"Element is smaller than its parent");
}
}
#endif
Modified: trunk/boost/graph/detail/histogram_sort.hpp
==============================================================================
--- trunk/boost/graph/detail/histogram_sort.hpp (original)
+++ trunk/boost/graph/detail/histogram_sort.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -10,6 +10,8 @@
#ifndef BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
#define BOOST_GRAPH_DETAIL_HISTOGRAM_SORT_HPP
+#include <boost/assert.hpp>
+
namespace boost {
namespace graph {
namespace detail {
@@ -165,7 +167,7 @@
while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
// Add a slot in the right bucket
size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
- assert (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
+ BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
if (target_pos == i) continue;
// Swap this edge into place
using std::swap;
@@ -199,7 +201,7 @@
while (!(i >= rowstart[key_transform(key_begin[i])] && i < insert_positions[key_transform(key_begin[i])])) {
// Add a slot in the right bucket
size_t target_pos = insert_positions[key_transform(key_begin[i])]++;
- assert (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
+ BOOST_ASSERT (target_pos < rowstart[key_transform(key_begin[i]) + 1]);
if (target_pos == i) continue;
// Swap this edge into place
using std::swap;
Modified: trunk/boost/graph/dimacs.hpp
==============================================================================
--- trunk/boost/graph/dimacs.hpp (original)
+++ trunk/boost/graph/dimacs.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -17,6 +17,7 @@
#include <exception>
#include <vector>
#include <queue>
+#include <boost/assert.hpp>
namespace boost { namespace graph {
@@ -54,27 +55,27 @@
num_edges( 0 ), seen_edges( 0 ), want_weights(false) {}
edge_type edge_deref() {
- assert( !read_edges.empty() );
+ BOOST_ASSERT( !read_edges.empty() );
return read_edges.front();
}
inline edge_type* edge_ref() {
- assert( !read_edges.empty() );
+ BOOST_ASSERT( !read_edges.empty() );
return &read_edges.front();
}
inline edge_weight_type edge_weight_deref() {
- assert( !read_edge_weights.empty() );
+ BOOST_ASSERT( !read_edge_weights.empty() );
return read_edge_weights.front();
}
inline dimacs_basic_reader incr( incr_mode mode ) {
if( mode == edge ) {
- assert( !read_edges.empty() );
+ BOOST_ASSERT( !read_edges.empty() );
read_edges.pop();
}
else if( mode == edge_weight ) {
- assert( !read_edge_weights.empty() );
+ BOOST_ASSERT( !read_edge_weights.empty() );
read_edge_weights.pop();
}
@@ -100,8 +101,8 @@
read_edge_weights.push( weight );
}
}
- assert( read_edges.size() < 100 );
- assert( read_edge_weights.size() < 100 );
+ BOOST_ASSERT( read_edges.size() < 100 );
+ BOOST_ASSERT( read_edge_weights.size() < 100 );
}
// the 1000000 just happens to be about how many edges can be read in
Modified: trunk/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- trunk/boost/graph/erdos_renyi_generator.hpp (original)
+++ trunk/boost/graph/erdos_renyi_generator.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -10,7 +10,7 @@
#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
-#include <cassert>
+#include <boost/assert.hpp>
#include <iterator>
#include <utility>
#include <boost/shared_ptr.hpp>
@@ -155,8 +155,8 @@
// bernoulli_distribution would need to be run until it returns true.
// Thus, this distribution can be used to step through the edges
// which are actually present.
- assert (src != (std::numeric_limits<vertices_size_type>::max)() &&
- src != n);
+ BOOST_ASSERT (src != (std::numeric_limits<vertices_size_type>::max)() &&
+ src != n);
while (src != n) {
vertices_size_type increment = rand_vertex(*gen);
size_t tgt_index_limit =
Modified: trunk/boost/graph/graph_stats.hpp
==============================================================================
--- trunk/boost/graph/graph_stats.hpp (original)
+++ trunk/boost/graph/graph_stats.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -12,6 +12,7 @@
#include <map>
#include <list>
#include <boost/graph/iteration_macros.hpp>
+#include <boost/assert.hpp>
namespace boost { namespace graph {
@@ -124,7 +125,7 @@
for( std::map<unsigned long, double>::iterator iter = dist.begin();
iter != dist.end(); ++iter ) {
- assert( n[iter->first] != 0 );
+ BOOST_ASSERT( n[iter->first] != 0 );
dist[iter->first] /= n[iter->first];
}
Modified: trunk/boost/graph/graph_test.hpp
==============================================================================
--- trunk/boost/graph/graph_test.hpp (original)
+++ trunk/boost/graph/graph_test.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -213,7 +213,7 @@
IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
copy_graph(g, cpy, orig_to_copy(iso_map));
- assert((verify_isomorphism(g, cpy, iso_map)));
+ BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
vertex_t v = add_vertex(g);
Modified: trunk/boost/graph/gursoy_atun_layout.hpp
==============================================================================
--- trunk/boost/graph/gursoy_atun_layout.hpp (original)
+++ trunk/boost/graph/gursoy_atun_layout.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -17,6 +17,7 @@
#include <boost/config/no_tr1/cmath.hpp>
#include <boost/throw_exception.hpp>
+#include <boost/assert.hpp>
#include <vector>
#include <exception>
#include <algorithm>
@@ -169,7 +170,7 @@
}
min_distance_unset = false;
}
- assert (!min_distance_unset); // Graph must have at least one vertex
+ BOOST_ASSERT (!min_distance_unset); // Graph must have at least one vertex
boost::detail::update_position_visitor<
PositionMap, NodeDistanceMap, Topology,
VertexListAndIncidenceGraph>
Modified: trunk/boost/graph/kamada_kawai_spring_layout.hpp
==============================================================================
--- trunk/boost/graph/kamada_kawai_spring_layout.hpp (original)
+++ trunk/boost/graph/kamada_kawai_spring_layout.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -17,6 +17,7 @@
#include <utility>
#include <iterator>
#include <vector>
+#include <iostream>
#include <boost/limits.hpp>
#include <boost/config/no_tr1/cmath.hpp>
@@ -216,11 +217,13 @@
weight_type edge_length =
detail::graph::compute_edge_length(g, distance, index,
edge_or_side_length);
+
+ std::cerr << "edge_length = " << edge_length << std::endl;
// Compute l_{ij} and k_{ij}
const weight_type K = spring_constant;
- vertex_iterator ui, end = vertices(g).second;
- for (ui = vertices(g).first; ui != end; ++ui) {
+ vertex_iterator ui, end;
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
vertex_iterator vi = ui;
for (++vi; vi != end; ++vi) {
weight_type dij = distance[get(index, *ui)][get(index, *vi)];
@@ -237,7 +240,7 @@
vertex_descriptor p = *vertices(g).first;
weight_type delta_p(0);
- for (ui = vertices(g).first; ui != end; ++ui) {
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
deriv_type deriv = compute_partial_derivatives(*ui);
put(partial_derivatives, *ui, deriv);
@@ -255,12 +258,25 @@
// update the delta_i values in O(n) time instead of O(n^2)
// time.
std::vector<deriv_type> p_partials(num_vertices(g));
- for (ui = vertices(g).first; ui != end; ++ui) {
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
vertex_descriptor i = *ui;
p_partials[get(index, i)] = compute_partial_derivative(i, p);
}
do {
+ // For debugging, compute the energy value E
+ double E = 0.;
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
+ vertex_iterator vi = ui;
+ for (++vi; vi != end; ++vi) {
+ double dist = topology.distance(position[*ui], position[*vi]);
+ weight_type k_ij = spring_strength[get(index,*ui)][get(index,*vi)];
+ weight_type l_ij = distance[get(index, *ui)][get(index, *vi)];
+ E += .5 * k_ij * (dist - l_ij) * (dist - l_ij);
+ }
+ }
+ std::cerr << "E = " << E << std::endl;
+
// Compute the elements of the Jacobian
// From
// http://www.cs.panam.edu/~rfowler/papers/1994_kumar_fowler_A_Spring_UTPACSTR.pdf
@@ -269,7 +285,7 @@
for (std::size_t i = 0; i < Point::dimensions; ++i)
for (std::size_t j = 0; j < Point::dimensions; ++j)
dE_d_d[i][j] = 0.;
- for (ui = vertices(g).first; ui != end; ++ui) {
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
vertex_descriptor i = *ui;
if (i != p) {
point_difference_type diff = topology.difference(position[p], position[i]);
@@ -284,6 +300,7 @@
dE_d_d[i][i] += k_mi * (1 + (l_mi * (diff[i] * diff[i] - dist_squared) * inv_dist_cubed));
} else {
dE_d_d[i][j] += k_mi * l_mi * diff[i] * diff[j] * inv_dist_cubed;
+ // dE_d_d[i][j] += k_mi * l_mi * sqrt(hypot(diff[i], diff[j])) * inv_dist_cubed;
}
}
}
@@ -292,7 +309,7 @@
deriv_type dE_d = get(partial_derivatives, p);
- // Solve dE_d_d * delta = dE_d to get delta
+ // Solve dE_d_d * delta = -dE_d to get delta
point_difference_type delta = -linear_solver<Point::dimensions>::solve(dE_d_d, dE_d);
// Move p by delta
@@ -307,7 +324,7 @@
// Select new p by updating each partial derivative and delta
vertex_descriptor old_p = p;
- for (ui = vertices(g).first; ui != end; ++ui) {
+ for (ui = vertices(g).first, end = vertices(g).second; ui != end; ++ui) {
deriv_type old_deriv_p = p_partials[get(index, *ui)];
deriv_type old_p_partial =
compute_partial_derivative(*ui, old_p);
Modified: trunk/boost/graph/loop_erased_random_walk.hpp
==============================================================================
--- trunk/boost/graph/loop_erased_random_walk.hpp (original)
+++ trunk/boost/graph/loop_erased_random_walk.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -15,7 +15,7 @@
#include <boost/graph/random.hpp>
#include <boost/next_prior.hpp>
#include <vector>
-#include <cassert>
+#include <boost/assert.hpp>
namespace boost {
@@ -51,7 +51,7 @@
typedef typename boost::property_traits<ColorMap>::value_type color_t;
typedef boost::color_traits<color_t> color_gen;
- assert (get(color, s) == color_gen::white());
+ BOOST_ASSERT (get(color, s) == color_gen::white());
path.clear();
path.push_back(s);
put(color, s, color_gen::gray());
@@ -67,7 +67,7 @@
// Found a loop; delete from path from the first occurrence of t to the
// end, coloring vertices white.
typename std::vector<vertex_descriptor>::iterator it = std::find(path.begin(), path.end(), t);
- assert (it != path.end());
+ BOOST_ASSERT (it != path.end());
++it;
for (typename std::vector<vertex_descriptor>::iterator j = it; j != path.end(); ++j) {
put(color, *j, color_gen::white());
Modified: trunk/boost/graph/mesh_graph_generator.hpp
==============================================================================
--- trunk/boost/graph/mesh_graph_generator.hpp (original)
+++ trunk/boost/graph/mesh_graph_generator.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -11,7 +11,7 @@
#include <iterator>
#include <utility>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/type_traits/is_same.hpp>
@@ -47,7 +47,7 @@
bool toroidal = true)
: x(x), y(y), n(x*y), source(0), target(1), current(0,1),
toroidal(toroidal), done(false)
- { assert(x > 1 && y > 1); }
+ { BOOST_ASSERT(x > 1 && y > 1); }
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
Modified: trunk/boost/graph/minimum_degree_ordering.hpp
==============================================================================
--- trunk/boost/graph/minimum_degree_ordering.hpp (original)
+++ trunk/boost/graph/minimum_degree_ordering.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -12,7 +12,7 @@
#define MINIMUM_DEGREE_ORDERING_HPP
#include <vector>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/config.hpp>
#include <boost/pending/bucket_sorter.hpp>
#include <boost/detail/numeric_traits.hpp> // for integer_traits
@@ -53,7 +53,7 @@
: data(_data), current(-(std::numeric_limits<value_type>::max)()) {}
void pop() {
- assert(! empty());
+ BOOST_ASSERT(! empty());
current = data[current];
}
void push(value_type v) {
Modified: trunk/boost/graph/one_bit_color_map.hpp
==============================================================================
--- trunk/boost/graph/one_bit_color_map.hpp (original)
+++ trunk/boost/graph/one_bit_color_map.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -18,6 +18,7 @@
#include <boost/graph/properties.hpp>
#include <boost/shared_array.hpp>
#include <boost/config.hpp>
+#include <boost/assert.hpp>
#include <algorithm>
#include <limits>
@@ -65,7 +66,7 @@
{
BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
- assert ((std::size_t)i < pm.n);
+ BOOST_ASSERT ((std::size_t)i < pm.n);
return one_bit_color_type((pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1);
}
@@ -77,8 +78,8 @@
{
BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
- assert ((std::size_t)i < pm.n);
- assert (value >= 0 && value < 2);
+ BOOST_ASSERT ((std::size_t)i < pm.n);
+ BOOST_ASSERT (value >= 0 && value < 2);
std::size_t byte_num = i / bits_per_char;
std::size_t bit_position = (i % bits_per_char);
pm.data.get()[byte_num] =
Modified: trunk/boost/graph/properties.hpp
==============================================================================
--- trunk/boost/graph/properties.hpp (original)
+++ trunk/boost/graph/properties.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -11,7 +11,7 @@
#define BOOST_GRAPH_PROPERTIES_HPP
#include <boost/config.hpp>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/pending/property.hpp>
#include <boost/detail/workaround.hpp>
@@ -353,7 +353,7 @@
>
make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
{
- assert(c.size() >= num_vertices(g));
+ BOOST_ASSERT(c.size() >= num_vertices(g));
return make_iterator_vertex_map(c.begin(), g);
}
Modified: trunk/boost/graph/push_relabel_max_flow.hpp
==============================================================================
--- trunk/boost/graph/push_relabel_max_flow.hpp (original)
+++ trunk/boost/graph/push_relabel_max_flow.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -11,7 +11,7 @@
#define BOOST_PUSH_RELABEL_MAX_FLOW_HPP
#include <boost/config.hpp>
-#include <cassert>
+#include <boost/assert.hpp>
#include <vector>
#include <list>
#include <iosfwd>
@@ -266,7 +266,7 @@
// but it is called "discharge" in the paper and in hi_pr.c.
void discharge(vertex_descriptor u)
{
- assert(get(excess_flow, u) > 0);
+ BOOST_ASSERT(get(excess_flow, u) > 0);
while (1) {
out_edge_iterator ai, ai_end;
for (boost::tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) {
@@ -703,8 +703,8 @@
algo.convert_preflow_to_flow();
- assert(algo.is_flow());
- assert(algo.is_optimal());
+ BOOST_ASSERT(algo.is_flow());
+ BOOST_ASSERT(algo.is_optimal());
return flow;
} // push_relabel_max_flow()
Modified: trunk/boost/graph/random.hpp
==============================================================================
--- trunk/boost/graph/random.hpp (original)
+++ trunk/boost/graph/random.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -26,7 +26,7 @@
#include <boost/type_traits/is_convertible.hpp>
#include <iostream>
-#include <cassert>
+#include <boost/assert.hpp>
namespace boost {
@@ -104,7 +104,7 @@
chosen_weight -= w;
}
}
- assert (false); // Should not get here
+ BOOST_ASSERT (false); // Should not get here
}
namespace detail {
Modified: trunk/boost/graph/random_spanning_tree.hpp
==============================================================================
--- trunk/boost/graph/random_spanning_tree.hpp (original)
+++ trunk/boost/graph/random_spanning_tree.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -11,6 +11,7 @@
#define BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP
#include <vector>
+#include <boost/assert.hpp>
#include <boost/graph/loop_erased_random_walk.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/iteration_macros.hpp>
@@ -34,7 +35,7 @@
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- assert (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected
+ BOOST_ASSERT (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected
typedef color_traits<typename property_traits<ColorMap>::value_type> color_gen;
BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white());
@@ -53,7 +54,7 @@
++i) {
typename std::vector<vertex_descriptor>::const_reverse_iterator j = i;
++j;
- assert (get(color, *j) == color_gen::gray());
+ BOOST_ASSERT (get(color, *j) == color_gen::gray());
put(color, *j, color_gen::black());
put(pred, *j, *i);
}
Modified: trunk/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- trunk/boost/graph/rmat_graph_generator.hpp (original)
+++ trunk/boost/graph/rmat_graph_generator.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -16,6 +16,7 @@
#include <queue>
#include <map>
#include <boost/shared_ptr.hpp>
+#include <boost/assert.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_01.hpp>
#include <boost/graph/graph_traits.hpp>
@@ -155,7 +156,7 @@
{
this->gen.reset(new uniform_01<RandomGenerator>(gen));
- assert(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
@@ -265,7 +266,7 @@
values(sort_pair<vertices_size_type>()), done(false)
{
- assert(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
@@ -366,7 +367,7 @@
: gen(), done(false)
{
- assert(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
@@ -479,7 +480,7 @@
values(sort_pair<vertices_size_type>()), done(false)
{
- assert(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
Modified: trunk/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- trunk/boost/graph/stoer_wagner_min_cut.hpp (original)
+++ trunk/boost/graph/stoer_wagner_min_cut.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -6,7 +6,7 @@
#ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
#define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
-#include <cassert>
+#include <boost/assert.hpp>
#include <set>
#include <vector>
#include <boost/concept_check.hpp>
@@ -61,7 +61,7 @@
typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
typedef typename boost::property_traits<WeightMap>::value_type weight_type;
- assert(pq.empty());
+ BOOST_ASSERT(pq.empty());
typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
@@ -72,7 +72,7 @@
}
}
- assert(pq.size() >= 2);
+ BOOST_ASSERT(pq.size() >= 2);
vertex_descriptor s = boost::graph_traits<UndirectedGraph>::null_vertex();
vertex_descriptor t = boost::graph_traits<UndirectedGraph>::null_vertex();
@@ -169,7 +169,7 @@
weight_type bestW;
boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
- assert(s != t);
+ BOOST_ASSERT(s != t);
BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
put(parities, v, parity_type(v == t ? 1 : 0));
}
@@ -180,7 +180,7 @@
for (; n >= 2; --n) {
weight_type w;
boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
- assert(s != t);
+ BOOST_ASSERT(s != t);
if (w < bestW) {
BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
@@ -201,7 +201,7 @@
assignedVertices.insert(t);
}
- assert(pq.empty());
+ BOOST_ASSERT(pq.empty());
return bestW;
}
Modified: trunk/boost/graph/subgraph.hpp
==============================================================================
--- trunk/boost/graph/subgraph.hpp (original)
+++ trunk/boost/graph/subgraph.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -16,7 +16,7 @@
#include <list>
#include <vector>
#include <map>
-#include <cassert>
+#include <boost/assert.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_mutability_traits.hpp>
#include <boost/graph/properties.hpp>
@@ -181,7 +181,7 @@
vertex_descriptor u_local; bool in_subgraph;
if (is_root()) return u_global;
boost::tie(u_local, in_subgraph) = this->find_vertex(u_global);
- assert(in_subgraph == true);
+ BOOST_ASSERT(in_subgraph == true);
return u_local;
}
@@ -345,7 +345,7 @@
add_vertex(typename subgraph<G>::vertex_descriptor u_global,
subgraph<G>& g)
{
- assert(!g.is_root());
+ BOOST_ASSERT(!g.is_root());
typename subgraph<G>::vertex_descriptor u_local, v_global;
typename subgraph<G>::edge_descriptor e_global;
@@ -751,7 +751,7 @@
// TODO: Under Construction
template <typename G>
void remove_vertex(typename subgraph<G>::vertex_descriptor u, subgraph<G>& g)
-{ assert(false); }
+{ BOOST_ASSERT(false); }
#endif
//===========================================================================
Modified: trunk/boost/graph/two_bit_color_map.hpp
==============================================================================
--- trunk/boost/graph/two_bit_color_map.hpp (original)
+++ trunk/boost/graph/two_bit_color_map.hpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -17,6 +17,7 @@
#include <boost/graph/properties.hpp>
#include <boost/shared_array.hpp>
#include <boost/config.hpp>
+#include <boost/assert.hpp>
#include <algorithm>
#include <limits>
@@ -68,7 +69,7 @@
{
BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
- assert ((std::size_t)i < pm.n);
+ BOOST_ASSERT ((std::size_t)i < pm.n);
std::size_t byte_num = i / elements_per_char;
std::size_t bit_position = ((i % elements_per_char) * 2);
return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
@@ -82,8 +83,8 @@
{
BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
- assert ((std::size_t)i < pm.n);
- assert (value >= 0 && value < 4);
+ BOOST_ASSERT ((std::size_t)i < pm.n);
+ BOOST_ASSERT (value >= 0 && value < 4);
std::size_t byte_num = i / elements_per_char;
std::size_t bit_position = ((i % elements_per_char) * 2);
pm.data.get()[byte_num] =
Modified: trunk/libs/graph/src/read_graphviz_new.cpp
==============================================================================
--- trunk/libs/graph/src/read_graphviz_new.cpp (original)
+++ trunk/libs/graph/src/read_graphviz_new.cpp 2011-01-05 21:08:41 EST (Wed, 05 Jan 2011)
@@ -26,6 +26,7 @@
//
#define BOOST_GRAPH_SOURCE
+#include <boost/assert.hpp>
#include <boost/ref.hpp>
#include <boost/function/function2.hpp>
#include <boost/property_map/dynamic_property_map.hpp>
@@ -167,10 +168,10 @@
#endif
boost::regex_search(begin, end, results, stuff_to_skip);
#ifndef NDEBUG
- assert (found);
+ BOOST_ASSERT (found);
#endif
boost::sub_match<std::string::const_iterator> sm1 = results.suffix();
- assert (sm1.second == end);
+ BOOST_ASSERT (sm1.second == end);
begin = sm1.first;
}
@@ -227,10 +228,10 @@
switch (str[1]) {
case '-': return token(token::dash_dash, str);
case '>': return token(token::dash_greater, str);
- default: assert (!"Definition of punctuation_token does not match switch statement");
+ default: BOOST_ASSERT (!"Definition of punctuation_token does not match switch statement");
}
}
- default: assert (!"Definition of punctuation_token does not match switch statement");
+ default: BOOST_ASSERT (!"Definition of punctuation_token does not match switch statement");
}
}
found = boost::regex_search(begin, end, results, number_token);
@@ -244,7 +245,7 @@
std::string str = results[1].str();
begin = results.suffix().first;
// Remove the beginning and ending quotes
- assert (str.size() >= 2);
+ BOOST_ASSERT (str.size() >= 2);
str.erase(str.begin());
str.erase(str.end() - 1);
// Unescape quotes in the middle, but nothing else (see format spec)
@@ -500,7 +501,7 @@
case token::kw_graph: parse_attr_list(current_graph_props()); break;
case token::kw_node: parse_attr_list(current().def_node_props); break;
case token::kw_edge: parse_attr_list(current().def_edge_props); break;
- default: assert (!"Bad attr_stmt case");
+ default: BOOST_ASSERT (!"Bad attr_stmt case");
}
}
@@ -637,7 +638,7 @@
}
properties this_edge_props = current().def_edge_props;
if (peek().type == token::left_bracket) parse_attr_list(this_edge_props);
- assert (nodes_in_chain.size() >= 2); // Should be in node parser otherwise
+ BOOST_ASSERT (nodes_in_chain.size() >= 2); // Should be in node parser otherwise
for (size_t i = 0; i + 1 < nodes_in_chain.size(); ++i) {
do_orig_edge(nodes_in_chain[i], nodes_in_chain[i + 1], this_edge_props);
}
@@ -780,7 +781,7 @@
}
}
std::map<subgraph_name, properties>::const_iterator root_graph_props_i = r.graph_props.find("___root___");
- assert (root_graph_props_i != r.graph_props.end()); // Should not happen
+ BOOST_ASSERT (root_graph_props_i != r.graph_props.end()); // Should not happen
const properties& root_graph_props = root_graph_props_i->second;
// std::cerr << "ending graph " << props_to_string(root_graph_props) << std::endl;
for (properties::const_iterator i = root_graph_props.begin(); i != root_graph_props.end(); ++i) {
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