[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

graph_item_impl.hxx
1#ifndef VIGRA_NODE_IMPL_HXX
2#define VIGRA_NODE_IMPL_HXX
3
4
5
6/*vigra*/
7#include "algorithm.hxx"
8#include "tinyvector.hxx"
9#include "random_access_set.hxx"
10#include "iteratorfacade.hxx"
11
12
13
14
15
16 namespace vigra{
17
18 /*
19 within this namespace we implement
20 filter to provide generic lemon iterators
21 for a single incEdgeIterator like iterator
22
23 These Iterators are used by:
24 - AdjacencyListGraph
25 - MergeGraphAdaptor
26 */
27 namespace detail{
28
29 /*
30 a filter is a functor
31 which makes an lemon iterator
32 from a std::set<Adjacency<...> >::const_iterator like
33 iterator.
34 Using these filters will reduce the code
35 needed to implement lemon compatible iterators
36 */
37
38 // filter to iterate over neighbor nodes for
39 // for a given node
40 template<class GRAPH>
41 struct NeighborNodeFilter{
42 typedef typename GRAPH::Node ResultType;
43 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
44
45 static bool valid(
46 const GRAPH &,
47 const AdjacencyElement &,
48 const typename GRAPH::index_type /*ownNodeId*/
49 ){
50 return true;
51 }
52
53
54 static ResultType transform(
55 const GRAPH & g,
56 const AdjacencyElement & adj,
57 const typename GRAPH::index_type /*ownNodeId*/
58 ){
59 return g.nodeFromId(adj.nodeId());
60 }
61
62 static const bool IsFilter = false ;
63 };
64
65 template<class GRAPH>
66 struct IncEdgeFilter{
67 typedef typename GRAPH::Edge ResultType;
68 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
69
70 static bool valid(
71 const GRAPH &,
72 const AdjacencyElement &,
73 const typename GRAPH::index_type /*ownNodeId*/
74 ){
75 return true;
76 }
77
78 static ResultType transform(
79 const GRAPH & g,
80 const AdjacencyElement & adj,
81 const typename GRAPH::index_type /*ownNodeId*/
82 ){
83 return g.edgeFromId(adj.edgeId());
84 }
85
86 static const bool IsFilter = false ;
87 };
88
89 template<class GRAPH>
90 struct BackEdgeFilter{
91 typedef typename GRAPH::Edge ResultType;
92 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
93
94 static bool valid(
95 const GRAPH &,
96 const AdjacencyElement & adj,
97 const typename GRAPH::index_type ownNodeId
98 ){
99 return adj.nodeId() < ownNodeId;
100 }
101
102 static ResultType transform(
103 const GRAPH & g,
104 const AdjacencyElement & adj,
105 const typename GRAPH::index_type /*ownNodeId*/
106 ){
107 return g.edgeFromId(adj.edgeId());
108 }
109
110 static const bool IsFilter = true ;
111 };
112 template<class GRAPH>
113 struct IsBackOutFilter{
114 typedef typename GRAPH::Arc ResultType;
115 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
116
117 static bool valid(
118 const GRAPH &,
119 const AdjacencyElement & adj,
120 const typename GRAPH::index_type ownNodeId
121 ){
122 return adj.nodeId() < ownNodeId;
123 }
124 static ResultType transform(
125 const GRAPH & g,
126 const AdjacencyElement & adj,
127 const typename GRAPH::index_type ownNodeId
128 ){
129 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(ownNodeId));
130 }
131
132 static const bool IsFilter = true ;
133 };
134 template<class GRAPH>
135 struct IsOutFilter{
136 typedef typename GRAPH::Arc ResultType;
137 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
138
139 static bool valid(
140 const GRAPH &,
141 const AdjacencyElement &,
142 const typename GRAPH::index_type /*ownNodeId*/
143 ){
144 return true;
145 }
146 static ResultType transform(
147 const GRAPH & g,
148 const AdjacencyElement & adj,
149 const typename GRAPH::index_type ownNodeId
150 ){
151 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(ownNodeId));
152 }
153
154 static const bool IsFilter = false ;
155 };
156
157
158
159 template<class GRAPH>
160 struct IsInFilter{
161 typedef typename GRAPH::Arc ResultType;
162 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
163
164 static bool valid(
165 const GRAPH &,
166 const AdjacencyElement &,
167 const typename GRAPH::index_type /*ownNodeId*/
168 ){
169 return true;
170 }
171 ResultType static transform(
172 const GRAPH & g,
173 const AdjacencyElement & adj,
174 const typename GRAPH::index_type /*ownNodeId*/
175 ){
176 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(adj.nodeId()));
177 }
178 static const bool IsFilter = false ;
179 };
180
181 template<class GRAPH,class NODE_IMPL,class FILTER>
182 class GenericIncEdgeIt
183 : public ForwardIteratorFacade<
184 GenericIncEdgeIt<GRAPH,NODE_IMPL,FILTER>,
185 typename FILTER::ResultType,true
186 >
187 {
188 public:
189
190 typedef GRAPH Graph;
191 typedef typename Graph::index_type index_type;
192 typedef typename Graph::NodeIt NodeIt;
193 typedef typename Graph::Edge Edge;
194 typedef typename Graph::Node Node;
195 typedef typename FILTER::ResultType ResultItem;
196 //typedef typename GraphItemHelper<GRAPH,typename FILTER::ResultType> ResultItem
197
198 // default constructor
199 GenericIncEdgeIt(const lemon::Invalid & /*invalid*/ = lemon::INVALID)
200 : nodeImpl_(NULL),
201 graph_(NULL),
202 ownNodeId_(-1),
203 adjIter_(),
204 resultItem_(lemon::INVALID){
205 }
206 // from a given node iterator
207 GenericIncEdgeIt(const Graph & g , const NodeIt & nodeIt)
208 : nodeImpl_(&g.nodeImpl(*nodeIt)),
209 graph_(&g),
210 ownNodeId_(g.id(*nodeIt)),
211 adjIter_(g.nodeImpl(*nodeIt).adjacencyBegin()),
212 resultItem_(lemon::INVALID){
213
214 if(FILTER::IsFilter){
215 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_) ) {
216 ++adjIter_;
217 }
218 }
219 }
220
221 // from a given node
222 GenericIncEdgeIt(const Graph & g , const Node & node)
223 : nodeImpl_(&g.nodeImpl(node)),
224 graph_(&g),
225 ownNodeId_(g.id(node)),
226 adjIter_(g.nodeImpl(node).adjacencyBegin()),
227 resultItem_(lemon::INVALID){
228
229 if(FILTER::IsFilter){
230 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_) ) {
231 ++adjIter_;
232 }
233 }
234 }
235
236 private:
237 friend class vigra::IteratorFacadeCoreAccess;
238
239 typedef NODE_IMPL NodeImpl;
240 typedef typename NodeImpl::AdjIt AdjIt;
241
242 bool isEnd()const{
243 return (nodeImpl_==NULL || adjIter_==nodeImpl_->adjacencyEnd());
244 }
245 bool isBegin()const{
246 return (nodeImpl_!=NULL && adjIter_==nodeImpl_->adjacencyBegin());
247 }
248 bool equal(const GenericIncEdgeIt<GRAPH,NODE_IMPL,FILTER> & other)const{
249 if(isEnd() && other.isEnd()){
250 return true;
251 }
252 else if (isEnd() != other.isEnd()){
253 return false;
254 }
255 else{
256 return adjIter_==other.adjIter_;
257 }
258 }
259
260 void increment(){
261 ++adjIter_;
262 if(FILTER::IsFilter){
263 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_)){
264 ++adjIter_;
265 }
266 }
267 }
268
269 // might no need to make this constant
270 // therefore we would lose the "mutabe"
271 const ResultItem & dereference()const{
272 resultItem_ = FILTER::transform(*graph_,*adjIter_,ownNodeId_);
273 return resultItem_;
274 }
275
276
277 const NODE_IMPL * nodeImpl_;
278 const GRAPH * graph_;
279 const index_type ownNodeId_;
280 AdjIt adjIter_;
281 mutable ResultItem resultItem_;
282 };
283
284 // an element in the implementation
285 // of adjacency list
286 // End users will not notice this class
287 // => implementation detail
288 template<class T>
289 class Adjacency {
290 public:
291 typedef T Value;
292
293 Adjacency(const Value nodeId, const Value edgeId)
294 : nodeId_(nodeId),
295 edgeId_(edgeId){
296
297 }
298 Value nodeId() const{
299 return nodeId_;
300 }
301 Value& nodeId(){
302 return nodeId_;
303 }
304 Value edgeId() const{
305 return edgeId_;
306 }
307 Value& edgeId(){
308 return edgeId_;
309 }
310 bool operator<(const Adjacency<Value> & other) const{
311 return nodeId_ < other.nodeId_;
312 }
313 private:
314 Value nodeId_;
315 Value edgeId_;
316 };
317
318
319 // an element in the implementation
320 // of adjacency list
321 // End users will not notice this class
322 // => implementation detail
323 template<class INDEX_TYPE,bool USE_STL_SET>
324 class GenericNodeImpl{
325
326 public:
327 typedef INDEX_TYPE index_type;
328 typedef Adjacency<index_type> AdjacencyElement;
329 typedef std::set<AdjacencyElement > StdSetType;
330 typedef RandomAccessSet<AdjacencyElement > RandAccessSet;
331 typedef typename IfBool<USE_STL_SET,StdSetType,RandAccessSet>::type SetType;
332
333 typedef typename SetType::const_iterator AdjIt;
334 public:
335
336 GenericNodeImpl(const lemon::Invalid /*iv*/=lemon::INVALID)
337 : id_(-1){
338 }
339
340 GenericNodeImpl(const index_type id)
341 : id_(id){
342 }
343 // query
344 size_t numberOfEdges()const{return adjacency_.size();}
345 size_t edgeNum()const{return adjacency_.size();}
346 size_t num_edges()const{return adjacency_.size();}
347
348 //bool hasEdgeId(const index_type edge)const{return edges_.find(edge)!=edges_.end();}
349
350 // modification
351 void merge(const GenericNodeImpl & other){
352 adjacency_.insert(other.adjacency_.begin(),other.adjacency_.end());
353 }
354
355 void setId(const index_type id){
356 id_=id;
357 }
358
359 std::pair<index_type,bool> findEdge(const index_type nodeId)const{
360 AdjIt iter = adjacency_.find(AdjacencyElement(nodeId,0));
361 if(iter==adjacency_.end()){
362 return std::pair<index_type,bool>(-1,false);
363 }
364 else{
365 return std::pair<index_type,bool>(iter->edgeId(),true);
366 }
367 }
368
369
370
371 void insert(const index_type nodeId,const index_type edgeId){
372 adjacency_.insert(AdjacencyElement(nodeId,edgeId));
373 }
374
375 AdjIt adjacencyBegin()const{
376 return adjacency_.begin();
377 }
378 AdjIt adjacencyEnd()const{
379 return adjacency_.end();
380 }
381
382
383 index_type id()const{
384 return id_;
385 }
386
387
388 void eraseFromAdjacency(const index_type nodeId){
389 // edge id does not matter?
390 adjacency_.erase(AdjacencyElement(nodeId,0));
391 }
392
393 void clear(){
394 adjacency_.clear();
395 id_=-1;
396 }
397
398 SetType adjacency_;
399 index_type id_;
400 };
401
402 template<class INDEX_TYPE>
403 class GenericEdgeImpl
404 : public vigra::TinyVector<INDEX_TYPE,3> {
405 // public typedefs
406 public:
407 typedef INDEX_TYPE index_type;
408
409 GenericEdgeImpl(const lemon::Invalid /*iv*/=lemon::INVALID)
410 : vigra::TinyVector<INDEX_TYPE,3>(-1){
411 }
412
413 GenericEdgeImpl(const index_type u,const index_type v, const index_type id)
414 : vigra::TinyVector<INDEX_TYPE,3>(u,v,id){
415 }
416 // public methods
417 public:
418 index_type u()const{return this->operator[](0);}
419 index_type v()const{return this->operator[](1);}
420 index_type id()const{return this->operator[](2);}
421 private:
422 };
423
424
425 template<class INDEX_TYPE>
426 class GenericEdge;
427
428 template<class INDEX_TYPE>
429 class GenericArc{
430 public:
431 typedef INDEX_TYPE index_type;
432
433 GenericArc(const lemon::Invalid & /*iv*/ = lemon::INVALID)
434 : id_(-1),
435 edgeId_(-1){
436
437 }
438
439
440
441 GenericArc(
442 const index_type id,
443 const index_type edgeId = static_cast<index_type>(-1)
444 )
445 : id_(id),
446 edgeId_(edgeId){
447
448 }
449 index_type id()const{return id_;}
450 index_type edgeId()const{return edgeId_;}
451
452 operator GenericEdge<INDEX_TYPE> () const{
453 return GenericEdge<INDEX_TYPE>(edgeId());
454 }
455
456 bool operator == (const GenericArc<INDEX_TYPE> & other )const{
457 return id_ == other.id_;
458 }
459 bool operator != (const GenericArc<INDEX_TYPE> & other )const{
460 return id_ != other.id_;
461 }
462 bool operator < (const GenericArc<INDEX_TYPE> & other )const{
463 return id_ < other.id_;
464 }
465 bool operator > (const GenericArc<INDEX_TYPE> & other )const{
466 return id_ > other.id_;
467 }
468
469
470
471 private:
472 index_type id_;
473 index_type edgeId_;
474 };
475
476 template<class INDEX_TYPE>
477 class GenericEdge{
478 public:
479 typedef INDEX_TYPE index_type;
480
481 GenericEdge(const lemon::Invalid & /*iv*/ = lemon::INVALID)
482 : id_(-1){
483
484 }
485
486 GenericEdge(const index_type id )
487 : id_(id){
488
489 }
490
491 GenericEdge(const GenericArc<INDEX_TYPE> & arc)
492 : id_(arc.edgeId())
493 {
494 }
495
496 bool operator == (const GenericEdge<INDEX_TYPE> & other )const{
497 return id_ == other.id_;
498 }
499 bool operator != (const GenericEdge<INDEX_TYPE> & other )const{
500 return id_ != other.id_;
501 }
502 bool operator < (const GenericEdge<INDEX_TYPE> & other )const{
503 return id_ < other.id_;
504 }
505 bool operator > (const GenericEdge<INDEX_TYPE> & other )const{
506 return id_ > other.id_;
507 }
508 bool operator <= (const GenericEdge<INDEX_TYPE> & other )const{
509 return id_ <= other.id_;
510 }
511 bool operator >= (const GenericEdge<INDEX_TYPE> & other )const{
512 return id_ >= other.id_;
513 }
514
515
516 index_type id()const{return id_;}
517 private:
518 index_type id_;
519 };
520
521
522 template<class INDEX_TYPE>
523 class GenericNode{
524 public:
525 typedef INDEX_TYPE index_type;
526
527 GenericNode(const lemon::Invalid & /*iv*/ = lemon::INVALID)
528 : id_(-1){
529
530 }
531
532 GenericNode(const index_type id )
533 : id_(id){
534
535 }
536 bool operator == (const GenericNode<INDEX_TYPE> & other )const{
537 return id_ == other.id_;
538 }
539 bool operator != (const GenericNode<INDEX_TYPE> & other )const{
540 return id_ != other.id_;
541 }
542 bool operator < (const GenericNode<INDEX_TYPE> & other )const{
543 return id_ < other.id_;
544 }
545 bool operator > (const GenericNode<INDEX_TYPE> & other )const{
546 return id_ > other.id_;
547 }
548
549 index_type id()const{return id_;}
550 private:
551 index_type id_;
552 };
553
554 } // namespace detail
555} // end namespace vigra
556
557 namespace std {
558
559 template<class INDEX_TYPE>
560ostream & operator<<(ostream & o, vigra::detail::GenericNode<INDEX_TYPE> const & n)
561{
562 o << "Node(" << n.id() << ")";
563 return o;
564}
565
566 template<class INDEX_TYPE>
567ostream & operator<<(ostream & o, vigra::detail::GenericEdge<INDEX_TYPE> const & e)
568{
569 o << "Edge(" << e.id() << ")";
570 return o;
571}
572
573}
574
575#endif // VIGRA_NODE_IMPL_HXX
vigra::TinyVectorBase::operator[]
reference operator[](difference_type i)
Definition tinyvector.hxx:845
vigra::TinyVector
Class for fixed size vectors.
Definition tinyvector.hxx:1008
vigra::TinyVector< INDEX_TYPE, 3 >::TinyVector
TinyVector()
Definition tinyvector.hxx:1113
vigra
vigra::operator<
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition fixedpoint.hxx:512

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.12.2