A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
utils/containers/matrix/operators.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2018 Lucas Czech and HITS gGmbH
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  Contact:
19  Lucas Czech <lucas.czech@h-its.org>
20  Exelixis Lab, Heidelberg Institute for Theoretical Studies
21  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
22 */
23 
32 
33 #include <cmath>
34 #include <stdexcept>
35 
36 namespace genesis {
37 namespace utils {
38 
39 // ================================================================================================
40 // Helpful Functions
41 // ================================================================================================
42 
43 std::pair<size_t, size_t> triangular_indices( size_t k, size_t n )
44 {
45  // Using equations from http://stackoverflow.com/a/27088560/4184258
46  // See also https://en.wikipedia.org/wiki/Triangular_number
47 
48  size_t const i = n - 2 - std::floor( std::sqrt( 4 * n * ( n - 1 ) - 7 - ( 8 * k )) / 2.0 - 0.5 );
49  size_t const j = k + i + 1 - n * ( n - 1 ) / 2 + ( n - i ) * (( n - i ) - 1 ) / 2;
50  return { i, j };
51 }
52 
53 size_t triangular_index( size_t i, size_t j, size_t n )
54 {
55  size_t const k = ( n * ( n - 1 ) / 2 ) - ( n - i ) * (( n - i ) - 1 ) / 2 + j - i - 1;
56  return k;
57 }
58 
59 size_t triangular_size( size_t n )
60 {
61  return ( n * n - n ) / 2;
62 }
63 
64 } // namespace utils
65 } // namespace genesis
Matrix operators.
size_t triangular_size(size_t n)
Calculate the number of linear indices needed for a triangular Matrix of size n.
size_t triangular_index(size_t i, size_t j, size_t n)
Given indices i and j in a quadratic Matrix, find the corresponding linear index. ...
std::pair< size_t, size_t > triangular_indices(size_t k, size_t n)
Given a linear index in a upper triangular Matrix, find the corresponding Matrix indices.