1 #ifndef VIGRA_NODE_IMPL_HXX
2 #define VIGRA_NODE_IMPL_HXX
7 #include "algorithm.hxx"
8 #include "tinyvector.hxx"
9 #include "random_access_set.hxx"
10 #include "iteratorfacade.hxx"
41 struct NeighborNodeFilter{
42 typedef typename GRAPH::Node ResultType;
43 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
47 const AdjacencyElement & adj,
48 const typename GRAPH::index_type ownNodeId
54 static ResultType transform(
56 const AdjacencyElement & adj,
57 const typename GRAPH::index_type ownNodeId
59 return g.nodeFromId(adj.nodeId());
62 static const bool IsFilter = false ;
67 typedef typename GRAPH::Edge ResultType;
68 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
72 const AdjacencyElement & adj,
73 const typename GRAPH::index_type ownNodeId
78 static ResultType transform(
80 const AdjacencyElement & adj,
81 const typename GRAPH::index_type ownNodeId
83 return g.edgeFromId(adj.edgeId());
86 static const bool IsFilter = false ;
90 struct BackEdgeFilter{
91 typedef typename GRAPH::Edge ResultType;
92 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
96 const AdjacencyElement & adj,
97 const typename GRAPH::index_type ownNodeId
99 return adj.nodeId() < ownNodeId;
102 static ResultType transform(
104 const AdjacencyElement & adj,
105 const typename GRAPH::index_type ownNodeId
107 return g.edgeFromId(adj.edgeId());
110 static const bool IsFilter = true ;
112 template<
class GRAPH>
113 struct IsBackOutFilter{
114 typedef typename GRAPH::Arc ResultType;
115 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
119 const AdjacencyElement & adj,
120 const typename GRAPH::index_type ownNodeId
122 return adj.nodeId() < ownNodeId;
124 static ResultType transform(
126 const AdjacencyElement & adj,
127 const typename GRAPH::index_type ownNodeId
129 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(ownNodeId));
132 static const bool IsFilter = true ;
134 template<
class GRAPH>
136 typedef typename GRAPH::Arc ResultType;
137 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
141 const AdjacencyElement & adj,
142 const typename GRAPH::index_type ownNodeId
146 static ResultType transform(
148 const AdjacencyElement & adj,
149 const typename GRAPH::index_type ownNodeId
151 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(ownNodeId));
154 static const bool IsFilter = false ;
159 template<
class GRAPH>
161 typedef typename GRAPH::Arc ResultType;
162 typedef typename GRAPH::NodeStorage::AdjacencyElement AdjacencyElement;
166 const AdjacencyElement & adj,
167 const typename GRAPH::index_type ownNodeId
171 ResultType
static transform(
173 const AdjacencyElement & adj,
174 const typename GRAPH::index_type ownNodeId
176 return g.direct(g.edgeFromId(adj.edgeId()) ,g.nodeFromId(adj.nodeId()));
178 static const bool IsFilter = false ;
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
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;
199 GenericIncEdgeIt(
const lemon::Invalid & invalid = lemon::INVALID)
204 resultItem_(lemon::INVALID){
207 GenericIncEdgeIt(
const Graph & g ,
const NodeIt & nodeIt)
208 : nodeImpl_(&g.nodeImpl(*nodeIt)),
210 ownNodeId_(g.id(*nodeIt)),
211 adjIter_(g.nodeImpl(*nodeIt).adjacencyBegin()),
212 resultItem_(lemon::INVALID){
214 if(FILTER::IsFilter){
215 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_) ) {
222 GenericIncEdgeIt(
const Graph & g ,
const Node & node)
223 : nodeImpl_(&g.nodeImpl(node)),
225 ownNodeId_(g.id(node)),
226 adjIter_(g.nodeImpl(node).adjacencyBegin()),
227 resultItem_(lemon::INVALID){
229 if(FILTER::IsFilter){
230 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_) ) {
237 friend class vigra::IteratorFacadeCoreAccess;
239 typedef NODE_IMPL NodeImpl;
240 typedef typename NodeImpl::AdjIt AdjIt;
243 return (nodeImpl_==NULL || adjIter_==nodeImpl_->adjacencyEnd());
246 return (nodeImpl_!=NULL && adjIter_==nodeImpl_->adjacencyBegin());
248 bool equal(
const GenericIncEdgeIt<GRAPH,NODE_IMPL,FILTER> & other)
const{
249 if(isEnd() && other.isEnd()){
252 else if (isEnd() != other.isEnd()){
256 return adjIter_==other.adjIter_;
262 if(FILTER::IsFilter){
263 while(adjIter_!=nodeImpl_->adjacencyEnd() && !FILTER::valid(*graph_,*adjIter_,ownNodeId_)){
271 const ResultItem & dereference()
const{
272 resultItem_ = FILTER::transform(*graph_,*adjIter_,ownNodeId_);
277 const NODE_IMPL * nodeImpl_;
278 const GRAPH * graph_;
279 const index_type ownNodeId_;
281 mutable ResultItem resultItem_;
293 Adjacency(
const Value nodeId,
const Value edgeId)
298 Value nodeId()
const{
304 Value edgeId()
const{
310 bool operator<(const Adjacency<Value> & other)
const{
311 return nodeId_ < other.nodeId_;
323 template<
class INDEX_TYPE,
bool USE_STL_SET>
324 class GenericNodeImpl{
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;
333 typedef typename SetType::const_iterator AdjIt;
336 GenericNodeImpl(
const lemon::Invalid iv=lemon::INVALID)
340 GenericNodeImpl(
const index_type
id)
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();}
351 void merge(
const GenericNodeImpl & other){
352 adjacency_.insert(other.adjacency_.begin(),other.adjacency_.end());
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);
362 return std::pair<index_type,bool>(iter->edgeId(),
true);
368 void insert(
const index_type nodeId,
const index_type edgeId){
369 adjacency_.insert(AdjacencyElement(nodeId,edgeId));
372 AdjIt adjacencyBegin()
const{
373 return adjacency_.begin();
375 AdjIt adjacencyEnd()
const{
376 return adjacency_.end();
380 index_type id()
const{
387 void eraseFromAdjacency(
const index_type nodeId){
389 adjacency_.erase(AdjacencyElement(nodeId,0));
396 template<
class INDEX_TYPE>
397 class GenericEdgeImpl
401 typedef INDEX_TYPE index_type;
403 GenericEdgeImpl(
const lemon::Invalid iv=lemon::INVALID)
407 GenericEdgeImpl(
const index_type u,
const index_type v,
const index_type
id)
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);}
419 template<
class INDEX_TYPE>
422 template<
class INDEX_TYPE>
425 typedef INDEX_TYPE index_type;
427 GenericArc(
const lemon::Invalid & iv = lemon::INVALID)
437 const index_type edgeId = static_cast<index_type>(-1)
443 index_type id()
const{
return id_;}
444 index_type edgeId()
const{
return edgeId_;}
446 operator GenericEdge<INDEX_TYPE> ()
const{
447 return GenericEdge<INDEX_TYPE>(edgeId());
450 bool operator == (
const GenericArc<INDEX_TYPE> & other )
const{
451 return id_ == other.id_;
453 bool operator != (
const GenericArc<INDEX_TYPE> & other )
const{
454 return id_ != other.id_;
456 bool operator < (const GenericArc<INDEX_TYPE> & other )
const{
457 return id_ < other.id_;
459 bool operator > (
const GenericArc<INDEX_TYPE> & other )
const{
460 return id_ > other.id_;
470 template<
class INDEX_TYPE>
473 typedef INDEX_TYPE index_type;
475 GenericEdge(
const lemon::Invalid & iv = lemon::INVALID)
480 GenericEdge(
const index_type
id )
485 GenericEdge(
const GenericArc<INDEX_TYPE> & arc)
490 bool operator == (
const GenericEdge<INDEX_TYPE> & other )
const{
491 return id_ == other.id_;
493 bool operator != (
const GenericEdge<INDEX_TYPE> & other )
const{
494 return id_ != other.id_;
496 bool operator < (const GenericEdge<INDEX_TYPE> & other )
const{
497 return id_ < other.id_;
499 bool operator > (
const GenericEdge<INDEX_TYPE> & other )
const{
500 return id_ > other.id_;
502 bool operator <= (const GenericEdge<INDEX_TYPE> & other )
const{
503 return id_ <= other.id_;
505 bool operator >= (
const GenericEdge<INDEX_TYPE> & other )
const{
506 return id_ >= other.id_;
510 index_type id()
const{
return id_;}
516 template<
class INDEX_TYPE>
519 typedef INDEX_TYPE index_type;
521 GenericNode(
const lemon::Invalid & iv = lemon::INVALID)
526 GenericNode(
const index_type
id )
530 bool operator == (
const GenericNode<INDEX_TYPE> & other )
const{
531 return id_ == other.id_;
533 bool operator != (
const GenericNode<INDEX_TYPE> & other )
const{
534 return id_ != other.id_;
536 bool operator < (const GenericNode<INDEX_TYPE> & other )
const{
537 return id_ < other.id_;
539 bool operator > (
const GenericNode<INDEX_TYPE> & other )
const{
540 return id_ > other.id_;
543 index_type id()
const{
return id_;}
553 template<
class INDEX_TYPE>
554 ostream & operator<<(ostream & o, vigra::detail::GenericNode<INDEX_TYPE>
const & n)
556 o <<
"Node(" << n.id() <<
")";
560 template<
class INDEX_TYPE>
561 ostream & operator<<(ostream & o, vigra::detail::GenericEdge<INDEX_TYPE>
const & e)
563 o <<
"Edge(" << e.id() <<
")";
569 #endif // VIGRA_NODE_IMPL_HXX