All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
metric_to_bgl.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_METRIC_TO_BGL_HPP
16 #define PAAL_METRIC_TO_BGL_HPP
17 
18 #define BOOST_RESULT_OF_USE_DECLTYPE
19 
23 #include "paal/utils/functors.hpp"
24 
25 #include <boost/graph/adjacency_matrix.hpp>
26 #include <boost/range/adaptor/transformed.hpp>
27 
28 namespace paal {
29 namespace data_structures {
30 // TODO it would be nice to adapt Matrix + something to bgl
31 
37 template <typename Metric> struct adjacency_matrix {
39  using type = boost::adjacency_matrix<
40  boost::undirectedS, boost::no_property,
41  boost::property<boost::edge_weight_t, typename MT::DistanceType>>;
42 };
43 
51 template <typename Metric, typename Vertices>
52 typename adjacency_matrix<Metric>::type metric_to_bgl(const Metric &m,
53  Vertices && vertices) {
54  using Graph = typename adjacency_matrix<Metric>::type;
55  const unsigned N = boost::distance(vertices);
56  using MT = metric_traits<Metric>;
57  using Dist = typename MT::DistanceType;
58  Graph g(N);
59  for (auto && v : vertices) {
60  for (auto && w : vertices) {
61  if (v < w) {
62  bool succ = add_edge(
63  v, w, boost::property<boost::edge_weight_t, Dist>(m(v, w)),
64  g).second;
65  assert(succ);
66  }
67  }
68  }
69  return g;
70 }
71 
83 template <typename Metric, typename Vertices>
84 typename adjacency_matrix<Metric>::type metric_to_bgl_with_index(
85  const Metric &m, Vertices && vertices,
86  bimap<typename boost::range_value<Vertices>::type> &idx) {
88  using VertexType = typename MT::VertexType;
89  idx = data_structures::bimap<VertexType>(vertices);
90  auto idxMetric = data_structures::make_metric_on_idx(m, idx);
91  auto get_idx = [&](VertexType v) { return idx.get_idx(v); };
92 
93  return metric_to_bgl(idxMetric, vertices |
94  boost::adaptors::transformed(get_idx));
95 }
96 
97 }
98 }
99 #endif // PAAL_METRIC_TO_BGL_HPP
adjacency_matrix< Metric >::type metric_to_bgl_with_index(const Metric &m, Vertices &&vertices, bimap< typename boost::range_value< Vertices >::type > &idx)
produces graph from metric with index
implements both sides mapping from the collection to (0,size(collection)) interval.
Definition: bimap.hpp:123
metric_on_idx< Metric, Bimap, Strategy > make_metric_on_idx(Metric &&m, Bimap &&b)
make for metric_on_idx
adjacency_matrix< Metric >::type metric_to_bgl(const Metric &m, Vertices &&vertices)
we assume that vertices is sequence of values (0, vertices.size()).
type of adjacency_matrix, for given metric
This file contains set of simple useful functors or functor adapters.