1 | //
|
---|
2 | // Copyright (C) 2004 Tanguy Fautré.
|
---|
3 | // For conditions of distribution and use,
|
---|
4 | // see copyright notice in tri_stripper.h
|
---|
5 | //
|
---|
6 | //////////////////////////////////////////////////////////////////////
|
---|
7 | // SVN: $Id: graph_array.h 86 2005-06-08 17:47:27Z gpsnoopy $
|
---|
8 | //////////////////////////////////////////////////////////////////////
|
---|
9 |
|
---|
10 | #ifndef TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
|
---|
11 | #define TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
|
---|
12 |
|
---|
13 | #include <cassert>
|
---|
14 | #include <algorithm>
|
---|
15 | #include <functional>
|
---|
16 | #include <limits>
|
---|
17 | #include <vector>
|
---|
18 |
|
---|
19 |
|
---|
20 |
|
---|
21 |
|
---|
22 | namespace triangle_stripper {
|
---|
23 |
|
---|
24 | namespace detail {
|
---|
25 |
|
---|
26 |
|
---|
27 |
|
---|
28 |
|
---|
29 | // graph_array main class
|
---|
30 | template <class nodetype>
|
---|
31 | class graph_array
|
---|
32 | {
|
---|
33 | public:
|
---|
34 |
|
---|
35 | class arc;
|
---|
36 | class node;
|
---|
37 |
|
---|
38 | // New types
|
---|
39 | typedef size_t nodeid;
|
---|
40 | typedef nodetype value_type;
|
---|
41 | typedef std::vector<node> node_vector;
|
---|
42 | typedef typename node_vector::iterator node_iterator;
|
---|
43 | typedef typename node_vector::const_iterator const_node_iterator;
|
---|
44 | typedef typename node_vector::reverse_iterator node_reverse_iterator;
|
---|
45 | typedef typename node_vector::const_reverse_iterator const_node_reverse_iterator;
|
---|
46 |
|
---|
47 | typedef graph_array<nodetype> graph_type;
|
---|
48 |
|
---|
49 |
|
---|
50 | // graph_array::arc class
|
---|
51 | class arc
|
---|
52 | {
|
---|
53 | public:
|
---|
54 | node_iterator terminal() const;
|
---|
55 |
|
---|
56 | protected:
|
---|
57 | friend class graph_array<nodetype>;
|
---|
58 |
|
---|
59 | arc(node_iterator Terminal);
|
---|
60 |
|
---|
61 | node_iterator m_Terminal;
|
---|
62 | };
|
---|
63 |
|
---|
64 |
|
---|
65 | // New types
|
---|
66 | typedef std::vector<arc> arc_list;
|
---|
67 | typedef typename arc_list::iterator out_arc_iterator;
|
---|
68 | typedef typename arc_list::const_iterator const_out_arc_iterator;
|
---|
69 |
|
---|
70 |
|
---|
71 | // graph_array::node class
|
---|
72 | class node
|
---|
73 | {
|
---|
74 | public:
|
---|
75 | void mark();
|
---|
76 | void unmark();
|
---|
77 | bool marked() const;
|
---|
78 |
|
---|
79 | bool out_empty() const;
|
---|
80 | size_t out_size() const;
|
---|
81 |
|
---|
82 | out_arc_iterator out_begin();
|
---|
83 | out_arc_iterator out_end();
|
---|
84 | const_out_arc_iterator out_begin() const;
|
---|
85 | const_out_arc_iterator out_end() const;
|
---|
86 |
|
---|
87 | value_type & operator * ();
|
---|
88 | value_type * operator -> ();
|
---|
89 | const value_type & operator * () const;
|
---|
90 | const value_type * operator -> () const;
|
---|
91 |
|
---|
92 | value_type & operator = (const value_type & Elem);
|
---|
93 |
|
---|
94 | protected:
|
---|
95 | friend class graph_array<nodetype>;
|
---|
96 | friend class std::vector<node>;
|
---|
97 |
|
---|
98 | node(arc_list & Arcs);
|
---|
99 |
|
---|
100 | arc_list & m_Arcs;
|
---|
101 | size_t m_Begin;
|
---|
102 | size_t m_End;
|
---|
103 |
|
---|
104 | value_type m_Elem;
|
---|
105 | bool m_Marker;
|
---|
106 | };
|
---|
107 |
|
---|
108 |
|
---|
109 | graph_array();
|
---|
110 | explicit graph_array(size_t NbNodes);
|
---|
111 |
|
---|
112 | // Node related member functions
|
---|
113 | bool empty() const;
|
---|
114 | size_t size() const;
|
---|
115 |
|
---|
116 | node & operator [] (nodeid i);
|
---|
117 | const node & operator [] (nodeid i) const;
|
---|
118 |
|
---|
119 | node_iterator begin();
|
---|
120 | node_iterator end();
|
---|
121 | const_node_iterator begin() const;
|
---|
122 | const_node_iterator end() const;
|
---|
123 |
|
---|
124 | node_reverse_iterator rbegin();
|
---|
125 | node_reverse_iterator rend();
|
---|
126 | const_node_reverse_iterator rbegin() const;
|
---|
127 | const_node_reverse_iterator rend() const;
|
---|
128 |
|
---|
129 | // Arc related member functions
|
---|
130 | out_arc_iterator insert_arc(nodeid Initial, nodeid Terminal);
|
---|
131 | out_arc_iterator insert_arc(node_iterator Initial, node_iterator Terminal);
|
---|
132 |
|
---|
133 | // Optimized (overloaded) functions
|
---|
134 | void swap(graph_type & Right);
|
---|
135 | friend void swap(graph_type & Left, graph_type & Right) { Left.swap(Right); }
|
---|
136 |
|
---|
137 | protected:
|
---|
138 | graph_array(const graph_type &);
|
---|
139 | graph_type & operator = (const graph_type &);
|
---|
140 |
|
---|
141 | node_vector m_Nodes;
|
---|
142 | arc_list m_Arcs;
|
---|
143 | };
|
---|
144 |
|
---|
145 |
|
---|
146 |
|
---|
147 | // Additional "low level", graph related, functions
|
---|
148 | template <class nodetype>
|
---|
149 | void unmark_nodes(graph_array<nodetype> & G);
|
---|
150 |
|
---|
151 |
|
---|
152 |
|
---|
153 |
|
---|
154 |
|
---|
155 | //////////////////////////////////////////////////////////////////////////
|
---|
156 | // graph_array::arc inline functions
|
---|
157 | //////////////////////////////////////////////////////////////////////////
|
---|
158 |
|
---|
159 | template <class N>
|
---|
160 | inline graph_array<N>::arc::arc(node_iterator Terminal)
|
---|
161 | : m_Terminal(Terminal) { }
|
---|
162 |
|
---|
163 |
|
---|
164 | template <class N>
|
---|
165 | inline typename graph_array<N>::node_iterator graph_array<N>::arc::terminal() const
|
---|
166 | {
|
---|
167 | return m_Terminal;
|
---|
168 | }
|
---|
169 |
|
---|
170 |
|
---|
171 |
|
---|
172 | //////////////////////////////////////////////////////////////////////////
|
---|
173 | // graph_array::node inline functions
|
---|
174 | //////////////////////////////////////////////////////////////////////////
|
---|
175 |
|
---|
176 | template <class N>
|
---|
177 | inline graph_array<N>::node::node(arc_list & Arcs)
|
---|
178 | : m_Arcs(Arcs),
|
---|
179 | m_Begin(std::numeric_limits<size_t>::max()),
|
---|
180 | m_End(std::numeric_limits<size_t>::max()),
|
---|
181 | m_Marker(false)
|
---|
182 | {
|
---|
183 |
|
---|
184 | }
|
---|
185 |
|
---|
186 |
|
---|
187 | template <class N>
|
---|
188 | inline void graph_array<N>::node::mark()
|
---|
189 | {
|
---|
190 | m_Marker = true;
|
---|
191 | }
|
---|
192 |
|
---|
193 |
|
---|
194 | template <class N>
|
---|
195 | inline void graph_array<N>::node::unmark()
|
---|
196 | {
|
---|
197 | m_Marker = false;
|
---|
198 | }
|
---|
199 |
|
---|
200 |
|
---|
201 | template <class N>
|
---|
202 | inline bool graph_array<N>::node::marked() const
|
---|
203 | {
|
---|
204 | return m_Marker;
|
---|
205 | }
|
---|
206 |
|
---|
207 |
|
---|
208 | template <class N>
|
---|
209 | inline bool graph_array<N>::node::out_empty() const
|
---|
210 | {
|
---|
211 | return (m_Begin == m_End);
|
---|
212 | }
|
---|
213 |
|
---|
214 |
|
---|
215 | template <class N>
|
---|
216 | inline size_t graph_array<N>::node::out_size() const
|
---|
217 | {
|
---|
218 | return (m_End - m_Begin);
|
---|
219 | }
|
---|
220 |
|
---|
221 |
|
---|
222 | template <class N>
|
---|
223 | inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_begin()
|
---|
224 | {
|
---|
225 | return (m_Arcs.begin() + m_Begin);
|
---|
226 | }
|
---|
227 |
|
---|
228 |
|
---|
229 | template <class N>
|
---|
230 | inline typename graph_array<N>::out_arc_iterator graph_array<N>::node::out_end()
|
---|
231 | {
|
---|
232 | return (m_Arcs.begin() + m_End);
|
---|
233 | }
|
---|
234 |
|
---|
235 |
|
---|
236 | template <class N>
|
---|
237 | inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_begin() const
|
---|
238 | {
|
---|
239 | return (m_Arcs.begin() + m_Begin);
|
---|
240 | }
|
---|
241 |
|
---|
242 |
|
---|
243 | template <class N>
|
---|
244 | inline typename graph_array<N>::const_out_arc_iterator graph_array<N>::node::out_end() const
|
---|
245 | {
|
---|
246 | return (m_Arcs.begin() + m_End);
|
---|
247 | }
|
---|
248 |
|
---|
249 |
|
---|
250 | template <class N>
|
---|
251 | inline N & graph_array<N>::node::operator * ()
|
---|
252 | {
|
---|
253 | return m_Elem;
|
---|
254 | }
|
---|
255 |
|
---|
256 |
|
---|
257 | template <class N>
|
---|
258 | inline N * graph_array<N>::node::operator -> ()
|
---|
259 | {
|
---|
260 | return &m_Elem;
|
---|
261 | }
|
---|
262 |
|
---|
263 |
|
---|
264 | template <class N>
|
---|
265 | inline const N & graph_array<N>::node::operator * () const
|
---|
266 | {
|
---|
267 | return m_Elem;
|
---|
268 | }
|
---|
269 |
|
---|
270 |
|
---|
271 | template <class N>
|
---|
272 | inline const N * graph_array<N>::node::operator -> () const
|
---|
273 | {
|
---|
274 | return &m_Elem;
|
---|
275 | }
|
---|
276 |
|
---|
277 |
|
---|
278 | template <class N>
|
---|
279 | inline N & graph_array<N>::node::operator = (const N & Elem)
|
---|
280 | {
|
---|
281 | return (m_Elem = Elem);
|
---|
282 | }
|
---|
283 |
|
---|
284 |
|
---|
285 |
|
---|
286 | //////////////////////////////////////////////////////////////////////////
|
---|
287 | // graph_array inline functions
|
---|
288 | //////////////////////////////////////////////////////////////////////////
|
---|
289 |
|
---|
290 | template <class N>
|
---|
291 | inline graph_array<N>::graph_array() { }
|
---|
292 |
|
---|
293 |
|
---|
294 | template <class N>
|
---|
295 | inline graph_array<N>::graph_array(const size_t NbNodes)
|
---|
296 | : m_Nodes(NbNodes, node(m_Arcs))
|
---|
297 | {
|
---|
298 | // optimisation: we consider that, averagely, a triangle may have at least 2 neighbours
|
---|
299 | // otherwise we are just wasting a bit of memory, but not that much
|
---|
300 | m_Arcs.reserve(NbNodes * 2);
|
---|
301 | }
|
---|
302 |
|
---|
303 |
|
---|
304 | template <class N>
|
---|
305 | inline bool graph_array<N>::empty() const
|
---|
306 | {
|
---|
307 | return m_Nodes.empty();
|
---|
308 | }
|
---|
309 |
|
---|
310 |
|
---|
311 | template <class N>
|
---|
312 | inline size_t graph_array<N>::size() const
|
---|
313 | {
|
---|
314 | return m_Nodes.size();
|
---|
315 | }
|
---|
316 |
|
---|
317 |
|
---|
318 | template <class N>
|
---|
319 | inline typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i)
|
---|
320 | {
|
---|
321 | assert(i < size());
|
---|
322 |
|
---|
323 | return m_Nodes[i];
|
---|
324 | }
|
---|
325 |
|
---|
326 |
|
---|
327 | template <class N>
|
---|
328 | inline const typename graph_array<N>::node & graph_array<N>::operator [] (const nodeid i) const
|
---|
329 | {
|
---|
330 | assert(i < size());
|
---|
331 |
|
---|
332 | return m_Nodes[i];
|
---|
333 | }
|
---|
334 |
|
---|
335 |
|
---|
336 | template <class N>
|
---|
337 | inline typename graph_array<N>::node_iterator graph_array<N>::begin()
|
---|
338 | {
|
---|
339 | return m_Nodes.begin();
|
---|
340 | }
|
---|
341 |
|
---|
342 |
|
---|
343 | template <class N>
|
---|
344 | inline typename graph_array<N>::node_iterator graph_array<N>::end()
|
---|
345 | {
|
---|
346 | return m_Nodes.end();
|
---|
347 | }
|
---|
348 |
|
---|
349 |
|
---|
350 | template <class N>
|
---|
351 | inline typename graph_array<N>::const_node_iterator graph_array<N>::begin() const
|
---|
352 | {
|
---|
353 | return m_Nodes.begin();
|
---|
354 | }
|
---|
355 |
|
---|
356 |
|
---|
357 | template <class N>
|
---|
358 | inline typename graph_array<N>::const_node_iterator graph_array<N>::end() const
|
---|
359 | {
|
---|
360 | return m_Nodes.end();
|
---|
361 | }
|
---|
362 |
|
---|
363 |
|
---|
364 | template <class N>
|
---|
365 | inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rbegin()
|
---|
366 | {
|
---|
367 | return m_Nodes.rbegin();
|
---|
368 | }
|
---|
369 |
|
---|
370 |
|
---|
371 | template <class N>
|
---|
372 | inline typename graph_array<N>::node_reverse_iterator graph_array<N>::rend()
|
---|
373 | {
|
---|
374 | return m_Nodes.rend();
|
---|
375 | }
|
---|
376 |
|
---|
377 |
|
---|
378 | template <class N>
|
---|
379 | inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rbegin() const
|
---|
380 | {
|
---|
381 | return m_Nodes.rbegin();
|
---|
382 | }
|
---|
383 |
|
---|
384 |
|
---|
385 | template <class N>
|
---|
386 | inline typename graph_array<N>::const_node_reverse_iterator graph_array<N>::rend() const
|
---|
387 | {
|
---|
388 | return m_Nodes.rend();
|
---|
389 | }
|
---|
390 |
|
---|
391 |
|
---|
392 | template <class N>
|
---|
393 | inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const nodeid Initial, const nodeid Terminal)
|
---|
394 | {
|
---|
395 | assert(Initial < size());
|
---|
396 | assert(Terminal < size());
|
---|
397 |
|
---|
398 | return insert_arc(m_Nodes.begin() + Initial, m_Nodes.begin() + Terminal);
|
---|
399 | }
|
---|
400 |
|
---|
401 |
|
---|
402 | template <class N>
|
---|
403 | inline typename graph_array<N>::out_arc_iterator graph_array<N>::insert_arc(const node_iterator Initial, const node_iterator Terminal)
|
---|
404 | {
|
---|
405 | assert((Initial >= begin()) && (Initial < end()));
|
---|
406 | assert((Terminal >= begin()) && (Terminal < end()));
|
---|
407 |
|
---|
408 | node & Node = * Initial;
|
---|
409 |
|
---|
410 | if (Node.out_empty()) {
|
---|
411 |
|
---|
412 | Node.m_Begin = m_Arcs.size();
|
---|
413 | Node.m_End = m_Arcs.size() + 1;
|
---|
414 |
|
---|
415 | } else {
|
---|
416 |
|
---|
417 | // we optimise here for make_connectivity_graph()
|
---|
418 | // we know all the arcs for a given node are successively and sequentially added
|
---|
419 | assert(Node.m_End == m_Arcs.size());
|
---|
420 |
|
---|
421 | ++(Node.m_End);
|
---|
422 | }
|
---|
423 |
|
---|
424 | m_Arcs.push_back(arc(Terminal));
|
---|
425 |
|
---|
426 | out_arc_iterator it = m_Arcs.end();
|
---|
427 | return (--it);
|
---|
428 | }
|
---|
429 |
|
---|
430 |
|
---|
431 | template <class N>
|
---|
432 | inline void graph_array<N>::swap(graph_type & Right)
|
---|
433 | {
|
---|
434 | std::swap(m_Nodes, Right.m_Nodes);
|
---|
435 | std::swap(m_Arcs, Right.m_Arcs);
|
---|
436 | }
|
---|
437 |
|
---|
438 |
|
---|
439 |
|
---|
440 | //////////////////////////////////////////////////////////////////////////
|
---|
441 | // additional functions
|
---|
442 | //////////////////////////////////////////////////////////////////////////
|
---|
443 |
|
---|
444 | template <class N>
|
---|
445 | inline void unmark_nodes(graph_array<N> & G)
|
---|
446 | {
|
---|
447 | std::for_each(G.begin(), G.end(), std::mem_fun_ref(&graph_array<N>::node::unmark));
|
---|
448 | }
|
---|
449 |
|
---|
450 |
|
---|
451 |
|
---|
452 |
|
---|
453 | } // namespace detail
|
---|
454 |
|
---|
455 | } // namespace triangle_stripper
|
---|
456 |
|
---|
457 |
|
---|
458 |
|
---|
459 |
|
---|
460 | #endif // TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H
|
---|