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

merge_graph_adaptor.hxx VIGRA

1 
2 /************************************************************************/
3 /* */
4 /* Copyright 2014 by Thorsten Beier and Ullrich Koethe */
5 /* */
6 /* This file is part of the VIGRA computer vision library. */
7 /* The VIGRA Website is */
8 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
9 /* Please direct questions, bug reports, and contributions to */
10 /* ullrich.koethe@iwr.uni-heidelberg.de or */
11 /* vigra@informatik.uni-hamburg.de */
12 /* */
13 /* Permission is hereby granted, free of charge, to any person */
14 /* obtaining a copy of this software and associated documentation */
15 /* files (the "Software"), to deal in the Software without */
16 /* restriction, including without limitation the rights to use, */
17 /* copy, modify, merge, publish, distribute, sublicense, and/or */
18 /* sell copies of the Software, and to permit persons to whom the */
19 /* Software is furnished to do so, subject to the following */
20 /* conditions: */
21 /* */
22 /* The above copyright notice and this permission notice shall be */
23 /* included in all copies or substantial portions of the */
24 /* Software. */
25 /* */
26 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
27 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
28 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
29 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
30 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
31 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
32 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
33 /* OTHER DEALINGS IN THE SOFTWARE. */
34 /* */
35 /************************************************************************/
36 
37 
38 #ifndef VIGRA_NEW_MERGE_GRAPH_HXX
39 #define VIGRA_NEW_MERGE_GRAPH_HXX
40 
41 
42 /* delegates / callbacks */
43 #include "delegate/delegate.hxx"
44 
45 /* std library */
46 #include <vector>
47 #include <algorithm>
48 #include <cmath>
49 #include <stdexcept>
50 #include <map>
51 
52 /* vigra */
53 #include "multi_array.hxx"
54 #include "tinyvector.hxx"
55 #include "multi_array.hxx"
56 #include "graphs.hxx"
57 #include "graph_maps.hxx"
58 #include "graph_item_impl.hxx"
59 #include "random_access_set.hxx"
60 #include "iteratorfacade.hxx"
61 
62 
63 namespace vigra {
64 
65 namespace merge_graph_detail {
66 
67 // ufd data structure structure for merge graph
68 // only useful for merge graphs internal usage
69 template<class T>
71 
72 // representative element iterator
73 // for IterablePartition
74 // only useful for merge graphs internal usage
75 template<class T>
76 struct ConstRepIter
77 : public ForwardIteratorFacade<
78  ConstRepIter<T>,T,true
79  >
80 
81 {
82  typedef IterablePartition<T> IterablePartitionType;
83  ConstRepIter(const IterablePartitionType & p,const T cr)
84  : partition_(&p),
85  currentRep_(cr){
86  }
87 
88 
89  ConstRepIter()
90  : partition_(NULL),
91  currentRep_()
92  {
93  }
94 
95 private:
96  friend class vigra::IteratorFacadeCoreAccess;
97 
98 
99  bool isBegin()const{
100  return partition_!=NULL && currentRep_==partition_->firstRep();
101  }
102  bool isEnd()const{
103  return partition_==NULL || currentRep_>partition_->lastRep();
104  }
105 
106  bool equal(const ConstRepIter & other)const{
107  return (this->isEnd() && other.isEnd() ) || ((this->isEnd()==other.isEnd() ) && this->currentRep_==other.currentRep_);
108  }
109 
110  void increment(){
111  if(partition_->jumpVec_[currentRep_].second==0){
112  currentRep_+=1;
113  }
114  else{
115  currentRep_+=partition_->jumpVec_[currentRep_].second;
116  }
117  }
118 
119  void decrement(){
120  if(partition_->jumpVec_[currentRep_].first==0){
121  //VIGRA_ASSERT_OP(currentRep_,==,partition_->firstRep());
122  //currentRep_+=1;
123  }
124  else{
125  currentRep_-=partition_->jumpVec_[currentRep_].first;
126  }
127  }
128 
129  const T & dereference()const{
130  return currentRep_;
131  }
132 
133 
134 
135  const IterablePartitionType * partition_;
136  T currentRep_;
137 
138 };
139 
140 
141 
142 // ufd data structure structure for merge graph
143 // only useful for merge graphs internal usage
144 /// Disjoint set data structure with path compression.
145 /// \ingroup datastructures
146 template<class T>
147 class IterablePartition {
148 public:
149  friend struct ConstRepIter<T>;
150  typedef T value_type;
151  typedef std::size_t SizeTType;
153  IterablePartition(const value_type&);
154 
155  // query
156  value_type find(const value_type&) const; // without path compression
157  value_type find(value_type); // with path compression
158  value_type numberOfElements() const;
159  value_type numberOfSets() const;
160  template<class Iterator> void elementLabeling(Iterator) const;
161  template<class Iterator> void representatives(Iterator) const;
162  void representativeLabeling(std::map<value_type, value_type>&) const;
163 
164  // manipulation
165  void reset(const value_type&);
166  void merge(value_type, value_type);
167 
168  value_type firstRep()const{
169  return firstRep_;
170  }
171  value_type lastRep()const{
172  return lastRep_;
173  }
174  typedef ConstRepIter<T> const_iterator;
175 
176  const_iterator begin()const{
177  if(numberOfSets_!=0)
178  return ConstRepIter<T>(*this,firstRep_);
179  else
180  return ConstRepIter<T>(*this,lastRep_+1);
181  }
182  const_iterator end()const{
183  return ConstRepIter<T>(*this,lastRep_+1);
184  }
185 
186 
187  const_iterator iteratorAt(const value_type & rep)const{
188  if(numberOfSets_!=0)
189  return ConstRepIter<T>(*this,rep);
190  else
191  return ConstRepIter<T>(*this,lastRep_+1);
192  }
193 
194  bool isErased(const value_type & value)const{
195  return jumpVec_[value].first == -1 && jumpVec_[value].second == -1;
196  }
197 
198  void eraseElement(const value_type & value,const bool reduceSize=true){
199  const T notRep=value;
200  const T jumpMinus = jumpVec_[notRep].first;
201  const T jumpPlus = jumpVec_[notRep].second;
202 
203  if(jumpMinus==0){
204  const T nextRep = notRep+jumpPlus;
205  firstRep_=nextRep;
206  jumpVec_[nextRep].first=0;
207  }
208  else if(jumpPlus==0){
209  //VIGRA_ASSERT_OP(lastRep_,==,notRep);
210  const T prevRep = notRep-jumpMinus;
211  lastRep_=prevRep;
212  jumpVec_[prevRep].second=0;
213 
214  }
215  else{
216  const T nextRep = notRep+jumpPlus;
217  const T prevRep = notRep-jumpMinus;
218  jumpVec_[nextRep].first+=jumpVec_[notRep].first;
219  jumpVec_[prevRep].second+=jumpVec_[notRep].second;
220  }
221  if(reduceSize){
222  --numberOfSets_;
223  }
224  jumpVec_[notRep].first =-1;
225  jumpVec_[notRep].second =-1;
226  }
227 
228 private:
229  std::vector<value_type> parents_;
230  std::vector<value_type> ranks_;
231  std::vector< std::pair< vigra::Int64, vigra::Int64> > jumpVec_;
232  value_type firstRep_;
233  value_type lastRep_;
234  value_type numberOfElements_;
235  value_type numberOfSets_;
236 };
237 
238 
239 } // end namespa merge graph detail
240 
241 
242 
243 // helper classes to generalize
244 // some functionality for
245 // nodes,edges and arcs
246 template<class GRAPH,class ITEM>
247 struct MergeGraphItemHelper;
248 
249 template<class MG>
250 struct MergeGraphItemHelper<MG,typename MG::Edge>{
251  typedef typename MG::Graph Graph;
252  typedef typename MG::index_type index_type ;
253  typedef typename MG::Edge Item;
254  typedef typename Graph::Edge GraphItem;
255  typedef typename MG::EdgeIt ItemIt;
256 
257 
258  static index_type maxItemId(const MG & g){
259  return g.maxEdgeId();
260  }
261  static index_type itemNum(const MG & g){
262  return g.edgeNum();
263  }
264 
265  static GraphItem itemToGraphItem(const MG & g,const Item & item){
266  const index_type id = g.id(item);
267  return g.graph().edgeFromId(id);
268  }
269 };
270 
271 template<class MG>
272 struct MergeGraphItemHelper<MG,typename MG::Node>{
273  typedef typename MG::Graph Graph;
274  typedef typename MG::index_type index_type ;
275  typedef typename MG::Node Item;
276  typedef typename Graph::Node GraphItem;
277  typedef typename MG::NodeIt ItemIt;
278 
279 
280  static index_type maxItemId(const MG & g){
281  return g.maxNodeId();
282  }
283  static index_type itemNum(const MG & g){
284  return g.nodeNum();
285  }
286  static GraphItem itemToGraphItem(const MG & g,const Item & item){
287  const index_type id = g.id(item);
288  return g.graph().nodeFromId(id);
289  }
290 };
291 
292 // merge graphs LEMON compatible iterator
293 template<class MERGE_GRAPH>
294 class MergeGraphNodeIt
295 : public ForwardIteratorFacade<MergeGraphNodeIt<MERGE_GRAPH>,typename MERGE_GRAPH::Node,true>{
296 public:
297  typedef MERGE_GRAPH Graph;
298  typedef typename Graph::Node Node;
299  // Invalid constructor & conversion.
300  MergeGraphNodeIt(const lemon::Invalid & invalid = lemon::INVALID)
301  : graph_(NULL),
302  nodeIdIt_(),
303  node_(){
304 
305  }
306  MergeGraphNodeIt(const Graph & g)
307  : graph_(&g),
308  nodeIdIt_(g.nodeUfd_.begin()),
309  node_(){
310  }
311  MergeGraphNodeIt(const Graph & g,const Node & node)
312  : graph_(&g),
313  nodeIdIt_(g.nodeUfd_.iteratorAt(g.id(node))),
314  node_(){
315 
316  }
317  bool isEnd()const{
318  return graph_==NULL || nodeIdIt_==graph_->nodeUfd_.end();
319  }
320  bool isBegin()const{
321  return graph_!=NULL && nodeIdIt_==graph_->nodeUfd_.begin();
322  }
323 private:
324  friend class vigra::IteratorFacadeCoreAccess;
325 
326 
327  bool equal(const MergeGraphNodeIt<MERGE_GRAPH> & other)const{
328  return (isEnd()&&other.isEnd()) || nodeIdIt_==other.nodeIdIt_;
329  }
330  void increment(){++nodeIdIt_;}
331  const Node & dereference()const{
332  node_=Node(*nodeIdIt_);
333  return node_;
334  }
335  // members
336  const Graph * graph_;
337  typename Graph::NodeIdIt nodeIdIt_;
338  mutable Node node_;
339 };
340 
341 // merge graphs LEMON compatible iterator
342 template<class MERGE_GRAPH>
343 class MergeGraphEdgeIt
344 : public ForwardIteratorFacade<MergeGraphEdgeIt<MERGE_GRAPH>,typename MERGE_GRAPH::Edge,true>{
345 public:
346  typedef MERGE_GRAPH Graph;
347  typedef typename Graph::Edge Edge;
348  // Invalid constructor & conversion.
349  MergeGraphEdgeIt(const lemon::Invalid & invalid = lemon::INVALID)
350  : graph_(NULL),
351  edgeIdIt_(),
352  edge_(){
353  }
354  MergeGraphEdgeIt(const Graph & g)
355  : graph_(&g),
356  edgeIdIt_(g.edgeUfd_.begin()),
357  edge_(){
358 
359  }
360  MergeGraphEdgeIt(const Graph & g,const Edge & node)
361  : graph_(&g),
362  edgeIdIt_(g.edgeUfd_.iteratorAt(g.id(node))),
363  edge_(){
364  }
365  bool isEnd()const{
366  return graph_==NULL || edgeIdIt_==graph_->edgeUfd_.end();
367  }
368  bool isBegin()const{
369  return graph_!=NULL && edgeIdIt_==graph_->edgeUfd_.begin();
370  }
371 private:
372  friend class vigra::IteratorFacadeCoreAccess;
373 
374 
375  bool equal(const MergeGraphEdgeIt<MERGE_GRAPH> & other)const{
376  return (isEnd()&&other.isEnd()) || edgeIdIt_==other.edgeIdIt_;
377  }
378  void increment(){
379  ++edgeIdIt_;
380  }
381  const Edge & dereference()const{
382  edge_=Edge(*edgeIdIt_);
383  return edge_;
384  }
385  // members
386  const Graph * graph_;
387  typename Graph::EdgeIdIt edgeIdIt_;
388  mutable Edge edge_;
389 };
390 
391 // merge graphs LEMON compatible iterator
392 template<class GRAPH>
393 class MergeGraphArcIt
394 : public ForwardIteratorFacade<
395  MergeGraphArcIt<GRAPH>,typename GRAPH::Arc,true
396 >
397 {
398 public:
399  typedef GRAPH Graph;
400  typedef typename Graph::Arc Arc;
401  typedef typename Graph::Edge Edge;
402  typedef typename Graph::EdgeIt EdgeIt;
403  MergeGraphArcIt(const lemon::Invalid invalid = lemon::INVALID )
404  : graph_(NULL),
405  pos_(),
406  inFirstHalf_(false),
407  veryEnd_(true),
408  arc_(){
409  }
410  MergeGraphArcIt(const GRAPH & g )
411  : graph_(&g),
412  pos_(g),
413  inFirstHalf_(true),
414  veryEnd_( g.edgeNum()==0 ? true : false),
415  arc_(){
416  }
417 
418  MergeGraphArcIt(const GRAPH & g , const Arc & arc )
419  : graph_(&g),
420  pos_(g,arc.edgeId()),
421  inFirstHalf_(g.id(arc)<=g.maxEdgeId()),
422  veryEnd_(false),
423  arc_(){
424  }
425 private:
426  friend class vigra::IteratorFacadeCoreAccess;
427  bool isEnd()const{
428  return veryEnd_ || graph_==NULL;
429  }
430 
431  bool isBegin()const{
432  return graph_!=NULL && veryEnd_==false && pos_ == EdgeIt(*graph_);
433  }
434 
435  void increment() {
436  if(inFirstHalf_){
437  ++pos_;
438  if(pos_ == lemon::INVALID ) {
439  pos_ = EdgeIt(*graph_);
440  inFirstHalf_=false;
441  }
442  return;
443  }
444  else{
445  ++pos_;
446  if(pos_ == lemon::INVALID){
447  veryEnd_=true;
448  }
449  return;
450  }
451 
452 
453  }
454  bool equal(MergeGraphArcIt const& other) const{
455  return (
456  (
457  isEnd()==other.isEnd() &&
458  inFirstHalf_==other.inFirstHalf_
459  ) &&
460  (isEnd() || graph_==NULL || pos_==other.pos_ )
461  );
462 
463  }
464 
465  const Arc & dereference() const {
466  //std::cout<<graph_->id(*pos_)<<"\n";
467  arc_ = graph_->direct(*pos_,inFirstHalf_);
468  return arc_;
469  }
470 
471 
472  const GRAPH * graph_;
473  EdgeIt pos_;
474  bool inFirstHalf_;
475  bool veryEnd_;
476  mutable Arc arc_;
477 };
478 
479 
480 // callbacks of merge graph
481 // to update node and edge maps w.r.t. edge contractions
482 template<class NODE,class EDGE>
483 class MergeGraphCallbacks{
484  public:
485 
486  typedef delegate2<void ,const NODE & ,const NODE &> MergeNodeCallBackType;
487  typedef delegate2<void ,const EDGE & ,const EDGE &> MergeEdgeCallBackType;
488  typedef delegate1<void ,const EDGE &> EraseEdgeCallBackType;
489 
490  MergeGraphCallbacks(){}
491 
492  void registerMergeNodeCallBack(MergeNodeCallBackType f){
493  mergeNodeCallbacks_.push_back(f);
494  }
495  void registerMergeEdgeCallBack(MergeEdgeCallBackType f){
496  mergeEdgeCallbacks_.push_back(f);
497  }
498  void registerEraseEdgeCallBack(EraseEdgeCallBackType f){
499  eraseEdgeCallbacks_.push_back(f);
500  }
501 
502  protected:
503  void callMergeNodeCallbacks(const NODE & a,const NODE & b){
504  for(size_t i=0;i<mergeNodeCallbacks_.size();++i)
505  mergeNodeCallbacks_[i](a,b);
506  }
507  void callMergeEdgeCallbacks(const EDGE & a,const EDGE & b){
508  for(size_t i=0;i<mergeEdgeCallbacks_.size();++i)
509  mergeEdgeCallbacks_[i](a,b);
510  }
511  void callEraseEdgeCallbacks(const EDGE & a){
512  for(size_t i=0;i<eraseEdgeCallbacks_.size();++i)
513  eraseEdgeCallbacks_[i](a);
514  }
515  private:
516  std::vector<MergeNodeCallBackType> mergeNodeCallbacks_;
517  std::vector<MergeEdgeCallBackType> mergeEdgeCallbacks_;
518  std::vector<EraseEdgeCallBackType> eraseEdgeCallbacks_;
519 };
520 
521 
522 
523 /** \brief undirected graph adaptor
524  for edge contraction and feature merging
525  */
526 template<class GRAPH>
528 : public MergeGraphCallbacks<
529  detail::GenericNode<vigra::Int64> ,
530  detail::GenericEdge<vigra::Int64>
531  >
532 
533 {
534 
535  public:
536  typedef vigra::Int64 IdType;
537  typedef IdType index_type;
539 
540 
541  typedef detail::GenericNode<index_type> Node;
542  typedef detail::GenericEdge<index_type> Edge;
543  typedef detail::GenericArc<index_type> Arc;
544 
545  typedef GRAPH Graph;
546  typedef typename Graph::Node GraphNode;
547  typedef typename Graph::Edge GraphEdge;
548  typedef typename Graph::Node GraphArc;
549 
550 
551 
552 
553 
554  //typedef std::set<index_type> NodeStorageEdgeSet;
555  typedef detail::GenericNodeImpl<index_type,false > NodeStorage;
556  typedef detail::GenericEdgeImpl<index_type > EdgeStorage;
557 
558 
559 
560  private:
561 
562  typedef std::map<vigra::UInt64 , std::vector<IdType> > DoubleMap;
564  typedef typename UfdType::const_iterator ConstUdfIter;
565  typedef ConstUdfIter EdgeIdIt;
566  typedef ConstUdfIter NodeIdIt;
567  typedef detail::NeighborNodeFilter<MergeGraphType> NnFilter;
568  typedef detail::IncEdgeFilter<MergeGraphType> IncFilter;
569  typedef detail::IsInFilter<MergeGraphType> InFlter;
570  typedef detail::IsOutFilter<MergeGraphType> OutFilter;
571  public:
572  typedef MergeGraphNodeIt<MergeGraphType> NodeIt;
573  typedef MergeGraphEdgeIt<MergeGraphType> EdgeIt;
574  typedef MergeGraphArcIt<MergeGraphType> ArcIt;
575  typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,NnFilter > NeighborNodeIt;
576  typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,IncFilter > IncEdgeIt;
577  typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,InFlter > InArcIt;
578  typedef detail::GenericIncEdgeIt<MergeGraphType,NodeStorage,OutFilter > OutArcIt;
579 
580 
581 
582  template<class T>
583  struct EdgeMap : DenseEdgeReferenceMap<MergeGraphType,T> {
584  EdgeMap(): DenseEdgeReferenceMap<MergeGraphType,T>(){
585  }
586  EdgeMap(const MergeGraphType & g)
587  : DenseEdgeReferenceMap<MergeGraphType,T>(g){
588  }
589  EdgeMap(const MergeGraphType & g,const T & val)
590  : DenseEdgeReferenceMap<MergeGraphType,T>(g,val){
591  }
592  };
593 
594  template<class T>
595  struct NodeMap : DenseNodeReferenceMap<MergeGraphType,T> {
596  NodeMap(): DenseNodeReferenceMap<MergeGraphType,T>(){
597  }
598  NodeMap(const MergeGraphType & g)
599  : DenseNodeReferenceMap<MergeGraphType,T>(g){
600  }
601  NodeMap(const MergeGraphType & g,const T & val)
602  : DenseNodeReferenceMap<MergeGraphType,T>(g,val){
603  }
604  };
605 
606  template<class T>
607  struct ArcMap : DenseArcReferenceMap<MergeGraphType,T> {
608  ArcMap(): DenseArcReferenceMap<MergeGraphType,T>(){
609  }
610  ArcMap(const MergeGraphType & g)
611  : DenseArcReferenceMap<MergeGraphType,T>(g){
612  }
613  ArcMap(const MergeGraphType & g,const T & val)
614  : DenseArcReferenceMap<MergeGraphType,T>(g,val){
615  }
616  };
617 
618 
619 
620  private:
621  MergeGraphAdaptor(); // non empty-construction
622  MergeGraphAdaptor( const MergeGraphAdaptor& other ); // non construction-copyable
623  MergeGraphAdaptor& operator=( const MergeGraphAdaptor& ); // non copyable
624  public:
625  MergeGraphAdaptor(const Graph & graph);
626  //void setInitalEdge(const size_t initEdge,const size_t initNode0,const size_t initNode1);
627 
628  // query (sizes)
629  size_t edgeNum()const;
630  size_t nodeNum()const;
631  size_t arcNum()const;
632 
633  IdType maxEdgeId()const;
634  IdType maxNodeId()const;
635  IdType maxArcId()const;
636 
637 
638  // query (iterators )
639  EdgeIdIt edgeIdsBegin()const;
640  EdgeIdIt edgeIdsEnd()const;
641  NodeIdIt nodeIdsBegin()const;
642  NodeIdIt nodeIdsEnd()const;
643 
644 
645 
646 
647  // query (get edge / nodes from id)
648  Edge edgeFromId(const IdType index)const;
649  Node nodeFromId(const IdType index)const;
650  Arc arcFromId( const IdType index)const;
651 
652 
653 
654 
655 
656  // query ( has edge )
657  bool hasEdgeId(const IdType edgeIndex)const;
658  bool hasNodeId(const IdType nodeIndex)const;
659  bool hasArcId(const IdType arcId)const{
660  return hasEdgeId(arcFromId(arcId).edgeId());
661  }
662 
663 
664  Edge findEdge(const Node & a,const Node & b)const;
665  Arc findArc(const Node & u,const Node & v)const;
666 
667 
668  IdType id(const Edge & edge)const;
669  IdType id(const Node & node)const;
670  IdType id(const Arc & arc)const;
671 
672 
673  size_t degree(const Node & node)const;
674 
675 
676 
677  Node u(const Edge & edge)const;
678  Node v(const Edge & edge)const;
679 
680  Node source(const Arc & arc)const{
681  if(arc!=lemon::INVALID)
682  return direction(arc) ? u(Edge(arc)) : v(Edge(arc));
683  else
684  return Node(lemon::INVALID);
685  }
686  Node target(const Arc & arc)const{
687  if(arc!=lemon::INVALID)
688  return direction(arc) ? v(Edge(arc)) : u(Edge(arc));
689  else
690  return Node(lemon::INVALID);
691  }
692 
693 
694  // query (w.r.t. inital nodesIds/edgesIds)
695  IdType reprEdgeId(const IdType edgeIndex)const;
696  IdType reprNodeId(const IdType nodeIndex)const;
697  bool stateOfInitalEdge(const IdType initalEdge)const;
698  // modification
699  void contractEdge(const Edge & edge);
700 
701 
702  Node oppositeNode(Node const &n, const Edge &e) const {
703  const Node uNode = u(e);
704  const Node vNode = v(e);
705  if(id(uNode)==id(n)){
706  return vNode;
707  }
708  else if(id(vNode)==id(n)){
709  return uNode;
710  }
711  else{
712  return Node(lemon::INVALID);
713  }
714  }
715 
716 
717  Arc direct(const Edge & edge,const bool forward)const{
718  if(edge!=lemon::INVALID){
719  if(forward)
720  return Arc(id(edge),id(edge));
721  else
722  return Arc(id(edge)+(maxEdgeId()+1),id(edge));
723  }
724  else{
725  return Arc(lemon::INVALID);
726  }
727  }
728  Arc direct(const Edge & edge,const Node & node)const{
729  if(u(edge)==node)
730  return direct(edge,true);
731  else if(v(edge)==node)
732  return direct(edge,false);
733  else
734  return Arc(lemon::INVALID);
735  }
736 
737  bool direction(const Arc & arc)const{
738  return arc.id()==arc.edgeId();
739  }
740 
741 
742  // special merge graph members
743  GraphEdge reprGraphEdge(const GraphEdge & edge)const{
744  return graph_.edgeFromId(reprEdgeId(graph_.id(edge)));
745  }
746  GraphNode reprGraphNode(const GraphNode & node)const{
747  return graph_.nodeFromId(reprNodeId(graph_.id(node)));
748  }
749 
750 
751  Edge reprEdge(const GraphEdge & edge)const{
752  return edgeFromId(reprEdgeId(graph_.id(edge)));
753  }
754  Node reprNode(const GraphNode & node)const{
755  return nodeFromId(reprNodeId(graph_.id(node)));
756  }
757 
758  const Graph & graph()const{
759  return graph_;
760  }
761  const Graph & graph(){
762  return graph_;
763  }
764 
765  // in which node is a "merged inactive" edge
766  Node inactiveEdgesNode(const Edge edge)const{
767  return reprNodeId(graphUId(id(edge)));
768  }
769  size_t maxDegree()const{
770  size_t md=0;
771  for(NodeIt it(*this);it!=lemon::INVALID;++it){
772  std::max(md, size_t( degree(*it) ) );
773  }
774  return md;
775  }
776 
777  private:
778  // needs acces to const nodeImpl
779  template<class G,class NIMPL,class FILT>
780  friend class detail::GenericIncEdgeIt;
781 
782  template<class G>
783  friend struct detail::NeighborNodeFilter;
784  template<class G>
785  friend struct detail::IncEdgeFilter;
786  template<class G>
787  friend struct detail::BackEdgeFilter;
788  template<class G>
789  friend struct detail::IsOutFilter;
790  template<class G>
791  friend struct detail::IsInFilter;
792  friend class MergeGraphNodeIt<MergeGraphType>;
793  friend class MergeGraphArcIt<MergeGraphType>;
794  friend class MergeGraphEdgeIt<MergeGraphType>;
795 
796  Edge edgeFromIdUnsave(const IdType index)const;
797 
798  index_type uId(const index_type edgeId)const;
799  index_type vId(const index_type edgeId)const;
800  index_type graphUId(const index_type edgeId)const;
801  index_type graphVId(const index_type edgeId)const;
802  //index_type uId(const Edge & edge)const{return uId(id(edge));}
803  //index_type vId(const Edge & edge)const{return vId(id(edge));}
804  const NodeStorage & nodeImpl(const Node & node)const{
805  return nodeVector_[id(node)];
806  }
807  NodeStorage & nodeImpl(const Node & node){
808  return nodeVector_[id(node)];
809  }
810 
811 
812  const GRAPH & graph_;
813  size_t nInitNodes_;
814  size_t nInitEdges_;
815 
816  UfdType nodeUfd_;
817  UfdType edgeUfd_;
818 
819  std::vector< NodeStorage > nodeVector_;
820 
821  size_t nDoubleEdges_;
822  std::vector<std::pair<index_type,index_type> > doubleEdges_;
823 };
824 
825 
826 template<class GRAPH>
828 : MergeGraphCallbacks<Node,Edge >(),
829  graph_(graph),
830  nInitNodes_(0),
831  nInitEdges_(0),
832  nodeUfd_(graph.maxNodeId()+1),
833  edgeUfd_(graph.maxEdgeId()+1),
834  nodeVector_(graph.maxNodeId()+1),
835  nDoubleEdges_(0),
836  doubleEdges_(graph_.edgeNum()/2 +1)
837 {
838  for(index_type possibleNodeId = 0 ; possibleNodeId <= graph_.maxNodeId(); ++possibleNodeId){
839  if(graph_.nodeFromId(possibleNodeId)==lemon::INVALID){
840  nodeUfd_.eraseElement(possibleNodeId);
841  }
842  else{
843  nodeVector_[possibleNodeId].id_ = -1;
844  }
845  }
846  for(index_type possibleEdgeId = 0 ; possibleEdgeId <= graph_.maxEdgeId(); ++possibleEdgeId){
847  const GraphEdge possibleEdge(graph_.edgeFromId(possibleEdgeId));
848  if(possibleEdge==lemon::INVALID){
849  edgeUfd_.eraseElement(possibleEdgeId);
850  }
851  else{
852  const index_type guid = graphUId(possibleEdgeId);
853  const index_type gvid = graphVId(possibleEdgeId);
854  nodeVector_[ guid ].insert(gvid,possibleEdgeId);
855  nodeVector_[ gvid ].insert(guid,possibleEdgeId);
856  }
857  }
858 
859 }
860 
861 
862 
863 template<class GRAPH>
864 inline typename MergeGraphAdaptor<GRAPH>::Edge
865 MergeGraphAdaptor<GRAPH>::findEdge (
866  const typename MergeGraphAdaptor<GRAPH>::Node & a,
867  const typename MergeGraphAdaptor<GRAPH>::Node & b
868 )const{
869 
870  if(a!=b){
871  std::pair<index_type,bool> res = nodeVector_[id(a)].findEdge(id(b));
872  if(res.second){
873  return Edge(res.first);
874  }
875  }
876  return Edge(lemon::INVALID);
877 }
878 
879 template<class GRAPH>
880 inline typename MergeGraphAdaptor<GRAPH>::Arc
881 MergeGraphAdaptor<GRAPH>::findArc (
882  const typename MergeGraphAdaptor<GRAPH>::Node & uNode,
883  const typename MergeGraphAdaptor<GRAPH>::Node & vNode
884 )const{
885  const Edge edge = findEdge(uNode,vNode);
886  if(edge==lemon::INVALID)
887  return Arc(lemon::INVALID);
888  else
889  return direct(edge,u(edge)==uNode);
890 }
891 
892 
893 template<class GRAPH>
894 inline typename MergeGraphAdaptor<GRAPH>::Node
895 MergeGraphAdaptor<GRAPH>::u(const Edge & edge)const{
896  return nodeFromId(uId(id(edge)));
897 }
898 
899 template<class GRAPH>
900 inline typename MergeGraphAdaptor<GRAPH>::Node
901 MergeGraphAdaptor<GRAPH>::v(const Edge & edge)const{
902  return nodeFromId(vId(id(edge)));
903 }
904 
905 template<class GRAPH>
906 inline typename MergeGraphAdaptor<GRAPH>::index_type
907 MergeGraphAdaptor<GRAPH>::uId(const index_type edgeId)const{
908  return reprNodeId(graphUId(edgeId));
909 }
910 
911 template<class GRAPH>
912 inline typename MergeGraphAdaptor<GRAPH>::index_type
913 MergeGraphAdaptor<GRAPH>::vId(const index_type edgeId)const{
914  return reprNodeId(graphVId(edgeId));
915 }
916 
917 
918 
919 template<class GRAPH>
920 inline typename MergeGraphAdaptor<GRAPH>::index_type
921 MergeGraphAdaptor<GRAPH>::graphUId(const index_type edgeId)const{
922  return graph_.id(graph_.u(graph_.edgeFromId(edgeId)));
923 }
924 
925 template<class GRAPH>
926 inline typename MergeGraphAdaptor<GRAPH>::index_type
927 MergeGraphAdaptor<GRAPH>::graphVId(const index_type edgeId)const{
928  return graph_.id(graph_.v(graph_.edgeFromId(edgeId)));
929 }
930 
931 
932 template<class GRAPH>
933 inline typename MergeGraphAdaptor<GRAPH>::IdType
934 MergeGraphAdaptor<GRAPH>::maxEdgeId()const {
935  return static_cast<index_type>(edgeUfd_.lastRep());
936 }
937 template<class GRAPH>
938 inline typename MergeGraphAdaptor<GRAPH>::IdType
939 MergeGraphAdaptor<GRAPH>::maxNodeId()const {
940  return static_cast<index_type>(nodeUfd_.lastRep());
941 }
942 
943 template<class GRAPH>
944 inline typename MergeGraphAdaptor<GRAPH>::IdType
945 MergeGraphAdaptor<GRAPH>::maxArcId()const {
946  return maxEdgeId()*2 +1 ;
947 }
948 
949 
950 #ifndef DOXYGEN // doxygen doesn't understand this
951 
952 template<class GRAPH>
953 inline typename MergeGraphAdaptor<GRAPH>::IdType
954 MergeGraphAdaptor<GRAPH>::id(
955  const typename MergeGraphAdaptor<GRAPH>::Edge & edge
956 )const{
957  return edge.id();
958 }
959 
960 template<class GRAPH>
961 inline typename MergeGraphAdaptor<GRAPH>::IdType
962 MergeGraphAdaptor<GRAPH>::id(
963  const typename MergeGraphAdaptor<GRAPH>::Node & node
964 )const{
965  return node.id();
966 }
967 
968 template<class GRAPH>
969 inline typename MergeGraphAdaptor<GRAPH>::IdType
970 MergeGraphAdaptor<GRAPH>::id(
971  const typename MergeGraphAdaptor<GRAPH>::Arc & arc
972 )const{
973  return arc.id();
974 }
975 
976 #endif //DOXYGEN
977 
978 
979 template<class GRAPH>
980 inline size_t
981 MergeGraphAdaptor<GRAPH>::degree(
982  typename MergeGraphAdaptor<GRAPH>::Node const & node
983 )const{
984  return static_cast<size_t>( nodeVector_[id(node)].edgeNum() );
985 }
986 
987 
988 
989 template<class GRAPH>
990 inline typename MergeGraphAdaptor<GRAPH>::EdgeIdIt
991 MergeGraphAdaptor<GRAPH>::edgeIdsBegin()const{
992  return edgeUfd_.begin();
993 }
994 
995 template<class GRAPH>
996 inline typename MergeGraphAdaptor<GRAPH>::EdgeIdIt
997 MergeGraphAdaptor<GRAPH>::edgeIdsEnd()const{
998  return edgeUfd_.end();
999 }
1000 
1001 
1002 template<class GRAPH>
1003 inline typename MergeGraphAdaptor<GRAPH>::NodeIdIt
1004 MergeGraphAdaptor<GRAPH>::nodeIdsBegin()const{
1005  return nodeUfd_.begin();
1006 }
1007 
1008 template<class GRAPH>
1009 inline typename MergeGraphAdaptor<GRAPH>::NodeIdIt
1010 MergeGraphAdaptor<GRAPH>::nodeIdsEnd()const{
1011  return nodeUfd_.end();
1012 }
1013 
1014 
1015 template<class GRAPH>
1016 inline typename MergeGraphAdaptor<GRAPH>::Edge
1017 MergeGraphAdaptor<GRAPH>::edgeFromIdUnsave(
1018  const typename MergeGraphAdaptor<GRAPH>::IdType index
1019 )const{
1020  return Edge(index);
1021 }
1022 
1023 template<class GRAPH>
1024 inline typename MergeGraphAdaptor<GRAPH>::Edge
1025 MergeGraphAdaptor<GRAPH>::edgeFromId(
1026  const typename MergeGraphAdaptor<GRAPH>::IdType index
1027 )const{
1028  if (hasEdgeId(index))
1029  return Edge(index);
1030  else
1031  return Edge(lemon::INVALID);
1032 }
1033 
1034 template<class GRAPH>
1035 inline typename MergeGraphAdaptor<GRAPH>::Node
1036 MergeGraphAdaptor<GRAPH>::nodeFromId(
1037  const typename MergeGraphAdaptor<GRAPH>::IdType index
1038 )const{
1039  if(hasNodeId(index))
1040  return Node(index);
1041  else
1042  return Node(lemon::INVALID);
1043 }
1044 
1045 template<class GRAPH>
1046 inline typename MergeGraphAdaptor<GRAPH>::Arc
1047 MergeGraphAdaptor<GRAPH>::arcFromId(
1048  const typename MergeGraphAdaptor<GRAPH>::IdType index
1049 )const{
1050  if(index<=maxEdgeId( ))
1051  return Arc(index,index);
1052  else
1053  return Arc(index, index-maxEdgeId() -1);
1054 }
1055 
1056 template<class GRAPH>
1057 inline bool
1058 MergeGraphAdaptor<GRAPH>::hasEdgeId(
1059  const typename MergeGraphAdaptor<GRAPH>::IdType edgeIndex
1060 )const{
1061  if(edgeIndex<=maxEdgeId() && !edgeUfd_.isErased(edgeIndex)){
1062  const IdType reprEdgeIndex = reprEdgeId(edgeIndex);
1063  if(reprEdgeIndex!=edgeIndex){
1064  return false;
1065  }
1066  else{
1067  const index_type rnid0= uId(reprEdgeIndex);
1068  const index_type rnid1= vId(reprEdgeIndex);
1069  return rnid0!=rnid1;
1070  }
1071  }
1072  else{
1073  return false;
1074  }
1075 }
1076 
1077 template<class GRAPH>
1078 inline bool
1079 MergeGraphAdaptor<GRAPH>::hasNodeId(
1080  const typename MergeGraphAdaptor<GRAPH>::IdType nodeIndex
1081 )const{
1082 
1083  return nodeIndex<=maxNodeId() && !nodeUfd_.isErased(nodeIndex) && nodeUfd_.find(nodeIndex)==nodeIndex;
1084 }
1085 
1086 template<class GRAPH>
1087 inline typename MergeGraphAdaptor<GRAPH>::IdType
1088 MergeGraphAdaptor<GRAPH>::reprEdgeId(
1089  const typename MergeGraphAdaptor<GRAPH>::IdType edgeIndex
1090 )const{
1091  return edgeUfd_.find(edgeIndex);
1092 }
1093 
1094 template<class GRAPH>
1095 inline typename MergeGraphAdaptor<GRAPH>::IdType
1096 MergeGraphAdaptor<GRAPH>::reprNodeId(
1097  const typename MergeGraphAdaptor<GRAPH>::IdType nodeIndex
1098 )const{
1099  return nodeUfd_.find(nodeIndex);
1100 }
1101 
1102 template<class GRAPH>
1103 inline bool MergeGraphAdaptor<GRAPH>::stateOfInitalEdge(
1104  const typename MergeGraphAdaptor<GRAPH>::IdType initalEdge
1105 )const{
1106  const index_type rep = reprEdgeId(initalEdge);
1107 
1108  const index_type rnid0= reprNodeId( graphUId(initalEdge) );
1109  const index_type rnid1= reprNodeId( graphVId(initalEdge) );
1110  return rnid0!=rnid1;
1111 }
1112 
1113 template<class GRAPH>
1114 inline size_t MergeGraphAdaptor<GRAPH>::nodeNum()const{
1115  return nodeUfd_.numberOfSets();
1116 }
1117 
1118 template<class GRAPH>
1119 inline size_t MergeGraphAdaptor<GRAPH>::arcNum()const{
1120  return edgeNum()*2;
1121 }
1122 
1123 template<class GRAPH>
1124 inline size_t MergeGraphAdaptor<GRAPH>::edgeNum()const{
1125  return edgeUfd_.numberOfSets();
1126 }
1127 
1128 template<class GRAPH>
1129 void MergeGraphAdaptor<GRAPH>::contractEdge(
1130  const typename MergeGraphAdaptor<GRAPH>::Edge & toDeleteEdge
1131 ){
1132  //std::cout<<"node num "<<nodeNum()<<"\n";
1133  const index_type toDeleteEdgeIndex = id(toDeleteEdge);
1134  const index_type nodesIds[2]={id(u(toDeleteEdge)),id(v(toDeleteEdge))};
1135 
1136  // merge the two nodes
1137  nodeUfd_.merge(nodesIds[0],nodesIds[1]);
1138  const IdType newNodeRep = reprNodeId(nodesIds[0]);
1139  const IdType notNewNodeRep = (newNodeRep == nodesIds[0] ? nodesIds[1] : nodesIds[0] );
1140 
1141  typename NodeStorage::AdjIt iter=nodeVector_[notNewNodeRep].adjacencyBegin();
1142  typename NodeStorage::AdjIt end =nodeVector_[notNewNodeRep].adjacencyEnd();
1143 
1144  nDoubleEdges_=0;
1145  for(;iter!=end;++iter){
1146  const size_t adjToDeadNodeId = iter->nodeId();
1147  if(adjToDeadNodeId!=newNodeRep){
1148 
1149  // REFACTOR ME, we can make that faster if
1150  // we do that in set intersect style
1151  std::pair<index_type,bool> found=nodeVector_[adjToDeadNodeId].findEdge(newNodeRep);
1152 
1153 
1154  if(found.second){
1155  edgeUfd_.merge(iter->edgeId(),found.first);
1156 
1157  const index_type edgeA = iter->edgeId();
1158  const index_type edgeB = found.first;
1159  const index_type edgeR = edgeUfd_.find(edgeA);
1160  const index_type edgeNR = edgeR==edgeA ? edgeB : edgeA;
1161 
1162  nodeVector_[adjToDeadNodeId].eraseFromAdjacency(notNewNodeRep);
1163 
1164  // refactor me ... this DOES NOT change the key
1165  nodeVector_[adjToDeadNodeId].eraseFromAdjacency(newNodeRep);
1166  nodeVector_[adjToDeadNodeId].insert(newNodeRep,edgeR);
1167 
1168  // refactor me .. this DOES NOT change the key
1169  nodeVector_[newNodeRep].eraseFromAdjacency(adjToDeadNodeId);
1170  nodeVector_[newNodeRep].insert(adjToDeadNodeId,edgeR);
1171 
1172  doubleEdges_[nDoubleEdges_]=std::pair<index_type,index_type>(edgeR,edgeNR );
1173  ++nDoubleEdges_;
1174  }
1175  else{
1176  nodeVector_[adjToDeadNodeId].eraseFromAdjacency(notNewNodeRep);
1177  //nodeVector_[adjToDeadNodeId].eraseFromAdjacency(newNodeRep);
1178  nodeVector_[adjToDeadNodeId].insert(newNodeRep,iter->edgeId());
1179 
1180  // symetric
1181  //nodeVector_[newNodeRep].eraseFromAdjacency(adjToDeadNodeId);
1182  nodeVector_[newNodeRep].insert(adjToDeadNodeId,iter->edgeId());
1183 
1184  }
1185  }
1186  }
1187 
1188  //nodeVector_[newNodeRep].merge(nodeVector_[notNewNodeRep]);
1189  nodeVector_[newNodeRep].eraseFromAdjacency(notNewNodeRep);
1190  //nodeVector_[newNodeRep].eraseFromAdjacency(newNodeRep); // no self adjacecy
1191  nodeVector_[notNewNodeRep].clear();
1192 
1193  edgeUfd_.eraseElement(toDeleteEdgeIndex);
1194 
1195  //std::cout<<"merge nodes callbacks\n";
1196 
1197  this->callMergeNodeCallbacks(Node(newNodeRep),Node(notNewNodeRep));
1198 
1199  //std::cout<<"merge double edge callbacks\n";
1200  for(size_t de=0;de<nDoubleEdges_;++de){
1201  this->callMergeEdgeCallbacks(Edge(doubleEdges_[de].first),Edge(doubleEdges_[de].second));
1202  }
1203  //std::cout<<"erase edge callbacks\n";
1204  this->callEraseEdgeCallbacks(Edge(toDeleteEdgeIndex));
1205 
1206  //std::cout<<"and done\n";
1207 }
1208 
1209 
1210 
1211 namespace merge_graph_detail {
1212 /// Construct a partition.
1213 template<class T>
1215 : parents_(),
1216  ranks_(),
1217  jumpVec_(),
1218  firstRep_(0),
1219  lastRep_(0),
1220  numberOfElements_(0),
1221  numberOfSets_(0)
1222 {}
1223 
1224 /// Construct a partition.
1225 ///
1226 /// \param size Number of distinct sets.
1227 ///
1228 template<class T>
1229 inline
1232  const value_type& size
1233 )
1234 : parents_(static_cast<SizeTType>(size)),
1235  ranks_(static_cast<SizeTType>(size)),
1236  jumpVec_(static_cast<SizeTType>(size)),
1237  firstRep_(0),
1238  lastRep_(static_cast<SizeTType>(size)-1),
1239  numberOfElements_(size),
1240  numberOfSets_(size)
1241 {
1242  for(T j=0; j<size; ++j) {
1243  parents_[static_cast<SizeTType>(j)] = j;
1244  }
1245 
1246  jumpVec_.front().first=0;
1247  jumpVec_.front().second=1;
1248  for(T j=1; j<size-1;++j){
1249  jumpVec_[j].first =1;
1250  jumpVec_[j].second=1;
1251  }
1252  jumpVec_.back().first=1;
1253  jumpVec_.back().second=0;
1254 }
1255 
1256 /// Reset a partition such that each set contains precisely one element
1257 ///
1258 /// \param size Number of distinct sets.
1259 ///
1260 template<class T>
1261 inline void
1264  const value_type& size
1265 )
1266 {
1267  numberOfElements_ = size;
1268  numberOfSets_ = size;
1269  ranks_.resize(static_cast<SizeTType>(size));
1270  parents_.resize(static_cast<SizeTType>(size));
1271  jumpVec_.resize(static_cast<SizeTType>(size));
1272  firstRep_=0;
1273  lastRep_=static_cast<SizeTType>(size)-1;
1274  for(T j=0; j<size; ++j) {
1275  ranks_[static_cast<SizeTType>(j)] = 0;
1276  parents_[static_cast<SizeTType>(j)] = j;
1277  }
1278 
1279  jumpVec_.front().first=0;
1280  jumpVec_.front().second=1;
1281  for(T j=1; j<size-1;++j){
1282  jumpVec_[j].first =1;
1283  jumpVec_[j].second=1;
1284  }
1285  jumpVec_.back().first=1;
1286  jumpVec_.back().second=0;
1287 }
1288 
1289 /// Find the representative element of the set that contains the given element.
1290 ///
1291 /// This constant function does not compress the search path.
1292 ///
1293 /// \param element Element.
1294 ///
1295 template<class T>
1296 inline typename IterablePartition<T>::value_type
1299  const value_type& element
1300 ) const
1301 {
1302  // find the root
1303  value_type root = element;
1304  while(parents_[static_cast<SizeTType>(root)] != root) {
1305  root = parents_[static_cast<SizeTType>(root)];
1306  }
1307  return root;
1308 }
1309 
1310 /// Find the representative element of the set that contains the given element.
1311 ///
1312 /// This mutable function compresses the search path.
1313 ///
1314 /// \param element Element.
1315 ///
1316 template<class T>
1317 inline typename IterablePartition<T>::value_type
1320  value_type element // copy to work with
1321 )
1322 {
1323  // find the root
1324  value_type root = element;
1325  while(parents_[static_cast<SizeTType>(root)] != root) {
1326  root = parents_[static_cast<SizeTType>(root)];
1327  }
1328  // path compression
1329  while(element != root) {
1330  value_type tmp = parents_[static_cast<SizeTType>(element)];
1331  parents_[static_cast<SizeTType>(element)] = root;
1332  element = tmp;
1333  }
1334  return root;
1335 }
1336 
1337 /// Merge two sets.
1338 ///
1339 /// \param element1 Element in the first set.
1340 /// \param element2 Element in the second set.
1341 ///
1342 template<class T>
1343 inline void
1346  value_type element1,
1347  value_type element2
1348 )
1349 {
1350  // merge by rank
1351  element1 = find(element1);
1352  element2 = find(element2);
1353  if(element1!=element2){
1354  T notRep;
1355  if(ranks_[static_cast<SizeTType>(element1)] < ranks_[static_cast<SizeTType>(element2)]) {
1356  parents_[static_cast<SizeTType>(element1)] = element2;
1357  --numberOfSets_;
1358  //rep=element2;
1359  notRep=element1;
1360  }
1361  else if(ranks_[static_cast<SizeTType>(element1)] > ranks_[static_cast<SizeTType>(element2)]) {
1362  parents_[static_cast<SizeTType>(element2)] = element1;
1363  --numberOfSets_;
1364  //rep=element1;
1365  notRep=element2;
1366  }
1367  else if(element1 != element2) {
1368  parents_[static_cast<SizeTType>(element2)] = element1;
1369  ++ranks_[static_cast<SizeTType>(element1)];
1370  --numberOfSets_;
1371  //rep=element1;
1372  notRep=element2;
1373  }
1374  this->eraseElement(notRep,false);
1375  }
1376 }
1377 
1378 template<class T>
1379 inline typename IterablePartition<T>::value_type
1381 {
1382  return numberOfElements_;
1383 }
1384 
1385 template<class T>
1386 inline typename IterablePartition<T>::value_type
1387 IterablePartition<T>::numberOfSets() const
1388 {
1389  return numberOfSets_;
1390 }
1391 
1392 template<class T>
1393 inline bool operator == (const ConstRepIter<T> & iter,const lemon::Invalid & iv){
1394  return iter.isEnd();
1395 }
1396 template<class T>
1397 inline bool operator == (const lemon::Invalid & iv , const ConstRepIter<T> & iter){
1398  return iter.isEnd();
1399 }
1400 
1401 template<class T>
1402 inline bool operator != (const ConstRepIter<T> & iter,const lemon::Invalid & iv){
1403  return !iter.isEnd();
1404 }
1405 template<class T>
1406 inline bool operator != (const lemon::Invalid & iv , const ConstRepIter<T> & iter){
1407  return !iter.isEnd();
1408 }
1409 
1410 
1411 } // end namespace merge_graph_detail
1412 
1413 
1414 } // end namespace vigra
1415 
1416 
1417 
1418 #endif //VIGRA_NEW_MERGE_GRAPH_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)