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

graph_item_impl.hxx VIGRA

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 & g,
47  const AdjacencyElement & adj,
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 & g,
72  const AdjacencyElement & adj,
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 & g,
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 & g,
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 & g,
141  const AdjacencyElement & adj,
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 & g,
166  const AdjacencyElement & adj,
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 
356  std::pair<index_type,bool> findEdge(const index_type nodeId)const{
357  AdjIt iter = adjacency_.find(AdjacencyElement(nodeId,0));
358  if(iter==adjacency_.end()){
359  return std::pair<index_type,bool>(-1,false);
360  }
361  else{
362  return std::pair<index_type,bool>(iter->edgeId(),true);
363  }
364  }
365 
366 
367 
368  void insert(const index_type nodeId,const index_type edgeId){
369  adjacency_.insert(AdjacencyElement(nodeId,edgeId));
370  }
371 
372  AdjIt adjacencyBegin()const{
373  return adjacency_.begin();
374  }
375  AdjIt adjacencyEnd()const{
376  return adjacency_.end();
377  }
378 
379 
380  index_type id()const{
381  return id_;
382  }
383  void clear(){
384  adjacency_.clear();
385  }
386 
387  void eraseFromAdjacency(const index_type nodeId){
388  // edge id does not matter?
389  adjacency_.erase(AdjacencyElement(nodeId,0));
390  }
391 
392  SetType adjacency_;
393  index_type id_;
394  };
395 
396  template<class INDEX_TYPE>
397  class GenericEdgeImpl
398  : public vigra::TinyVector<INDEX_TYPE,3> {
399  // public typedefs
400  public:
401  typedef INDEX_TYPE index_type;
402 
403  GenericEdgeImpl(const lemon::Invalid iv=lemon::INVALID)
404  : vigra::TinyVector<INDEX_TYPE,3>(-1){
405  }
406 
407  GenericEdgeImpl(const index_type u,const index_type v, const index_type id)
408  : vigra::TinyVector<INDEX_TYPE,3>(u,v,id){
409  }
410  // public methods
411  public:
412  index_type u()const{return this->operator[](0);}
413  index_type v()const{return this->operator[](1);}
414  index_type id()const{return this->operator[](2);}
415  private:
416  };
417 
418 
419  template<class INDEX_TYPE>
420  class GenericEdge;
421 
422  template<class INDEX_TYPE>
423  class GenericArc{
424  public:
425  typedef INDEX_TYPE index_type;
426 
427  GenericArc(const lemon::Invalid & iv = lemon::INVALID)
428  : id_(-1),
429  edgeId_(-1){
430 
431  }
432 
433 
434 
435  GenericArc(
436  const index_type id,
437  const index_type edgeId = static_cast<index_type>(-1)
438  )
439  : id_(id),
440  edgeId_(edgeId){
441 
442  }
443  index_type id()const{return id_;}
444  index_type edgeId()const{return edgeId_;}
445 
446  operator GenericEdge<INDEX_TYPE> () const{
447  return GenericEdge<INDEX_TYPE>(edgeId());
448  }
449 
450  bool operator == (const GenericArc<INDEX_TYPE> & other )const{
451  return id_ == other.id_;
452  }
453  bool operator != (const GenericArc<INDEX_TYPE> & other )const{
454  return id_ != other.id_;
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 
463 
464 
465  private:
466  index_type id_;
467  index_type edgeId_;
468  };
469 
470  template<class INDEX_TYPE>
471  class GenericEdge{
472  public:
473  typedef INDEX_TYPE index_type;
474 
475  GenericEdge(const lemon::Invalid & iv = lemon::INVALID)
476  : id_(-1){
477 
478  }
479 
480  GenericEdge(const index_type id )
481  : id_(id){
482 
483  }
484 
485  GenericEdge(const GenericArc<INDEX_TYPE> & arc)
486  : id_(arc.edgeId())
487  {
488  }
489 
490  bool operator == (const GenericEdge<INDEX_TYPE> & other )const{
491  return id_ == other.id_;
492  }
493  bool operator != (const GenericEdge<INDEX_TYPE> & other )const{
494  return id_ != other.id_;
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 
509 
510  index_type id()const{return id_;}
511  private:
512  index_type id_;
513  };
514 
515 
516  template<class INDEX_TYPE>
517  class GenericNode{
518  public:
519  typedef INDEX_TYPE index_type;
520 
521  GenericNode(const lemon::Invalid & iv = lemon::INVALID)
522  : id_(-1){
523 
524  }
525 
526  GenericNode(const index_type id )
527  : id_(id){
528 
529  }
530  bool operator == (const GenericNode<INDEX_TYPE> & other )const{
531  return id_ == other.id_;
532  }
533  bool operator != (const GenericNode<INDEX_TYPE> & other )const{
534  return id_ != other.id_;
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 
543  index_type id()const{return id_;}
544  private:
545  index_type id_;
546  };
547 
548  } // namespace detail
549 } // end namespace vigra
550 
551 namespace std {
552 
553 template<class INDEX_TYPE>
554 ostream & operator<<(ostream & o, vigra::detail::GenericNode<INDEX_TYPE> const & n)
555 {
556  o << "Node(" << n.id() << ")";
557  return o;
558 }
559 
560 template<class INDEX_TYPE>
561 ostream & operator<<(ostream & o, vigra::detail::GenericEdge<INDEX_TYPE> const & e)
562 {
563  o << "Edge(" << e.id() << ")";
564  return o;
565 }
566 
567 }
568 
569 #endif // VIGRA_NODE_IMPL_HXX

© 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.10.0 (Thu Jan 8 2015)