Subject: [Boost-commit] svn:boost r52116 - in trunk: boost boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-04-01 14:07:03
Author: jewillco
Date: 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
New Revision: 52116
URL: http://svn.boost.org/trac/boost/changeset/52116
Log:
Merged more changes from Parallel BGL
Added:
trunk/boost/graph/accounting.hpp (contents, props changed)
trunk/boost/graph/dimacs.hpp (contents, props changed)
trunk/boost/graph/graph_stats.hpp (contents, props changed)
trunk/boost/graph/mesh_graph_generator.hpp (contents, props changed)
trunk/boost/graph/metis.hpp (contents, props changed)
trunk/boost/graph/overloading.hpp (contents, props changed)
trunk/boost/graph/point_traits.hpp (contents, props changed)
trunk/boost/graph/ssca_graph_generator.hpp (contents, props changed)
trunk/boost/graph/st_connected.hpp (contents, props changed)
trunk/boost/graph/vertex_and_edge_range.hpp (contents, props changed)
Text files modified:
trunk/boost/graph/betweenness_centrality.hpp | 19 ++
trunk/boost/graph/breadth_first_search.hpp | 61 ++++++++-
trunk/boost/graph/connected_components.hpp | 10
trunk/boost/graph/dijkstra_shortest_paths.hpp | 36 +++++
trunk/boost/graph/fruchterman_reingold.hpp | 243 +++++++++++++++++++++++++++------------
trunk/boost/graph/graphviz.hpp | 44 ++++--
trunk/boost/graph/named_function_params.hpp | 40 ++++++
trunk/boost/graph/page_rank.hpp | 8
trunk/boost/graph/properties.hpp | 11 +
trunk/boost/graph/random_layout.hpp | 18 +-
trunk/boost/graph/strong_components.hpp | 7
trunk/boost/property_map.hpp | 25 ++++
trunk/boost/vector_property_map.hpp | 5
trunk/libs/graph/test/layout_test.cpp | 26 ++-
14 files changed, 418 insertions(+), 135 deletions(-)
Added: trunk/boost/graph/accounting.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/accounting.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,37 @@
+// Copyright 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_ACCOUNTING_HPP
+#define BOOST_GRAPH_ACCOUNTING_HPP
+
+#include <iomanip>
+#include <iostream>
+#include <string>
+#include <sstream>
+#include <boost/mpi/config.hpp>
+
+namespace boost { namespace graph { namespace accounting {
+
+typedef double time_type;
+
+inline time_type get_time()
+{
+ return MPI_Wtime();
+}
+
+inline std::string print_time(time_type t)
+{
+ std::ostringstream out;
+ out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
+ return out.str();
+}
+
+} } } // end namespace boost::graph::accounting
+
+#endif // BOOST_GRAPH_ACCOUNTING_HPP
+
Modified: trunk/boost/graph/betweenness_centrality.hpp
==============================================================================
--- trunk/boost/graph/betweenness_centrality.hpp (original)
+++ trunk/boost/graph/betweenness_centrality.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -11,6 +11,7 @@
#include <stack>
#include <vector>
+#include <boost/graph/overloading.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/relax.hpp>
@@ -369,7 +370,8 @@
DistanceMap distance, // d
DependencyMap dependency, // delta
PathCountMap path_count, // sigma
- VertexIndexMap vertex_index)
+ VertexIndexMap vertex_index
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
detail::graph::brandes_unweighted_shortest_paths shortest_paths;
@@ -394,7 +396,8 @@
DependencyMap dependency, // delta
PathCountMap path_count, // sigma
VertexIndexMap vertex_index,
- WeightMap weight_map)
+ WeightMap weight_map
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
shortest_paths(weight_map);
@@ -514,7 +517,8 @@
template<typename Graph, typename Param, typename Tag, typename Rest>
void
brandes_betweenness_centrality(const Graph& g,
- const bgl_named_params<Param,Tag,Rest>& params)
+ const bgl_named_params<Param,Tag,Rest>& params
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
typedef bgl_named_params<Param,Tag,Rest> named_params;
@@ -531,7 +535,8 @@
template<typename Graph, typename CentralityMap>
void
-brandes_betweenness_centrality(const Graph& g, CentralityMap centrality)
+brandes_betweenness_centrality(const Graph& g, CentralityMap centrality
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
detail::graph::brandes_betweenness_centrality_dispatch2(
g, centrality, dummy_property_map(), get(vertex_index, g));
@@ -540,7 +545,8 @@
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
void
brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
- EdgeCentralityMap edge_centrality_map)
+ EdgeCentralityMap edge_centrality_map
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
detail::graph::brandes_betweenness_centrality_dispatch2(
g, centrality, edge_centrality_map, get(vertex_index, g));
@@ -570,7 +576,8 @@
// Compute the central point dominance of a graph.
template<typename Graph, typename CentralityMap>
typename property_traits<CentralityMap>::value_type
-central_point_dominance(const Graph& g, CentralityMap centrality)
+central_point_dominance(const Graph& g, CentralityMap centrality
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
using std::max;
Modified: trunk/boost/graph/breadth_first_search.hpp
==============================================================================
--- trunk/boost/graph/breadth_first_search.hpp (original)
+++ trunk/boost/graph/breadth_first_search.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -21,6 +21,8 @@
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/overloading.hpp>
+#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/two_bit_color_map.hpp>
namespace boost {
@@ -101,6 +103,8 @@
breadth_first_visit(g, s, Q, vis, color);
}
+ namespace graph { struct bfs_visitor_event_not_overridden {}; }
+
template <class Visitors = null_visitor>
class bfs_visitor {
@@ -109,40 +113,75 @@
bfs_visitor(Visitors vis) : m_vis(vis) { }
template <class Vertex, class Graph>
- void initialize_vertex(Vertex u, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ initialize_vertex(Vertex u, Graph& g)
+ {
invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Vertex, class Graph>
- void discover_vertex(Vertex u, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ discover_vertex(Vertex u, Graph& g)
+ {
invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Vertex, class Graph>
- void examine_vertex(Vertex u, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ examine_vertex(Vertex u, Graph& g)
+ {
invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Edge, class Graph>
- void examine_edge(Edge e, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ examine_edge(Edge e, Graph& g)
+ {
invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Edge, class Graph>
- void tree_edge(Edge e, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ tree_edge(Edge e, Graph& g)
+ {
invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Edge, class Graph>
- void non_tree_edge(Edge e, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ non_tree_edge(Edge e, Graph& g)
+ {
invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Edge, class Graph>
- void gray_target(Edge e, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ gray_target(Edge e, Graph& g)
+ {
invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Edge, class Graph>
- void black_target(Edge e, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ black_target(Edge e, Graph& g)
+ {
invoke_visitors(m_vis, e, g, ::boost::on_black_target());
+ return graph::bfs_visitor_event_not_overridden();
}
+
template <class Vertex, class Graph>
- void finish_vertex(Vertex u, Graph& g) {
+ graph::bfs_visitor_event_not_overridden
+ finish_vertex(Vertex u, Graph& g)
+ {
invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
+ return graph::bfs_visitor_event_not_overridden();
}
BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)
@@ -175,7 +214,9 @@
typename graph_traits<VertexListGraph>::vertex_descriptor s,
ColorMap color,
BFSVisitor vis,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params,
+ BOOST_GRAPH_ENABLE_IF_MODELS(VertexListGraph, vertex_list_graph_tag,
+ void)* = 0)
{
typedef graph_traits<VertexListGraph> Traits;
// Buffer default
Modified: trunk/boost/graph/connected_components.hpp
==============================================================================
--- trunk/boost/graph/connected_components.hpp (original)
+++ trunk/boost/graph/connected_components.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -15,7 +15,7 @@
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_concepts.hpp>
-
+#include <boost/graph/overloading.hpp>
#include <boost/static_assert.hpp>
namespace boost {
@@ -58,7 +58,8 @@
template <class Graph, class ComponentMap, class P, class T, class R>
inline typename property_traits<ComponentMap>::value_type
connected_components(const Graph& g, ComponentMap c,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
if (num_vertices(g) == 0) return 0;
@@ -77,14 +78,15 @@
template <class Graph, class ComponentMap>
inline typename property_traits<ComponentMap>::value_type
- connected_components(const Graph& g, ComponentMap c)
+ connected_components(const Graph& g, ComponentMap c
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
if (num_vertices(g) == 0) return 0;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
function_requires< WritablePropertyMapConcept<ComponentMap, Vertex> >();
typedef typename boost::graph_traits<Graph>::directed_category directed;
- BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
+ // BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
typedef typename property_traits<ComponentMap>::value_type comp_type;
// c_count initialized to "nil" (with nil represented by (max)())
Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp (original)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -6,6 +6,12 @@
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
+//
+//
+// Revision History:
+// 04 April 2001: Added named parameter variant. (Jeremy Siek)
+// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
+//
#ifndef BOOST_GRAPH_DIJKSTRA_HPP
#define BOOST_GRAPH_DIJKSTRA_HPP
@@ -17,6 +23,7 @@
#include <boost/pending/indirect_cmp.hpp>
#include <boost/graph/exception.hpp>
#include <boost/pending/relaxed_heap.hpp>
+#include <boost/graph/overloading.hpp>
#include <boost/smart_ptr.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/graph/two_bit_color_map.hpp>
@@ -30,6 +37,28 @@
namespace boost {
+ /**
+ * @brief Updates a particular value in a queue used by Dijkstra's
+ * algorithm.
+ *
+ * This routine is called by Dijkstra's algorithm after it has
+ * decreased the distance from the source vertex to the given @p
+ * vertex. By default, this routine will just call @c
+ * Q.update(vertex). However, other queues may provide more
+ * specialized versions of this routine.
+ *
+ * @param Q the queue that will be updated.
+ * @param vertex the vertex whose distance has been updated
+ * @param old_distance the previous distance to @p vertex
+ */
+ template<typename Buffer, typename Vertex, typename DistanceType>
+ inline void
+ dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance)
+ {
+ (void)old_distance;
+ Q.update(vertex);
+ }
+
#ifdef BOOST_GRAPH_DIJKSTRA_TESTING
// This is a misnomer now: it now just refers to the "default heap", which is
// currently d-ary (d=4) but can be changed by a #define.
@@ -107,17 +136,20 @@
}
template <class Edge, class Graph>
void gray_target(Edge e, Graph& g) {
+ D old_distance = get(m_distance, target(e, g));
+
bool decreased = relax(e, g, m_weight, m_predecessor, m_distance,
m_combine, m_compare);
if (decreased) {
- m_Q.update(target(e, g));
+ dijkstra_queue_update(m_Q, target(e, g), old_distance);
m_vis.edge_relaxed(e, g);
} else
m_vis.edge_not_relaxed(e, g);
}
template <class Vertex, class Graph>
- void initialize_vertex(Vertex /*u*/, Graph& /*g*/) { }
+ void initialize_vertex(Vertex u, Graph& g)
+ { m_vis.initialize_vertex(u, g); }
template <class Edge, class Graph>
void non_tree_edge(Edge, Graph&) { }
template <class Vertex, class Graph>
Added: trunk/boost/graph/dimacs.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/dimacs.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,403 @@
+// Copyright 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Alex Breuer
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_DIMACS_HPP
+#define BOOST_GRAPH_DIMACS_HPP
+
+#include <string>
+#include <sstream>
+#include <iostream>
+#include <fstream>
+#include <iterator>
+#include <exception>
+#include <vector>
+#include <queue>
+
+namespace boost { namespace graph {
+
+class dimacs_exception : public std::exception {};
+
+class dimacs_basic_reader {
+public:
+ typedef std::size_t vertices_size_type;
+ typedef std::size_t edges_size_type;
+ typedef double vertex_weight_type;
+ typedef double edge_weight_type;
+ typedef std::pair<vertices_size_type,
+ vertices_size_type> edge_type;
+ enum incr_mode {edge, edge_weight};
+
+ dimacs_basic_reader( std::istream& in, bool want_weights = true ) :
+ inpt( in ), seen_edges( 0 ), want_weights(want_weights)
+ {
+ while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
+
+ if( buf[0] != 'p' ) {
+ boost::throw_exception(dimacs_exception());
+ }
+
+ std::stringstream instr( buf );
+ std::string junk;
+
+ instr >> junk >> junk >> num_vertices >> num_edges;
+ read_edge_weights.push( -1 );
+ incr( edge_weight );
+ }
+
+ //for a past the end iterator
+ dimacs_basic_reader() : inpt( std::cin ), num_vertices( 0 ),
+ num_edges( 0 ), seen_edges( 0 ), want_weights(false) {}
+
+ edge_type edge_deref() {
+ assert( !read_edges.empty() );
+ return read_edges.front();
+ }
+
+ inline edge_type* edge_ref() {
+ assert( !read_edges.empty() );
+ return &read_edges.front();
+ }
+
+ inline edge_weight_type edge_weight_deref() {
+ assert( !read_edge_weights.empty() );
+ return read_edge_weights.front();
+ }
+
+ inline dimacs_basic_reader incr( incr_mode mode ) {
+ if( mode == edge ) {
+ assert( !read_edges.empty() );
+ read_edges.pop();
+ }
+ else if( mode == edge_weight ) {
+ assert( !read_edge_weights.empty() );
+ read_edge_weights.pop();
+ }
+
+ if( (mode == edge && read_edges.empty()) ||
+ (mode == edge_weight && read_edge_weights.empty() )) {
+
+ if( seen_edges > num_edges ) {
+ boost::throw_exception(dimacs_exception());
+ }
+
+ while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
+
+ if( !inpt.eof() ) {
+ int source, dest, weight;
+ read_edge_line((char*) buf.c_str(), source, dest, weight);
+
+ seen_edges++;
+ source--;
+ dest--;
+
+ read_edges.push( edge_type( source, dest ) );
+ if (want_weights) {
+ read_edge_weights.push( weight );
+ }
+ }
+ assert( read_edges.size() < 100 );
+ assert( read_edge_weights.size() < 100 );
+ }
+
+ // the 1000000 just happens to be about how many edges can be read in
+ // 10s
+// if( !(seen_edges % 1000000) && !process_id( pg ) && mode == edge ) {
+// std::cout << "read " << seen_edges << " edges" << std::endl;
+// }
+ return *this;
+ }
+
+ inline bool done_edges() {
+ return inpt.eof() && read_edges.size() == 0;
+ }
+
+ inline bool done_edge_weights() {
+ return inpt.eof() && read_edge_weights.size() == 0;
+ }
+
+ inline vertices_size_type n_vertices() {
+ return num_vertices;
+ }
+
+ inline vertices_size_type processed_edges() {
+ return seen_edges - read_edges.size();
+ }
+
+ inline vertices_size_type processed_edge_weights() {
+ return seen_edges - read_edge_weights.size();
+ }
+
+ inline vertices_size_type n_edges() {
+ return num_edges;
+ }
+
+protected:
+ bool read_edge_line(char *linebuf, int &from, int &to, int &weight)
+ {
+ char *fs = NULL, *ts = NULL, *ws = NULL;
+ char *tmp = linebuf + 2;
+
+ fs = tmp;
+ if ('e' == linebuf[0]) {
+ while (*tmp != '\n' && *tmp != '\0') {
+ if (*tmp == ' ') {
+ *tmp = '\0';
+ ts = ++tmp;
+ break;
+ }
+ tmp++;
+ }
+ *tmp = '\0';
+ if (NULL == fs || NULL == ts) return false;
+ from = atoi(fs); to = atoi(ts); weight = 0;
+
+ } else if ('a' == linebuf[0]) {
+ while (*tmp != '\n' && *tmp != '\0') {
+ if (*tmp == ' ') {
+ *tmp = '\0';
+ ts = ++tmp;
+ break;
+ }
+ tmp++;
+ }
+ while (*tmp != '\n' && *tmp != '\0') {
+ if (*tmp == ' ') {
+ *tmp = '\0';
+ ws = ++tmp;
+ break;
+ }
+ tmp++;
+ }
+ while (*tmp != '\n' && *tmp != '\0') tmp++;
+ *tmp = '\0';
+ if (fs == NULL || ts == NULL || ws == NULL) return false;
+ from = atoi(fs); to = atoi(ts) ;
+ if (want_weights) weight = atoi(ws); else weight = 0;
+
+ } else {
+ return false;
+ }
+
+ return true;
+ }
+
+ std::queue<edge_type> read_edges;
+ std::queue<edge_weight_type> read_edge_weights;
+
+ std::istream& inpt;
+ std::string buf;
+ vertices_size_type num_vertices, num_edges, seen_edges;
+ bool want_weights;
+};
+
+#if 0
+class dimacs_indexed_reader : public dimacs_basic_reader {
+public:
+ dimacs_indexed_reader( std::istream& in, std::istream& idx ) :
+ dimacs_basic_reader( in ),
+ index( idx ), start( 0 ), stop( 0 ), still_reading( true ) {
+
+ int n = process_id( pg );
+ std::stringstream instr;
+
+ while( getline( index, buf ) ) {
+ instr.str( buf );
+ instr.clear();
+ long p, begin, end;
+
+ instr >> p >> begin >> end;
+
+ if( p == n ) {
+ start = begin;
+ stop = end;
+ break;
+ }
+ }
+
+ std::cerr << "start is " << start << " stop is " << stop << std::endl;
+ assert( start != 0 && stop != 0 );
+ inpt.seekg( start, std::ios::beg );
+
+ //what a kludge!
+ seen_edges = 0;
+ read_edges.pop();
+ incr( dimacs_basic_reader::edge_weight );
+ }
+
+ dimacs_indexed_reader() : dimacs_basic_reader(), index( std::cin ) {
+ }
+ bool done_edges() {
+ return (stop < 0 ? (long)inpt.tellg() == stop && read_edges.size() == 0 : (long)inpt.tellg())
+ >= stop && read_edges.size() == 0;
+ }
+
+ inline dimacs_indexed_reader incr( incr_mode mode ) {
+ if( mode == edge ) {
+ assert( !read_edges.empty() );
+ read_edges.pop();
+ }
+ else if( mode == edge_weight ) {
+ assert( !read_edge_weights.empty() );
+ read_edge_weights.pop();
+ }
+
+ if( (mode == edge && read_edges.empty()) ||
+ (mode == edge_weight && read_edge_weights.empty() )) {
+
+ if( seen_edges > num_edges ) {
+ boost::throw_exception(dimacs_exception());
+ }
+
+ while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
+
+ if( still_reading && !inpt.eof() ) {
+ std::stringstream instr( buf );
+ vertices_size_type source, dest;
+ edge_weight_type weight;
+ instr >> buf >> source >> dest >> weight;
+ seen_edges++;
+
+ // take care of indexing
+ source--;
+ dest--;
+
+ read_edges.push( edge_type( source, dest ) );
+ read_edge_weights.push( weight );
+ }
+ still_reading = stop < 0 ? (long)inpt.tellg() != stop : (long)inpt.tellg() < stop;
+ assert( read_edges.size() < 100 );
+ assert( read_edge_weights.size() < 100 );
+ }
+
+ // the 1000000 just happens to be about how many edges can be read in
+ // 10s
+ if( !(seen_edges % 1000000) && !process_id( pg ) && mode == edge ) {
+ // std::cout << "read " << seen_edges << " edges" << std::endl;
+ }
+ return *this;
+ }
+
+private:
+ std::istream& index;
+ long start, stop;
+ bool still_reading;
+};
+#endif
+
+template<typename T>
+class dimacs_edge_iterator {
+public:
+ typedef dimacs_basic_reader::edge_type edge_type;
+ typedef dimacs_basic_reader::incr_mode incr_mode;
+
+ typedef std::input_iterator_tag iterator_category;
+ typedef edge_type value_type;
+ typedef value_type reference;
+ typedef edge_type* pointer;
+ typedef std::ptrdiff_t difference_type;
+
+ dimacs_edge_iterator( T& reader ) :
+ reader( reader ) {}
+
+ inline dimacs_edge_iterator& operator++() {
+ reader.incr( dimacs_basic_reader::edge );
+ return *this;
+ }
+
+ inline edge_type operator*() {
+ return reader.edge_deref();
+ }
+
+ inline edge_type* operator->() {
+ return reader.edge_ref();
+ }
+
+ // don't expect this to do the right thing if you're not comparing against a
+ // general past-the-end-iterator made with the default constructor for
+ // dimacs_basic_reader
+ inline bool operator==( dimacs_edge_iterator arg ) {
+ if( reader.n_vertices() == 0 ) {
+ return arg.reader.done_edges();
+ }
+ else if( arg.reader.n_vertices() == 0 ) {
+ return reader.done_edges();
+ }
+ else {
+ return false;
+ }
+ return false;
+ }
+
+ inline bool operator!=( dimacs_edge_iterator arg ) {
+ if( reader.n_vertices() == 0 ) {
+ return !arg.reader.done_edges();
+ }
+ else if( arg.reader.n_vertices() == 0 ) {
+ return !reader.done_edges();
+ }
+ else {
+ return true;
+ }
+ return true;
+ }
+
+private:
+ T& reader;
+};
+
+template<typename T>
+class dimacs_edge_weight_iterator {
+public:
+ typedef dimacs_basic_reader::edge_weight_type edge_weight_type;
+ typedef dimacs_basic_reader::incr_mode incr_mode;
+
+ dimacs_edge_weight_iterator( T& reader ) : reader( reader ) {}
+
+ inline dimacs_edge_weight_iterator& operator++() {
+ reader.incr( dimacs_basic_reader::edge_weight );
+ return *this;
+ }
+
+ inline edge_weight_type operator*() {
+ return reader.edge_weight_deref();
+ }
+
+ // don't expect this to do the right thing if you're not comparing against a
+ // general past-the-end-iterator made with the default constructor for
+ // dimacs_basic_reader
+ inline bool operator==( dimacs_edge_weight_iterator arg ) {
+ if( reader.n_vertices() == 0 ) {
+ return arg.reader.done_edge_weights();
+ }
+ else if( arg.reader.n_vertices() == 0 ) {
+ return reader.done_edge_weights();
+ }
+ else {
+ return false;
+ }
+ return false;
+ }
+
+ inline bool operator!=( dimacs_edge_weight_iterator arg ) {
+ if( reader.n_vertices() == 0 ) {
+ return !arg.reader.done_edge_weights();
+ }
+ else if( arg.reader.n_vertices() == 0 ) {
+ return !reader.done_edge_weights();
+ }
+ else {
+ return true;
+ }
+ return true;
+ }
+private:
+ T& reader;
+};
+
+} } // end namespace boost::graph
+#endif
Modified: trunk/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- trunk/boost/graph/fruchterman_reingold.hpp (original)
+++ trunk/boost/graph/fruchterman_reingold.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -1,4 +1,4 @@
-// Copyright 2004 The Trustees of Indiana University.
+// Copyright 2004, 2005 The Trustees of Indiana University.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -12,13 +12,20 @@
#include <boost/config/no_tr1/cmath.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/named_function_params.hpp>
-#include <boost/graph/simple_point.hpp>
#include <vector>
#include <list>
#include <algorithm> // for std::min and std::max
+#include <numeric> // for std::accumulate
+#include <cmath> // for std::sqrt and std::fabs
+#include <math.h> // for hypot (not in <cmath>)
+#include <functional>
+
+#include <stdlib.h> // for drand48
namespace boost {
+ bool vertex_migration = false;
+
struct square_distance_attractive_force {
template<typename Graph, typename T>
T
@@ -84,13 +91,17 @@
}
};
-template<typename Dim, typename PositionMap>
+template<typename PositionMap>
struct grid_force_pairs
{
+ typedef typename property_traits<PositionMap>::value_type Point;
+ typedef double Dim;
+
template<typename Graph>
explicit
- grid_force_pairs(Dim width, Dim height, PositionMap position, const Graph& g)
- : width(width), height(height), position(position)
+ grid_force_pairs(const Point& origin, const Point& extent,
+ PositionMap position, const Graph& g)
+ : width(extent.x), height(extent.y), position(position)
{
#ifndef BOOST_NO_STDC_NAMESPACE
using std::sqrt;
@@ -147,8 +158,12 @@
// Repulse vertices in this bucket
bucket_t& other_bucket
= buckets[other_row * columns + other_column];
- for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
- apply_force(*u, *v);
+ for (v = other_bucket.begin(); v != other_bucket.end(); ++v) {
+ Dim delta_x = position[*u].x - position[*v].x;
+ Dim delta_y = position[*u].y - position[*v].y;
+ Dim dist = hypot(delta_x, delta_y);
+ if (dist < two_k) apply_force(*u, *v);
+ }
}
}
}
@@ -161,11 +176,13 @@
Dim two_k;
};
-template<typename Dim, typename PositionMap, typename Graph>
-inline grid_force_pairs<Dim, PositionMap>
-make_grid_force_pairs(Dim width, Dim height, const PositionMap& position,
- const Graph& g)
-{ return grid_force_pairs<Dim, PositionMap>(width, height, position, g); }
+template<typename PositionMap, typename Graph>
+inline grid_force_pairs<PositionMap>
+make_grid_force_pairs
+ (typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
+ const PositionMap& position, const Graph& g)
+{ return grid_force_pairs<PositionMap>(origin, extent, position, g); }
template<typename Graph, typename PositionMap, typename Dim>
void
@@ -204,17 +221,47 @@
}
namespace detail {
+ template<typename Point>
+ void
+ maybe_jitter_point(Point& p1, const Point& p2, Point origin, Point extent)
+ {
+#ifndef BOOST_NO_STDC_NAMESPACE
+ using std::sqrt;
+ using std::fabs;
+#endif // BOOST_NO_STDC_NAMESPACE
+ typedef double Dim;
+ Dim too_close_x = extent.x / Dim(10000);
+ if (fabs(p1.x - p2.x) < too_close_x) {
+ Dim dist_to_move = sqrt(extent.x) / Dim(200);
+ if (p1.x - origin.x < origin.x + extent.x - p1.x)
+ p1.x += dist_to_move * drand48();
+ else
+ p1.x -= dist_to_move * drand48();
+ }
+ Dim too_close_y = extent.y / Dim(10000);
+ if (fabs(p1.y - p2.y) < too_close_y) {
+ Dim dist_to_move = sqrt(extent.y) / Dim(200);
+ if (p1.y - origin.y < origin.y + extent.y - p1.y)
+ p1.y += dist_to_move * drand48();
+ else
+ p1.y -= dist_to_move * drand48();
+ }
+ }
+
template<typename PositionMap, typename DisplacementMap,
- typename RepulsiveForce, typename Dim, typename Graph>
+ typename RepulsiveForce, typename Graph>
struct fr_apply_force
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename property_traits<PositionMap>::value_type Point;
+ typedef double Dim;
fr_apply_force(const PositionMap& position,
const DisplacementMap& displacement,
+ Point origin, Point extent,
RepulsiveForce repulsive_force, Dim k, const Graph& g)
- : position(position), displacement(displacement),
- repulsive_force(repulsive_force), k(k), g(g)
+ : position(position), displacement(displacement), origin(origin),
+ extent(extent), repulsive_force(repulsive_force), k(k), g(g)
{ }
void operator()(vertex_descriptor u, vertex_descriptor v)
@@ -223,18 +270,31 @@
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
if (u != v) {
+ // When the vertices land on top of each other, move the
+ // first vertex away from the boundaries.
+ maybe_jitter_point(position[u], position[v], origin, extent);
+
+ // DPG TBD: Can we use the Topology concept's
+ // distance/move_position_toward to handle this?
Dim delta_x = position[v].x - position[u].x;
Dim delta_y = position[v].y - position[u].y;
- Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
- Dim fr = repulsive_force(u, v, k, dist, g);
- displacement[v].x += delta_x / dist * fr;
- displacement[v].y += delta_y / dist * fr;
+ Dim dist = hypot(delta_x, delta_y);
+ if (dist == Dim(0)) {
+ displacement[v].x += 0.01;
+ displacement[v].y += 0.01;
+ } else {
+ Dim fr = repulsive_force(u, v, k, dist, g);
+ displacement[v].x += delta_x / dist * fr;
+ displacement[v].y += delta_y / dist * fr;
+ }
}
}
private:
PositionMap position;
DisplacementMap displacement;
+ Point origin;
+ Point extent;
RepulsiveForce repulsive_force;
Dim k;
const Graph& g;
@@ -242,21 +302,23 @@
} // end namespace detail
-template<typename Graph, typename PositionMap, typename Dim,
+template<typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling, typename DisplacementMap>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
Cooling cool,
DisplacementMap displacement)
{
+ typedef typename property_traits<PositionMap>::value_type Point;
+ typedef double Dim;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
@@ -265,22 +327,20 @@
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
- Dim area = width * height;
+ Dim volume = extent.x * extent.y;
+
// assume positions are initialized randomly
- Dim k = sqrt(area / num_vertices(g));
+ Dim k = sqrt(volume / num_vertices(g));
detail::fr_apply_force<PositionMap, DisplacementMap,
- RepulsiveForce, Dim, Graph>
- apply_force(position, displacement, repulsive_force, k, g);
+ RepulsiveForce, Graph>
+ apply_force(position, displacement, origin, extent, repulsive_force, k, g);
- Dim temp = cool();
- if (temp) do {
+ do {
// Calculate repulsive forces
vertex_iterator v, v_end;
- for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
- displacement[*v].x = 0;
- displacement[*v].y = 0;
- }
+ for (tie(v, v_end) = vertices(g); v != v_end; ++v)
+ displacement[*v] = Point();
force_pairs(g, apply_force);
// Calculate attractive forces
@@ -288,9 +348,17 @@
for (tie(e, e_end) = edges(g); e != e_end; ++e) {
vertex_descriptor v = source(*e, g);
vertex_descriptor u = target(*e, g);
+
+ // When the vertices land on top of each other, move the
+ // first vertex away from the boundaries.
+ ::boost::detail::maybe_jitter_point(position[u], position[v],
+ origin, extent);
+
+ // DPG TBD: Can we use the Topology concept's
+ // distance/move_position_toward to handle this?
Dim delta_x = position[v].x - position[u].x;
Dim delta_y = position[v].y - position[u].y;
- Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
+ Dim dist = hypot(delta_x, delta_y);
Dim fa = attractive_force(*e, k, dist, g);
displacement[v].x -= delta_x / dist * fa;
@@ -299,41 +367,66 @@
displacement[u].y += delta_y / dist * fa;
}
- // Update positions
- for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
- BOOST_USING_STD_MIN();
- BOOST_USING_STD_MAX();
- Dim disp_size = sqrt(displacement[*v].x * displacement[*v].x
- + displacement[*v].y * displacement[*v].y);
- position[*v].x += displacement[*v].x / disp_size
- * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
- position[*v].y += displacement[*v].y / disp_size
- * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
- position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION
- (width / 2,
- max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2,
- position[*v].x));
- position[*v].y = min BOOST_PREVENT_MACRO_SUBSTITUTION
- (height / 2,
- max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2,
- position[*v].y));
+ if (Dim temp = cool()) {
+ // Update positions
+ for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ Dim disp_size = hypot(displacement[*v].x, displacement[*v].y);
+ {
+ position[*v].x += displacement[*v].x / disp_size
+ * (min)(disp_size, temp);
+ if (vertex_migration) {
+ position[*v].x = (min)(Dim(1.0),
+ (max)(Dim(-1.0), position[*v].x));
+ } else {
+ position[*v].x = (min)(origin.x + extent.x,
+ (max)(origin.x, position[*v].x));
+ }
+
+ // CEM HACK: Jitter if we're on the edges
+ if(position[*v].x == 1.0f) // origin.x + extent.x)
+ position[*v].x -= drand48() * .1 * extent.x;
+ else if(position[*v].x == -1.0f) // origin.x)
+ position[*v].x += drand48() * .1 * extent.x;
+ }
+ {
+ position[*v].y += displacement[*v].y / disp_size
+ * (min)(disp_size, temp);
+ if (vertex_migration) {
+ position[*v].y = (min)(Dim(1.0),
+ (max)(Dim(-1.0), position[*v].y));
+ } else {
+ position[*v].y = (min)(origin.y + extent.y,
+ (max)(origin.y, position[*v].y));
+ }
+
+ // CEM HACK: Jitter if we're on the edges
+ if(position[*v].y == 1.0f) // origin.y + extent.y)
+ position[*v].y -= drand48() * .1 * extent.y;
+ else if(position[*v].y == -1.0f) // origin.y)
+ position[*v].y += drand48() * .1 * extent.y;
+ }
+ }
+ } else {
+ break;
}
- } while ((temp = cool()));
+ } while (true);
}
namespace detail {
template<typename DisplacementMap>
struct fr_force_directed_layout
{
- template<typename Graph, typename PositionMap, typename Dim,
+ template<typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling,
typename Param, typename Tag, typename Rest>
static void
run(const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
@@ -342,7 +435,7 @@
const bgl_named_params<Param, Tag, Rest>&)
{
fruchterman_reingold_force_directed_layout
- (g, position, width, height, attractive_force, repulsive_force,
+ (g, position, origin, extent, attractive_force, repulsive_force,
force_pairs, cool, displacement);
}
};
@@ -350,15 +443,15 @@
template<>
struct fr_force_directed_layout<error_property_not_found>
{
- template<typename Graph, typename PositionMap, typename Dim,
+ template<typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling,
typename Param, typename Tag, typename Rest>
static void
run(const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
@@ -366,56 +459,58 @@
error_property_not_found,
const bgl_named_params<Param, Tag, Rest>& params)
{
- std::vector<simple_point<Dim> > displacements(num_vertices(g));
+ typedef typename property_traits<PositionMap>::value_type Point;
+ std::vector<Point> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
- (g, position, width, height, attractive_force, repulsive_force,
+ (g, position, origin, extent, attractive_force, repulsive_force,
force_pairs, cool,
make_iterator_property_map
(displacements.begin(),
choose_const_pmap(get_param(params, vertex_index), g,
vertex_index),
- simple_point<Dim>()));
+ Point()));
}
};
} // end namespace detail
-template<typename Graph, typename PositionMap, typename Dim, typename Param,
+template<typename Graph, typename PositionMap, typename Param,
typename Tag, typename Rest>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- Dim width,
- Dim height,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
const bgl_named_params<Param, Tag, Rest>& params)
{
typedef typename property_value<bgl_named_params<Param,Tag,Rest>,
vertex_displacement_t>::type D;
detail::fr_force_directed_layout<D>::run
- (g, position, width, height,
+ (g, position, origin, extent,
choose_param(get_param(params, attractive_force_t()),
square_distance_attractive_force()),
choose_param(get_param(params, repulsive_force_t()),
square_distance_repulsive_force()),
choose_param(get_param(params, force_pairs_t()),
- make_grid_force_pairs(width, height, position, g)),
+ make_grid_force_pairs(origin, extent, position, g)),
choose_param(get_param(params, cooling_t()),
- linear_cooling<Dim>(100)),
+ linear_cooling<double>(100)),
get_param(params, vertex_displacement_t()),
params);
}
-template<typename Graph, typename PositionMap, typename Dim>
+template<typename Graph, typename PositionMap>
void
-fruchterman_reingold_force_directed_layout(const Graph& g,
- PositionMap position,
- Dim width,
- Dim height)
+fruchterman_reingold_force_directed_layout
+ (const Graph& g,
+ PositionMap position,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent)
{
fruchterman_reingold_force_directed_layout
- (g, position, width, height,
+ (g, position, origin, extent,
attractive_force(square_distance_attractive_force()));
}
Added: trunk/boost/graph/graph_stats.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/graph_stats.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,136 @@
+// Copyright 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Alex Breuer
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_GRAPH_STATS_HPP
+#define BOOST_GRAPH_GRAPH_STATS_HPP
+
+#include <map>
+#include <list>
+#include <boost/graph/iteration_macros.hpp>
+
+namespace boost { namespace graph {
+
+template<typename Graph>
+struct sort_edge_by_origin {
+public:
+ typedef typename graph_traits<Graph>::edge_descriptor edge_type;
+
+ explicit sort_edge_by_origin( Graph& g ) : g(g) {}
+
+ inline bool operator()( edge_type a, edge_type b ) {
+ return source( a, g ) == source( b, g ) ? target( a, g ) < target( b, g ) :
+ source( a, g ) < source( b, g );
+ }
+
+private:
+ Graph& g;
+};
+
+template<typename Graph>
+struct equal_edge {
+public:
+ typedef typename graph_traits<Graph>::edge_descriptor edge_type;
+
+ explicit equal_edge( Graph& g ) : g(g) {}
+
+ inline bool operator()( edge_type a, edge_type b ) {
+ return source( a, g ) == source( b, g ) &&
+ target( a, g ) == target( b, g );
+ }
+
+private:
+ Graph& g;
+};
+
+template<typename Graph>
+unsigned long num_dup_edges( Graph& g ) {
+ typedef typename graph_traits<Graph>::edge_iterator e_iterator_type;
+ typedef typename graph_traits<Graph>::edge_descriptor edge_type;
+
+ std::list<edge_type> all_edges;
+
+ BGL_FORALL_EDGES_T( e, g, Graph ) {
+ all_edges.push_back( e );
+ }
+
+ sort_edge_by_origin<Graph> cmp1( g );
+ all_edges.sort( cmp1 );
+ equal_edge<Graph> cmp2( g );
+ all_edges.unique( cmp2 );
+
+ return num_edges( g ) - all_edges.size();
+}
+
+
+template<typename Graph>
+std::map<unsigned long, unsigned long> dup_edge_dist( Graph& g ) {
+ std::map<unsigned long, unsigned long> dist;
+ typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
+
+
+ BGL_FORALL_VERTICES_T( v, g, Graph ) {
+ std::list<vertex_type> front_neighbors;
+ a_iterator_type a_iter, a_end;
+ for( tie( a_iter, a_end ) = adjacent_vertices( v, g );
+ a_iter != a_end; ++a_iter ) {
+ front_neighbors.push_back( *a_iter );
+ }
+
+ front_neighbors.sort();
+ front_neighbors.unique();
+ dist[out_degree( v, g ) - front_neighbors.size()] += 1;
+ }
+ return dist;
+}
+
+template<typename Graph>
+std::map<unsigned long, unsigned long> degree_dist( Graph& g ) {
+ std::map<unsigned long, unsigned long> dist;
+ typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
+
+ BGL_FORALL_VERTICES_T( v, g, Graph ) {
+ dist[out_degree( v, g )] += 1;
+ }
+
+ return dist;
+}
+
+template<typename Graph>
+std::map<unsigned long, double> weight_degree_dist( Graph& g ) {
+ std::map<unsigned long, double> dist, n;
+ typedef typename graph_traits<Graph>::adjacency_iterator a_iterator_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
+ typedef typename property_map<Graph, edge_weight_t>::const_type edge_map_type;
+ typedef typename property_traits<edge_map_type>::value_type
+ edge_weight_type;
+
+ typename property_map<Graph, edge_weight_t>::type em = get( edge_weight, g );
+
+ BGL_FORALL_VERTICES_T( v, g, Graph ) {
+ edge_weight_type tmp = 0;
+ BGL_FORALL_OUTEDGES_T( v, e, g, Graph ) {
+ tmp += em[e];
+ }
+ n[out_degree( v, g )] += 1.;
+ dist[out_degree( v, g )] += tmp;
+ }
+
+ for( std::map<unsigned long, double>::iterator iter = dist.begin();
+ iter != dist.end(); ++iter ) {
+ assert( n[iter->first] != 0 );
+ dist[iter->first] /= n[iter->first];
+ }
+
+ return dist;
+}
+
+}}
+
+#endif
Modified: trunk/boost/graph/graphviz.hpp
==============================================================================
--- trunk/boost/graph/graphviz.hpp (original)
+++ trunk/boost/graph/graphviz.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -1,7 +1,7 @@
//=======================================================================
// Copyright 2001 University of Notre Dame.
// Copyright 2003 Jeremy Siek
-// Authors: Lie-Quan Lee and Jeremy Siek
+// Authors: Lie-Quan Lee, Jeremy Siek, and Douglas Gregor
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -23,6 +23,7 @@
#include <boost/graph/subgraph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/dynamic_property_map.hpp>
+#include <boost/graph/overloading.hpp>
#ifdef BOOST_HAS_DECLSPEC
# if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK)
@@ -236,11 +237,14 @@
template <typename Graph, typename VertexPropertiesWriter,
typename EdgePropertiesWriter, typename GraphPropertiesWriter,
typename VertexID>
- inline void write_graphviz(std::ostream& out, const Graph& g,
- VertexPropertiesWriter vpw,
- EdgePropertiesWriter epw,
- GraphPropertiesWriter gpw,
- VertexID vertex_id)
+ inline void
+ write_graphviz
+ (std::ostream& out, const Graph& g,
+ VertexPropertiesWriter vpw,
+ EdgePropertiesWriter epw,
+ GraphPropertiesWriter gpw,
+ VertexID vertex_id
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
typedef typename graph_traits<Graph>::directed_category cat_type;
typedef graphviz_io_traits<cat_type> Traits;
@@ -267,17 +271,21 @@
template <typename Graph, typename VertexPropertiesWriter,
typename EdgePropertiesWriter, typename GraphPropertiesWriter>
- inline void write_graphviz(std::ostream& out, const Graph& g,
- VertexPropertiesWriter vpw,
- EdgePropertiesWriter epw,
- GraphPropertiesWriter gpw)
+ inline void
+ write_graphviz(std::ostream& out, const Graph& g,
+ VertexPropertiesWriter vpw,
+ EdgePropertiesWriter epw,
+ GraphPropertiesWriter gpw
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{ write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }
#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
// ambiguous overload problem with VC++
template <typename Graph>
inline void
- write_graphviz(std::ostream& out, const Graph& g) {
+ write_graphviz(std::ostream& out, const Graph& g
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
+ {
default_writer dw;
default_writer gw;
write_graphviz(out, g, dw, dw, gw);
@@ -286,7 +294,9 @@
template <typename Graph, typename VertexWriter>
inline void
- write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw) {
+ write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
+ {
default_writer dw;
default_writer gw;
write_graphviz(out, g, vw, dw, gw);
@@ -295,7 +305,9 @@
template <typename Graph, typename VertexWriter, typename EdgeWriter>
inline void
write_graphviz(std::ostream& out, const Graph& g,
- VertexWriter vw, EdgeWriter ew) {
+ VertexWriter vw, EdgeWriter ew
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
+ {
default_writer gw;
write_graphviz(out, g, vw, ew, gw);
}
@@ -575,7 +587,8 @@
inline void
write_graphviz(std::ostream& out, const Graph& g,
const dynamic_properties& dp,
- const std::string& node_id = "node_id")
+ const std::string& node_id = "node_id"
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
write_graphviz(out, g, dp, node_id,
@@ -586,7 +599,8 @@
void
write_graphviz(std::ostream& out, const Graph& g,
const dynamic_properties& dp, const std::string& node_id,
- VertexID id)
+ VertexID id
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
{
write_graphviz
(out, g,
Added: trunk/boost/graph/mesh_graph_generator.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/mesh_graph_generator.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,158 @@
+// Copyright 2004, 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Nick Edmonds
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
+#define BOOST_GRAPH_MESH_GENERATOR_HPP
+
+#include <iterator>
+#include <utility>
+#include <cassert>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/type_traits/is_base_and_derived.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost {
+
+ template<typename Graph>
+ class mesh_iterator
+ {
+ typedef typename graph_traits<Graph>::directed_category directed_category;
+ typedef typename graph_traits<Graph>::vertices_size_type
+ vertices_size_type;
+
+ BOOST_STATIC_CONSTANT
+ (bool,
+ is_undirected = (is_base_and_derived<undirected_tag,
+ directed_category>::value
+ || is_same<undirected_tag, directed_category>::value));
+
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ mesh_iterator()
+ : x(0), y(0), done(true) { }
+
+ // Vertices are numbered in row-major order
+ // Assumes directed
+ mesh_iterator(vertices_size_type x, vertices_size_type y,
+ bool toroidal = true)
+ : x(x), y(y), n(x*y), source(0), target(1), current(0,1),
+ toroidal(toroidal), done(false)
+ { assert(x > 1 && y > 1); }
+
+ reference operator*() const { return current; }
+ pointer operator->() const { return ¤t; }
+
+ mesh_iterator& operator++()
+ {
+ if (is_undirected) {
+ if (!toroidal) {
+ if (target == source + 1)
+ if (source < x * (y - 1))
+ target = source + x;
+ else {
+ source++;
+ target = (source % x) < x - 1 ? source + 1 : source + x;
+ if (target > n)
+ done = true;
+ }
+ else if (target == source + x) {
+ source++;
+ target = (source % x) < x - 1 ? source + 1 : source + x;
+ }
+ } else {
+ if (target == source + 1 || target == source - (source % x))
+ target = (source + x) % n;
+ else if (target == (source + x) % n) {
+ if (source == n - 1)
+ done = true;
+ else {
+ source++;
+ target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
+ }
+ }
+ }
+ } else { // Directed
+ if ( !toroidal ) {
+ if (target == source - x)
+ target = source % x > 0 ? source - 1 : source + 1;
+ else if (target == source - 1)
+ if ((source % x) < (x - 1))
+ target = source + 1;
+ else if (source < x * (y - 1))
+ target = source + x;
+ else {
+ done = true;
+ }
+ else if (target == source + 1)
+ if (source < x * (y - 1))
+ target = source + x;
+ else {
+ source++;
+ target = source - x;
+ }
+ else if (target == source + x) {
+ source++;
+ target = (source >= x) ? source - x : source - 1;
+ }
+ } else {
+ if (source == n - 1 && target == (source + x) % n)
+ done = true;
+ else if (target == source - 1 || target == source + x - 1)
+ target = (source + x) % n;
+ else if (target == source + 1 || target == source - (source % x))
+ target = (source - x + n) % n;
+ else if (target == (source - x + n) % n)
+ target = (source % x > 0) ? source - 1 : source + x - 1;
+ else if (target == (source + x) % n) {
+ source++;
+ target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
+ }
+ }
+ }
+
+ current.first = source;
+ current.second = target;
+
+ return *this;
+ }
+
+ mesh_iterator operator++(int)
+ {
+ mesh_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const mesh_iterator& other) const
+ {
+ return done == other.done;
+ }
+
+ bool operator!=(const mesh_iterator& other) const
+ { return !(*this == other); }
+
+ private:
+
+ vertices_size_type x,y;
+ vertices_size_type n;
+ vertices_size_type source;
+ vertices_size_type target;
+ value_type current;
+ bool toroidal;
+ bool done;
+ };
+
+
+} // end namespace boost
+
+#endif // BOOST_GRAPH_MESH_GENERATOR_HPP
Added: trunk/boost/graph/metis.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/metis.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,339 @@
+// Copyright 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_METIS_HPP
+#define BOOST_GRAPH_METIS_HPP
+
+#ifdef BOOST_GRAPH_METIS_NO_INLINE
+# define BOOST_GRAPH_METIS_INLINE_KEYWORD
+#else
+# define BOOST_GRAPH_METIS_INLINE_KEYWORD inline
+#endif
+
+#include <string>
+#include <iostream>
+#include <iterator>
+#include <utility>
+#include <sstream>
+#include <exception>
+#include <vector>
+#include <algorithm>
+
+namespace boost { namespace graph {
+
+class metis_exception : public std::exception {};
+class metis_input_exception : public metis_exception {};
+
+class metis_reader
+{
+ public:
+ typedef std::size_t vertices_size_type;
+ typedef std::size_t edges_size_type;
+ typedef double vertex_weight_type;
+ typedef double edge_weight_type;
+
+ class edge_iterator
+ {
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef std::ptrdiff_t difference_type;
+
+ private:
+ class postincrement_proxy
+ {
+ postincrement_proxy(const value_type& value) : value(value) { }
+
+ public:
+ reference operator*() const { return value; }
+
+ private:
+ value_type value;
+ friend class edge_iterator;
+ };
+
+ public:
+ edge_iterator& operator++();
+ postincrement_proxy operator++(int);
+
+ reference operator*() const { return self->edge; }
+ pointer operator->() const { return &self->edge; }
+
+ // Default copy constructor and assignment operator are okay
+
+ private:
+ edge_iterator(metis_reader* self);
+ void advance(bool skip_initial_read);
+
+ metis_reader* self;
+
+ friend class metis_reader;
+ friend bool operator==(edge_iterator, edge_iterator);
+ friend bool operator!=(edge_iterator, edge_iterator);
+ };
+ friend class edge_iterator;
+
+ class edge_weight_iterator
+ {
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef edge_weight_type value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+
+ // Default copy constructor and assignment operator are okay
+
+ reference operator*() const { return self->edge_weight; }
+ pointer operator->() const { return &self->edge_weight; }
+
+ edge_weight_iterator& operator++() { return *this; }
+ edge_weight_iterator operator++(int) { return *this; }
+
+ private:
+ edge_weight_iterator(metis_reader* self) : self(self) { }
+
+ metis_reader* self;
+
+ friend class metis_reader;
+ };
+
+ metis_reader(std::istream& in) : in(in), edge_weight(1.0) { start(); }
+
+ edge_iterator begin();
+ edge_iterator end();
+ edge_weight_iterator weight_begin();
+
+ vertices_size_type num_vertices() const { return n_vertices; }
+ edges_size_type num_edges() const { return n_edges; }
+
+ std::size_t num_vertex_weights() const { return n_vertex_weights; }
+
+ vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n)
+ { return vertex_weights[v*num_vertex_weights() + n]; }
+
+ bool has_edge_weights() const { return edge_weights; }
+
+ private:
+ void start();
+
+ // Configuration information
+ std::istream& in;
+
+ // Information about the current METIS file
+ vertices_size_type n_vertices;
+ edges_size_type n_edges;
+ std::size_t n_vertex_weights;
+ bool edge_weights;
+
+ // Information about the current edge/vertex
+ std::istringstream line_in;
+ std::pair<vertices_size_type, vertices_size_type> edge;
+ std::vector<vertex_weight_type> vertex_weights;
+ edge_weight_type edge_weight;
+
+ friend bool operator==(edge_iterator, edge_iterator);
+ friend bool operator!=(edge_iterator, edge_iterator);
+};
+
+class metis_distribution
+{
+ public:
+ typedef int process_id_type;
+ typedef std::size_t size_type;
+ typedef std::vector<process_id_type>::iterator iterator;
+
+ metis_distribution(std::istream& in, process_id_type my_id);
+
+ size_type block_size(process_id_type id, size_type) const;
+ process_id_type operator()(size_type n) const { return vertices[n]; }
+ size_type local(size_type n) const;
+ size_type global(size_type n) const { return global(my_id, n); }
+ size_type global(process_id_type id, size_type n) const;
+
+ iterator begin() { return vertices.begin(); }
+ iterator end() { return vertices.end(); }
+
+ private:
+ std::istream& in;
+ process_id_type my_id;
+ std::vector<process_id_type> vertices;
+};
+
+#if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE)
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
+{
+ return (x.self == y.self
+ || (x.self && x.self->edge.first == x.self->num_vertices())
+ || (y.self && y.self->edge.first == y.self->num_vertices()));
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
+{
+ return !(x == y);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_iterator::edge_iterator(metis_reader* self)
+ : self(self)
+{
+ if (self) advance(true);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_iterator& metis_reader::edge_iterator::operator++()
+{
+ advance(false);
+ return *this;
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+void metis_reader::edge_iterator::advance(bool skip_initial_read)
+{
+ do {
+
+ if (!skip_initial_read) {
+ // Try to read the next edge
+ if (self->line_in >> std::ws >> self->edge.second) {
+ --self->edge.second;
+ if (self->has_edge_weights()) {
+ if (!(self->line_in >> self->edge_weight))
+ boost::throw_exception(metis_input_exception());
+ }
+ return;
+ }
+
+ // Check if we're done
+ ++self->edge.first;
+ if (self->edge.first == self->num_vertices())
+ return;
+ }
+
+ // Find the next line
+ std::string line;
+ while (getline(self->in, line) && !line.empty() && line[0] == '%') {
+ /* Keep reading lines in the loop header... */
+ }
+ if (!self->in) boost::throw_exception(metis_input_exception());
+ self->line_in.str(line);
+ self->line_in.clear();
+
+ // Read the next line
+ std::size_t weights_left = self->n_vertex_weights;
+ vertex_weight_type weight;
+ while (weights_left > 0) {
+ if (self->line_in >> weight) self->vertex_weights.push_back(weight);
+ else boost::throw_exception(metis_input_exception());
+ --weights_left;
+ }
+
+ // Successive iterations will pick up edges for this vertex.
+ skip_initial_read = false;
+ } while (true);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_iterator::postincrement_proxy
+metis_reader::edge_iterator::operator++(int)
+{
+ postincrement_proxy result(**this);
+ ++(*this);
+ return result;
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_iterator metis_reader::begin()
+{
+ if (edge.first != 0) start();
+ return edge_iterator(this);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_iterator metis_reader::end()
+{
+ return edge_iterator(0);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+metis_reader::edge_weight_iterator metis_reader::weight_begin()
+{
+ return edge_weight_iterator(this);
+}
+
+BOOST_GRAPH_METIS_INLINE_KEYWORD
+void metis_reader::start()
+{
+ in.seekg(0, std::ios::beg);
+ std::string line;
+ while (getline(in, line) && !line.empty() && line[0] == '%') {
+ /* Keep getting lines in loop header. */
+ }
+
+ if (!in || line.empty()) boost::throw_exception(metis_input_exception());
+
+ // Determine number of vertices and edges in the graph
+ line_in.str(line);
+ if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception());
+
+ // Determine whether vertex or edge weights are included in the graph
+ int fmt = 0;
+ line_in >> fmt;
+ n_vertex_weights = fmt / 10;
+ edge_weights = (fmt % 10 == 1);
+
+ // Determine how many (if any!) vertex weights are included
+ if (n_vertex_weights) line_in >> n_vertex_weights;
+
+ // Setup the iteration data structures
+ edge_weight = 1.0;
+ edge.first = 0;
+ edge.second = 0;
+ vertex_weights.reserve(n_vertex_weights * num_vertices());
+}
+
+metis_distribution::metis_distribution(std::istream& in, process_id_type my_id)
+ : in(in), my_id(my_id),
+ vertices(std::istream_iterator<process_id_type>(in),
+ std::istream_iterator<process_id_type>())
+{
+}
+
+
+metis_distribution::size_type
+metis_distribution::block_size(process_id_type id, size_type) const
+{
+ return std::count(vertices.begin(), vertices.end(), id);
+}
+
+metis_distribution::size_type metis_distribution::local(size_type n) const
+{
+ return std::count(vertices.begin(), vertices.begin() + n, vertices[n]);
+}
+
+metis_distribution::size_type
+metis_distribution::global(process_id_type id, size_type n) const
+{
+ std::vector<process_id_type>::const_iterator i = vertices.begin();
+ while (*i != id) ++i;
+
+ while (n > 0) {
+ do { ++i; } while (*i != id);
+ --n;
+ }
+
+ return i - vertices.begin();
+}
+
+#endif
+
+} } // end namespace boost::graph
+
+#endif // BOOST_GRAPH_METIS_HPP
Modified: trunk/boost/graph/named_function_params.hpp
==============================================================================
--- trunk/boost/graph/named_function_params.hpp (original)
+++ trunk/boost/graph/named_function_params.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -29,6 +29,9 @@
struct vertex_max_invariant_t { };
struct orig_to_copy_t { };
struct root_vertex_t { };
+ struct polling_t { };
+ struct lookahead_t { };
+ struct in_parallel_t { };
struct attractive_force_t { };
struct repulsive_force_t { };
struct force_pairs_t { };
@@ -53,7 +56,7 @@
typedef Base next_type;
typedef Tag tag_type;
typedef T value_type;
- bgl_named_params(T v) : m_value(v) { }
+ bgl_named_params(T v = T()) : m_value(v) { }
bgl_named_params(T v, const Base& b) : Base(b), m_value(v) { }
T m_value;
@@ -305,6 +308,23 @@
return Params(c, *this);
}
+ bgl_named_params<bool, polling_t, self>
+ polling(bool b) const {
+ return bgl_named_params<bool, polling_t, self>(b, *this);
+ }
+
+ template<typename Tp>
+ bgl_named_params<Tp, lookahead_t, self>
+ lookahead(const Tp& x) const {
+ return bgl_named_params<Tp, lookahead_t, self>(x, *this);
+ }
+
+ template<typename Tp>
+ bgl_named_params<Tp, in_parallel_t, self>
+ in_parallel(const Tp& x) const {
+ return bgl_named_params<Tp, in_parallel_t, self>(x, *this);
+ }
+
template <typename VertexDisplacement>
bgl_named_params<VertexDisplacement, vertex_displacement_t, self>
displacement_map(const VertexDisplacement& c) const {
@@ -589,6 +609,24 @@
return Params(c);
}
+ bgl_named_params<bool, polling_t>
+ inline polling(bool b) {
+ return bgl_named_params<bool, polling_t>(b);
+ }
+
+
+ template<typename T>
+ bgl_named_params<T, lookahead_t>
+ lookahead(const T& x) {
+ return bgl_named_params<T, lookahead_t>(x);
+ }
+
+ template<typename T>
+ bgl_named_params<T, in_parallel_t>
+ in_parallel(const T& x) {
+ return bgl_named_params<T, in_parallel_t>(x);
+ }
+
template <typename VertexDisplacement>
bgl_named_params<VertexDisplacement, vertex_displacement_t>
displacement_map(const VertexDisplacement& c) {
Added: trunk/boost/graph/overloading.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/overloading.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,46 @@
+// Copyright 2004 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+
+//
+// This file contains helps that enable concept-based overloading
+// within the Boost Graph Library.
+//
+#ifndef BOOST_GRAPH_OVERLOADING_HPP
+#define BOOST_GRAPH_OVERLOADING_HPP
+
+#include <boost/type_traits/is_base_and_derived.hpp>
+#include <boost/utility/enable_if.hpp>
+
+namespace boost { namespace graph { namespace detail {
+
+struct no_parameter {};
+
+} } } // end namespace boost::graph::detail
+
+#ifndef BOOST_NO_SFINAE
+
+#define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type) \
+ typename enable_if_c<(is_base_and_derived< \
+ Tag, \
+ typename graph_traits<Graph>::traversal_category>::value), \
+ Type>::type
+
+#define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag) \
+ , BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, \
+ ::boost::graph::detail::no_parameter) \
+ = ::boost::graph::detail::no_parameter()
+
+#else
+
+#define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type) Type
+#define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag)
+
+#endif // no SFINAE support
+
+#endif // BOOST_GRAPH_OVERLOADING_HPP
Modified: trunk/boost/graph/page_rank.hpp
==============================================================================
--- trunk/boost/graph/page_rank.hpp (original)
+++ trunk/boost/graph/page_rank.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -15,6 +15,7 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/overloading.hpp>
#include <vector>
namespace boost { namespace graph {
@@ -72,7 +73,8 @@
page_rank(const Graph& g, RankMap rank_map, Done done,
typename property_traits<RankMap>::value_type damping,
typename graph_traits<Graph>::vertices_size_type n,
- RankMap2 rank_map2)
+ RankMap2 rank_map2
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
typedef typename property_traits<RankMap>::value_type rank_type;
@@ -131,7 +133,9 @@
// applies when we have a bidirectional graph.
template<typename MutableGraph>
void
-remove_dangling_links(MutableGraph& g)
+remove_dangling_links(MutableGraph& g
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(MutableGraph,
+ vertex_list_graph_tag))
{
typename graph_traits<MutableGraph>::vertices_size_type old_n;
do {
Added: trunk/boost/graph/point_traits.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/point_traits.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,26 @@
+// Copyright 2004, 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_POINT_TRAITS_HPP
+#define BOOST_GRAPH_POINT_TRAITS_HPP
+
+namespace boost { namespace graph {
+
+template<typename Point>
+struct point_traits
+{
+ // The type of each component of the point
+ typedef typename Point::component_type component_type;
+
+ // The number of dimensions in the point
+ static std::size_t dimensions(const Point& point);
+};
+
+} } // end namespace boost::graph
+
+#endif // BOOST_GRAPH_POINT_TRAITS_HPP
Modified: trunk/boost/graph/properties.hpp
==============================================================================
--- trunk/boost/graph/properties.hpp (original)
+++ trunk/boost/graph/properties.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -122,6 +122,17 @@
BOOST_DEF_PROPERTY(vertex, bundle);
BOOST_DEF_PROPERTY(edge, bundle);
+ // These tags are used to denote the owners and local descriptors
+ // for the vertices and edges of a distributed graph.
+ BOOST_DEF_PROPERTY(vertex, global);
+ BOOST_DEF_PROPERTY(vertex, owner);
+ BOOST_DEF_PROPERTY(vertex, local);
+ BOOST_DEF_PROPERTY(edge, global);
+ BOOST_DEF_PROPERTY(edge, owner);
+ BOOST_DEF_PROPERTY(edge, local);
+ BOOST_DEF_PROPERTY(vertex, local_index);
+ BOOST_DEF_PROPERTY(edge, local_index);
+
#undef BOOST_DEF_PROPERTY
namespace detail {
Modified: trunk/boost/graph/random_layout.hpp
==============================================================================
--- trunk/boost/graph/random_layout.hpp (original)
+++ trunk/boost/graph/random_layout.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -18,14 +18,18 @@
namespace boost {
-template<typename Graph, typename PositionMap, typename Dimension,
+template<typename Graph, typename PositionMap,
typename RandomNumberGenerator>
void
-random_graph_layout(const Graph& g, PositionMap position_map,
- Dimension minX, Dimension maxX,
- Dimension minY, Dimension maxY,
- RandomNumberGenerator& gen)
+random_graph_layout
+ (const Graph& g, PositionMap position_map,
+ typename property_traits<PositionMap>::value_type const& origin,
+ typename property_traits<PositionMap>::value_type const& extent,
+ RandomNumberGenerator& gen)
{
+ typedef typename property_traits<PositionMap>::value_type Point;
+ typedef double Dimension;
+
typedef typename mpl::if_<is_integral<Dimension>,
uniform_int<Dimension>,
uniform_real<Dimension> >::type distrib_t;
@@ -35,8 +39,8 @@
::type gen_t;
gen_t my_gen(gen);
- distrib_t x(minX, maxX);
- distrib_t y(minY, maxY);
+ distrib_t x(origin.x, origin.x + extent.x);
+ distrib_t y(origin.y, origin.y + extent.y);
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
position_map[*vi].x = x(my_gen);
Added: trunk/boost/graph/ssca_graph_generator.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/ssca_graph_generator.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,164 @@
+// Copyright 2004, 2005 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Nick Edmonds
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_SSCA_GENERATOR_HPP
+#define BOOST_GRAPH_SSCA_GENERATOR_HPP
+
+#include <iterator>
+#include <utility>
+#include <vector>
+#include <queue>
+#include <boost/random/uniform_int.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/type_traits/is_base_and_derived.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+enum Direction {FORWARD = 1, BACKWARD = 2, BOTH = FORWARD | BACKWARD};
+
+namespace boost {
+
+ template<typename RandomGenerator, typename Graph>
+ class ssca_iterator
+ {
+ typedef typename graph_traits<Graph>::directed_category directed_category;
+ typedef typename graph_traits<Graph>::vertices_size_type
+ vertices_size_type;
+
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef void difference_type;
+
+ // No argument constructor, set to terminating condition
+ ssca_iterator()
+ : gen(), verticesRemaining(0) { }
+
+ // Initialize for edge generation
+ ssca_iterator(RandomGenerator& gen, vertices_size_type totVertices,
+ vertices_size_type maxCliqueSize, double probUnidirectional,
+ int maxParallelEdges, double probIntercliqueEdges)
+ : gen(&gen), totVertices(totVertices), maxCliqueSize(maxCliqueSize),
+ probUnidirectional(probUnidirectional), maxParallelEdges(maxParallelEdges),
+ probIntercliqueEdges(probIntercliqueEdges), currentClique(0),
+ verticesRemaining(totVertices)
+ {
+ cliqueNum = std::vector<int>(totVertices, -1);
+ current = std::make_pair(0,0);
+ }
+
+ reference operator*() const { return current; }
+ pointer operator->() const { return ¤t; }
+
+ ssca_iterator& operator++()
+ {
+ while (values.empty() && verticesRemaining > 0) { // If there are no values left, generate a new clique
+ uniform_int<vertices_size_type> clique_size(1, maxCliqueSize);
+ uniform_int<vertices_size_type> rand_vertex(0, totVertices-1);
+ uniform_int<int> num_parallel_edges(1, maxParallelEdges);
+ uniform_int<short> direction(0,1);
+ uniform_01<RandomGenerator> prob(*gen);
+ std::vector<vertices_size_type> cliqueVertices;
+
+ cliqueVertices.clear();
+ vertices_size_type size = std::min(clique_size(*gen), verticesRemaining);
+ while (cliqueVertices.size() < size) {
+ vertices_size_type v = rand_vertex(*gen);
+ if (cliqueNum[v] == -1) {
+ cliqueNum[v] = currentClique;
+ cliqueVertices.push_back(v);
+ verticesRemaining--;
+ }
+ } // Nick: This is inefficient when only a few vertices remain...
+ // I should probably just select the remaining vertices
+ // in order when only a certain fraction remain.
+
+ typename std::vector<vertices_size_type>::iterator first, second;
+ for (first = cliqueVertices.begin(); first != cliqueVertices.end(); ++first)
+ for (second = first+1; second != cliqueVertices.end(); ++second) {
+ Direction d;
+ int edges;
+
+ d = prob() < probUnidirectional ? (direction(*gen) == 0 ? FORWARD : BACKWARD) : BOTH;
+
+ if (d & FORWARD) {
+ edges = num_parallel_edges(*gen);
+ for (int i = 0; i < edges; ++i)
+ values.push(std::make_pair(*first, *second));
+ }
+
+ if (d & BACKWARD) {
+ edges = num_parallel_edges(*gen);
+ for (int i = 0; i < edges; ++i)
+ values.push(std::make_pair(*second, *first));
+ }
+ }
+
+ if (verticesRemaining == 0) {
+ // Generate interclique edges
+ for (vertices_size_type i = 0; i < totVertices; ++i) {
+ double p = probIntercliqueEdges;
+ for (vertices_size_type d = 2; d < totVertices/2; d *= 2, p/= 2) {
+ vertices_size_type j = (i+d) % totVertices;
+ if (cliqueNum[j] != cliqueNum[i] && prob() < p) {
+ int edges = num_parallel_edges(*gen);
+ for (int i = 0; i < edges; ++i)
+ values.push(std::make_pair(i, j));
+ }
+ }
+ }
+ }
+
+ currentClique++;
+ }
+
+ if (!values.empty()) { // If we're not done return a value
+ current = values.front();
+ values.pop();
+ }
+
+ return *this;
+ }
+
+ ssca_iterator operator++(int)
+ {
+ ssca_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const ssca_iterator& other) const
+ {
+ return verticesRemaining == other.verticesRemaining && values.empty() && other.values.empty();
+ }
+
+ bool operator!=(const ssca_iterator& other) const
+ { return !(*this == other); }
+
+ private:
+
+ // Parameters
+ RandomGenerator* gen;
+ vertices_size_type totVertices;
+ vertices_size_type maxCliqueSize;
+ double probUnidirectional;
+ int maxParallelEdges;
+ double probIntercliqueEdges;
+
+ // Internal data structures
+ std::vector<int> cliqueNum;
+ std::queue<value_type> values;
+ int currentClique;
+ vertices_size_type verticesRemaining;
+ value_type current;
+ };
+
+} // end namespace boost
+
+#endif // BOOST_GRAPH_SSCA_GENERATOR_HPP
Added: trunk/boost/graph/st_connected.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/st_connected.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,82 @@
+// Copyright (C) 2006 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
+#define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/two_bit_color_map.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/pending/queue.hpp>
+
+namespace boost { namespace graph {
+
+template<typename Graph, typename ColorMap>
+bool
+st_connected(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ ColorMap color)
+{
+ typedef typename property_traits<ColorMap>::value_type Color;
+ typedef color_traits<Color> ColorTraits;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // Set all vertices to white (unvisited)
+ BGL_FORALL_VERTICES_T(v, g, Graph)
+ put(color, v, ColorTraits::white());
+
+ // Vertices found from the source are grey
+ put(color, s, ColorTraits::gray());
+
+ // Vertices found from the target are greeen
+ put(color, t, ColorTraits::green());
+ queue<Vertex> Q;
+ Q.push(s);
+ Q.push(t);
+
+ while (!Q.empty()) {
+ Vertex u = Q.top(); Q.pop();
+ Color u_color = get(color, u);
+
+ BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
+ Vertex v = target(e, g);
+ Color v_color = get(color, v);
+ if (v_color == ColorTraits::white()) {
+ // We have not seen "v" before; mark it with the same color as u
+ Color u_color = get(color, u);
+ put(color, v, u_color);
+
+ // Push it on the queue
+ Q.push(v);
+ } else if (v_color != ColorTraits::black() && u_color != v_color) {
+ // Colors have collided. We're done!
+ return true;
+ }
+ }
+ // u is done, so mark it black
+ put(color, u, ColorTraits::black());
+ }
+
+ return false;
+}
+
+template<typename Graph>
+inline bool
+st_connected(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t)
+{
+ return st_connected(g, s, t,
+ make_two_bit_color_map(num_vertices(g),
+ get(vertex_index, g)));
+}
+
+} } // end namespace boost::graph
+
+#endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
Modified: trunk/boost/graph/strong_components.hpp
==============================================================================
--- trunk/boost/graph/strong_components.hpp (original)
+++ trunk/boost/graph/strong_components.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -17,6 +17,7 @@
#include <boost/graph/depth_first_search.hpp>
#include <boost/type_traits/conversion_traits.hpp>
#include <boost/static_assert.hpp>
+#include <boost/graph/overloading.hpp>
namespace boost {
@@ -219,7 +220,8 @@
class P, class T, class R>
inline typename property_traits<ComponentMap>::value_type
strong_components(const Graph& g, ComponentMap comp,
- const bgl_named_params<P, T, R>& params)
+ const bgl_named_params<P, T, R>& params
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
typedef typename graph_traits<Graph>::directed_category DirCat;
BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true));
@@ -229,7 +231,8 @@
template <class Graph, class ComponentMap>
inline typename property_traits<ComponentMap>::value_type
- strong_components(const Graph& g, ComponentMap comp)
+ strong_components(const Graph& g, ComponentMap comp
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
typedef typename graph_traits<Graph>::directed_category DirCat;
BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true));
Added: trunk/boost/graph/vertex_and_edge_range.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/vertex_and_edge_range.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -0,0 +1,141 @@
+// Copyright 2004 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Douglas Gregor
+// Andrew Lumsdaine
+
+#ifndef BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
+#define BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
+
+#include <boost/graph/graph_traits.hpp>
+#include <iterator>
+
+namespace boost {
+
+namespace graph {
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ class vertex_and_edge_range
+ {
+ typedef graph_traits<Graph> traits_type;
+
+ public:
+ typedef typename traits_type::directed_category directed_category;
+ typedef typename traits_type::edge_parallel_category
+ edge_parallel_category;
+ struct traversal_category
+ : public virtual vertex_list_graph_tag,
+ public virtual edge_list_graph_tag { };
+
+ typedef std::size_t vertices_size_type;
+ typedef VertexIterator vertex_iterator;
+ typedef typename std::iterator_traits<VertexIterator>::value_type
+ vertex_descriptor;
+
+ typedef EdgeIterator edge_iterator;
+ typedef typename std::iterator_traits<EdgeIterator>::value_type
+ edge_descriptor;
+
+ typedef std::size_t edges_size_type;
+
+ typedef void adjacency_iterator;
+ typedef void out_edge_iterator;
+ typedef void in_edge_iterator;
+ typedef void degree_size_type;
+
+ static vertex_descriptor null_vertex()
+ { return traits_type::null_vertex(); }
+
+ vertex_and_edge_range(const Graph& g,
+ VertexIterator first_v, VertexIterator last_v,
+ vertices_size_type n,
+ EdgeIterator first_e, EdgeIterator last_e,
+ edges_size_type m)
+ : g(&g),
+ first_vertex(first_v), last_vertex(last_v), m_num_vertices(n),
+ first_edge(first_e), last_edge(last_e), m_num_edges(m)
+ {
+ }
+
+ vertex_and_edge_range(const Graph& g,
+ VertexIterator first_v, VertexIterator last_v,
+ EdgeIterator first_e, EdgeIterator last_e)
+ : g(&g),
+ first_vertex(first_v), last_vertex(last_v),
+ first_edge(first_e), last_edge(last_e)
+ {
+ m_num_vertices = std::distance(first_v, last_v);
+ m_num_edges = std::distance(first_e, last_e);
+ }
+
+ const Graph* g;
+ vertex_iterator first_vertex;
+ vertex_iterator last_vertex;
+ vertices_size_type m_num_vertices;
+ edge_iterator first_edge;
+ edge_iterator last_edge;
+ edges_size_type m_num_edges;
+ };
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline std::pair<VertexIterator, VertexIterator>
+ vertices(const vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>& g)
+ { return std::make_pair(g.first_vertex, g.last_vertex); }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::vertices_size_type
+ num_vertices(const vertex_and_edge_range<Graph, VertexIterator,
+ EdgeIterator>& g)
+ { return g.m_num_vertices; }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline std::pair<EdgeIterator, EdgeIterator>
+ edges(const vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>& g)
+ { return std::make_pair(g.first_edge, g.last_edge); }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::edges_size_type
+ num_edges(const vertex_and_edge_range<Graph, VertexIterator,
+ EdgeIterator>& g)
+ { return g.m_num_edges; }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::vertex_descriptor
+ source(typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::edge_descriptor e,
+ const vertex_and_edge_range<Graph, VertexIterator,
+ EdgeIterator>& g)
+ { return source(e, *g.g); }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::vertex_descriptor
+ target(typename vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ ::edge_descriptor e,
+ const vertex_and_edge_range<Graph, VertexIterator,
+ EdgeIterator>& g)
+ { return target(e, *g.g); }
+
+ template<typename Graph, typename VertexIterator, typename EdgeIterator>
+ inline vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ make_vertex_and_edge_range(const Graph& g,
+ VertexIterator first_v, VertexIterator last_v,
+ EdgeIterator first_e, EdgeIterator last_e)
+ {
+ typedef vertex_and_edge_range<Graph, VertexIterator, EdgeIterator>
+ result_type;
+ return result_type(g, first_v, last_v, first_e, last_e);
+ }
+
+} // end namespace graph
+
+using graph::vertex_and_edge_range;
+using graph::make_vertex_and_edge_range;
+
+} // end namespace boost
+#endif // BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
Modified: trunk/boost/property_map.hpp
==============================================================================
--- trunk/boost/property_map.hpp (original)
+++ trunk/boost/property_map.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -1,4 +1,7 @@
// (C) Copyright Jeremy Siek 1999-2001.
+// Copyright (C) 2006 Trustees of Indiana University
+// Authors: Douglas Gregor and Jeremy Siek
+
// 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)
@@ -498,6 +501,26 @@
}
//=========================================================================
+ // A property map that always returns the same object by value.
+ //
+ template <typename ValueType>
+ class static_property_map :
+ public
+ boost::put_get_helper<ValueType,static_property_map<ValueType> >
+ {
+ ValueType value;
+ public:
+ typedef void key_type;
+ typedef ValueType value_type;
+ typedef ValueType reference;
+ typedef readable_property_map_tag category;
+ static_property_map(ValueType v) : value(v) {}
+
+ template<typename T>
+ inline reference operator[](T) const { return value; }
+ };
+
+ //=========================================================================
// A property map that always returns a reference to the same object.
//
template <typename KeyType, typename ValueType>
@@ -562,5 +585,7 @@
} // namespace boost
+#include <boost/vector_property_map.hpp>
+
#endif /* BOOST_PROPERTY_MAP_HPP */
Modified: trunk/boost/vector_property_map.hpp
==============================================================================
--- trunk/boost/vector_property_map.hpp (original)
+++ trunk/boost/vector_property_map.hpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -57,7 +57,10 @@
{
return store->end();
}
-
+
+ IndexMap& get_index_map() { return index; }
+ const IndexMap& get_index_map() const { return index; }
+
public:
// Copy ctor absent, default semantics is OK.
// Assignment operator absent, default semantics is OK.
Modified: trunk/libs/graph/test/layout_test.cpp
==============================================================================
--- trunk/libs/graph/test/layout_test.cpp (original)
+++ trunk/libs/graph/test/layout_test.cpp 2009-04-01 14:07:00 EDT (Wed, 01 Apr 2009)
@@ -11,6 +11,7 @@
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/graph/circle_layout.hpp>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/point_traits.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/test/minimal.hpp>
#include <iostream>
@@ -24,8 +25,9 @@
struct point
{
- double x;
- double y;
+ double x, y;
+ point(double x, double y): x(x), y(y) {}
+ point() {}
};
template<typename Graph, typename PositionMap>
@@ -200,15 +202,17 @@
dump_graph_layout("cube", g, get(vertex_position, g));
minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
+ random_graph_layout(g, get(vertex_position, g),
+ point(-25.0, -25.0),
+ point(25.0, 25.0),
gen);
std::vector<point> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- 50.0,
- 50.0,
+ point(50.0, 50.0),
+ point(50.0, 50.0),
square_distance_attractive_force(),
square_distance_repulsive_force(),
all_force_pairs(),
@@ -267,7 +271,7 @@
dump_graph_layout("triangular-kk", g, get(vertex_position, g));
minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
+ random_graph_layout(g, get(vertex_position, g), point(-25.0, -25.0), point(25.0, 25.0),
gen);
dump_graph_layout("random", g, get(vertex_position, g));
@@ -276,8 +280,8 @@
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- 50.0,
- 50.0,
+ point(50.0, 50.0),
+ point(50.0, 50.0),
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(100)));
@@ -327,15 +331,15 @@
BOOST_CHECK(!ok);
minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
+ random_graph_layout(g, get(vertex_position, g), point(-25.0, -25.0), point(25.0, 25.0),
gen);
std::vector<point> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- 50.0,
- 50.0,
+ point(50.0, 50.0),
+ point(50.0, 50.0),
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(50)));