Line data Source code
1 : /*
2 : * Copyright (c) 2020: G-CSC, Goethe University Frankfurt
3 : * Author: Lukas Larisch
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #ifndef UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_BOOST_CUTHILL_MCKEE_ORDERING_H
34 : #define UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_BOOST_CUTHILL_MCKEE_ORDERING_H
35 :
36 : #include <boost/graph/adjacency_list.hpp>
37 : #include <boost/graph/graph_traits.hpp>
38 : #include <boost/graph/properties.hpp>
39 :
40 : #include <boost/graph/cuthill_mckee_ordering.hpp>
41 :
42 : #include "IOrderingAlgorithm.h"
43 : #include "util.h"
44 :
45 : //debug
46 : #include "common/error.h"
47 : #include "common/log.h"
48 :
49 : namespace ug{
50 :
51 :
52 : template <typename G_t, typename M_t>
53 0 : void induced_subgraph(G_t& ind_g, M_t* A, const std::vector<size_t>& inv_map){
54 : size_t n = A->num_rows();
55 : size_t k = inv_map.size();
56 0 : ind_g = G_t(k);
57 :
58 0 : std::vector<int> ind_map(n, -1);
59 0 : for(unsigned i = 0; i < k; ++i){
60 0 : ind_map[inv_map[i]] = i;
61 : }
62 :
63 : typename boost::graph_traits<G_t>::adjacency_iterator nIt, nEnd;
64 0 : for(unsigned i = 0; i < inv_map.size(); ++i){
65 0 : for(typename M_t::row_iterator conn = A->begin_row(inv_map[i]); conn != A->end_row(inv_map[i]); ++conn){
66 0 : if(conn.value() != 0.0 && conn.index() != i){
67 0 : int idx = ind_map[conn.index()];
68 0 : if(idx >= 0){
69 0 : boost::add_edge(i, idx, ind_g);
70 : }
71 : }
72 : }
73 : }
74 0 : }
75 :
76 :
77 :
78 : #ifndef MCKEE_GRAPH_T
79 : #define MCKEE_GRAPH_T
80 : /* boost graph type for Cuthill-McKee */
81 : typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
82 : boost::property<boost::vertex_color_t,
83 : boost::default_color_type,
84 : boost::property<boost::vertex_degree_t, int> > >
85 : Graph_t;
86 : #endif
87 :
88 :
89 : template <typename TAlgebra, typename O_t=std::vector<size_t> >
90 : class BoostCuthillMcKeeOrdering : public IOrderingAlgorithm<TAlgebra, O_t>
91 : {
92 : public:
93 : typedef typename TAlgebra::matrix_type M_t;
94 : typedef typename TAlgebra::vector_type V_t;
95 : typedef Graph_t G_t;
96 : typedef boost::graph_traits<G_t>::vertex_descriptor Vertex_t;
97 : typedef IOrderingAlgorithm<TAlgebra, O_t> baseclass;
98 :
99 0 : BoostCuthillMcKeeOrdering() : m_bReverse(false){}
100 :
101 : /// clone constructor
102 0 : BoostCuthillMcKeeOrdering( const BoostCuthillMcKeeOrdering<TAlgebra, O_t> &parent )
103 0 : : baseclass(), m_bReverse(parent.m_bReverse){}
104 :
105 0 : SmartPtr<IOrderingAlgorithm<TAlgebra, O_t> > clone()
106 : {
107 0 : return make_sp(new BoostCuthillMcKeeOrdering<TAlgebra, O_t>(*this));
108 : }
109 :
110 0 : void compute(){
111 0 : UG_COND_THROW(boost::num_vertices(g) == 0, name() << "::compute: Graph is empty!");
112 :
113 : boost::property_map<G_t, boost::vertex_index_t>::type index_map = get(boost::vertex_index, g);
114 :
115 0 : std::vector<Vertex_t> inv_perm(boost::num_vertices(g));
116 :
117 0 : if(m_bReverse){
118 0 : boost::cuthill_mckee_ordering(g, inv_perm.rbegin(), get(boost::vertex_color, g), boost::make_degree_map(g));
119 : }
120 : else{
121 0 : boost::cuthill_mckee_ordering(g, inv_perm.begin(), get(boost::vertex_color, g), boost::make_degree_map(g));
122 : }
123 :
124 0 : o.resize(boost::num_vertices(g));
125 :
126 0 : for(unsigned i = 0; i != inv_perm.size(); ++i){
127 0 : o[index_map[inv_perm[i]]] = i;
128 : }
129 :
130 0 : g = G_t(0);
131 :
132 : #ifdef UG_DEBUG
133 : check();
134 : #endif
135 0 : }
136 :
137 0 : void check(){
138 0 : UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
139 0 : }
140 :
141 0 : O_t& ordering(){
142 0 : return o;
143 : }
144 :
145 0 : void init(M_t* A, const V_t&){
146 0 : init(A);
147 0 : }
148 :
149 0 : void init(M_t* A){
150 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
151 : #ifdef UG_ENABLE_DEBUG_LOGS
152 : UG_LOG("Using " << name() << "\n");
153 : #endif
154 :
155 0 : unsigned rows = A->num_rows();
156 :
157 0 : g = G_t(rows);
158 :
159 0 : for(unsigned i = 0; i < rows; i++){
160 0 : for(typename M_t::row_iterator conn = A->begin_row(i); conn != A->end_row(i); ++conn){
161 0 : if(conn.value() != 0.0 && conn.index() != i){ //TODO: think about this!!
162 0 : if(!boost::edge(i, conn.index(), g).second){
163 0 : boost::add_edge(i, conn.index(), g);
164 : }
165 : }
166 : }
167 : }
168 0 : }
169 :
170 0 : void init(M_t* A, const V_t&, const O_t& inv_map){
171 0 : init(A, inv_map);
172 0 : }
173 :
174 0 : void init(M_t* A, const O_t& inv_map){
175 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
176 : #ifdef UG_ENABLE_DEBUG_LOGS
177 : UG_LOG("Using " << name() << " on induced matrix of size " << inv_map.size() << "\n");
178 : #endif
179 :
180 0 : induced_subgraph<G_t, M_t>(g, A, inv_map);
181 0 : }
182 :
183 0 : void set_reverse(bool b){
184 0 : m_bReverse = b;
185 0 : }
186 :
187 0 : virtual const char* name() const {
188 0 : if(m_bReverse){
189 : return "ReverseBoostCuthillMcKeeOrdering";
190 : }
191 : else{
192 0 : return "BoostCuthillMcKeeOrdering";
193 : }
194 : }
195 :
196 : private:
197 : G_t g;
198 : O_t o;
199 :
200 : bool m_bReverse;
201 : };
202 :
203 : }
204 :
205 : #endif
|
