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_SCC_ORDERING_H
34 : #define UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_SCC_ORDERING_H
35 :
36 : #include <boost/graph/adjacency_list.hpp>
37 : #include <boost/graph/graph_traits.hpp>
38 : #include <boost/graph/properties.hpp>
39 : #include <boost/graph/graph_utility.hpp>
40 :
41 : #include <boost/graph/strong_components.hpp>
42 :
43 : #include "IOrderingAlgorithm.h"
44 : #include "topological_ordering.h"
45 : #include "util.h"
46 : #include "lib_algebra/algebra_common/permutation_util.h"
47 :
48 : //debug
49 : #include "common/error.h"
50 : #include "common/log.h"
51 :
52 :
53 :
54 : namespace ug{
55 : template <typename TAlgebra, typename O_t>
56 : class SCCOrdering : public IOrderingAlgorithm<TAlgebra, O_t>
57 : {
58 : public:
59 : typedef typename TAlgebra::matrix_type M_t;
60 : typedef typename TAlgebra::vector_type V_t;
61 : typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> G_t;
62 : typedef IOrderingAlgorithm<TAlgebra, O_t> baseclass;
63 :
64 : typedef std::vector<size_t> ordering_container_type;
65 : typedef IOrderingAlgorithm<TAlgebra, ordering_container_type> ordering_algo_type;
66 :
67 : typedef boost::graph_traits<G_t>::vertex_descriptor vd_t;
68 : typedef boost::graph_traits<G_t>::vertex_iterator vIt_t;
69 : typedef boost::graph_traits<G_t>::adjacency_iterator nIt_t;
70 : typedef boost::graph_traits<G_t>::adjacency_iterator adj_iter;
71 : typedef boost::graph_traits<G_t>::in_edge_iterator inedge_iter;
72 :
73 0 : SCCOrdering(){}
74 :
75 : /// clone constructor
76 0 : SCCOrdering( const SCCOrdering<TAlgebra, O_t> &parent )
77 0 : : baseclass(), m_spOrderingSubAlgo(parent.m_spOrderingSubAlgo){}
78 :
79 0 : SmartPtr<IOrderingAlgorithm<TAlgebra, O_t> > clone()
80 : {
81 0 : return make_sp(new SCCOrdering<TAlgebra, O_t>(*this));
82 : }
83 :
84 : /// sets an ordering algorithm
85 0 : void set_ordering_subalgorithm(SmartPtr<ordering_algo_type> ordering_subalgo){
86 0 : m_spOrderingSubAlgo = ordering_subalgo;
87 0 : }
88 :
89 0 : void compute(){
90 0 : unsigned n = boost::num_vertices(g);
91 :
92 0 : if(n == 0){
93 0 : UG_THROW(name() << "::compute: Graph is empty!");
94 : return;
95 : }
96 :
97 0 : std::vector<int> component(n), discover_time(n);
98 0 : std::vector<boost::default_color_type> color(n);
99 0 : std::vector<vd_t> root(n);
100 0 : size_t num_components = boost::strong_components(g,
101 : boost::make_iterator_property_map(component.begin(), boost::get(boost::vertex_index, g)),
102 : boost::root_map(boost::make_iterator_property_map(root.begin(), boost::get(boost::vertex_index, g)))
103 : .color_map(
104 : boost::make_iterator_property_map(color.begin(), boost::get(boost::vertex_index, g)))
105 0 : .discover_time_map(boost::make_iterator_property_map(
106 : discover_time.begin(), boost::get(boost::vertex_index, g))));
107 :
108 :
109 0 : std::vector<std::vector<vd_t> > comp_members(num_components);
110 0 : for(unsigned i = 0; i < n; ++i){
111 0 : comp_members[component[i]].push_back(i);
112 : }
113 :
114 : //create scc meta graph
115 0 : scc_g = G_t(num_components);
116 :
117 : adj_iter nIt, nEnd;
118 : size_t i_comp, n_comp;
119 0 : for(unsigned i = 0; i < n; ++i){
120 0 : i_comp = component[i];
121 0 : for(boost::tie(nIt, nEnd) = boost::adjacent_vertices(i, g); nIt != nEnd; ++nIt){
122 0 : n_comp = component[*nIt];
123 0 : if(i_comp != n_comp && !boost::edge(i_comp, n_comp, scc_g).second){
124 0 : boost::add_edge(i_comp, n_comp, scc_g);
125 : }
126 : }
127 : }
128 :
129 0 : O_t scc_topo_ordering(num_components);
130 0 : topological_ordering_core_directed(scc_topo_ordering, scc_g, true); //true = inverse
131 :
132 : //scc_topo_ordering is now a topological ordering of scc_g
133 :
134 0 : o.resize(n);
135 :
136 0 : if(m_spOrderingSubAlgo.invalid()){
137 0 : UG_LOG(name() << "::compute: not using ordering subalgo\n");
138 : //enumerate members of components where components are iterated using the
139 : //topological ordering of the scc meta graph
140 :
141 : size_t k = 0;
142 0 : for(unsigned i = 0; i < num_components; ++i){
143 0 : for(unsigned j = 0; j < comp_members[scc_topo_ordering[i]].size(); ++j){
144 0 : o[comp_members[scc_topo_ordering[i]][j]] = k++;
145 : }
146 : }
147 : }
148 : else{
149 0 : UG_LOG(name() << ":compute: using " << m_spOrderingSubAlgo->name() << " as subalgo\n");
150 :
151 : size_t k = 0;
152 0 : for(unsigned i = 0; i < num_components; ++i){
153 0 : size_t c_size = comp_members[scc_topo_ordering[i]].size();
154 :
155 0 : if(c_size == 1){
156 0 : o[comp_members[scc_topo_ordering[i]][0]] = k++;
157 : }
158 : else{
159 0 : m_spOrderingSubAlgo->init(m, comp_members[scc_topo_ordering[i]]);
160 0 : m_spOrderingSubAlgo->compute();
161 0 : std::vector<size_t>& sub_o = m_spOrderingSubAlgo->ordering();
162 : std::vector<size_t> inv_sub_o;
163 0 : GetInversePermutation(sub_o, inv_sub_o);
164 :
165 0 : for(unsigned j = 0; j < c_size; ++j){
166 0 : o[comp_members[scc_topo_ordering[i]][inv_sub_o[j]]] = k++;
167 : }
168 0 : }
169 : }
170 :
171 0 : UG_COND_THROW(k != n, "k!=n, k=" << k << ", n=" << n);
172 : }
173 :
174 : //reset
175 0 : scc_g = G_t(0);
176 0 : g = G_t(0);
177 :
178 : #ifdef UG_DEBUG
179 : check();
180 : #endif
181 0 : }
182 :
183 0 : void check(){
184 0 : UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
185 0 : }
186 :
187 0 : O_t& ordering(){
188 0 : return o;
189 : }
190 :
191 0 : void init(M_t* A, const V_t&){
192 0 : init(A);
193 0 : }
194 :
195 0 : void init(M_t* A){
196 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
197 : #ifdef UG_ENABLE_DEBUG_LOGS
198 : UG_LOG("Using " << name() << "\n");
199 : #endif
200 :
201 0 : m = A;
202 :
203 0 : unsigned rows = A->num_rows();
204 :
205 0 : g = G_t(rows);
206 :
207 0 : for(unsigned i = 0; i < rows; i++){
208 0 : for(typename M_t::row_iterator conn = A->begin_row(i); conn != A->end_row(i); ++conn){
209 0 : if(conn.value() != 0.0 && conn.index() != i){
210 0 : boost::add_edge(i, conn.index(), g);
211 : }
212 : }
213 : }
214 0 : }
215 :
216 0 : void init(M_t*, const V_t&, const O_t&){
217 0 : UG_THROW(name() << "::init: Algorithm does not support induced subgraph version!");
218 : }
219 :
220 0 : void init(M_t*, const O_t&){
221 0 : UG_THROW(name() << "::init: Algorithm does not support induced subgraph version!");
222 : }
223 :
224 0 : virtual const char* name() const {return "SCCOrdering";}
225 :
226 : private:
227 : G_t g, scc_g;
228 : O_t o;
229 :
230 : M_t* m;
231 :
232 : SmartPtr<ordering_algo_type> m_spOrderingSubAlgo;
233 : };
234 :
235 :
236 : }
237 :
238 :
239 : #endif
|
