Line data Source code
1 : /*
2 : * Copyright (c) 2022: 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_TOPOLOGICAL_ORDERING_H
34 : #define UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_TOPOLOGICAL_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 "lib_algebra/graph_interface/sparsematrix_boost.h"
41 : #include "lib_algebra/graph_interface/parallel_matrix_boost.h"
42 : #include "lib_algebra/graph_interface/bidirectional.h"
43 : #include "lib_algebra/graph_interface/bidirectional_boost.h"
44 :
45 : #include <vector>
46 : #include <utility> //for pair
47 : #include <deque>
48 :
49 : #include "IOrderingAlgorithm.h"
50 : #include "util.h"
51 :
52 : //debug
53 : #include "common/error.h"
54 : #include "common/log.h"
55 :
56 : namespace ug{
57 :
58 : template <typename O_t, typename G_t>
59 0 : void topological_ordering_core_bidirectional(O_t& o, G_t& g, bool inverse){
60 : typedef typename boost::graph_traits<G_t>::vertex_descriptor vd_t;
61 : typedef typename boost::graph_traits<G_t>::edge_descriptor ed_t;
62 : typedef typename boost::graph_traits<G_t>::vertex_iterator vIt_t;
63 : typedef typename boost::graph_traits<G_t>::in_edge_iterator in_edge_iterator;
64 :
65 0 : size_t n = boost::num_vertices(g);
66 :
67 0 : if(n == 0){
68 0 : UG_THROW("topological_ordering_core: Graph is empty!");
69 : }
70 :
71 0 : o.resize(n);
72 0 : std::vector<int> indegs(n);
73 0 : std::vector<BOOL> isindeq(n, false);
74 : std::deque<vd_t> deq;
75 :
76 : vIt_t vIt, vEnd;
77 0 : for(boost::tie(vIt, vEnd) = boost::vertices(g); vIt != vEnd; ++vIt){
78 0 : indegs[*vIt] = boost::out_degree(*vIt, g)-1; //self-loop
79 0 : if(indegs[*vIt] == 0){
80 0 : deq.push_front(*vIt);
81 0 : isindeq[*vIt] = true;
82 : }
83 : }
84 :
85 0 : if(deq.empty()){
86 0 : UG_THROW("topological_ordering_core: Graph is not cycle-free [1]!\n");
87 : }
88 :
89 : std::pair<in_edge_iterator, in_edge_iterator> e;
90 : vd_t cur_v;
91 : size_t k = 0;
92 : size_t miss = 0;
93 0 : while(!deq.empty() && miss < deq.size()){
94 0 : cur_v = deq.front();
95 0 : deq.pop_front();
96 :
97 : //rotate deque, there is a cycle iff miss==deq.size()
98 0 : if(indegs[cur_v] > 0){
99 : deq.push_back(cur_v);
100 0 : ++miss;
101 0 : continue;
102 : }
103 :
104 : miss = 0;
105 :
106 0 : if(inverse){
107 0 : o[k++] = cur_v;
108 : }
109 : else{
110 0 : o[cur_v] = k++;
111 : }
112 :
113 0 : e = boost::in_edges(cur_v, g);
114 0 : for(; e.first != e.second; ++e.first){
115 : ed_t const& edg = *e.first;
116 : auto t = boost::source(edg, g);
117 :
118 0 : --indegs[t];
119 :
120 0 : if(isindeq[t]){
121 : continue;
122 : }
123 :
124 0 : if(indegs[t] == 0){
125 0 : deq.push_front(t);
126 0 : isindeq[t] = true;
127 : }
128 0 : else if(indegs[t] > 0){
129 0 : deq.push_back(t);
130 0 : isindeq[t] = true;
131 : }
132 : else{} //ignore vertex
133 : }
134 : }
135 :
136 0 : if(!deq.empty()){
137 0 : UG_THROW("topological_ordering_core: Graph is not cycle-free [2]!\n");
138 : }
139 0 : }
140 :
141 : template <typename O_t, typename G_t>
142 0 : void topological_ordering_core_directed(O_t& o, G_t& g, bool inverse){
143 : typedef typename boost::graph_traits<G_t>::vertex_descriptor vd_t;
144 : typedef typename boost::graph_traits<G_t>::vertex_iterator vIt_t;
145 : typedef typename boost::graph_traits<G_t>::adjacency_iterator nIt_t;
146 :
147 : size_t n = boost::num_vertices(g);
148 :
149 0 : if(n == 0){
150 0 : UG_THROW("topological_ordering_core: Graph is empty!");
151 : }
152 :
153 0 : o.resize(n);
154 0 : std::vector<int> indegs(n);
155 0 : std::vector<BOOL> isindeq(n, false);
156 : std::deque<vd_t> deq;
157 :
158 :
159 : vIt_t vIt, vEnd;
160 : nIt_t nIt, nEnd;
161 0 : for(boost::tie(vIt, vEnd) = boost::vertices(g); vIt != vEnd; ++vIt){
162 0 : for(boost::tie(nIt, nEnd) = boost::adjacent_vertices(*vIt, g); nIt != nEnd; ++nIt){
163 0 : ++indegs[*nIt];
164 : }
165 : }
166 :
167 0 : for(boost::tie(vIt, vEnd) = boost::vertices(g); vIt != vEnd; ++vIt){
168 0 : if(indegs[*vIt] == 0){
169 0 : deq.push_front(*vIt);
170 0 : isindeq[*vIt] = true;
171 : }
172 : }
173 :
174 0 : if(deq.empty()){
175 0 : UG_THROW("topological_ordering_core: Graph is not cycle-free [1]!\n");
176 : }
177 :
178 : vd_t cur_v;
179 : size_t k = 0;
180 : size_t miss = 0;
181 0 : while(!deq.empty() && miss < deq.size()){
182 0 : cur_v = deq.front();
183 0 : deq.pop_front();
184 :
185 : //rotate deque, there is a cycle iff miss==deq.size()
186 0 : if(indegs[cur_v] > 0){
187 : deq.push_back(cur_v);
188 0 : ++miss;
189 0 : continue;
190 : }
191 :
192 : miss = 0;
193 :
194 0 : if(inverse){
195 0 : o[k++] = cur_v;
196 : }
197 : else{
198 0 : o[cur_v] = k++;
199 : }
200 :
201 0 : for(boost::tie(nIt, nEnd) = boost::adjacent_vertices(cur_v, g); nIt != nEnd; ++nIt){
202 0 : --indegs[*nIt];
203 :
204 0 : if(isindeq[*nIt]){
205 0 : continue;
206 : }
207 :
208 0 : if(indegs[*nIt] == 0){
209 0 : deq.push_front(*nIt);
210 0 : isindeq[*nIt] = true;
211 : }
212 0 : else if(indegs[*nIt] > 0){
213 0 : deq.push_back(*nIt);
214 0 : isindeq[*nIt] = true;
215 : }
216 : else{} //ignore vertex
217 : }
218 : }
219 :
220 0 : if(!deq.empty()){
221 0 : UG_THROW("topological_ordering_core: Graph is not cycle-free [2]!\n");
222 : }
223 0 : }
224 :
225 :
226 : //for cycle-free matrices only
227 : template <typename TAlgebra, typename O_t>
228 : class TopologicalOrdering : public IOrderingAlgorithm<TAlgebra, O_t>
229 : {
230 : public:
231 : typedef typename TAlgebra::matrix_type M_t;
232 : typedef typename TAlgebra::vector_type V_t;
233 : typedef typename boost::graph_traits<M_t>::vertex_descriptor vd_t;
234 : typedef IOrderingAlgorithm<TAlgebra, O_t> baseclass;
235 :
236 0 : TopologicalOrdering(){}
237 :
238 : /// clone constructor
239 0 : TopologicalOrdering( const TopologicalOrdering<TAlgebra, O_t> &parent )
240 0 : : baseclass(){}
241 :
242 0 : SmartPtr<IOrderingAlgorithm<TAlgebra, O_t> > clone()
243 : {
244 0 : return make_sp(new TopologicalOrdering<TAlgebra, O_t>(*this));
245 : }
246 :
247 0 : void compute(){
248 0 : topological_ordering_core_bidirectional(o, bidir, false); //false = do not compute inverse permutation
249 :
250 : #ifdef UG_DEBUG
251 : check();
252 : #endif
253 0 : }
254 :
255 0 : void init(M_t* A, const V_t&){
256 0 : init(A);
257 0 : }
258 :
259 0 : void init(M_t* A){
260 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
261 : #ifdef UG_ENABLE_DEBUG_LOGS
262 : UG_LOG("Using " << name() << "\n");
263 : #endif
264 :
265 0 : bidir = BidirectionalMatrix<M_t>(A);
266 0 : }
267 :
268 0 : void init(M_t*, const V_t&, const O_t&){
269 0 : UG_THROW(name() << "::init: Algorithm does not support induced subgraph version!");
270 : }
271 :
272 0 : void init(M_t*, const O_t&){
273 0 : UG_THROW(name() << "::init: Algorithm does not support induced subgraph version!");
274 : }
275 :
276 0 : void check(){
277 0 : UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
278 0 : }
279 :
280 0 : O_t& ordering(){
281 0 : return o;
282 : }
283 :
284 0 : virtual const char* name() const {return "TopologicalOrdering";}
285 :
286 : private:
287 : BidirectionalMatrix<M_t> bidir;
288 : O_t o;
289 : };
290 :
291 : }
292 :
293 : #endif
|
