Line data Source code
1 : /*
2 : * Copyright (c) 2012-2013: G-CSC, Goethe University Frankfurt
3 : * Author: Martin Rupp
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 : /**
34 : * \file ugbase/lib_algebra/common/graph/old_graph.h
35 : *
36 : * \author Martin Rupp
37 : *
38 : * \date 25.11.09
39 : *
40 : * \brief a simple graph class
41 : *
42 : * Goethe-Center for Scientific Computing 2009-2010.
43 : */
44 :
45 : #ifndef __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
46 : #define __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
47 :
48 : #include <fstream>
49 : #include <algorithm> // for lower_bound
50 : #include <vector>
51 : #include "lib_algebra/common/stl_debug.h"
52 :
53 : #include "common/assert.h"
54 : #include "common/log.h"
55 :
56 :
57 :
58 : namespace ug{
59 : //!
60 : //! cgraph graph class
61 : class cgraph
62 : {
63 : public:
64 : typedef stdvector<size_t>::const_iterator const_row_iterator;
65 : typedef stdvector<size_t>::iterator row_iterator;
66 : public:
67 : /** constructor
68 : */
69 : cgraph()
70 : {
71 : }
72 :
73 : cgraph(size_t n) : m_data(n)
74 : {
75 : for(size_t i=0; i<m_data.size(); ++i)
76 : m_data[i].resize(0);
77 :
78 : #ifdef FORCE_CREATION
79 : FORCE_CREATION { print(); pr(0);}
80 : #endif
81 : }
82 :
83 0 : void resize(size_t n)
84 : {
85 0 : m_data.resize(n);
86 0 : for(size_t i=0; i<m_data.size(); ++i)
87 0 : m_data[i].resize(0);
88 0 : }
89 :
90 : //!
91 : //! destructor
92 : ~cgraph()
93 : {
94 : // destructors of std::vector are getting called
95 0 : }
96 :
97 : //! returns nr of nodes the node "node" is connected to.
98 : size_t num_connections(size_t node) const
99 : {
100 : size_check(node);
101 : return m_data[node].size() ;
102 : }
103 :
104 : bool is_isolated(size_t i) const
105 : {
106 : size_check(i);
107 : return num_connections(i)==0 ||
108 : (num_connections(i)==1 && m_data[i][0] == i);
109 : }
110 :
111 : //! returns true if graph has connection from "from" to "to", otherwise false
112 : bool has_connection(size_t from, size_t to) const
113 : {
114 : size_check(from, to);
115 : return binary_search(begin_row(from), end_row(from), to);
116 : }
117 :
118 : //! set a connection from "from" to "to" if not already there
119 0 : void set_connection(size_t from, size_t to)
120 : {
121 : size_check(from, to);
122 0 : stdvector<size_t>::iterator it = std::lower_bound(begin_row(from), end_row(from), to);
123 0 : if(it == m_data[from].end())
124 0 : m_data[from].push_back(to);
125 0 : else if((*it) != to)
126 0 : m_data[from].insert(it, to);
127 0 : }
128 :
129 : row_iterator begin_row(size_t row)
130 : {
131 : size_check(row);
132 : return m_data[row].begin();
133 : }
134 :
135 : row_iterator end_row(size_t row)
136 : {
137 : size_check(row);
138 : return m_data[row].end();
139 : }
140 :
141 : const_row_iterator begin_row(size_t row) const
142 : {
143 : size_check(row);
144 : return m_data[row].begin();
145 : }
146 :
147 : const_row_iterator end_row(size_t row) const
148 : {
149 : size_check(row);
150 : return m_data[row].end();
151 : }
152 :
153 : //! tranpose this graph (by using create_as_tranpose of)
154 : void transpose()
155 : {
156 : cgraph G;
157 : G.set_as_transpose_of(*this);
158 : swap(m_data, G.m_data);
159 : }
160 :
161 : //! creates this graph as the transpose of other
162 : void set_as_transpose_of(const cgraph &other)
163 : {
164 : stdvector<size_t> rowSize(other.size());
165 : for(size_t i=0; i<other.size(); i++) rowSize[i] = 0;
166 :
167 : for(size_t i=0; i<other.size(); i++)
168 : {
169 : for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
170 : rowSize[(*it)]++;
171 : }
172 :
173 : m_data.resize(other.size());
174 : for(size_t i=0; i<other.size(); i++)
175 : {
176 : m_data[i].clear();
177 : m_data[i].reserve(rowSize[i]);
178 : }
179 :
180 : for(size_t i=0; i < other.size(); i++)
181 : for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
182 : {
183 : size_t from = (*it);
184 : size_t to = i;
185 : m_data[from].push_back(to);
186 : }
187 : }
188 :
189 :
190 : size_t size() const { return m_data.size(); }
191 :
192 : public:
193 : // print functions
194 :
195 : //! print row i
196 : void pr(size_t i) const
197 : {
198 : std::cout << "graph row " << i << ", length " << num_connections(i) << ":" << std::endl;
199 : for(const_row_iterator it = begin_row(i); it != end_row(i); ++it)
200 : std::cout << (*it) << " ";
201 : std::cout << std::endl;
202 : std::cout.flush();
203 : }
204 : //! print whole graph to cout
205 : void print() const
206 : {
207 : std::cout << *this << std::endl;
208 : }
209 :
210 : friend std::ostream &operator << (std::ostream &out, const cgraph &g)
211 : {
212 : std::cout << "============= graph ================ " << std::endl;
213 : for(size_t i=0; i<g.size(); ++i)
214 : {
215 : out << "[" << i << "]: ";
216 : for(const_row_iterator it = g.begin_row(i); it != g.end_row(i); ++it)
217 : out << (*it) << " ";
218 : out << std::endl;
219 : }
220 : out.flush();
221 : return out;
222 : }
223 :
224 : inline void size_check(size_t i) const
225 : {
226 : UG_ASSERT(i < m_data.size(), "graph contains " << m_data.size() << " nodes, but trying to access node " << i);
227 : }
228 : inline void size_check(size_t a, size_t b) const
229 : {
230 : UG_ASSERT(a < m_data.size() || b < m_data.size(), "graph contains " << m_data.size() << " nodes, but trying to access nodes " << a << " and " << b);
231 : }
232 :
233 : protected:
234 : stdvector<stdvector<size_t> > m_data;
235 : };
236 :
237 :
238 : } // namespace ug
239 :
240 : #endif // __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
|
