|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50933 - in branches/release: boost/graph boost/graph/detail boost/graph/planar_detail libs/graph/doc libs/graph/example libs/graph/src libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-01-31 15:06:26
Author: jewillco
Date: 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
New Revision: 50933
URL: http://svn.boost.org/trac/boost/changeset/50933
Log:
Ported bug fixes over from trunk
Text files modified:
branches/release/boost/graph/adjacency_list.hpp | 2
branches/release/boost/graph/detail/read_graphviz_spirit.hpp | 69 +++---
branches/release/boost/graph/detail/sparse_ordering.hpp | 4
branches/release/boost/graph/floyd_warshall_shortest.hpp | 14
branches/release/boost/graph/howard_cycle_ratio.hpp | 2
branches/release/boost/graph/is_kuratowski_subgraph.hpp | 14
branches/release/boost/graph/is_straight_line_drawing.hpp | 2
branches/release/boost/graph/johnson_all_pairs_shortest.hpp | 4
branches/release/boost/graph/kolmogorov_max_flow.hpp | 10
branches/release/boost/graph/make_biconnected_planar.hpp | 2
branches/release/boost/graph/max_cardinality_matching.hpp | 10
branches/release/boost/graph/named_graph.hpp | 28 +-
branches/release/boost/graph/planar_canonical_ordering.hpp | 41 ++--
branches/release/boost/graph/planar_detail/boyer_myrvold_impl.hpp | 28 +-
branches/release/boost/graph/planar_detail/face_iterators.hpp | 2
branches/release/boost/graph/r_c_shortest_paths.hpp | 2
branches/release/boost/graph/read_dimacs.hpp | 2
branches/release/boost/graph/relax.hpp | 9
branches/release/boost/graph/sloan_ordering.hpp | 2
branches/release/libs/graph/doc/edmonds_karp_max_flow.html | 12
branches/release/libs/graph/doc/floyd_warshall_shortest.html | 12
branches/release/libs/graph/doc/metric_tsp_approx.html | 2
branches/release/libs/graph/doc/table_of_contents.html | 6
branches/release/libs/graph/example/cycle_ratio_example.cpp | 106 +++++-----
branches/release/libs/graph/example/file_dependencies.cpp | 2
branches/release/libs/graph/example/graph-thingie.cpp | 12
branches/release/libs/graph/example/read_write_dimacs-eg.cpp | 2
branches/release/libs/graph/src/read_graphviz_spirit.cpp | 2
branches/release/libs/graph/test/cycle_ratio_tests.cpp | 376 ++++++++++++++++++++--------------------
branches/release/libs/graph/test/floyd_warshall_test.cpp | 29 --
branches/release/libs/graph/test/graphml_test.cpp | 4
branches/release/libs/graph/test/named_vertices_test.cpp | 4
branches/release/libs/graph/test/serialize.cpp | 20 +-
33 files changed, 410 insertions(+), 426 deletions(-)
Modified: branches/release/boost/graph/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/adjacency_list.hpp (original)
+++ branches/release/boost/graph/adjacency_list.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/detail/read_graphviz_spirit.hpp
==============================================================================
--- branches/release/boost/graph/detail/read_graphviz_spirit.hpp (original)
+++ branches/release/boost/graph/detail/read_graphviz_spirit.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -1,4 +1,4 @@
-// Copyright 2004-5 Trustees of Indiana University
+// Copyright 2004-9 Trustees of Indiana University
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -28,17 +28,18 @@
#define BOOST_SPIRIT_CLOSURE_LIMIT 6
-#include <boost/spirit/iterator/multi_pass.hpp>
-#include <boost/spirit/core.hpp>
-#include <boost/spirit/utility/confix.hpp>
-#include <boost/spirit/utility/distinct.hpp>
-#include <boost/spirit/utility/lists.hpp>
-#include <boost/spirit/utility/escape_char.hpp>
-#include <boost/spirit/attribute.hpp>
-#include <boost/spirit/dynamic.hpp>
-#include <boost/spirit/actor.hpp>
-#include <boost/spirit/phoenix.hpp>
-#include <boost/spirit/phoenix/binders.hpp>
+#include <boost/spirit/include/classic_multi_pass.hpp>
+#include <boost/spirit/include/classic_core.hpp>
+#include <boost/spirit/include/classic_confix.hpp>
+#include <boost/spirit/include/classic_distinct.hpp>
+#include <boost/spirit/include/classic_lists.hpp>
+#include <boost/spirit/include/classic_escape_char.hpp>
+#include <boost/spirit/include/classic_attribute.hpp>
+#include <boost/spirit/include/classic_dynamic.hpp>
+#include <boost/spirit/include/classic_actor.hpp>
+#include <boost/spirit/include/classic_closure.hpp>
+#include <boost/spirit/include/phoenix1.hpp>
+#include <boost/spirit/include/phoenix1_binders.hpp>
#include <boost/ref.hpp>
#include <boost/function/function2.hpp>
#include <boost/type_traits/is_same.hpp>
@@ -93,25 +94,25 @@
/////////////////////////////////////////////////////////////////////////////
// Stack frames used by semantic actions
/////////////////////////////////////////////////////////////////////////////
-struct id_closure : boost::spirit::closure<id_closure, node_t> {
+struct id_closure : boost::spirit::classic::closure<id_closure, node_t> {
member1 name;
};
-struct node_id_closure : boost::spirit::closure<node_id_closure, node_t> {
+struct node_id_closure : boost::spirit::classic::closure<node_id_closure, node_t> {
member1 name;
};
-struct attr_list_closure : boost::spirit::closure<attr_list_closure, actor_t> {
+struct attr_list_closure : boost::spirit::classic::closure<attr_list_closure, actor_t> {
member1 prop_actor;
};
-struct property_closure : boost::spirit::closure<property_closure, id_t, id_t> {
+struct property_closure : boost::spirit::classic::closure<property_closure, id_t, id_t> {
member1 key;
member2 value;
};
-struct data_stmt_closure : boost::spirit::closure<data_stmt_closure,
+struct data_stmt_closure : boost::spirit::classic::closure<data_stmt_closure,
nodes_t,nodes_t,edge_stack_t,bool,node_t> {
member1 sources;
member2 dests;
@@ -120,7 +121,7 @@
member5 active_node;
};
-struct subgraph_closure : boost::spirit::closure<subgraph_closure,
+struct subgraph_closure : boost::spirit::classic::closure<subgraph_closure,
nodes_t, edges_t, node_t> {
member1 nodes;
member2 edges;
@@ -132,7 +133,7 @@
/////////////////////////////////////////////////////////////////////////////
// Grammar for a dot file.
-struct dot_grammar : public boost::spirit::grammar<dot_grammar> {
+struct dot_grammar : public boost::spirit::classic::grammar<dot_grammar> {
mutate_graph& graph_;
explicit dot_grammar(mutate_graph& graph) : graph_(graph) { }
@@ -141,7 +142,7 @@
definition(dot_grammar const& self) : self(self), subgraph_depth(0),
keyword_p("0-9a-zA-Z_") {
- using namespace boost::spirit;
+ using namespace boost::spirit::classic;
using namespace phoenix;
// RG - Future Work
@@ -282,7 +283,7 @@
} // definition()
- typedef boost::spirit::rule<ScannerT> rule_t;
+ typedef boost::spirit::classic::rule<ScannerT> rule_t;
rule_t const& start() const { return the_grammar; }
@@ -492,21 +493,21 @@
int subgraph_depth;
// Keywords;
- const boost::spirit::distinct_parser<> keyword_p;
+ const boost::spirit::classic::distinct_parser<> keyword_p;
//
// rules that make up the grammar
//
- boost::spirit::rule<ScannerT,id_closure::context_t> ID;
- boost::spirit::rule<ScannerT,property_closure::context_t> a_list;
- boost::spirit::rule<ScannerT,attr_list_closure::context_t> attr_list;
+ boost::spirit::classic::rule<ScannerT,id_closure::context_t> ID;
+ boost::spirit::classic::rule<ScannerT,property_closure::context_t> a_list;
+ boost::spirit::classic::rule<ScannerT,attr_list_closure::context_t> attr_list;
rule_t port_location;
rule_t port_angle;
rule_t port;
- boost::spirit::rule<ScannerT,node_id_closure::context_t> node_id;
- boost::spirit::rule<ScannerT,property_closure::context_t> graph_stmt;
+ boost::spirit::classic::rule<ScannerT,node_id_closure::context_t> node_id;
+ boost::spirit::classic::rule<ScannerT,property_closure::context_t> graph_stmt;
rule_t attr_stmt;
- boost::spirit::rule<ScannerT,data_stmt_closure::context_t> data_stmt;
- boost::spirit::rule<ScannerT,subgraph_closure::context_t> subgraph;
+ boost::spirit::classic::rule<ScannerT,data_stmt_closure::context_t> data_stmt;
+ boost::spirit::classic::rule<ScannerT,subgraph_closure::context_t> subgraph;
rule_t edgeop;
rule_t edgeRHS;
rule_t stmt;
@@ -544,7 +545,7 @@
//
// dot_skipper - GraphViz whitespace and comment skipper
//
-struct dot_skipper : public boost::spirit::grammar<dot_skipper>
+struct dot_skipper : public boost::spirit::classic::grammar<dot_skipper>
{
dot_skipper() {}
@@ -552,7 +553,7 @@
struct definition
{
definition(dot_skipper const& /*self*/) {
- using namespace boost::spirit;
+ using namespace boost::spirit::classic;
using namespace phoenix;
// comment forms
skip = eol_p >> comment_p("#")
@@ -570,8 +571,8 @@
#endif
}
- boost::spirit::rule<ScannerT> skip;
- boost::spirit::rule<ScannerT> const&
+ boost::spirit::classic::rule<ScannerT> skip;
+ boost::spirit::classic::rule<ScannerT> const&
start() const { return skip; }
}; // definition
}; // dot_skipper
@@ -584,7 +585,7 @@
MutableGraph& graph, dynamic_properties& dp,
std::string const& node_id = "node_id") {
using namespace boost;
- using namespace boost::spirit;
+ using namespace boost::spirit::classic;
typedef MultiPassIterator iterator_t;
typedef skip_parser_iteration_policy< boost::detail::graph::dot_skipper>
Modified: branches/release/boost/graph/detail/sparse_ordering.hpp
==============================================================================
--- branches/release/boost/graph/detail/sparse_ordering.hpp (original)
+++ branches/release/boost/graph/detail/sparse_ordering.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -128,7 +128,7 @@
//
template <class Graph, class Vertex, class ColorMap, class DegreeMap>
Vertex
- pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
+ pseudo_peripheral_pair(Graph const& G, const Vertex& u, int& ecc,
ColorMap color, DegreeMap degree)
{
typedef typename property_traits<ColorMap>::value_type ColorValue;
@@ -152,7 +152,7 @@
// of the ordering generated by RCM.
//
template <class Graph, class Vertex, class Color, class Degree>
- Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
+ Vertex find_starting_node(Graph const& G, Vertex r, Color color, Degree degree)
{
Vertex x, y;
int eccen_r, eccen_x;
Modified: branches/release/boost/graph/floyd_warshall_shortest.hpp
==============================================================================
--- branches/release/boost/graph/floyd_warshall_shortest.hpp (original)
+++ branches/release/boost/graph/floyd_warshall_shortest.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- branches/release/boost/graph/howard_cycle_ratio.hpp (original)
+++ branches/release/boost/graph/howard_cycle_ratio.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/is_kuratowski_subgraph.hpp
==============================================================================
--- branches/release/boost/graph/is_kuratowski_subgraph.hpp (original)
+++ branches/release/boost/graph/is_kuratowski_subgraph.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -97,6 +97,8 @@
}
+ enum target_graph_t { tg_k_3_3, tg_k_5};
+
} // namespace detail
@@ -123,9 +125,7 @@
typedef adjacency_list<vecS, vecS, undirectedS> small_graph_t;
- enum target_graph_t { k_3_3, k_5};
-
- target_graph_t target_graph = k_3_3; //unless we decide otherwise later
+ detail::target_graph_t target_graph = detail::tg_k_3_3; //unless we decide otherwise later
static small_graph_t K_5(detail::make_K_5<small_graph_t>());
@@ -245,11 +245,11 @@
for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
if (neighbors[*vi].size() == 4)
{
- target_graph = k_5;
+ target_graph = detail::tg_k_5;
break;
}
- if (target_graph == k_3_3)
+ if (target_graph == detail::tg_k_3_3)
break;
}
@@ -299,11 +299,11 @@
}
}
- if (target_graph == k_5)
+ if (target_graph == detail::tg_k_5)
{
return isomorphism(K_5,contracted_graph);
}
- else //target_graph == k_3_3
+ else //target_graph == tg_k_3_3
{
return isomorphism(K_3_3,contracted_graph);
}
Modified: branches/release/boost/graph/is_straight_line_drawing.hpp
==============================================================================
--- branches/release/boost/graph/is_straight_line_drawing.hpp (original)
+++ branches/release/boost/graph/is_straight_line_drawing.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/johnson_all_pairs_shortest.hpp
==============================================================================
--- branches/release/boost/graph/johnson_all_pairs_shortest.hpp (original)
+++ branches/release/boost/graph/johnson_all_pairs_shortest.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -113,7 +113,7 @@
for (tie(e, e_end) = edges(g2); e != e_end; ++e) {
typename Traits2::vertex_descriptor a = source(*e, g2),
b = target(*e, g2);
- put(w_hat, *e, get(w, *e) + get(h, a) - get(h, b));
+ put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b))));
}
for (tie(u, u_end) = vertices(g2); u != u_end; ++u) {
dijkstra_visitor<> dvis;
@@ -123,7 +123,7 @@
if (*u != s && *v != s) {
typename Traits1::vertex_descriptor u1, v1;
u1 = verts1[id2[*u]]; v1 = verts1[id2[*v]];
- D[id2[*u]-1][id2[*v]-1] = get(d, *v) + get(h, *v) - get(h, *u);
+ D[id2[*u]-1][id2[*v]-1] = combine(get(d, *v), (get(h, *v) - get(h, *u)));
}
}
}
Modified: branches/release/boost/graph/kolmogorov_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/kolmogorov_max_flow.hpp (original)
+++ branches/release/boost/graph/kolmogorov_max_flow.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/make_biconnected_planar.hpp
==============================================================================
--- branches/release/boost/graph/make_biconnected_planar.hpp (original)
+++ branches/release/boost/graph/make_biconnected_planar.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: 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 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/named_graph.hpp
==============================================================================
--- branches/release/boost/graph/named_graph.hpp (original)
+++ branches/release/boost/graph/named_graph.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/planar_canonical_ordering.hpp
==============================================================================
--- branches/release/boost/graph/planar_canonical_ordering.hpp (original)
+++ branches/release/boost/graph/planar_canonical_ordering.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -21,6 +21,14 @@
{
+ namespace detail {
+ enum planar_canonical_ordering_state
+ {PCO_PROCESSED,
+ PCO_UNPROCESSED,
+ PCO_ONE_NEIGHBOR_PROCESSED,
+ PCO_READY_TO_BE_PROCESSED};
+ }
+
template<typename Graph,
typename PlanarEmbedding,
typename OutputIterator,
@@ -47,16 +55,11 @@
<typename std::vector<std::size_t>::iterator, VertexIndexMap>
vertex_to_size_t_map_t;
- enum {PROCESSED,
- UNPROCESSED,
- ONE_NEIGHBOR_PROCESSED,
- READY_TO_BE_PROCESSED};
-
std::vector<vertex_t> processed_neighbor_vector(num_vertices(g));
vertex_to_vertex_map_t processed_neighbor
(processed_neighbor_vector.begin(), vm);
- std::vector<std::size_t> status_vector(num_vertices(g), UNPROCESSED);
+ std::vector<std::size_t> status_vector(num_vertices(g), detail::PCO_UNPROCESSED);
vertex_to_size_t_map_t status(status_vector.begin(), vm);
std::list<vertex_t> ready_to_be_processed;
@@ -73,16 +76,16 @@
}
ready_to_be_processed.push_back(first_vertex);
- status[first_vertex] = READY_TO_BE_PROCESSED;
+ status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
ready_to_be_processed.push_back(second_vertex);
- status[second_vertex] = READY_TO_BE_PROCESSED;
+ status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
while(!ready_to_be_processed.empty())
{
vertex_t u = ready_to_be_processed.front();
ready_to_be_processed.pop_front();
- if (status[u] != READY_TO_BE_PROCESSED && u != second_vertex)
+ if (status[u] != detail::PCO_READY_TO_BE_PROCESSED && u != second_vertex)
continue;
embedding_iterator_t ei, ei_start, ei_end;
@@ -131,12 +134,12 @@
}
- if (status[v] == UNPROCESSED)
+ if (status[v] == detail::PCO_UNPROCESSED)
{
- status[v] = ONE_NEIGHBOR_PROCESSED;
+ status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
processed_neighbor[v] = u;
}
- else if (status[v] == ONE_NEIGHBOR_PROCESSED)
+ else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
{
vertex_t x = processed_neighbor[v];
//are edges (v,u) and (v,x) adjacent in the planar
@@ -152,24 +155,24 @@
)
)
{
- status[v] = READY_TO_BE_PROCESSED;
+ status[v] = detail::PCO_READY_TO_BE_PROCESSED;
}
else
{
- status[v] = READY_TO_BE_PROCESSED + 1;
+ status[v] = detail::PCO_READY_TO_BE_PROCESSED + 1;
}
}
- else if (status[v] > ONE_NEIGHBOR_PROCESSED)
+ else if (status[v] > detail::PCO_ONE_NEIGHBOR_PROCESSED)
{
//check the two edges before and after (v,u) in the planar
//embedding, and update status[v] accordingly
bool processed_before = false;
- if (status[prior_vertex] == PROCESSED)
+ if (status[prior_vertex] == detail::PCO_PROCESSED)
processed_before = true;
bool processed_after = false;
- if (status[next_vertex] == PROCESSED)
+ if (status[next_vertex] == detail::PCO_PROCESSED)
processed_after = true;
if (!processed_before && !processed_after)
@@ -180,14 +183,14 @@
}
- if (status[v] == READY_TO_BE_PROCESSED)
+ if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
ready_to_be_processed.push_back(v);
prior_edge_itr = ei;
}
- status[u] = PROCESSED;
+ status[u] = detail::PCO_PROCESSED;
*ordering = u;
++ordering;
Modified: branches/release/boost/graph/planar_detail/boyer_myrvold_impl.hpp
==============================================================================
--- branches/release/boost/graph/planar_detail/boyer_myrvold_impl.hpp (original)
+++ branches/release/boost/graph/planar_detail/boyer_myrvold_impl.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -25,6 +25,9 @@
namespace boost
{
+ namespace detail {
+ enum bm_case_t{BM_NO_CASE_CHOSEN, BM_CASE_A, BM_CASE_B, BM_CASE_C, BM_CASE_D, BM_CASE_E};
+ }
template<typename LowPointMap, typename DFSParentMap,
typename DFSNumberMap, typename LeastAncestorMap,
@@ -1240,8 +1243,7 @@
vertex_t second_x_y_path_endpoint = graph_traits<Graph>::null_vertex();
vertex_t w_ancestor = v;
- enum case_t{NO_CASE_CHOSEN, CASE_A, CASE_B, CASE_C, CASE_D, CASE_E};
- case_t chosen_case = NO_CASE_CHOSEN;
+ detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN;
std::vector<edge_t> x_external_path;
std::vector<edge_t> y_external_path;
@@ -1403,7 +1405,7 @@
//If v isn't on the same bicomp as x and y, it's a case A
if (bicomp_root != v)
{
- chosen_case = CASE_A;
+ chosen_case = detail::BM_CASE_A;
for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
if (lower_face_vertex[*vi])
@@ -1420,7 +1422,7 @@
}
else if (w != graph_traits<Graph>::null_vertex())
{
- chosen_case = CASE_B;
+ chosen_case = detail::BM_CASE_B;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
@@ -1512,7 +1514,7 @@
//We need to find a valid z, since the x-y path re-defines the lower
//face, and the z we found earlier may now be on the upper face.
- chosen_case = CASE_E;
+ chosen_case = detail::BM_CASE_E;
// The z we've used so far is just an externally active vertex on the
@@ -1631,7 +1633,7 @@
}
else if (previous_vertex == x || previous_vertex == y)
{
- chosen_case = CASE_C;
+ chosen_case = detail::BM_CASE_C;
}
}
@@ -1688,7 +1690,7 @@
if (x_y_path_vertex[current_vertex])
{
- chosen_case = CASE_D;
+ chosen_case = detail::BM_CASE_D;
break;
}
else
@@ -1704,7 +1706,7 @@
- if (chosen_case != CASE_B && chosen_case != CASE_A)
+ if (chosen_case != detail::BM_CASE_B && chosen_case != detail::BM_CASE_A)
{
//Finding z and w.
@@ -1724,7 +1726,7 @@
z_v_path
);
- if (chosen_case == CASE_E)
+ if (chosen_case == detail::BM_CASE_E)
{
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
@@ -1810,11 +1812,11 @@
// a deterministic process, and we can simplify the function
// is_kuratowski_subgraph by cleaning up some edges here.
- if (chosen_case == CASE_B)
+ if (chosen_case == detail::BM_CASE_B)
{
is_in_subgraph[dfs_parent_edge[v]] = false;
}
- else if (chosen_case == CASE_C)
+ else if (chosen_case == detail::BM_CASE_C)
{
// In a case C subgraph, at least one of the x-y path endpoints
// (call it alpha) is above either x or y on the outer face. The
@@ -1857,7 +1859,7 @@
}
}
- else if (chosen_case == CASE_D)
+ else if (chosen_case == detail::BM_CASE_D)
{
// Need to remove both of the edges adjacent to v on the outer face.
// remove the connecting edges from v to bicomp, then
@@ -1868,7 +1870,7 @@
is_in_subgraph[v_dfchild_handle.second_edge()] = false;
}
- else if (chosen_case == CASE_E)
+ else if (chosen_case == detail::BM_CASE_E)
{
// Similarly to case C, if the endpoints of the x-y path are both
// below x and y, we should remove an edge to allow the subgraph to
Modified: branches/release/boost/graph/planar_detail/face_iterators.hpp
==============================================================================
--- branches/release/boost/graph/planar_detail/face_iterators.hpp (original)
+++ branches/release/boost/graph/planar_detail/face_iterators.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/r_c_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/r_c_shortest_paths.hpp (original)
+++ branches/release/boost/graph/r_c_shortest_paths.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/boost/graph/read_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/read_dimacs.hpp (original)
+++ branches/release/boost/graph/read_dimacs.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -250,7 +250,7 @@
/* ----- all is red or error while reading ----- */
- if ( feof (stdin) == 0 ) /* reading error */
+ if ( in.eof() == 0 ) /* reading error */
{ err_no=EN21; goto error; }
if ( no_lines == 0 ) /* empty input */
Modified: branches/release/boost/graph/relax.hpp
==============================================================================
--- branches/release/boost/graph/relax.hpp (original)
+++ branches/release/boost/graph/relax.hpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -24,11 +24,10 @@
{
T operator()(const T& a, const T& b) const {
using namespace std;
- T zero(0);
- T result = a + b;
- if (result < zero && a >= zero && b >= zero)
- return (numeric_limits<T>::max)();
- return result;
+ const T inf = (std::numeric_limits<T>::max)();
+ if (a == inf) return inf;
+ if (b == inf) return inf;
+ return a + b;
}
};
Modified: branches/release/boost/graph/sloan_ordering.hpp
==============================================================================
--- branches/release/boost/graph/sloan_ordering.hpp (original)
+++ branches/release/boost/graph/sloan_ordering.hpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/doc/edmonds_karp_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/edmonds_karp_max_flow.html (original)
+++ branches/release/libs/graph/doc/edmonds_karp_max_flow.html 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -1,10 +1,10 @@
<HTML>
<!--
- -- Copyright (c) Jeremy Siek 2000
- --
- -- Distributed under the Boost Software License, Version 1.0.
- -- (See accompanying file LICENSE_1_0.txt or copy at
- -- http://www.boost.org/LICENSE_1_0.txt)
+ Copyright (c) Jeremy Siek 2000
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
-->
<Head>
<Title>Boost Graph Library: Edmonds-Karp Maximum Flow</Title>
@@ -223,7 +223,7 @@
<HR>
<TABLE>
<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
+<TD nowrap>Copyright © 2000-2001</TD><TD>
<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek_at_[hidden]">jsiek_at_[hidden]</A>)
</TD></TR></TABLE>
Modified: branches/release/libs/graph/doc/floyd_warshall_shortest.html
==============================================================================
--- branches/release/libs/graph/doc/floyd_warshall_shortest.html (original)
+++ branches/release/libs/graph/doc/floyd_warshall_shortest.html 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -1,10 +1,10 @@
<HTML>
<!--
- -- Copyright (c) 2002 Rensselaer Polytechnic Institute
- --
- -- Distributed under the Boost Software License, Version 1.0.
- -- (See accompanying file LICENSE_1_0.txt or copy at
- -- http://www.boost.org/LICENSE_1_0.txt)
+ Copyright (c) 2002 Rensselaer Polytechnic Institute
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
-->
<Head>
<Title>Floyd-Warshall All Pairs Shortest Paths</Title>
@@ -127,7 +127,7 @@
The argument types must match the value type of the <code>WeightMap</code>.
The result type must be the same as the distance value type.<br>
-<b>Default:</b> <code>std::plus<WM></code> with <code>WM = typename property_traits<WeightMap>::value_type</code>
+<b>Default:</b> <code>boost::closed_plus<WM></code> with <code>WM = typename property_traits<WeightMap>::value_type</code>
</blockquote>
IN: <code>distance_inf(WM inf)</code>
Modified: branches/release/libs/graph/doc/metric_tsp_approx.html
==============================================================================
--- branches/release/libs/graph/doc/metric_tsp_approx.html (original)
+++ branches/release/libs/graph/doc/metric_tsp_approx.html 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -172,10 +172,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: branches/release/libs/graph/example/cycle_ratio_example.cpp
==============================================================================
--- branches/release/libs/graph/example/cycle_ratio_example.cpp (original)
+++ branches/release/libs/graph/example/cycle_ratio_example.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/example/file_dependencies.cpp
==============================================================================
--- branches/release/libs/graph/example/file_dependencies.cpp (original)
+++ branches/release/libs/graph/example/file_dependencies.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/example/graph-thingie.cpp
==============================================================================
--- branches/release/libs/graph/example/graph-thingie.cpp (original)
+++ branches/release/libs/graph/example/graph-thingie.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/example/read_write_dimacs-eg.cpp
==============================================================================
--- branches/release/libs/graph/example/read_write_dimacs-eg.cpp (original)
+++ branches/release/libs/graph/example/read_write_dimacs-eg.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/src/read_graphviz_spirit.cpp
==============================================================================
--- branches/release/libs/graph/src/read_graphviz_spirit.cpp (original)
+++ branches/release/libs/graph/src/read_graphviz_spirit.cpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -33,7 +33,7 @@
bool read_graphviz(std::istream& in, mutate_graph& graph)
{
using namespace boost;
- using namespace boost::spirit;
+ using namespace boost::spirit::classic;
typedef std::istream_iterator<char> is_t;
typedef multi_pass<is_t> iterator_t;
Modified: branches/release/libs/graph/test/cycle_ratio_tests.cpp
==============================================================================
--- branches/release/libs/graph/test/cycle_ratio_tests.cpp (original)
+++ branches/release/libs/graph/test/cycle_ratio_tests.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/test/floyd_warshall_test.cpp
==============================================================================
--- branches/release/libs/graph/test/floyd_warshall_test.cpp (original)
+++ branches/release/libs/graph/test/floyd_warshall_test.cpp 2009-01-31 15:06:23 EST (Sat, 31 Jan 2009)
@@ -21,17 +21,6 @@
#include <algorithm>
using namespace boost;
-template <typename T>
-struct inf_plus{
- T operator()(const T& a, const T& b) const {
- T inf = std::numeric_limits<T>::max BOOST_PREVENT_MACRO_SUBSTITUTION();
- if (a == inf || b == inf){
- return inf;
- }
- return a + b;
- }
-};
-
template<typename T>
inline const T& my_min(const T& x, const T& y)
{ return x < y? x : y; }
@@ -125,20 +114,16 @@
bool bellman, floyd1, floyd2, floyd3;
- std::less<int> compare;
- inf_plus<int> combine;
floyd1 =
boost::floyd_warshall_initialized_all_pairs_shortest_paths
(g,
matrix, weight_map(boost::get(boost::edge_weight, g)).
- distance_compare(compare). distance_combine(combine).
distance_inf(int_inf). distance_zero(0));
floyd2 =
boost::floyd_warshall_all_pairs_shortest_paths
(g, matrix3,
- weight_map(local_edge_map). distance_compare(compare).
- distance_combine(combine).
+ weight_map(local_edge_map).
distance_inf(int_inf). distance_zero(0));
floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4);
@@ -153,8 +138,7 @@
(g, vec,
weight_map(boost::get(boost::edge_weight, g)).
distance_map(boost::get(boost::vertex_distance, g)).
- predecessor_map(dummy_map).distance_compare(compare).
- distance_combine(combine));
+ predecessor_map(dummy_map));
distance_row = boost::get(boost::vertex_distance, g);
for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2;
firstv2++){
@@ -302,20 +286,16 @@
bool bellman, floyd1, floyd2, floyd3;
- std::less<int> compare;
- inf_plus<int> combine;
floyd1 =
boost::floyd_warshall_initialized_all_pairs_shortest_paths
(g,
matrix, weight_map(boost::get(boost::edge_weight, g)).
- distance_compare(compare). distance_combine(combine).
distance_inf(int_inf). distance_zero(0));
floyd2 =
boost::floyd_warshall_all_pairs_shortest_paths
(g, matrix3,
- weight_map(local_edge_map). distance_compare(compare).
- distance_combine(combine).
+ weight_map(local_edge_map).
distance_inf(int_inf). distance_zero(0));
floyd3 = boost::floyd_warshall_all_pairs_shortest_paths(g, matrix4);
@@ -330,8 +310,7 @@
(g, vec,
weight_map(boost::get(boost::edge_weight, g)).
distance_map(boost::get(boost::vertex_distance, g)).
- predecessor_map(dummy_map).distance_compare(compare).
- distance_combine(combine));
+ predecessor_map(dummy_map));
distance_row = boost::get(boost::vertex_distance, g);
for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2;
firstv2++){
Modified: branches/release/libs/graph/test/graphml_test.cpp
==============================================================================
--- branches/release/libs/graph/test/graphml_test.cpp (original)
+++ branches/release/libs/graph/test/graphml_test.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/test/named_vertices_test.cpp
==============================================================================
--- branches/release/libs/graph/test/named_vertices_test.cpp (original)
+++ branches/release/libs/graph/test/named_vertices_test.cpp 2009-01-31 15:06:23 EST (Sat, 31 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: branches/release/libs/graph/test/serialize.cpp
==============================================================================
--- branches/release/libs/graph/test/serialize.cpp (original)
+++ branches/release/libs/graph/test/serialize.cpp 2009-01-31 15:06:23 EST (Sat, 31 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);
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