Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:43:00 

0001 // Copyright 2004 The Trustees of Indiana University.
0002 
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010 #ifndef BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP
0011 #define BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP
0012 
0013 // Gürsoy-Atun graph layout, based on:
0014 // "Neighbourhood Preserving Load Balancing: A Self-Organizing Approach"
0015 // in 6th International Euro-Par Conference Munich, Germany, August 29 –
0016 // September 1, 2000 Proceedings, pp 234-241
0017 // https://doi.org/10.1007/3-540-44520-X_32
0018 
0019 #include <boost/config/no_tr1/cmath.hpp>
0020 #include <boost/throw_exception.hpp>
0021 #include <boost/assert.hpp>
0022 #include <vector>
0023 #include <exception>
0024 #include <algorithm>
0025 
0026 #include <boost/graph/visitors.hpp>
0027 #include <boost/graph/properties.hpp>
0028 #include <boost/random/uniform_01.hpp>
0029 #include <boost/random/linear_congruential.hpp>
0030 #include <boost/shared_ptr.hpp>
0031 #include <boost/graph/breadth_first_search.hpp>
0032 #include <boost/graph/dijkstra_shortest_paths.hpp>
0033 #include <boost/graph/named_function_params.hpp>
0034 #include <boost/graph/topology.hpp>
0035 
0036 namespace boost
0037 {
0038 
0039 namespace detail
0040 {
0041 
0042     struct over_distance_limit : public std::exception
0043     {
0044     };
0045 
0046     template < typename PositionMap, typename NodeDistanceMap,
0047         typename Topology, typename Graph >
0048     struct update_position_visitor
0049     {
0050         typedef typename Topology::point_type Point;
0051         PositionMap position_map;
0052         NodeDistanceMap node_distance;
0053         const Topology& space;
0054         Point input_vector;
0055         double distance_limit;
0056         double learning_constant;
0057         double falloff_ratio;
0058 
0059         typedef boost::on_examine_vertex event_filter;
0060 
0061         typedef
0062             typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0063 
0064         update_position_visitor(PositionMap position_map,
0065             NodeDistanceMap node_distance, const Topology& space,
0066             const Point& input_vector, double distance_limit,
0067             double learning_constant, double falloff_ratio)
0068         : position_map(position_map)
0069         , node_distance(node_distance)
0070         , space(space)
0071         , input_vector(input_vector)
0072         , distance_limit(distance_limit)
0073         , learning_constant(learning_constant)
0074         , falloff_ratio(falloff_ratio)
0075         {
0076         }
0077 
0078         void operator()(vertex_descriptor v, const Graph&) const
0079         {
0080 #ifndef BOOST_NO_STDC_NAMESPACE
0081             using std::pow;
0082 #endif
0083 
0084             if (get(node_distance, v) > distance_limit)
0085                 BOOST_THROW_EXCEPTION(over_distance_limit());
0086             Point old_position = get(position_map, v);
0087             double distance = get(node_distance, v);
0088             double fraction
0089                 = learning_constant * pow(falloff_ratio, distance * distance);
0090             put(position_map, v,
0091                 space.move_position_toward(
0092                     old_position, fraction, input_vector));
0093         }
0094     };
0095 
0096     template < typename EdgeWeightMap > struct gursoy_shortest
0097     {
0098         template < typename Graph, typename NodeDistanceMap,
0099             typename UpdatePosition >
0100         static inline void run(const Graph& g,
0101             typename graph_traits< Graph >::vertex_descriptor s,
0102             NodeDistanceMap node_distance, UpdatePosition& update_position,
0103             EdgeWeightMap weight)
0104         {
0105             boost::dijkstra_shortest_paths(g, s,
0106                 weight_map(weight).visitor(boost::make_dijkstra_visitor(
0107                     std::make_pair(boost::record_distances(
0108                                        node_distance, boost::on_edge_relaxed()),
0109                         update_position))));
0110         }
0111     };
0112 
0113     template <> struct gursoy_shortest< dummy_property_map >
0114     {
0115         template < typename Graph, typename NodeDistanceMap,
0116             typename UpdatePosition >
0117         static inline void run(const Graph& g,
0118             typename graph_traits< Graph >::vertex_descriptor s,
0119             NodeDistanceMap node_distance, UpdatePosition& update_position,
0120             dummy_property_map)
0121         {
0122             boost::breadth_first_search(g, s,
0123                 visitor(boost::make_bfs_visitor(
0124                     std::make_pair(boost::record_distances(
0125                                        node_distance, boost::on_tree_edge()),
0126                         update_position))));
0127         }
0128     };
0129 
0130 } // namespace detail
0131 
0132 template < typename VertexListAndIncidenceGraph, typename Topology,
0133     typename PositionMap, typename Diameter, typename VertexIndexMap,
0134     typename EdgeWeightMap >
0135 void gursoy_atun_step(const VertexListAndIncidenceGraph& graph,
0136     const Topology& space, PositionMap position, Diameter diameter,
0137     double learning_constant, VertexIndexMap vertex_index_map,
0138     EdgeWeightMap weight)
0139 {
0140 #ifndef BOOST_NO_STDC_NAMESPACE
0141     using std::exp;
0142     using std::pow;
0143 #endif
0144 
0145     typedef
0146         typename graph_traits< VertexListAndIncidenceGraph >::vertex_iterator
0147             vertex_iterator;
0148     typedef
0149         typename graph_traits< VertexListAndIncidenceGraph >::vertex_descriptor
0150             vertex_descriptor;
0151     typedef typename Topology::point_type point_type;
0152     vertex_iterator i, iend;
0153     std::vector< double > distance_from_input_vector(num_vertices(graph));
0154     typedef boost::iterator_property_map< std::vector< double >::iterator,
0155         VertexIndexMap, double, double& >
0156         DistanceFromInputMap;
0157     DistanceFromInputMap distance_from_input(
0158         distance_from_input_vector.begin(), vertex_index_map);
0159     std::vector< double > node_distance_map_vector(num_vertices(graph));
0160     typedef boost::iterator_property_map< std::vector< double >::iterator,
0161         VertexIndexMap, double, double& >
0162         NodeDistanceMap;
0163     NodeDistanceMap node_distance(
0164         node_distance_map_vector.begin(), vertex_index_map);
0165     point_type input_vector = space.random_point();
0166     vertex_descriptor min_distance_loc
0167         = graph_traits< VertexListAndIncidenceGraph >::null_vertex();
0168     double min_distance = 0.0;
0169     bool min_distance_unset = true;
0170     for (boost::tie(i, iend) = vertices(graph); i != iend; ++i)
0171     {
0172         double this_distance = space.distance(get(position, *i), input_vector);
0173         put(distance_from_input, *i, this_distance);
0174         if (min_distance_unset || this_distance < min_distance)
0175         {
0176             min_distance = this_distance;
0177             min_distance_loc = *i;
0178         }
0179         min_distance_unset = false;
0180     }
0181     BOOST_ASSERT(!min_distance_unset); // Graph must have at least one vertex
0182     boost::detail::update_position_visitor< PositionMap, NodeDistanceMap,
0183         Topology, VertexListAndIncidenceGraph >
0184         update_position(position, node_distance, space, input_vector, diameter,
0185             learning_constant, exp(-1. / (2 * diameter * diameter)));
0186     std::fill(
0187         node_distance_map_vector.begin(), node_distance_map_vector.end(), 0);
0188     try
0189     {
0190         typedef detail::gursoy_shortest< EdgeWeightMap > shortest;
0191         shortest::run(
0192             graph, min_distance_loc, node_distance, update_position, weight);
0193     }
0194     catch (const detail::over_distance_limit&)
0195     {
0196         /* Thrown to break out of BFS or Dijkstra early */
0197     }
0198 }
0199 
0200 template < typename VertexListAndIncidenceGraph, typename Topology,
0201     typename PositionMap, typename VertexIndexMap, typename EdgeWeightMap >
0202 void gursoy_atun_refine(const VertexListAndIncidenceGraph& graph,
0203     const Topology& space, PositionMap position, int nsteps,
0204     double diameter_initial, double diameter_final,
0205     double learning_constant_initial, double learning_constant_final,
0206     VertexIndexMap vertex_index_map, EdgeWeightMap weight)
0207 {
0208 #ifndef BOOST_NO_STDC_NAMESPACE
0209     using std::exp;
0210     using std::pow;
0211 #endif
0212 
0213     typedef
0214         typename graph_traits< VertexListAndIncidenceGraph >::vertex_iterator
0215             vertex_iterator;
0216     vertex_iterator i, iend;
0217     double diameter_ratio = (double)diameter_final / diameter_initial;
0218     double learning_constant_ratio
0219         = learning_constant_final / learning_constant_initial;
0220     std::vector< double > distance_from_input_vector(num_vertices(graph));
0221     typedef boost::iterator_property_map< std::vector< double >::iterator,
0222         VertexIndexMap, double, double& >
0223         DistanceFromInputMap;
0224     DistanceFromInputMap distance_from_input(
0225         distance_from_input_vector.begin(), vertex_index_map);
0226     std::vector< int > node_distance_map_vector(num_vertices(graph));
0227     typedef boost::iterator_property_map< std::vector< int >::iterator,
0228         VertexIndexMap, double, double& >
0229         NodeDistanceMap;
0230     NodeDistanceMap node_distance(
0231         node_distance_map_vector.begin(), vertex_index_map);
0232     for (int round = 0; round < nsteps; ++round)
0233     {
0234         double part_done = (double)round / (nsteps - 1);
0235         // fprintf(stderr, "%2d%% done\n", int(rint(part_done * 100.)));
0236         int diameter = (int)(diameter_initial * pow(diameter_ratio, part_done));
0237         double learning_constant = learning_constant_initial
0238             * pow(learning_constant_ratio, part_done);
0239         gursoy_atun_step(graph, space, position, diameter, learning_constant,
0240             vertex_index_map, weight);
0241     }
0242 }
0243 
0244 template < typename VertexListAndIncidenceGraph, typename Topology,
0245     typename PositionMap, typename VertexIndexMap, typename EdgeWeightMap >
0246 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0247     const Topology& space, PositionMap position, int nsteps,
0248     double diameter_initial, double diameter_final,
0249     double learning_constant_initial, double learning_constant_final,
0250     VertexIndexMap vertex_index_map, EdgeWeightMap weight)
0251 {
0252     typedef
0253         typename graph_traits< VertexListAndIncidenceGraph >::vertex_iterator
0254             vertex_iterator;
0255     vertex_iterator i, iend;
0256     for (boost::tie(i, iend) = vertices(graph); i != iend; ++i)
0257     {
0258         put(position, *i, space.random_point());
0259     }
0260     gursoy_atun_refine(graph, space, position, nsteps, diameter_initial,
0261         diameter_final, learning_constant_initial, learning_constant_final,
0262         vertex_index_map, weight);
0263 }
0264 
0265 template < typename VertexListAndIncidenceGraph, typename Topology,
0266     typename PositionMap, typename VertexIndexMap >
0267 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0268     const Topology& space, PositionMap position, int nsteps,
0269     double diameter_initial, double diameter_final,
0270     double learning_constant_initial, double learning_constant_final,
0271     VertexIndexMap vertex_index_map)
0272 {
0273     gursoy_atun_layout(graph, space, position, nsteps, diameter_initial,
0274         diameter_final, learning_constant_initial, learning_constant_final,
0275         vertex_index_map, dummy_property_map());
0276 }
0277 
0278 template < typename VertexListAndIncidenceGraph, typename Topology,
0279     typename PositionMap >
0280 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0281     const Topology& space, PositionMap position, int nsteps,
0282     double diameter_initial, double diameter_final = 1.0,
0283     double learning_constant_initial = 0.8,
0284     double learning_constant_final = 0.2)
0285 {
0286     gursoy_atun_layout(graph, space, position, nsteps, diameter_initial,
0287         diameter_final, learning_constant_initial, learning_constant_final,
0288         get(vertex_index, graph));
0289 }
0290 
0291 template < typename VertexListAndIncidenceGraph, typename Topology,
0292     typename PositionMap >
0293 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0294     const Topology& space, PositionMap position, int nsteps)
0295 {
0296 #ifndef BOOST_NO_STDC_NAMESPACE
0297     using std::sqrt;
0298 #endif
0299 
0300     gursoy_atun_layout(
0301         graph, space, position, nsteps, sqrt((double)num_vertices(graph)));
0302 }
0303 
0304 template < typename VertexListAndIncidenceGraph, typename Topology,
0305     typename PositionMap >
0306 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0307     const Topology& space, PositionMap position)
0308 {
0309     gursoy_atun_layout(graph, space, position, num_vertices(graph));
0310 }
0311 
0312 template < typename VertexListAndIncidenceGraph, typename Topology,
0313     typename PositionMap, typename P, typename T, typename R >
0314 void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph,
0315     const Topology& space, PositionMap position,
0316     const bgl_named_params< P, T, R >& params)
0317 {
0318 #ifndef BOOST_NO_STDC_NAMESPACE
0319     using std::sqrt;
0320 #endif
0321 
0322     std::pair< double, double > diam(sqrt(double(num_vertices(graph))), 1.0);
0323     std::pair< double, double > learn(0.8, 0.2);
0324     gursoy_atun_layout(graph, space, position,
0325         choose_param(get_param(params, iterations_t()), num_vertices(graph)),
0326         choose_param(get_param(params, diameter_range_t()), diam).first,
0327         choose_param(get_param(params, diameter_range_t()), diam).second,
0328         choose_param(get_param(params, learning_constant_range_t()), learn)
0329             .first,
0330         choose_param(get_param(params, learning_constant_range_t()), learn)
0331             .second,
0332         choose_const_pmap(get_param(params, vertex_index), graph, vertex_index),
0333         choose_param(get_param(params, edge_weight), dummy_property_map()));
0334 }
0335 
0336 } // namespace boost
0337 
0338 #endif // BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!