Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
old_graph.h
Go to the documentation of this file.
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
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>
52
53#include "common/assert.h"
54#include "common/log.h"
55
56
57
58namespace ug{
61class cgraph
62{
63public:
66public:
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 void resize(size_t n)
84 {
85 m_data.resize(n);
86 for(size_t i=0; i<m_data.size(); ++i)
87 m_data[i].resize(0);
88 }
89
93 {
94 // destructors of std::vector are getting called
95 }
96
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
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
119 void set_connection(size_t from, size_t to)
120 {
121 size_check(from, to);
122 stdvector<size_t>::iterator it = std::lower_bound(begin_row(from), end_row(from), to);
123 if(it == m_data[from].end())
124 m_data[from].push_back(to);
125 else if((*it) != to)
126 m_data[from].insert(it, to);
127 }
128
130 {
131 size_check(row);
132 return m_data[row].begin();
133 }
134
136 {
137 size_check(row);
138 return m_data[row].end();
139 }
140
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
155 {
156 cgraph G;
157 G.set_as_transpose_of(*this);
158 swap(m_data, G.m_data);
159 }
160
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
192public:
193 // print functions
194
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 }
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
233protected:
235};
236
237
238} // namespace ug
239
240#endif // __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
Definition new_graph.h:69
row_iterator begin_row(size_t row)
Definition new_graph.h:168
stdvector< stdvector< size_t > > m_data
Definition old_graph.h:234
row_iterator end_row(size_t row)
Definition new_graph.h:175
void set_as_transpose_of(const cgraph &other)
creates this graph as the transpose of other
Definition old_graph.h:162
size_t size() const
Definition old_graph.h:190
~cgraph()
Definition old_graph.h:92
cgraph()
Definition old_graph.h:69
void print() const
Definition new_graph.h:316
size_t num_connections(size_t node) const
returns nr of nodes the node "node" is connected to.
Definition old_graph.h:98
const size_t * const_row_iterator
Definition new_graph.h:71
void size_check(size_t i) const
Definition new_graph.h:306
stdvector< size_t >::const_iterator const_row_iterator
Definition old_graph.h:64
size_t * row_iterator
Definition new_graph.h:72
const_row_iterator end_row(size_t row) const
Definition old_graph.h:147
void transpose()
tranpose this graph (by using create_as_tranpose of)
Definition old_graph.h:154
void resize(size_t n)
Definition new_graph.h:88
bool is_isolated(size_t i) const
Definition old_graph.h:104
cgraph(size_t n)
Definition old_graph.h:73
stdvector< size_t >::iterator row_iterator
Definition old_graph.h:65
bool has_connection(size_t from, size_t to) const
returns true if graph has connection from "from" to "to", otherwise false
Definition old_graph.h:112
const_row_iterator begin_row(size_t row) const
Definition old_graph.h:141
void size_check(size_t a, size_t b) const
Definition old_graph.h:228
friend std::ostream & operator<<(std::ostream &out, const cgraph &g)
Definition old_graph.h:210
void pr(size_t i) const
print row i
Definition old_graph.h:196
void set_connection(size_t from, size_t to)
set a connection from "from" to "to" if not already there
Definition old_graph.h:119
Definition stl_debug.h:45
#define FORCE_CREATION
Definition algebra_misc.h:46
#define UG_ASSERT(expr, msg)
Definition assert.h:70
the ug namespace