Debian Codegraph @

src/atlas/mesh/actions/ReorderReverseCuthillMckee.cc

raw
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