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_MINIMUM_DEGREE_ORDERING_H
34 : #define UG_BASE_LIB_ALGEBRA_ORDERING_STRATEGIES_ALGORITHMS_BOOST_MINIMUM_DEGREE_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/minimum_degree_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 : //Important Note: This implementation requires the BGL graph to be
52 : //directed. Therefore, nonzero entry (i, j) in a symmetrical matrix
53 : //A coresponds to two directed edges (i->j and j->i).
54 : template <typename TAlgebra, typename O_t>
55 : class BoostMinimumDegreeOrdering final : public IOrderingAlgorithm<TAlgebra, O_t>
56 : {
57 : public:
58 : typedef typename TAlgebra::matrix_type M_t;
59 : typedef typename TAlgebra::vector_type V_t;
60 : typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> G_t;
61 : typedef IOrderingAlgorithm<TAlgebra, O_t> baseclass;
62 :
63 0 : BoostMinimumDegreeOrdering(){}
64 :
65 : /// clone constructor
66 0 : BoostMinimumDegreeOrdering( const BoostMinimumDegreeOrdering<TAlgebra, O_t> &parent )
67 0 : : baseclass(){}
68 :
69 0 : SmartPtr<IOrderingAlgorithm<TAlgebra, O_t> > clone()
70 : {
71 0 : return make_sp(new BoostMinimumDegreeOrdering<TAlgebra, O_t>(*this));
72 : }
73 :
74 0 : void compute(){
75 0 : unsigned n = boost::num_vertices(g);
76 0 : unsigned e = boost::num_edges(g);
77 :
78 0 : O_t io(n, 0);
79 :
80 0 : o.resize(n);
81 : unsigned i = 0;
82 :
83 0 : if(n == 0){
84 0 : UG_THROW(name() << "::compute: Graph is empty!");
85 : return;
86 : }
87 0 : else if(n*(n-1u)==e || e==0){
88 0 : UG_LOG(name() << "::compute: Graph is complete or edgeless!");
89 : typename boost::graph_traits<G_t>::vertex_iterator vIt, vEnd;
90 0 : for(boost::tie(vIt, vEnd) = boost::vertices(g); vIt != vEnd; vIt++){
91 0 : o[i++] = *vIt;
92 : }
93 : }
94 :
95 0 : std::vector<int> inverse_perm(n, 0);
96 0 : std::vector<int> supernode_sizes(n, 1);
97 : auto id = boost::get(boost::vertex_index, g);
98 0 : std::vector<int> degree(n, 0);
99 :
100 : /*
101 : * (Graph& G,
102 : * DegreeMap degree,
103 : * InversePermutationMap inverse_perm,
104 : * PermutationMap perm,
105 : * SuperNodeMap supernode_size,
106 : * int delta,
107 : * VertexIndexMap vertex_index_map)
108 : */
109 :
110 : boost::minimum_degree_ordering
111 0 : (g,
112 : boost::make_iterator_property_map(°ree[0], id, degree[0]),
113 : &io[0],
114 : &(o[0]),
115 : boost::make_iterator_property_map(&supernode_sizes[0], id, supernode_sizes[0]),
116 : 0,
117 : id
118 : );
119 :
120 0 : g = G_t(0);
121 :
122 : #ifdef UG_DEBUG
123 : check();
124 : #endif
125 0 : }
126 :
127 0 : void check(){
128 0 : UG_COND_THROW(!is_permutation(o), name() << "::check: Not a permutation!");
129 0 : }
130 :
131 0 : O_t& ordering(){
132 0 : return o;
133 : }
134 :
135 0 : void init(M_t* A, const V_t&){
136 0 : init(A);
137 0 : }
138 :
139 0 : void init(M_t* A){
140 : //TODO: replace this by UG_DLOG if permutation_util does not depend on this file anymore
141 : #ifdef UG_ENABLE_DEBUG_LOGS
142 : UG_LOG("Using " << name() << "\n");
143 : #endif
144 :
145 0 : unsigned rows = A->num_rows();
146 :
147 0 : g = G_t(rows);
148 :
149 0 : for(unsigned i = 0; i < rows; i++){
150 0 : for(typename M_t::row_iterator conn = A->begin_row(i); conn != A->end_row(i); ++conn){
151 0 : if(conn.value() != 0.0 && conn.index() != i){ //TODO: think about this!!
152 0 : boost::add_edge(i, conn.index(), g);
153 : }
154 : }
155 : }
156 0 : }
157 :
158 0 : void init(M_t*, const V_t&, const O_t&){
159 0 : UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
160 : }
161 :
162 0 : void init(M_t*, const O_t&){
163 0 : UG_THROW(name() << "::init: induced subgraph version not implemented yet!");
164 : }
165 :
166 0 : virtual const char* name() const {return "BoostMinimumDegreeOrdering";}
167 :
168 : private:
169 : G_t g;
170 : O_t o;
171 : };
172 :
173 : }
174 :
175 : #endif
|
