Muster
 All Classes Namespaces Files Functions Variables Typedefs Macros
dissimilarity.h
Go to the documentation of this file.
1 //////////////////////////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2010, Lawrence Livermore National Security, LLC.
3 // Produced at the Lawrence Livermore National Laboratory
4 // LLNL-CODE-433662
5 // All rights reserved.
6 //
7 // This file is part of Muster. For details, see http://github.com/tgamblin/muster.
8 // Please also read the LICENSE file for further information.
9 //
10 // Redistribution and use in source and binary forms, with or without modification, are
11 // permitted provided that the following conditions are met:
12 //
13 // * Redistributions of source code must retain the above copyright notice, this list of
14 // conditions and the disclaimer below.
15 // * Redistributions in binary form must reproduce the above copyright notice, this list of
16 // conditions and the disclaimer (as noted below) in the documentation and/or other materials
17 // provided with the distribution.
18 // * Neither the name of the LLNS/LLNL nor the names of its contributors may be used to endorse
19 // or promote products derived from this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
22 // OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
23 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
24 // LAWRENCE LIVERMORE NATIONAL SECURITY, LLC, THE U.S. DEPARTMENT OF ENERGY OR CONTRIBUTORS BE
25 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
28 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
29 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 //////////////////////////////////////////////////////////////////////////////////////////////////
31 
32 ///
33 /// @file dissimilarity.h
34 /// @author Todd Gamblin tgamblin@llnl.gov
35 /// @brief Data types and functions for dealing with dissimilarity matrices.
36 ///
37 #ifndef DISSIMILARITY_MATRIX_H
38 #define DISSIMILARITY_MATRIX_H
39 
40 #include <vector>
41 #include <boost/numeric/ublas/symmetric.hpp>
42 #include <iostream>
43 
44 namespace cluster {
45  ///
46  /// Packed repersentation of symmetric dissimilarity matrix.
47  ///
48  typedef boost::numeric::ublas::symmetric_matrix<double> dissimilarity_matrix;
49 
50  ///
51  /// Computes a dissimilarity matrix from a vector of objects.
52  ///
53  /// @param[in] objects Vector of any type T.
54  /// @param[in] dissimilarity A dissimilarity measure that gives the distance between two T's.
55  /// Needs to be callable on (T, T).
56  /// @param[out] mat Output parameter. Dissimiliarity matrix is stored here.
57  ///
58  template <class T, class D>
59  void build_dissimilarity_matrix(const std::vector<T>& objects, D dissimilarity,
60  dissimilarity_matrix& mat) {
61  if (mat.size1() != objects.size() || mat.size2() != objects.size()) {
62  mat.resize(objects.size(), objects.size());
63  }
64 
65  for (size_t i=0; i < objects.size(); i++) {
66  for (size_t j=0; j <= i; j++) {
67  mat(i,j) = dissimilarity(objects[i], objects[j]);
68  }
69  }
70  }
71 
72 
73  ///
74  /// Computes a dissimilarity matrix from a subset of a vector of objects.
75  ///
76  /// @param objects Vector of any type T.
77  /// @param subset Indirection vector. Contains indices into objects for
78  /// elements to be compared.
79  /// @param dissimilarity A dissimilarity measure that gives the distance between two T's.
80  /// Needs to be callable(T, T).
81  /// @param mat Output parameter. Dissimiliarity matrix is stored here.
82  template <class T, class D>
83  void build_dissimilarity_matrix(const std::vector<T>& objects, const std::vector<size_t>& subset,
84  D dissimilarity, dissimilarity_matrix& mat) {
85  if (mat.size1() != subset.size() || mat.size2() != subset.size()) {
86  mat.resize(subset.size(), subset.size());
87  }
88 
89  for (size_t i=0; i < subset.size(); i++) {
90  for (size_t j=0; j <= i; j++) {
91  mat(i,j) = dissimilarity(objects[subset[i]], objects[subset[j]]);
92  }
93  }
94  }
95 
96 
97  /// Adaptor for passing a matrix by reference to template functions that take
98  /// a callable distance function. Avoids copying distance matrix.
99  struct matrix_distance {
102  double operator()(size_t i, size_t j) { return mat(i,j); }
103  };
104 
105 
106  /// Functor for computing distance lazily from an object array and
107  /// a distance metric. Use this for CLARA, where we don't want to
108  /// precompute the entire distance matrix.
109  template <class T, class D>
111  const std::vector<T>& objects;
113 
114  lazy_distance_functor(const std::vector<T>& objs, D d)
115  : objects(objs), dissimilarity(d) { }
116 
117  double operator()(size_t i, size_t j) {
118  return dissimilarity(objects[i], objects[j]);
119  }
120  };
121 
122  /// Type-inferred syntactic sugar for constructing lazy_distance_functor.
123  template <class T, class D>
124  lazy_distance_functor<T,D> lazy_distance(const std::vector<T>& objs, D dist) {
125  return lazy_distance_functor<T,D>(objs, dist);
126  }
127 
128 }; // namespace cluster
129 
130 #endif // DISSIMILARITY_MATRIX_H
double operator()(size_t i, size_t j)
const std::vector< T > & objects
void build_dissimilarity_matrix(const std::vector< T > &objects, D dissimilarity, dissimilarity_matrix &mat)
Computes a dissimilarity matrix from a vector of objects.
Definition: dissimilarity.h:59
lazy_distance_functor(const std::vector< T > &objs, D d)
Adaptor for passing a matrix by reference to template functions that take a callable distance functio...
Definition: dissimilarity.h:99
lazy_distance_functor< T, D > lazy_distance(const std::vector< T > &objs, D dist)
Type-inferred syntactic sugar for constructing lazy_distance_functor.
boost::numeric::ublas::symmetric_matrix< double > dissimilarity_matrix
Packed repersentation of symmetric dissimilarity matrix.
Definition: dissimilarity.h:48
matrix_distance(const dissimilarity_matrix &m)
const dissimilarity_matrix & mat
double operator()(size_t i, size_t j)
Functor for computing distance lazily from an object array and a distance metric. ...
Muster. Copyright © 2010, Lawrence Livermore National Laboratory, LLNL-CODE-433662.
Distribution of Muster and its documentation is subject to terms of the Muster LICENSE.
Generated on Thu Sep 1 2016 using Doxygen 1.8.5