Gnn/detail/CantorEdge.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include <cmath>
0012 #include <cstdint>
0013
0014 namespace ActsPlugins::detail {
0015
0016 /// Class that encapsulates a cantor pair, which represents an edge of a graph
0017 /// By default ensures all edges are ordered, so the represented graph is
0018 /// undirected: (a,b) and (b,a) are the same edge.
0019 template <typename T>
0020 class CantorEdge {
0021   T m_value;
0022
0023  public:
0024   CantorEdge(T x, T y, bool sort = true) {
0025     if ((x > y) && sort) {
0026       std::swap(x, y);
0027     }
0028     m_value = y + ((x + y) * (x + y + 1)) / 2;
0029   }
0030
0031   std::pair<T, T> inverse() const {
0032     auto f = [](T w) -> T { return (w * (w + 1)) / 2; };
0033     auto q = [](T w) -> T {
0034       return std::floor((std::sqrt(8 * w + 1) - 1) / 2);
0035     };
0036
0037     auto y = m_value - f(q(m_value));
0038     auto x = q(m_value) - y;
0039
0040     return {x, y};
0041   }
0042
0043   T value() const { return m_value; }
0044
0045   auto operator<=>(const CantorEdge<T>& other) const = default;
0046 };
0047
0048 }  // namespace ActsPlugins::detail