| 1 |
/* |
| 2 |
* (C) Copyright 2013 ECMWF. |
| 3 |
* |
| 4 |
* This software is licensed under the terms of the Apache Licence Version 2.0 |
| 5 |
* which can be obtained at http://www.apache.org/licenses/LICENSE-2.0. |
| 6 |
* In applying this licence, ECMWF does not waive the privileges and immunities |
| 7 |
* granted to it by virtue of its status as an intergovernmental organisation |
| 8 |
* nor does it submit to any jurisdiction. |
| 9 |
*/ |
| 10 |
|
| 11 |
#include <array> |
| 12 |
#include <bitset> |
| 13 |
#include <list> |
| 14 |
#include <queue> |
| 15 |
#include <utility> |
| 16 |
#include <vector> |
| 17 |
|
| 18 |
|
| 19 |
#include "atlas/mesh/actions/ReorderReverseCuthillMckee.h" |
| 20 |
|
| 21 |
#include "atlas/array.h" |
| 22 |
#include "atlas/mesh/Mesh.h" |
| 23 |
#include "atlas/mesh/Nodes.h" |
| 24 |
#include "atlas/mesh/detail/AccumulateFacets.h" |
| 25 |
#include "atlas/runtime/Trace.h" |
| 26 |
|
| 27 |
#include "eckit/linalg/SparseMatrix.h" |
| 28 |
#include "eckit/linalg/Triplet.h" |
| 29 |
|
| 30 |
namespace atlas { |
| 31 |
namespace mesh { |
| 32 |
namespace actions { |
| 33 |
|
| 34 |
using NotVisited_t = std::list<std::pair<int, double>>; |
| 35 |
|
| 36 |
NotVisited_t::iterator find_index(NotVisited_t& a, int x) { |
| 37 |
return std::find_if(a.begin(), a.end(), [x](NotVisited_t::value_type& element) { return element.first == x; }); |
| 38 |
} |
| 39 |
|
| 40 |
class CuthillMckee { |
| 41 |
private: |
| 42 |
eckit::linalg::SparseMatrix sparse_; |
| 43 |
|
| 44 |
public: |
| 45 |
CuthillMckee(eckit::linalg::SparseMatrix&& m): sparse_(std::move(m)) {} |
| 46 |
|
| 47 |
// Function to generate degree of all the nodes |
| 48 |
std::vector<int> computeDegrees(const eckit::linalg::SparseMatrix& m) { |
| 49 |
std::vector<int> degrees; |
| 50 |
degrees.reserve(m.rows()); |
| 51 |
const auto outer = m.outer(); |
| 52 |
for (size_t i = 0; i < m.rows(); i++) { |
| 53 |
degrees.emplace_back(outer[i + 1] - outer[i]); |
| 54 |
} |
| 55 |
return degrees; |
| 56 |
} |
| 57 |
|
| 58 |
// Cuthill-Mckee algorithm |
| 59 |
std::vector<idx_t> order() { |
| 60 |
auto degrees = computeDegrees(sparse_); |
| 61 |
|
| 62 |
std::queue<idx_t> Q; |
| 63 |
std::vector<idx_t> R; |
| 64 |
R.reserve(degrees.size()); |
| 65 |
|
| 66 |
std::vector<idx_t> sorted_row; |
| 67 |
sorted_row.reserve(sparse_.cols()); |
| 68 |
|
| 69 |
NotVisited_t not_visited; |
| 70 |
|
| 71 |
for (size_t i = 0; i < degrees.size(); i++) { |
| 72 |
not_visited.emplace_back(i, degrees[i]); |
| 73 |
} |
| 74 |
|
| 75 |
not_visited.sort( |
| 76 |
[](const NotVisited_t::value_type& a, const NotVisited_t::value_type& b) { return a.second < b.second; }); |
| 77 |
|
| 78 |
// notVisited helps in running Breadth First Search even when there are disjoint graphs |
| 79 |
|
| 80 |
const auto outer = sparse_.outer(); |
| 81 |
const auto index = sparse_.inner(); |
| 82 |
|
| 83 |
while (not_visited.size()) { |
| 84 |
Q.emplace(not_visited.front().first); |
| 85 |
not_visited.pop_front(); |
| 86 |
|
| 87 |
// Simple Breadth First Search |
| 88 |
while (!Q.empty()) { |
| 89 |
idx_t row = Q.front(); |
| 90 |
|
| 91 |
sorted_row.clear(); |
| 92 |
|
| 93 |
for (auto j = outer[row]; j < outer[row + 1]; ++j) { |
| 94 |
if (index[j] != row) { |
| 95 |
auto found_index = find_index(not_visited, index[j]); |
| 96 |
if (found_index != not_visited.end()) { |
| 97 |
sorted_row.emplace_back(index[j]); |
| 98 |
not_visited.erase(found_index); |
| 99 |
} |
| 100 |
} |
| 101 |
} |
| 102 |
|
| 103 |
std::sort(sorted_row.begin(), sorted_row.end(), |
| 104 |
[&](idx_t i, idx_t j) { return degrees[i] - degrees[j]; }); |
| 105 |
|
| 106 |
for (size_t i = 0; i < sorted_row.size(); i++) { |
| 107 |
Q.emplace(sorted_row[i]); |
| 108 |
} |
| 109 |
|
| 110 |
R.emplace_back(Q.front()); |
| 111 |
Q.pop(); |
| 112 |
} |
| 113 |
} |
| 114 |
|
| 115 |
return R; |
| 116 |
} |
| 117 |
}; |
| 118 |
|
| 119 |
class ReverseCuthillMckee { |
| 120 |
private: |
| 121 |
CuthillMckee cuthill_mckee_; |
| 122 |
|
| 123 |
public: |
| 124 |
ReverseCuthillMckee(eckit::linalg::SparseMatrix&& m): cuthill_mckee_(std::move(m)) {} |
| 125 |
|
| 126 |
// Reverse Cuthill-Mckee algorithm |
| 127 |
std::vector<idx_t> order() { |
| 128 |
std::vector<idx_t> cuthill = cuthill_mckee_.order(); |
| 129 |
|
| 130 |
idx_t size = static_cast<idx_t>(cuthill.size()); |
| 131 |
idx_t n = size; |
| 132 |
|
| 133 |
if (n % 2 == 0) { |
| 134 |
n -= 1; |
| 135 |
} |
| 136 |
|
| 137 |
n = n / 2; |
| 138 |
|
| 139 |
for (idx_t i = 0; i <= n; i++) { |
| 140 |
idx_t j = cuthill[size - 1 - i]; |
| 141 |
cuthill[size - 1 - i] = cuthill[i]; |
| 142 |
cuthill[i] = j; |
| 143 |
} |
| 144 |
|
| 145 |
return cuthill; |
| 146 |
} |
| 147 |
}; |
| 148 |
|
| 149 |
|
| 150 |
ReorderReverseCuthillMckee::ReorderReverseCuthillMckee(const eckit::Parametrisation& config) { |
| 151 |
config.get("ghost_at_end", ghost_at_end_); |
| 152 |
} |
| 153 |
|
| 154 |
std::vector<idx_t> ReorderReverseCuthillMckee::computeNodesOrder(Mesh& mesh) { |
| 155 |
ATLAS_TRACE(); |
| 156 |
std::vector<eckit::linalg::Triplet> n2n_triplets; |
| 157 |
{ |
| 158 |
auto ghost_node = array::make_view<int, 1>(mesh.nodes().ghost()); |
| 159 |
|
| 160 |
std::vector<idx_t> facet_nodes_data; |
| 161 |
std::vector<idx_t> connectivity_facet_to_elem; |
| 162 |
idx_t nb_facets; |
| 163 |
idx_t nb_inner_facets; |
| 164 |
idx_t missing_value; |
| 165 |
|
| 166 |
detail::accumulate_facets(mesh.cells(), mesh.nodes(), |
| 167 |
facet_nodes_data, // shape(nb_facets,nb_nodes_per_facet) |
| 168 |
connectivity_facet_to_elem, nb_facets, nb_inner_facets, missing_value); |
| 169 |
|
| 170 |
n2n_triplets.reserve(2 * nb_facets); |
| 171 |
|
| 172 |
for (idx_t e = 0; e < nb_facets; ++e) { |
| 173 |
idx_t node_0 = facet_nodes_data[2 * e + 0]; |
| 174 |
idx_t node_1 = facet_nodes_data[2 * e + 1]; |
| 175 |
if (ghost_at_end_ && (ghost_node(node_0) || ghost_node(node_1))) { |
| 176 |
continue; |
| 177 |
} |
| 178 |
n2n_triplets.emplace_back(node_0, node_1, 1.); |
| 179 |
n2n_triplets.emplace_back(node_1, node_0, 1.); |
| 180 |
} |
| 181 |
} |
| 182 |
|
| 183 |
std::sort(n2n_triplets.begin(), n2n_triplets.end()); |
| 184 |
|
| 185 |
auto nb_nodes = static_cast<eckit::linalg::Size>(mesh.nodes().size()); |
| 186 |
return ReverseCuthillMckee{{nb_nodes, nb_nodes, n2n_triplets}}.order(); |
| 187 |
} |
| 188 |
|
| 189 |
|
| 190 |
namespace { |
| 191 |
static ReorderBuilder<ReorderReverseCuthillMckee> __ReorderReverseCuthillMckee("reverse_cuthill_mckee"); |
| 192 |
} // namespace |
| 193 |
|
| 194 |
} // namespace actions |
| 195 |
} // namespace mesh |
| 196 |
} // namespace atlas |