Subject: [Boost-commit] svn:boost r50706 - in trunk: boost/graph boost/graph/planar_detail libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-01-21 13:59:40
Author: jewillco
Date: 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
New Revision: 50706
URL: http://svn.boost.org/trac/boost/changeset/50706
Log:
Fixed inspection report problems
Text files modified:
trunk/boost/graph/adjacency_list.hpp | 2
trunk/boost/graph/floyd_warshall_shortest.hpp | 14
trunk/boost/graph/howard_cycle_ratio.hpp | 2
trunk/boost/graph/is_straight_line_drawing.hpp | 2
trunk/boost/graph/kolmogorov_max_flow.hpp | 10
trunk/boost/graph/make_biconnected_planar.hpp | 2
trunk/boost/graph/max_cardinality_matching.hpp | 10
trunk/boost/graph/named_graph.hpp | 28 +-
trunk/boost/graph/planar_detail/face_iterators.hpp | 2
trunk/boost/graph/r_c_shortest_paths.hpp | 2
trunk/boost/graph/sloan_ordering.hpp | 2
trunk/libs/graph/doc/edmonds_karp_max_flow.html | 2
trunk/libs/graph/doc/metric_tsp_approx.html | 2
trunk/libs/graph/doc/table_of_contents.html | 6
trunk/libs/graph/example/cycle_ratio_example.cpp | 106 +++++-----
trunk/libs/graph/example/file_dependencies.cpp | 2
trunk/libs/graph/example/graph-thingie.cpp | 12
trunk/libs/graph/example/read_write_dimacs-eg.cpp | 2
trunk/libs/graph/test/cycle_ratio_tests.cpp | 376 ++++++++++++++++++++--------------------
trunk/libs/graph/test/graphml_test.cpp | 4
trunk/libs/graph/test/named_vertices_test.cpp | 4
trunk/libs/graph/test/serialize.cpp | 20 +-
22 files changed, 306 insertions(+), 306 deletions(-)
Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp (original)
+++ trunk/boost/graph/adjacency_list.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -343,7 +343,7 @@
adjacency_list<OutEdgeListS,VertexListS,DirectedS,
VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
- EdgeListS>::vertex_descriptor,
+ EdgeListS>::vertex_descriptor,
VertexProperty>
{
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
Modified: trunk/boost/graph/floyd_warshall_shortest.hpp
==============================================================================
--- trunk/boost/graph/floyd_warshall_shortest.hpp (original)
+++ trunk/boost/graph/floyd_warshall_shortest.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -59,13 +59,13 @@
for (tie(k, lastk) = vertices(g); k != lastk; k++)
for (tie(i, lasti) = vertices(g); i != lasti; i++)
- if(d[*i][*k] != inf)
- for (tie(j, lastj) = vertices(g); j != lastj; j++)
- if(d[*k][*j] != inf)
- d[*i][*j] =
- detail::min_with_compare(d[*i][*j],
- combine(d[*i][*k], d[*k][*j]),
- compare);
+ if(d[*i][*k] != inf)
+ for (tie(j, lastj) = vertices(g); j != lastj; j++)
+ if(d[*k][*j] != inf)
+ d[*i][*j] =
+ detail::min_with_compare(d[*i][*j],
+ combine(d[*i][*k], d[*k][*j]),
+ compare);
for (tie(i, lasti) = vertices(g); i != lasti; i++)
Modified: trunk/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- trunk/boost/graph/howard_cycle_ratio.hpp (original)
+++ trunk/boost/graph/howard_cycle_ratio.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -255,7 +255,7 @@
}
/*!
- * Value determination. Find a generalized eigenmode (n^{k+1}, x^{k+1}) of A^{Ï_{k+1}} of the pi graph (Algorithm IV.1).
+ * Value determination. Find a generalized eigenmode (n^{k+1}, x^{k+1}) of A^{I_{k+1}} of the pi graph (Algorithm IV.1).
*/
void pi_eingen_value(
TPiGraphVertexIndexMap index_map,
Modified: trunk/boost/graph/is_straight_line_drawing.hpp
==============================================================================
--- trunk/boost/graph/is_straight_line_drawing.hpp (original)
+++ trunk/boost/graph/is_straight_line_drawing.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -187,7 +187,7 @@
before = prior(a_itr);
after = next(a_itr);
- if (before != active_edges.end())
+ if (before != active_edges.end())
{
edge_t f = before->second;
Modified: trunk/boost/graph/kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/kolmogorov_max_flow.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -344,7 +344,7 @@
/**
* returns the bottleneck of a s->t path (end_of_path is last vertex in source-tree, begin_of_path is first vertex in sink-tree)
- */
+ */
inline tEdgeVal find_bottleneck(edge_descriptor e){
BOOST_USING_STD_MIN();
tEdgeVal minimum_cap = m_res_cap_map[e];
@@ -467,7 +467,7 @@
/**
* return next active vertex if there is one, otherwise a null_vertex
- */
+ */
inline vertex_descriptor get_next_active_node(){
while(true){
if(m_active_nodes.empty())
@@ -486,7 +486,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());
if(m_in_active_list_map[v]){
@@ -545,7 +545,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);
m_pre_map[v] = f_edge_to_parent;
@@ -676,7 +676,7 @@
/**
* non-named-parameter version, given everything
* this is the catch all version
- */
+ */
template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
typename property_traits<CapacityEdgeMap>::value_type
Modified: trunk/boost/graph/make_biconnected_planar.hpp
==============================================================================
--- trunk/boost/graph/make_biconnected_planar.hpp (original)
+++ trunk/boost/graph/make_biconnected_planar.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -44,7 +44,7 @@
typedef iterator_property_map
<std::vector<std::size_t>::iterator, EdgeIndexMap> component_map_t;
- edge_size_t n_edges(num_edges(g));
+ edge_size_t n_edges(num_edges(g));
std::vector<vertex_t> articulation_points;
std::vector<edge_size_t> component_vector(n_edges);
component_map_t component_map(component_vector.begin(), em);
Modified: trunk/boost/graph/max_cardinality_matching.hpp
==============================================================================
--- trunk/boost/graph/max_cardinality_matching.hpp (original)
+++ trunk/boost/graph/max_cardinality_matching.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -266,7 +266,7 @@
pred[w_prime] = v;
}
- //w_prime == v_prime can happen below if we get an edge that has been
+ //w_prime == v_prime can happen below if we get an edge that has been
//shrunk into a blossom
else if (vertex_state[w_prime] == graph::detail::V_EVEN && w_prime != v_prime)
{
@@ -682,7 +682,7 @@
void discover_vertex(Vertex u, Graph&)
{
m_parity = !m_parity;
- m_parity ? ++m_count : --m_count;
+ m_parity ? ++m_count : --m_count;
}
protected:
@@ -736,12 +736,12 @@
//excludes vertices labeled "graph::detail::V_ODD"
non_odd_vertex() : vertex_state(0) { }
- non_odd_vertex(VertexStateMap* arg_vertex_state)
+ non_odd_vertex(VertexStateMap* arg_vertex_state)
: vertex_state(arg_vertex_state) { }
- template <typename Vertex>
+ template <typename Vertex>
bool operator()(const Vertex& v) const
- {
+ {
BOOST_ASSERT(vertex_state);
return get(*vertex_state, v) != graph::detail::V_ODD;
}
Modified: trunk/boost/graph/named_graph.hpp
==============================================================================
--- trunk/boost/graph/named_graph.hpp (original)
+++ trunk/boost/graph/named_graph.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -274,8 +274,8 @@
typedef multi_index::multi_index_container<
Vertex,
multi_index::indexed_by<
- multi_index::hashed_unique<multi_index::tag<vertex_name_t>,
- extract_name_from_vertex> >
+ multi_index::hashed_unique<multi_index::tag<vertex_name_t>,
+ extract_name_from_vertex> >
> named_vertices_type;
/// The set of vertices, indexed by name
@@ -337,8 +337,8 @@
boost::make_tuple(
0, // initial number of buckets
extract_name_from_vertex(derived(), extract),
- boost::hash<vertex_name_type>(),
- std::equal_to<vertex_name_type>())))),
+ boost::hash<vertex_name_type>(),
+ std::equal_to<vertex_name_type>())))),
vertex_constructor(vertex_constructor)
{
}
@@ -380,7 +380,7 @@
template<BGL_NAMED_GRAPH_PARAMS>
optional<Vertex>
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
- const BGL_NAMED_GRAPH& g)
+ const BGL_NAMED_GRAPH& g)
{
typedef typename BGL_NAMED_GRAPH::vertices_by_name_type
vertices_by_name_type;
@@ -418,8 +418,8 @@
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
- typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
- BGL_NAMED_GRAPH& g)
+ typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
+ BGL_NAMED_GRAPH& g)
{
return add_edge(add_vertex(u_name, g.derived()),
add_vertex(v_name, g.derived()),
@@ -430,8 +430,8 @@
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
- typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
- BGL_NAMED_GRAPH& g)
+ typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
+ BGL_NAMED_GRAPH& g)
{
return add_edge(u,
add_vertex(v_name, g.derived()),
@@ -443,7 +443,7 @@
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
- BGL_NAMED_GRAPH& g)
+ BGL_NAMED_GRAPH& g)
{
return add_edge(add_vertex(u_name, g.derived()),
v,
@@ -464,8 +464,8 @@
* graphs.
*/
template<typename Graph, typename Vertex, typename VertexProperty,
- typename ExtractName
- = typename internal_vertex_name<VertexProperty>::type>
+ typename ExtractName
+ = typename internal_vertex_name<VertexProperty>::type>
struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty>
{
};
@@ -506,8 +506,8 @@
};
#else
template<typename Graph, typename Vertex, typename VertexProperty,
- typename ExtractName
- = typename internal_vertex_name<VertexProperty>::type>
+ typename ExtractName
+ = typename internal_vertex_name<VertexProperty>::type>
struct maybe_named_graph
{
/// The type of the "bundled" property, from which the name can be
Modified: trunk/boost/graph/planar_detail/face_iterators.hpp
==============================================================================
--- trunk/boost/graph/planar_detail/face_iterators.hpp (original)
+++ trunk/boost/graph/planar_detail/face_iterators.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -270,7 +270,7 @@
vertex_t m_lead;
vertex_t m_follow;
- edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge;
+ edge_storage<Graph, boost::is_same<ValueType, edge_t>::value > m_edge;
FaceHandlesMap m_face_handles;
};
Modified: trunk/boost/graph/r_c_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/r_c_shortest_paths.hpp (original)
+++ trunk/boost/graph/r_c_shortest_paths.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -316,7 +316,7 @@
}
}
if( !b_outer_iter_erased )
- ++outer_iter;
+ ++outer_iter;
}
if( static_cast<int>( list_labels_cur_vertex.size() ) > 1 )
vec_last_valid_positions_for_dominance[i_cur_resident_vertex_num] =
Modified: trunk/boost/graph/sloan_ordering.hpp
==============================================================================
--- trunk/boost/graph/sloan_ordering.hpp (original)
+++ trunk/boost/graph/sloan_ordering.hpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -196,7 +196,7 @@
// step 5
// Initializing w
- w_e = std::numeric_limits<unsigned>::max();
+ w_e = (std::numeric_limits<unsigned>::max)();
//end 5
Modified: trunk/libs/graph/doc/edmonds_karp_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/edmonds_karp_max_flow.html (original)
+++ trunk/libs/graph/doc/edmonds_karp_max_flow.html 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -224,7 +224,7 @@
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek_at_[hidden]">jsiek_at_[hidden]</A>)
+<A HREF="http://www.boost.org/users/people/jeremy_siek.html">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek_at_[hidden]">jsiek_at_[hidden]</A>)
</TD></TR></TABLE>
</BODY>
Modified: trunk/libs/graph/doc/metric_tsp_approx.html
==============================================================================
--- trunk/libs/graph/doc/metric_tsp_approx.html (original)
+++ trunk/libs/graph/doc/metric_tsp_approx.html 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -176,7 +176,7 @@
<P>
The file <a
-href="../example/metric_tsp_approx_example.cpp"><TT>examples/metric_tsp_approx_example.cpp</TT></a>
+href="../test/metric_tsp_approx_example.cpp"><TT>test/metric_tsp_approx_example.cpp</TT></a>
contains an example of using this TSP approximation algorithm.
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -173,10 +173,10 @@
</OL></LI>
<LI>Maximum Flow and Matching Algorithms
<OL>
- <LI>edmunds_karp_max_flow
- <LI>push_relabel_max_flow
+ <LI>edmonds_karp_max_flow
+ <LI>push_relabel_max_flow
<li>kolmogorov_max_flow</li>
- <LI>edmonds_maximum_cardinality_matching
+ <LI>edmonds_maximum_cardinality_matching
</OL>
<li>Sparse Matrix Ordering Algorithms
Modified: trunk/libs/graph/example/cycle_ratio_example.cpp
==============================================================================
--- trunk/libs/graph/example/cycle_ratio_example.cpp (original)
+++ trunk/libs/graph/example/cycle_ratio_example.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -20,65 +20,65 @@
using namespace boost;
-typedef adjacency_list<listS, listS, directedS, property<vertex_index_t, int, property<boost::vertex_name_t, std::string> >,
- property<edge_weight_t, double, property<edge_weight2_t, double, property<edge_index_t, int> > > > grap_real_t;
+typedef adjacency_list<listS, listS, directedS, property<vertex_index_t, int, property<boost::vertex_name_t, std::string> >,
+ property<edge_weight_t, double, property<edge_weight2_t, double, property<edge_index_t, int> > > > grap_real_t;
-template <typename TGraph>
+template <typename TGraph>
void gen_rand_graph(TGraph& g, size_t nV, size_t nE)
{
- g.clear();
- boost::mt19937 rng;
- boost::generate_random_graph(g, nV, nE, rng, true, true);
- boost::uniform_real<> ur(-1,10);
- boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
- randomize_property<edge_weight_t>(g, ew1rg);
- boost::uniform_int<> uint(1,5);
- boost::variate_generator<boost::mt19937&, boost::uniform_int<> > ew2rg(rng, uint);
- randomize_property<edge_weight2_t>(g, ew2rg);
+ g.clear();
+ boost::mt19937 rng;
+ boost::generate_random_graph(g, nV, nE, rng, true, true);
+ boost::uniform_real<> ur(-1,10);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
+ randomize_property<edge_weight_t>(g, ew1rg);
+ boost::uniform_int<> uint(1,5);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > ew2rg(rng, uint);
+ randomize_property<edge_weight2_t>(g, ew2rg);
}
int main(int argc, char* argv[])
{
- const double epsilon = 0.000000001;
- double min_cr, max_cr; ///Minimum and maximum cycle ratio
- typedef std::vector<graph_traits<grap_real_t>::edge_descriptor> ccReal_t;
- ccReal_t cc; ///For storing critical edges
-
-
- grap_real_t tgr;
- property_map<grap_real_t, vertex_index_t>::type vim = get(vertex_index, tgr);
- property_map<grap_real_t, edge_weight_t>::type ew1m = get(edge_weight, tgr);
- property_map<grap_real_t, edge_weight2_t>::type ew2m = ew2m;
-
- gen_rand_graph(tgr, 1000, 300000);
- std::cout << "Vertices number: " << num_vertices(tgr) << '\n';
- std::cout << "Edges number: " << num_edges(tgr) << '\n';
- int i = 0;
- BGL_FORALL_VERTICES(vd, tgr, grap_real_t) put(vertex_index, tgr, vd, i++); ///Initialize vertex index property
- boost::posix_time::ptime st = boost::posix_time::microsec_clock::local_time();
- max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- std::cout << "Run time of the maximum_cycle_ratio() is " << to_simple_string(boost::posix_time::microsec_clock::local_time() - st) << '\n';
-
-
- ///One way to get the "good" value of the plus_infinity parameter
- double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
- *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
- std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
- i = 0;
- BGL_FORALL_EDGES(ed, tgr, grap_real_t) put(edge_index, tgr, ed, i++); ///Initialize edge index property
- min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr), get(edge_index, tgr), &cc, pl_infnt);
- std::cout << "Minimal cycle ratio is " << min_cr << '\n';
- std::pair<double, double> cr(.0,.0);
- std::cout << "\nCritical cycle is:\n";
- for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
- {
- cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
- std::cout << "(" << get(vertex_index, tgr, source(*itr, tgr)) << "," << get(vertex_index, tgr, target(*itr, tgr)) << ") ";
- }
- std::cout << '\n';
- assert(std::abs(cr.first / cr.second - min_cr) < epsilon);
-
- return 0;
+ const double epsilon = 0.000000001;
+ double min_cr, max_cr; ///Minimum and maximum cycle ratio
+ typedef std::vector<graph_traits<grap_real_t>::edge_descriptor> ccReal_t;
+ ccReal_t cc; ///For storing critical edges
+
+
+ grap_real_t tgr;
+ property_map<grap_real_t, vertex_index_t>::type vim = get(vertex_index, tgr);
+ property_map<grap_real_t, edge_weight_t>::type ew1m = get(edge_weight, tgr);
+ property_map<grap_real_t, edge_weight2_t>::type ew2m = ew2m;
+
+ gen_rand_graph(tgr, 1000, 300000);
+ std::cout << "Vertices number: " << num_vertices(tgr) << '\n';
+ std::cout << "Edges number: " << num_edges(tgr) << '\n';
+ int i = 0;
+ BGL_FORALL_VERTICES(vd, tgr, grap_real_t) put(vertex_index, tgr, vd, i++); ///Initialize vertex index property
+ boost::posix_time::ptime st = boost::posix_time::microsec_clock::local_time();
+ max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
+ std::cout << "Maximum cycle ratio is " << max_cr << '\n';
+ std::cout << "Run time of the maximum_cycle_ratio() is " << to_simple_string(boost::posix_time::microsec_clock::local_time() - st) << '\n';
+
+
+ ///One way to get the "good" value of the plus_infinity parameter
+ double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
+ *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
+ std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
+ i = 0;
+ BGL_FORALL_EDGES(ed, tgr, grap_real_t) put(edge_index, tgr, ed, i++); ///Initialize edge index property
+ min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr), get(edge_index, tgr), &cc, pl_infnt);
+ std::cout << "Minimal cycle ratio is " << min_cr << '\n';
+ std::pair<double, double> cr(.0,.0);
+ std::cout << "\nCritical cycle is:\n";
+ for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
+ {
+ cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
+ std::cout << "(" << get(vertex_index, tgr, source(*itr, tgr)) << "," << get(vertex_index, tgr, target(*itr, tgr)) << ") ";
+ }
+ std::cout << '\n';
+ assert(std::abs(cr.first / cr.second - min_cr) < epsilon);
+
+ return 0;
}
Modified: trunk/libs/graph/example/file_dependencies.cpp
==============================================================================
--- trunk/libs/graph/example/file_dependencies.cpp (original)
+++ trunk/libs/graph/example/file_dependencies.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -136,7 +136,7 @@
// Through the order from topological sort, we are sure that every
// time we are using here is already initialized.
for (tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
- maxdist=std::max(time[source(*j, g)], maxdist);
+ maxdist=(std::max)(time[source(*j, g)], maxdist);
time[*i]=maxdist+1;
}
}
Modified: trunk/libs/graph/example/graph-thingie.cpp
==============================================================================
--- trunk/libs/graph/example/graph-thingie.cpp (original)
+++ trunk/libs/graph/example/graph-thingie.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -76,13 +76,13 @@
const char* dot =
"digraph \
{ \
- graph [name=\"GRAPH\", identifier=\"CX2A1Z\"] \
- \
- a [label=\"NODE_A\", root=\"1\"] \
- b [label=\"NODE_B\", root=\"0\"] \
+ graph [name=\"GRAPH\", identifier=\"CX2A1Z\"] \
+ \
+ a [label=\"NODE_A\", root=\"1\"] \
+ b [label=\"NODE_B\", root=\"0\"] \
\
- a -> b [label=\"EDGE_1\"] \
- b -> c [label=\"EDGE_2\"] \
+ a -> b [label=\"EDGE_1\"] \
+ b -> c [label=\"EDGE_2\"] \
}";
Modified: trunk/libs/graph/example/read_write_dimacs-eg.cpp
==============================================================================
--- trunk/libs/graph/example/read_write_dimacs-eg.cpp (original)
+++ trunk/libs/graph/example/read_write_dimacs-eg.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -103,7 +103,7 @@
capacity[to_sink] -= to_augment;
augmented_flow += to_augment;
}else{
- tCapMapValue to_augment = get(capacity, to_sink);
+ tCapMapValue to_augment = get(capacity, to_sink);
capacity[to_sink] = 0;
capacity[from_source] -= to_augment;
augmented_flow += to_augment;
Modified: trunk/libs/graph/test/cycle_ratio_tests.cpp
==============================================================================
--- trunk/libs/graph/test/cycle_ratio_tests.cpp (original)
+++ trunk/libs/graph/test/cycle_ratio_tests.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -23,15 +23,15 @@
* The graph has two equal cycles with ratio 2/3
*/
static const char test_graph1[] = "digraph G {\
- edge [w1=1, w2=1];\
- 1->2\
- 2->3 [w1=0]\
- 3->4\
- 4->2\
- 1->5\
- 5->6\
- 6->7 [w1=0]\
- 7->5 \
+ edge [w1=1, w2=1];\
+ 1->2\
+ 2->3 [w1=0]\
+ 3->4\
+ 4->2\
+ 1->5\
+ 5->6\
+ 6->7 [w1=0]\
+ 7->5 \
}";
/*!
@@ -45,16 +45,16 @@
*/
static const char test_graph3[] = "\
digraph article {\
- edge [w2 =2];\
- 1->1 [w1 = 1];\
- 1->2 [w1 = 2];\
- 1->4 [w1 = 7];\
- 2->2 [w1 = 3];\
- 2->3 [w1 = 5];\
- 3->2 [w1 = 4];\
- 3->4 [w1 = 3];\
- 4->2 [w1 = 2];\
- 4->3 [w1 = 8];\
+ edge [w2 =2];\
+ 1->1 [w1 = 1];\
+ 1->2 [w1 = 2];\
+ 1->4 [w1 = 7];\
+ 2->2 [w1 = 3];\
+ 2->3 [w1 = 5];\
+ 3->2 [w1 = 4];\
+ 3->4 [w1 = 3];\
+ 4->2 [w1 = 2];\
+ 4->3 [w1 = 8];\
}";
/*!
@@ -83,99 +83,99 @@
* Maximum cycle ratio is 3.58, minimum is 0.294118
*/
static const char test_graph6[]= "digraph test_graph6 {\
- 16;\
- 17;\
+ 16;\
+ 17;\
\
- 1->2 [w1=1, w2=0.1];\
- 2->3 [w1 = 2, w2=3.6];\
- 3->4 [w1=7, w2=8];\
- 4->5 [w1=3.1,w2=0.8];\
- 4->5 [w1 = 4.2, w2=0.6];\
- 4->5 [w1 = 5.3, w2=0.4];\
- 5->6 [w1=-10, w2 = 34.75]\
- 6->1 [w1=100, w2 = 20]\
+ 1->2 [w1=1, w2=0.1];\
+ 2->3 [w1 = 2, w2=3.6];\
+ 3->4 [w1=7, w2=8];\
+ 4->5 [w1=3.1,w2=0.8];\
+ 4->5 [w1 = 4.2, w2=0.6];\
+ 4->5 [w1 = 5.3, w2=0.4];\
+ 5->6 [w1=-10, w2 = 34.75]\
+ 6->1 [w1=100, w2 = 20]\
\
- 1->7 [w1=10, w2 = 20];\
- 7->8 [w1=3.75, w2 = 1.25];\
- 7->8 [w1=30, w2 = 22.2];\
- 8->9 [w1=10, w2 = 20];\
- 9->10 [w1=-2.1, w2 = 30]\
- 10->6 [w1=10, w2 = 20]\
+ 1->7 [w1=10, w2 = 20];\
+ 7->8 [w1=3.75, w2 = 1.25];\
+ 7->8 [w1=30, w2 = 22.2];\
+ 8->9 [w1=10, w2 = 20];\
+ 9->10 [w1=-2.1, w2 = 30]\
+ 10->6 [w1=10, w2 = 20]\
\
- 11->12 [w1 = 5, w2=0.45];\
- 12->13 [w1 = 4, w2=0.2];\
- 13->14 [w1 = 3, w2=15.75];\
- 14->11 [w1 = -2.5, w2=0.6];\
- 11->10 [w1 = -8, w2=0.9];\
- 11->10 [w1 = -15, w2=2.9];\
+ 11->12 [w1 = 5, w2=0.45];\
+ 12->13 [w1 = 4, w2=0.2];\
+ 13->14 [w1 = 3, w2=15.75];\
+ 14->11 [w1 = -2.5, w2=0.6];\
+ 11->10 [w1 = -8, w2=0.9];\
+ 11->10 [w1 = -15, w2=2.9];\
\
- 18 -> 19 [w1=18, w2=6];\
- 18 -> 20 [w1=16.3, w2=8.2];\
- 18 -> 21 [w1=-3, w2=15];\
- 18 -> 18 [w1=2, w2=1];\
- 19 -> 18 [w1=0.06, w2=0.01];\
- 19 -> 19 [w1=1, w2=1.2];\
- 19 -> 20 [w1=5, w2=2];\
- 19 -> 21 [w1=3, w2=0.1];\
- 20 -> 18 [w1=4, w2=0.2];\
- 20 -> 19 [w1=11, w2=21];\
- 20 -> 20 [w1=6, w2=5];\
- 20 -> 21 [w1=7, w2=1];\
- 21 -> 18 [w1=8, w2=2];\
- 21 -> 19 [w1=12, w2=6];\
- 21 -> 20 [w1=7.5, w2=4.3];\
- 21 -> 21 [w1=1.25, w2=2.15];\
+ 18 -> 19 [w1=18, w2=6];\
+ 18 -> 20 [w1=16.3, w2=8.2];\
+ 18 -> 21 [w1=-3, w2=15];\
+ 18 -> 18 [w1=2, w2=1];\
+ 19 -> 18 [w1=0.06, w2=0.01];\
+ 19 -> 19 [w1=1, w2=1.2];\
+ 19 -> 20 [w1=5, w2=2];\
+ 19 -> 21 [w1=3, w2=0.1];\
+ 20 -> 18 [w1=4, w2=0.2];\
+ 20 -> 19 [w1=11, w2=21];\
+ 20 -> 20 [w1=6, w2=5];\
+ 20 -> 21 [w1=7, w2=1];\
+ 21 -> 18 [w1=8, w2=2];\
+ 21 -> 19 [w1=12, w2=6];\
+ 21 -> 20 [w1=7.5, w2=4.3];\
+ 21 -> 21 [w1=1.25, w2=2.15];\
}";
using namespace boost;
-typedef property<boost::vertex_index_t, int, boost::property<boost::vertex_name_t, std::string> > vertex_props_t;
+typedef property<boost::vertex_index_t, int, boost::property<boost::vertex_name_t, std::string> > vertex_props_t;
template <typename EdgeWeight1, typename EdgeWeight2> struct Graph {
- typedef typename boost::property<boost::edge_weight_t, EdgeWeight1, typename boost::property<boost::edge_weight2_t,
- EdgeWeight2, boost::property<boost::edge_index_t, int> > > edge_props_t;
- typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, vertex_props_t, edge_props_t> type;
+ typedef typename boost::property<boost::edge_weight_t, EdgeWeight1, typename boost::property<boost::edge_weight2_t,
+ EdgeWeight2, boost::property<boost::edge_index_t, int> > > edge_props_t;
+ typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, vertex_props_t, edge_props_t> type;
};
typedef Graph<int, int>::type GraphInt;
typedef Graph<double, double>::type GraphReal;
template <typename TW1, typename TW2> struct CEdgeProps {
- CEdgeProps(TW1 w1 = 1, TW2 w2 = 2) : m_w1(w1), m_w2(w2), m_edge_index((std::numeric_limits<int>::max)()) {}
- TW1 m_w1;
- TW2 m_w2;
- int m_edge_index;
+ CEdgeProps(TW1 w1 = 1, TW2 w2 = 2) : m_w1(w1), m_w2(w2), m_edge_index((std::numeric_limits<int>::max)()) {}
+ TW1 m_w1;
+ TW2 m_w2;
+ int m_edge_index;
};
-typedef adjacency_matrix<directedS, no_property, CEdgeProps<int, int> > GraphMInt;
-
+typedef adjacency_matrix<directedS, no_property, CEdgeProps<int, int> > GraphMInt;
+
///Create "tokens_map" for reading graph properties from .dot file
template <typename TGraph>
-void make_dynamic_properties(TGraph& g, dynamic_properties& p)
+void make_dynamic_properties(TGraph& g, dynamic_properties& p)
{
- p.property("node_id", get(vertex_name, g));
- p.property("label", get(edge_weight, g));
- p.property("w1", get(edge_weight, g));
- p.property("w2", get(edge_weight2, g));
+ p.property("node_id", get(vertex_name, g));
+ p.property("label", get(edge_weight, g));
+ p.property("w1", get(edge_weight, g));
+ p.property("w2", get(edge_weight2, g));
}
template <typename TGraph>
void read_data1(std::istream& is, TGraph& g)
{
- dynamic_properties p;
- make_dynamic_properties(g, p);
- read_graphviz(is, g, p);
- std::cout << "Number of vertices: " << num_vertices(g) << "\n";
- std::cout << "Number of edges: " << num_edges(g) << "\n";
- int i = 0;
- BGL_FORALL_VERTICES_T(vd, g, TGraph) put(vertex_index, g, vd, i++);
- i=0;
- BGL_FORALL_EDGES_T(ed, g, TGraph) put(edge_index, g, ed, i++);
+ dynamic_properties p;
+ make_dynamic_properties(g, p);
+ read_graphviz(is, g, p);
+ std::cout << "Number of vertices: " << num_vertices(g) << "\n";
+ std::cout << "Number of edges: " << num_edges(g) << "\n";
+ int i = 0;
+ BGL_FORALL_VERTICES_T(vd, g, TGraph) put(vertex_index, g, vd, i++);
+ i=0;
+ BGL_FORALL_EDGES_T(ed, g, TGraph) put(edge_index, g, ed, i++);
}
template <typename TGraph>
void read_data(const char* file, TGraph& g)
{
- std::cout << "Reading data from file: " << file << "\n";
- std::ifstream ifs(file);
- BOOST_REQUIRE(ifs.good());
- read_data1(ifs, g);
+ std::cout << "Reading data from file: " << file << "\n";
+ std::ifstream ifs(file);
+ BOOST_REQUIRE(ifs.good());
+ read_data1(ifs, g);
}
int test_main(int argc, char* argv[])
@@ -183,108 +183,108 @@
std::string input_file = "cycle_ratio_s382.90.dot";
if (argc > 1) input_file = argv[1];
- const double epsilon = 0.00000001;
- double min_cr, max_cr; ///Minimum and maximum cycle ratio
- typedef std::vector<graph_traits<GraphInt>::edge_descriptor> ccInt_t;
- typedef std::vector<graph_traits<GraphReal>::edge_descriptor> ccReal_t;
- ccInt_t cc; ///For storing critical edges
-
- GraphInt tg;
- property_map<GraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
- property_map<GraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
- property_map<GraphInt, edge_weight2_t>::type ew2m = ew2m;
-
- std::istringstream iss(test_graph1);
- read_data1(/*std::istringstream(test_graph1)*/iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
- std::cout << "Maximum cycle ratio is " << max_cr << "\n";
- BOOST_CHECK(std::abs( max_cr - 0.666666666) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph2);
- read_data1(iss, tg);
- BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m) + (std::numeric_limits<int>::max)()) < epsilon );
- BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), 1000) - 1000) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph3);
- read_data1(iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), -1);
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- BOOST_CHECK(std::abs( max_cr - 2.75) < epsilon );
- double maxmc = maximum_mean_cycle(tg, vim, ew1m, get(edge_index, tg));
- std::cout << "Maximum mean cycle is " << maxmc << '\n';
- BOOST_CHECK(std::abs( maxmc - 5.5) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph4);
- read_data1(iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- BOOST_CHECK(std::abs( max_cr - 2.5) < epsilon );
- min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index, tg));
- std::cout << "Minimum cycle ratio is " << min_cr << '\n';
- BOOST_CHECK(std::abs( min_cr - 0.5) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph5);
- read_data1(iss, tg);
- min_cr = minimum_cycle_ratio_good_graph(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc);
- BOOST_CHECK(std::abs( min_cr - 0.666666666) < epsilon );
- std::cout << "Minimum cycle ratio is " << min_cr << "\n";
- std::cout << "Critical cycle is:\n";
- for (ccInt_t::iterator itr = cc.begin(); itr != cc.end(); ++itr) {
- std::cout << "(" << get(vertex_name, tg, source(*itr, tg)) << "," << get(vertex_name, tg, target(*itr, tg)) << ") ";
- }
- std::cout << '\n';
- tg.clear();
-
- /**/read_data(input_file.c_str(), tg);
- min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc, 2);
- std::cout << "Minimum cycle ratio is " << min_cr << "\n";
- BOOST_CHECK(std::abs(min_cr - 0.33333333333) < epsilon );
- std::cout << "Critical cycle is:\n";
- for (ccInt_t::iterator it = cc.begin(); it != cc.end(); ++it)
- {
- std::cout << "(" << get(vertex_name, tg, source(*it, tg)) << "," << get(vertex_name, tg, target(*it, tg)) << ") ";
- }
- std::cout << '\n';
- tg.clear();
-
- GraphReal tgr;
- ccReal_t cc1;
-
- iss.clear(); iss.str(test_graph6);
- read_data1(iss, tgr);
- max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
- *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
- std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
- min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr),
- get(edge_index, tgr), &cc, pl_infnt);
- std::cout << "Minimal cycle ratio is " << min_cr << '\n';
- std::pair<double, double> cr(.0,.0);
- std::cout << "Critical cycle is:\n";
- for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
- {
- cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
- std::cout << "(" << get(vertex_name, tgr, source(*itr, tgr)) << "," << get(vertex_name, tgr, target(*itr, tgr)) << ") ";
- }
- BOOST_CHECK(std::abs(cr.first / cr.second - min_cr) < epsilon);
- std::cout << '\n';
-
- GraphMInt gm(10);
- typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
- typedef graph_traits<GraphMInt>::edge_descriptor EdgeM;
- VertexItM vi1, vi2, vi_end;
- for (tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
- {
- for (vi2 = vertices(gm).first; vi2 != vi_end; ++vi2)
- add_edge(*vi1, *vi2, gm);
- }
- max_cr = maximum_cycle_ratio(gm, get(vertex_index, gm), get(&CEdgeProps<int, int>::m_w1, gm), get(&CEdgeProps<int, int>::m_w2, gm));
- BOOST_CHECK(std::abs(max_cr - 0.5) < epsilon);
- return 0;
+ const double epsilon = 0.00000001;
+ double min_cr, max_cr; ///Minimum and maximum cycle ratio
+ typedef std::vector<graph_traits<GraphInt>::edge_descriptor> ccInt_t;
+ typedef std::vector<graph_traits<GraphReal>::edge_descriptor> ccReal_t;
+ ccInt_t cc; ///For storing critical edges
+
+ GraphInt tg;
+ property_map<GraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
+ property_map<GraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
+ property_map<GraphInt, edge_weight2_t>::type ew2m = ew2m;
+
+ std::istringstream iss(test_graph1);
+ read_data1(/*std::istringstream(test_graph1)*/iss, tg);
+ max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
+ std::cout << "Maximum cycle ratio is " << max_cr << "\n";
+ BOOST_CHECK(std::abs( max_cr - 0.666666666) < epsilon );
+ tg.clear();
+
+ iss.clear(); iss.str(test_graph2);
+ read_data1(iss, tg);
+ BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m) + (std::numeric_limits<int>::max)()) < epsilon );
+ BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), 1000) - 1000) < epsilon );
+ tg.clear();
+
+ iss.clear(); iss.str(test_graph3);
+ read_data1(iss, tg);
+ max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), -1);
+ std::cout << "Maximum cycle ratio is " << max_cr << '\n';
+ BOOST_CHECK(std::abs( max_cr - 2.75) < epsilon );
+ double maxmc = maximum_mean_cycle(tg, vim, ew1m, get(edge_index, tg));
+ std::cout << "Maximum mean cycle is " << maxmc << '\n';
+ BOOST_CHECK(std::abs( maxmc - 5.5) < epsilon );
+ tg.clear();
+
+ iss.clear(); iss.str(test_graph4);
+ read_data1(iss, tg);
+ max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
+ std::cout << "Maximum cycle ratio is " << max_cr << '\n';
+ BOOST_CHECK(std::abs( max_cr - 2.5) < epsilon );
+ min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index, tg));
+ std::cout << "Minimum cycle ratio is " << min_cr << '\n';
+ BOOST_CHECK(std::abs( min_cr - 0.5) < epsilon );
+ tg.clear();
+
+ iss.clear(); iss.str(test_graph5);
+ read_data1(iss, tg);
+ min_cr = minimum_cycle_ratio_good_graph(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc);
+ BOOST_CHECK(std::abs( min_cr - 0.666666666) < epsilon );
+ std::cout << "Minimum cycle ratio is " << min_cr << "\n";
+ std::cout << "Critical cycle is:\n";
+ for (ccInt_t::iterator itr = cc.begin(); itr != cc.end(); ++itr) {
+ std::cout << "(" << get(vertex_name, tg, source(*itr, tg)) << "," << get(vertex_name, tg, target(*itr, tg)) << ") ";
+ }
+ std::cout << '\n';
+ tg.clear();
+
+ /**/read_data(input_file.c_str(), tg);
+ min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc, 2);
+ std::cout << "Minimum cycle ratio is " << min_cr << "\n";
+ BOOST_CHECK(std::abs(min_cr - 0.33333333333) < epsilon );
+ std::cout << "Critical cycle is:\n";
+ for (ccInt_t::iterator it = cc.begin(); it != cc.end(); ++it)
+ {
+ std::cout << "(" << get(vertex_name, tg, source(*it, tg)) << "," << get(vertex_name, tg, target(*it, tg)) << ") ";
+ }
+ std::cout << '\n';
+ tg.clear();
+
+ GraphReal tgr;
+ ccReal_t cc1;
+
+ iss.clear(); iss.str(test_graph6);
+ read_data1(iss, tgr);
+ max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
+ std::cout << "Maximum cycle ratio is " << max_cr << '\n';
+ double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
+ *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
+ std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
+ min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr),
+ get(edge_index, tgr), &cc, pl_infnt);
+ std::cout << "Minimal cycle ratio is " << min_cr << '\n';
+ std::pair<double, double> cr(.0,.0);
+ std::cout << "Critical cycle is:\n";
+ for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
+ {
+ cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
+ std::cout << "(" << get(vertex_name, tgr, source(*itr, tgr)) << "," << get(vertex_name, tgr, target(*itr, tgr)) << ") ";
+ }
+ BOOST_CHECK(std::abs(cr.first / cr.second - min_cr) < epsilon);
+ std::cout << '\n';
+
+ GraphMInt gm(10);
+ typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
+ typedef graph_traits<GraphMInt>::edge_descriptor EdgeM;
+ VertexItM vi1, vi2, vi_end;
+ for (tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
+ {
+ for (vi2 = vertices(gm).first; vi2 != vi_end; ++vi2)
+ add_edge(*vi1, *vi2, gm);
+ }
+ max_cr = maximum_cycle_ratio(gm, get(vertex_index, gm), get(&CEdgeProps<int, int>::m_w1, gm), get(&CEdgeProps<int, int>::m_w2, gm));
+ BOOST_CHECK(std::abs(max_cr - 0.5) < epsilon);
+ return 0;
}
Modified: trunk/libs/graph/test/graphml_test.cpp
==============================================================================
--- trunk/libs/graph/test/graphml_test.cpp (original)
+++ trunk/libs/graph/test/graphml_test.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -71,11 +71,11 @@
graph_traits<graph_t>::vertex_iterator v, v_end;
for (tie(v,v_end) = vertices(g); v != v_end; ++v)
- assert(get(vertex_color_t(), g, *v) == get(vertex_color_t(), g2, *v));
+ assert(get(vertex_color_t(), g, *v) == get(vertex_color_t(), g2, *v));
graph_traits<graph_t>::edge_iterator e, e_end;
for (tie(e,e_end) = edges(g); e != e_end; ++e)
- assert(get(edge_weight_t(), g, *e) == get(edge_weight_t(), g2, *e));
+ assert(get(edge_weight_t(), g, *e) == get(edge_weight_t(), g2, *e));
return 0;
}
Modified: trunk/libs/graph/test/named_vertices_test.cpp
==============================================================================
--- trunk/libs/graph/test/named_vertices_test.cpp (original)
+++ trunk/libs/graph/test/named_vertices_test.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -71,7 +71,7 @@
BGL_FORALL_VERTICES(city, map, RoadMap)
std::cout << map[city].name << ", population " << map[city].population
- << std::endl;
+ << std::endl;
BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington);
BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis);
@@ -83,7 +83,7 @@
BGL_FORALL_EDGES(road, map, RoadMap)
std::cout << map[source(road, map)].name << " -> "
- << map[target(road, map)].name << std::endl;
+ << map[target(road, map)].name << std::endl;
BOOST_CHECK(map[*find_vertex("Cincinnatti", map)].population == -1);
Modified: trunk/libs/graph/test/serialize.cpp
==============================================================================
--- trunk/libs/graph/test/serialize.cpp (original)
+++ trunk/libs/graph/test/serialize.cpp 2009-01-21 13:59:38 EST (Wed, 21 Jan 2009)
@@ -52,15 +52,15 @@
std::ofstream ofs("./kevin-bacon2.dat");
archive::xml_oarchive oa(ofs);
Graph g;
- vertex_properties vp;
- vp.name = "A";
- vd_type A = add_vertex( vp, g );
- vp.name = "B";
- vd_type B = add_vertex( vp, g );
-
- edge_properties ep;
- ep.name = "a";
- add_edge( A, B, ep, g);
+ vertex_properties vp;
+ vp.name = "A";
+ vd_type A = add_vertex( vp, g );
+ vp.name = "B";
+ vd_type B = add_vertex( vp, g );
+
+ edge_properties ep;
+ ep.name = "a";
+ add_edge( A, B, ep, g);
oa << BOOST_SERIALIZATION_NVP(g);
@@ -74,7 +74,7 @@
Graph g;
ia >> BOOST_SERIALIZATION_NVP(g);
- if (!( g[*(vertices( g ).first)].name == "A" )) return -1;
+ if (!( g[*(vertices( g ).first)].name == "A" )) return -1;
Graph_no_edge_property g_n;
ia >> BOOST_SERIALIZATION_NVP(g_n);