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

adjacency_list_graph.hxx
1/************************************************************************/
2/* */
3/* Copyright 2011 by Ullrich Koethe */
4/* */
5/* This file is part of the VIGRA computer vision library. */
6/* The VIGRA Website is */
7/* http://hci.iwr.uni-heidelberg.de/vigra/ */
8/* Please direct questions, bug reports, and contributions to */
9/* ullrich.koethe@iwr.uni-heidelberg.de or */
10/* vigra@informatik.uni-hamburg.de */
11/* */
12/* Permission is hereby granted, free of charge, to any person */
13/* obtaining a copy of this software and associated documentation */
14/* files (the "Software"), to deal in the Software without */
15/* restriction, including without limitation the rights to use, */
16/* copy, modify, merge, publish, distribute, sublicense, and/or */
17/* sell copies of the Software, and to permit persons to whom the */
18/* Software is furnished to do so, subject to the following */
19/* conditions: */
20/* */
21/* The above copyright notice and this permission notice shall be */
22/* included in all copies or substantial portions of the */
23/* Software. */
24/* */
25/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27/* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28/* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29/* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30/* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32/* OTHER DEALINGS IN THE SOFTWARE. */
33/* */
34/************************************************************************/
35
36
37#ifndef VIGRA_ADJACENCY_LIST_GRAPH_HXX
38#define VIGRA_ADJACENCY_LIST_GRAPH_HXX
39
40/*std*/
41#include <vector>
42#include <set>
43
44/*vigra*/
45#include "multi_array.hxx"
46#include "multi_gridgraph.hxx"
47#include "graphs.hxx"
48#include "tinyvector.hxx"
49#include "random_access_set.hxx"
50#include "graph_maps.hxx"
51#include "iteratorfacade.hxx"
52
53#include "algorithm.hxx"
54#include "graph_item_impl.hxx"
55
56
57 namespace vigra{
58
59/** \addtogroup GraphDataStructures
60*/
61//@{
62
63 namespace detail_adjacency_list_graph{
64
65 template<class G,class ITEM>
66 class ItemIter
67 : public ForwardIteratorFacade<
68 ItemIter<G,ITEM>,ITEM,true
69 >
70 {
71
72 typedef vigra::GraphItemHelper<G,ITEM> ItemHelper;
73 typedef typename G::index_type index_type;
74
75 public:
76 ItemIter(const lemon::Invalid & /*iv*/ = lemon::INVALID)
77 : graph_(NULL),
78 id_(-1),
79 item_(lemon::INVALID)
80 {
81 }
82
83 ItemIter(const G & g)
84 : graph_(&g),
85 id_(0),
86 item_(ItemHelper::itemFromId(*graph_,id_))
87 {
88 while( !isEnd() && item_==lemon::INVALID ){
89 ++id_;
90 item_ = ItemHelper::itemFromId(*graph_,id_);
91 }
92 }
93
94 ItemIter(const G & g,const ITEM & item)
95 : graph_(&g),
96 id_(g.id(item)),
97 item_(item)
98 {
99
100 }
101
102 private:
103
104 friend class vigra::IteratorFacadeCoreAccess;
105 bool isEnd( )const{
106 return graph_==NULL || ItemHelper::itemNum(*graph_)==0 || id_>ItemHelper::maxItemId(*graph_);
107 }
108 bool isBegin( )const{
109 return graph_!=NULL && id_ == 0 ;
110 }
111
112 bool equal(const ItemIter & other) const{
113 return (isEnd() && other.isEnd() ) || (isEnd()==other.isEnd() && (id_ == other.id_) );
114 }
115
116 void increment(){
117 ++id_;
118 item_ = ItemHelper::itemFromId(*graph_,id_);
119 while( !isEnd() && item_==lemon::INVALID ){
120 ++id_;
121 item_ = ItemHelper::itemFromId(*graph_,id_);
122 }
123 }
124 const ITEM & dereference()const{
125 return item_;
126 }
127 const G * graph_;
128 index_type id_;
129 ITEM item_;
130 };
131
132
133
134 template<class GRAPH>
135 class ArcIt
136 : public ForwardIteratorFacade<
137 ArcIt<GRAPH>,
138 typename GRAPH::Arc,true
139 >
140 {
141 public:
142 typedef GRAPH Graph;
143 typedef typename Graph::Arc Arc;
144 typedef typename Graph::Edge Edge;
145 typedef typename Graph::EdgeIt EdgeIt;
146 ArcIt(const lemon::Invalid /*invalid*/ = lemon::INVALID )
147 : graph_(NULL),
148 pos_(),
149 inFirstHalf_(false),
150 veryEnd_(true),
151 arc_(){
152 }
153 ArcIt(const GRAPH & g )
154 : graph_(&g),
155 pos_(g),
156 inFirstHalf_(true),
157 veryEnd_( g.edgeNum()==0 ? true : false),
158 arc_(){
159 }
160
161 ArcIt(const GRAPH & g , const Arc & arc )
162 : graph_(&g),
163 pos_(g,arc.edgeId()),
164 inFirstHalf_(g.id(arc)<=g.maxEdgeId()),
165 veryEnd_(false),
166 arc_(){
167 }
168 private:
169 friend class vigra::IteratorFacadeCoreAccess;
170 bool isEnd()const{
171 return veryEnd_ || graph_==NULL;
172 }
173
174 bool isBegin()const{
175 return graph_!=NULL && veryEnd_==false && pos_ == EdgeIt(*graph_);
176 }
177 void increment() {
178 if(inFirstHalf_){
179 ++pos_;
180 if(pos_ == lemon::INVALID ) {
181 pos_ = EdgeIt(*graph_);
182 inFirstHalf_=false;
183 }
184 return;
185 }
186 else{
187 ++pos_;
188 if(pos_ == lemon::INVALID){
189 veryEnd_=true;
190 }
191 return;
192 }
193
194
195 }
196 bool equal(ArcIt const& other) const{
197 return (
198 (
199 isEnd()==other.isEnd() &&
200 inFirstHalf_==other.inFirstHalf_
201 ) &&
202 (isEnd() || graph_==NULL || pos_==other.pos_ )
203 );
204
205 }
206
207 const Arc & dereference() const {
208 //std::cout<<graph_->id(*pos_)<<"\n";
209 arc_ = graph_->direct(*pos_,inFirstHalf_);
210 return arc_;
211 }
212
213
214 const GRAPH * graph_;
215 EdgeIt pos_;
216 bool inFirstHalf_;
217 bool veryEnd_;
218 mutable Arc arc_;
219 };
220
221 } // namespace detail_adjacency_list_graph
222
223
224 /** \brief undirected adjacency list graph in the LEMON API
225
226 */
227 class AdjacencyListGraph
228 {
229
230 public:
231 // public typdedfs
232 typedef Int64 index_type;
233 private:
234 // private typedes which are needed for defining public typedes
235 typedef AdjacencyListGraph GraphType;
236 typedef detail::GenericNodeImpl<index_type,false> NodeStorage;
237 typedef detail::GenericEdgeImpl<index_type > EdgeStorage;
238 typedef detail::NeighborNodeFilter<GraphType> NnFilter;
239 typedef detail::IncEdgeFilter<GraphType> IncFilter;
240 typedef detail::IsInFilter<GraphType> InFlter;
241 typedef detail::IsOutFilter<GraphType> OutFilter;
242 typedef detail::IsBackOutFilter<GraphType> BackOutFilter;
243 public:
244 // LEMON API TYPEDEFS (and a few more(NeighborNodeIt))
245
246 /// node descriptor
247 typedef detail::GenericNode<index_type> Node;
248 /// edge descriptor
249 typedef detail::GenericEdge<index_type> Edge;
250 /// arc descriptor
251 typedef detail::GenericArc<index_type> Arc;
252 /// edge iterator
253 typedef detail_adjacency_list_graph::ItemIter<GraphType,Edge> EdgeIt;
254 /// node iterator
255 typedef detail_adjacency_list_graph::ItemIter<GraphType,Node> NodeIt;
256 /// arc iterator
257 typedef detail_adjacency_list_graph::ArcIt<GraphType> ArcIt;
258
259 /// incident edge iterator
260 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,IncFilter > IncEdgeIt;
261 /// incoming arc iterator
262 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,InFlter > InArcIt;
263 /// outgoing arc iterator
264 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,OutFilter > OutArcIt;
265
266 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,NnFilter > NeighborNodeIt;
267
268
269 /// outgoing back arc iterator
270 typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,BackOutFilter > OutBackArcIt;
271
272
273 // BOOST GRAPH API TYPEDEFS
274 // - categories (not complete yet)
275 typedef directed_tag directed_category;
276 // iterators
277 typedef NeighborNodeIt adjacency_iterator;
278 typedef EdgeIt edge_iterator;
279 typedef NodeIt vertex_iterator;
280 typedef IncEdgeIt in_edge_iterator;
281 typedef IncEdgeIt out_edge_iterator;
282
283 // size types
284 typedef size_t degree_size_type;
285 typedef size_t edge_size_type;
286 typedef size_t vertex_size_type;
287 // item descriptors
288 typedef Edge edge_descriptor;
289 typedef Node vertex_descriptor;
290
291
292 /// default edge map
293 template<class T>
294 struct EdgeMap : DenseEdgeReferenceMap<GraphType,T> {
295 EdgeMap(): DenseEdgeReferenceMap<GraphType,T>(){
296 }
297 EdgeMap(const GraphType & g)
298 : DenseEdgeReferenceMap<GraphType,T>(g){
299 }
300 EdgeMap(const GraphType & g,const T & val)
301 : DenseEdgeReferenceMap<GraphType,T>(g,val){
302 }
303 };
304
305 /// default node map
306 template<class T>
307 struct NodeMap : DenseNodeReferenceMap<GraphType,T> {
308 NodeMap(): DenseNodeReferenceMap<GraphType,T>(){
309 }
310 NodeMap(const GraphType & g)
311 : DenseNodeReferenceMap<GraphType,T>(g){
312 }
313 NodeMap(const GraphType & g,const T & val)
314 : DenseNodeReferenceMap<GraphType,T>(g,val){
315 }
316 };
317
318 /// default arc map
319 template<class T>
320 struct ArcMap : DenseArcReferenceMap<GraphType,T> {
321 ArcMap(): DenseArcReferenceMap<GraphType,T>(){
322 }
323 ArcMap(const GraphType & g)
324 : DenseArcReferenceMap<GraphType,T>(g){
325 }
326 ArcMap(const GraphType & g,const T & val)
327 : DenseArcReferenceMap<GraphType,T>(g,val){
328 }
329 };
330
331
332
333 // public member functions
334 public:
335 /** \brief Constructor.
336
337 @param nodes : reserve space for so many nodes
338 @param edges : reserve space for so many edges
339 */
340 AdjacencyListGraph(const size_t nodes=0,const size_t edges=0);
341
342 /** \brief Get the number of edges in this graph (API: LEMON).
343 */
344 index_type edgeNum()const;
345
346 /** \brief Get the number of nodes in this graph (API: LEMON).
347 */
348 index_type nodeNum()const;
349 /** \brief Get the number of arcs in this graph (API: LEMON).
350 */
351 index_type arcNum()const;
352
353 /** \brief Get the maximum ID of any edge in this graph (API: LEMON).
354 */
355 index_type maxEdgeId()const;
356 /** \brief Get the maximum ID of any node in this graph (API: LEMON).
357 */
358 index_type maxNodeId()const;
359 /** \brief Get the maximum ID of any edge in arc graph (API: LEMON).
360 */
361 index_type maxArcId()const;
362
363 /** \brief Create an arc for the given edge \a e, oriented along the
364 edge's natural (<tt>forward = true</tt>) or reversed
365 (<tt>forward = false</tt>) direction (API: LEMON).
366 */
367 Arc direct(const Edge & edge,const bool forward)const;
368
369 /** \brief Create an arc for the given edge \a e oriented
370 so that node \a n is the starting node of the arc (API: LEMON), or
371 return <tt>lemon::INVALID</tt> if the edge is not incident to this node.
372 */
373 Arc direct(const Edge & edge,const Node & node)const;
374
375 /** \brief Return <tt>true</tt> when the arc is looking on the underlying
376 edge in its natural (i.e. forward) direction, <tt>false</tt> otherwise (API: LEMON).
377 */
378 bool direction(const Arc & arc)const;
379 /** \brief Get the start node of the given edge \a e (API: LEMON,<br/>
380 the boost::graph API provides the free function <tt>boost::source(e, graph)</tt>).
381 */
382 Node u(const Edge & edge)const;
383 /** \brief Get the end node of the given edge \a e (API: LEMON,<br/>
384 the boost::graph API provides the free function <tt>boost::target(e, graph)</tt>).
385 */
386 Node v(const Edge & edge)const;
387 /** \brief Get the start node of the given arc \a a (API: LEMON).
388 */
389 Node source(const Arc & arc)const;
390 /** \brief Get the end node of the given arc \a a (API: LEMON).
391 */
392 Node target(const Arc & arc)const;
393 /** \brief Return the opposite node of the given node \a n
394 along edge \a e (API: LEMON), or return <tt>lemon::INVALID</tt>
395 if the edge is not incident to this node.
396 */
397 Node oppositeNode(Node const &n, const Edge &e) const;
398
399 /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
400 */
401 Node baseNode(const IncEdgeIt & iter)const;
402 /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
403 */
404 Node baseNode(const OutArcIt & iter)const;
405
406 /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
407 */
408 Node runningNode(const IncEdgeIt & iter)const;
409 /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
410 */
411 Node runningNode(const OutArcIt & iter)const;
412
413
414 /** \brief Get the ID for node desciptor \a v (API: LEMON).
415 */
416 index_type id(const Node & node)const;
417 /** \brief Get the ID for edge desciptor \a v (API: LEMON).
418 */
419 index_type id(const Edge & edge)const;
420 /** \brief Get the ID for arc desciptor \a v (API: LEMON).
421 */
422 index_type id(const Arc & arc )const;
423
424 /** \brief Get edge descriptor for given node ID \a i (API: LEMON).
425 Return <tt>Edge(lemon::INVALID)</tt> when the ID does not exist in this graph.
426 */
427 Edge edgeFromId(const index_type id)const;
428
429 /** \brief Get node descriptor for given node ID \a i (API: LEMON).
430 Return <tt>Node(lemon::INVALID)</tt> when the ID does not exist in this graph.
431 */
432 Node nodeFromId(const index_type id)const;
433 /** \brief Get arc descriptor for given node ID \a i (API: LEMON).
434 Return <tt>Arc(lemon::INVALID)</tt> when the ID does not exist in this graph.
435 */
436 Arc arcFromId(const index_type id)const;
437
438
439 /** \brief Get a descriptor for the edge connecting vertices \a u and \a v,<br/>or <tt>lemon::INVALID</tt> if no such edge exists (API: LEMON).
440 */
441 Edge findEdge(const Node & a,const Node & b)const;
442 /** \brief Get a descriptor for the arc connecting vertices \a u and \a v,<br/>or <tt>lemon::INVALID</tt> if no such edge exists (API: LEMON).
443 */
444 Arc findArc(const Node & u,const Node & v)const;
445
446 /* \brief add a new node to the graph.
447 the next unused id will be assigned to the node
448 */
449 Node addNode();
450 /* \brief add a node to the graph with a given id.
451 If there is another node with this id, no
452 new node will be added.
453 */
454 Node addNode(const index_type id);
455
456
457 /* \brief this will remove any nodes if there are existing nodes (and edges)
458 and will add nodes in the range of ids , endId is not included!
459 */
460 void assignNodeRange(const index_type beginId, const index_type endId);
461
462
463
464 /* \brief add an edge to the graph.
465 If there is an other edge between u and v no new edge will be added.
466 */
467 Edge addEdge(const Node & u , const Node & v);
468 /* \brief add an edge to the graph.
469 If there is an other edge between u and v no new edge will be added.
470 If the nodes for the given id's are not in the graph, they will be added.
471 */
472 Edge addEdge(const index_type u ,const index_type v);
473
474
475 size_t maxDegree()const{
476 size_t md=0;
477 for(NodeIt it(*this);it!=lemon::INVALID;++it){
478 md = std::max(md, size_t( degree(*it) ) );
479 }
480 return md;
481 }
482
483
484 ////////////////////////
485 // BOOST API
486 /////////////////////////
487 // - sizes
488 // - iterators
489 vertex_iterator get_vertex_iterator()const;
490 vertex_iterator get_vertex_end_iterator()const ;
491 edge_iterator get_edge_iterator()const;
492 edge_iterator get_edge_end_iterator()const ;
493 degree_size_type degree(const vertex_descriptor & node)const{
494 return nodeImpl(node).numberOfEdges();
495 }
496
497 static const bool is_directed = false;
498
499 public:
500
501 void reserveMaxNodeId(const index_type mxid ){
502 if(nodeNum()==0 || mxid>maxNodeId())
503 nodes_.reserve(mxid+1);
504 }
505
506 void reserveEdges(const size_t size ){
507 if(size>(size_t)edgeNum())
508 edges_.reserve(size);
509 }
510
511
512 void clear(){
513 nodeNum_=0;
514 edgeNum_=0;
515 edges_.clear();
516 nodes_.clear();
517 }
518 size_t serializationSize()const{
519
520 // num edges + num nodes
521 // max edge id + max node id
522 size_t size=4;
523
524 // edge ids
525 size+= 2*edgeNum();
526
527
528 for(NodeIt iter(*this); iter!= lemon::INVALID ; ++iter){
529 size+= 2+this->degree(*iter)*2;
530 }
531
532 return size;
533 }
534
535 template<class ITER>
536 void serialize(ITER outIter) const {
537
538 // sizes of graph
539 *outIter = nodeNum(); ++outIter;
540 *outIter = edgeNum(); ++outIter;
541 *outIter = maxNodeId(); ++outIter;
542 *outIter = maxEdgeId(); ++outIter;
543
544 // edges
545 for(EdgeIt iter(*this); iter!=lemon::INVALID; ++iter){
546 const Edge e(*iter);
547 const size_t ui = this->id(this->u(e));
548 const size_t vi = this->id(this->v(e));
549 *outIter = ui; ++outIter;
550 *outIter = vi; ++outIter;
551 }
552
553
554
555 // node neighbors
556 for(NodeIt iter(*this); iter!= lemon::INVALID ; ++iter){
557 const Node n(*iter);
558
559 *outIter = this->id(*iter); ++outIter;
560 *outIter = this->degree(*iter); ++outIter;
561
562 for(OutArcIt eIter(*this,n); eIter!=lemon::INVALID; ++eIter){
563 const Edge e(*eIter);
564 const Node oNode(this->target(*eIter));
565
566 const size_t ei = this->id(e);
567 const size_t oni = this->id(oNode);
568
569 *outIter = ei; ++outIter;
570 *outIter = oni; ++outIter;
571 }
572 }
573
574 }
575
576 template<class ITER>
577 void deserialize(ITER begin, ITER){
578
579
580 nodeNum_ = *begin; ++begin;
581 edgeNum_ = *begin; ++begin;
582 const size_t maxNid = *begin; ++begin;
583 const size_t maxEid = *begin; ++begin;
584
585 nodes_.clear();
586 edges_.clear();
587 nodes_.resize(maxNid+1, NodeStorage());
588 edges_.resize(maxEid+1, EdgeStorage());
589
590 // set up edges
591 for(size_t eid=0; eid<edgeNum_; ++eid){
592 const size_t u = *begin; ++begin;
593 const size_t v = *begin; ++begin;
594 nodes_[u].setId(u);
595 nodes_[v].setId(v);
596 edges_[eid]=EdgeStorage(u,v,eid);
597 }
598
599 // set up nodes
600 for(size_t i=0; i<nodeNum_; ++i){
601
602 const size_t id = *begin; ++begin;
603 const size_t nodeDegree=*begin; ++begin;
604
605 NodeStorage & nodeImpl = nodes_[id];
606 nodeImpl.setId(id);
607 for(size_t d=0; d<nodeDegree; ++d){
608 const size_t ei = *begin; ++begin;
609 const size_t oni = *begin; ++begin;
610 nodeImpl.insert(oni, ei);
611 }
612 }
613 }
614
615 private:
616 // private typedefs
617 typedef std::vector<NodeStorage> NodeVector;
618 typedef std::vector<EdgeStorage> EdgeVector;
619
620
621 // needs acces to const nodeImpl
622 template<class G,class NIMPL,class FILT>
623 friend class detail::GenericIncEdgeIt;
624
625 template<class G>
626 friend struct detail::NeighborNodeFilter;
627 template<class G>
628 friend struct detail::IncEdgeFilter;
629 template<class G>
630 friend struct detail::BackEdgeFilter;
631 template<class G>
632 friend struct detail::IsOutFilter;
633 template<class G>
634 friend struct detail::IsBackOutFilter;
635 template<class G>
636 friend struct detail::IsInFilter;
637
638
639 friend class detail_adjacency_list_graph::ItemIter<GraphType,Node>;
640 friend class detail_adjacency_list_graph::ItemIter<GraphType,Edge>;
641
642
643 const NodeStorage & nodeImpl(const Node & node)const{
644 return nodes_[node.id()];
645 }
646
647 NodeStorage & nodeImpl(const Node & node){
648 return nodes_[node.id()];
649 }
650
651
652
653
654
655 // graph
656 NodeVector nodes_;
657 EdgeVector edges_;
658
659 size_t nodeNum_;
660 size_t edgeNum_;
661 };
662
663
664
665#ifndef DOXYGEN // doxygen doesn't like out-of-line definitions
666
667 inline AdjacencyListGraph::AdjacencyListGraph(
668 const size_t reserveNodes,
669 const size_t reserveEdges
670 )
671 : nodes_(),
672 edges_(),
673 nodeNum_(0),
674 edgeNum_(0)
675 {
676 nodes_.reserve(reserveNodes);
677 edges_.reserve(reserveEdges);
678 }
679
680
681 inline AdjacencyListGraph::Node
682 AdjacencyListGraph::addNode(){
683 const index_type id = nodes_.size();
684 nodes_.push_back(NodeStorage(id));
685 ++nodeNum_;
686 return Node(id);
687 }
688
689 inline AdjacencyListGraph::Node
690 AdjacencyListGraph::addNode(const AdjacencyListGraph::index_type id){
691 if((std::size_t)id == nodes_.size()){
692 nodes_.push_back(NodeStorage(id));
693 ++nodeNum_;
694 return Node(id);
695 }
696 else if((std::size_t)id < nodes_.size()){
697 const Node node = nodeFromId(id);
698 if(node==lemon::INVALID){
699 nodes_[id]=NodeStorage(id);
700 ++nodeNum_;
701 return Node(id);
702 }
703 else{
704 return node;
705 }
706 }
707 else{
708 // refactor me
709 while(nodes_.size() < (std::size_t)id){
710 nodes_.push_back(NodeStorage(lemon::INVALID));
711 }
712 nodes_.push_back(NodeStorage(id));
713 ++nodeNum_;
714 return Node(id);
715 }
716 }
717
718
719 inline void
720 AdjacencyListGraph::assignNodeRange(const AdjacencyListGraph::index_type beginId, const AdjacencyListGraph::index_type endId){
721 nodes_.clear();
722 edges_.clear();
723 edgeNum_=0;
724 nodeNum_ = endId - beginId;
725 nodes_.resize(endId);
726 for(index_type i=beginId; i<endId; ++i)
727 nodes_[i]=NodeStorage(i);
728 }
729
730
731
732 inline AdjacencyListGraph::Edge
733 AdjacencyListGraph::addEdge(
734 const AdjacencyListGraph::Node & u ,
735 const AdjacencyListGraph::Node & v
736 ){
737 const Edge foundEdge = findEdge(u,v);
738 if(foundEdge!=lemon::INVALID){
739 return foundEdge;
740 }
741 else if(u==lemon::INVALID || v==lemon::INVALID){
742 return Edge(lemon::INVALID);
743 }
744 else{
745 const index_type eid = edges_.size();
746 const index_type uid = u.id();
747 const index_type vid = v.id();
748 edges_.push_back(EdgeStorage(uid,vid,eid));
749 nodeImpl(u).insert(vid,eid);
750 nodeImpl(v).insert(uid,eid);
751 ++edgeNum_;
752 return Edge(eid);
753 }
754 }
755
756 inline AdjacencyListGraph::Edge
757 AdjacencyListGraph::addEdge(
758 const AdjacencyListGraph::index_type u ,
759 const AdjacencyListGraph::index_type v
760 ){
761 const Node uu = addNode(u);
762 const Node vv = addNode(v);
763 return addEdge(uu,vv);
764 }
765
766
767
768 inline AdjacencyListGraph::Arc
769 AdjacencyListGraph::direct(
770 const AdjacencyListGraph::Edge & edge,
771 const bool forward
772 )const{
773 if(edge!=lemon::INVALID){
774 if(forward)
775 return Arc(id(edge),id(edge));
776 else
777 return Arc(id(edge)+maxEdgeId()+1,id(edge));
778 }
779 else
780 return Arc(lemon::INVALID);
781 }
782
783
784 inline AdjacencyListGraph::Arc
785 AdjacencyListGraph::direct(
786 const AdjacencyListGraph::Edge & edge,
787 const AdjacencyListGraph::Node & node
788 )const{
789 if(u(edge)==node){
790 return Arc(id(edge),id(edge));
791 }
792 else if(v(edge)==node){
793 return Arc(id(edge)+maxEdgeId()+1,id(edge));
794 }
795 else{
796 return Arc(lemon::INVALID);
797 }
798 }
799
800
801 inline bool
802 AdjacencyListGraph::direction(
803 const AdjacencyListGraph::Arc & arc
804 )const{
805 return id(arc)<=maxEdgeId();
806 }
807
808
809 inline AdjacencyListGraph::Node
810 AdjacencyListGraph::u(
811 const AdjacencyListGraph::Edge & edge
812 )const{
813 return Node(edges_[id(edge)].u());
814 }
815
816
817 inline AdjacencyListGraph::Node
818 AdjacencyListGraph::v(
819 const AdjacencyListGraph::Edge & edge
820 )const{
821 return Node(edges_[id(edge)].v());
822 }
823
824
825
826 inline AdjacencyListGraph::Node
827 AdjacencyListGraph::source(
828 const AdjacencyListGraph::Arc & arc
829 )const{
830 const index_type arcIndex = id(arc);
831 if (arcIndex > maxEdgeId() ){
832 const index_type edgeIndex = arc.edgeId();
833 const Edge edge = edgeFromId(edgeIndex);
834 return v(edge);
835 }
836 else{
837 const index_type edgeIndex = arcIndex;
838 const Edge edge = edgeFromId(edgeIndex);
839 return u(edge);
840 }
841 }
842
843
844
845 inline AdjacencyListGraph::Node
846 AdjacencyListGraph::target(
847 const AdjacencyListGraph::Arc & arc
848 )const{
849 const index_type arcIndex = id(arc);
850 if (arcIndex > maxEdgeId() ){
851 const index_type edgeIndex = arc.edgeId();
852 const Edge edge = edgeFromId(edgeIndex);
853 return u(edge);
854 }
855 else{
856 const index_type edgeIndex = arcIndex;
857 const Edge edge = edgeFromId(edgeIndex);
858 return v(edge);
859 }
860 }
861
862 inline AdjacencyListGraph::Node
863 AdjacencyListGraph::oppositeNode(
864 const AdjacencyListGraph::Node &n,
865 const AdjacencyListGraph::Edge &e
866 ) const {
867 const Node uNode = u(e);
868 const Node vNode = v(e);
869 if(id(uNode)==id(n)){
870 return vNode;
871 }
872 else if(id(vNode)==id(n)){
873 return uNode;
874 }
875 else{
876 return Node(-1);
877 }
878 }
879
880
881
882 inline AdjacencyListGraph::Node
883 AdjacencyListGraph::baseNode(
884 const AdjacencyListGraph::IncEdgeIt & iter
885 )const{
886 return u(*iter);
887 }
888
889
890 inline AdjacencyListGraph::Node
891 AdjacencyListGraph::baseNode(
892 const AdjacencyListGraph::OutArcIt & iter
893 )const{
894 return source(*iter);
895 }
896
897
898
899 inline AdjacencyListGraph::Node
900 AdjacencyListGraph::runningNode(
901 const AdjacencyListGraph::IncEdgeIt & iter
902 )const{
903 return v(*iter);
904 }
905
906
907 inline AdjacencyListGraph::Node
908 AdjacencyListGraph::runningNode(
909 const AdjacencyListGraph::OutArcIt & iter
910 )const{
911 return target(*iter);
912 }
913
914
915 inline AdjacencyListGraph::index_type
916 AdjacencyListGraph::edgeNum()const{
917 return edgeNum_;
918 }
919
920
921 inline AdjacencyListGraph::index_type
922 AdjacencyListGraph::nodeNum()const{
923 return nodeNum_;
924 }
925
926
927 inline AdjacencyListGraph::index_type
928 AdjacencyListGraph::arcNum()const{
929 return edgeNum()*2;
930 }
931
932
933 inline AdjacencyListGraph::index_type
934 AdjacencyListGraph::maxEdgeId()const{
935 return edges_.back().id();
936 }
937
938
939 inline AdjacencyListGraph::index_type
940 AdjacencyListGraph::maxNodeId()const{
941 return nodes_.back().id();
942 }
943
944
945 inline AdjacencyListGraph::index_type
946 AdjacencyListGraph::maxArcId()const{
947 return maxEdgeId()*2+1;
948 }
949
950 // ids
951
952 inline AdjacencyListGraph::index_type
953 AdjacencyListGraph::id(
954 const AdjacencyListGraph::Node & node
955 )const{
956 return node.id();
957 }
958
959
960 inline AdjacencyListGraph::index_type
961 AdjacencyListGraph::id(
962 const AdjacencyListGraph::Edge & edge
963 )const{
964 return edge.id();
965 }
966
967
968 inline AdjacencyListGraph::index_type
969 AdjacencyListGraph::id(
970 const AdjacencyListGraph::Arc & arc
971 )const{
972 return arc.id();
973 }
974
975 // get edge / node from id
976
977 inline AdjacencyListGraph::Edge
978 AdjacencyListGraph::edgeFromId(
979 const AdjacencyListGraph::index_type id
980 )const{
981 if((std::size_t)id < edges_.size() && edges_[id].id() != -1)
982 return Edge(edges_[id].id());
983 else
984 return Edge(lemon::INVALID);
985 }
986
987
988 inline AdjacencyListGraph::Node
989 AdjacencyListGraph::nodeFromId(
990 const AdjacencyListGraph::index_type id
991 )const{
992 if((std::size_t)id < nodes_.size() && nodes_[id].id() != -1)
993 return Node(nodes_[id].id());
994 else
995 return Node(lemon::INVALID);
996 }
997
998
999 inline AdjacencyListGraph::Arc
1000 AdjacencyListGraph::arcFromId(
1001 const AdjacencyListGraph::index_type id
1002 )const{
1003 if(id<=maxEdgeId()){
1004 if(edgeFromId(id)==lemon::INVALID)
1005 return Arc(lemon::INVALID);
1006 else
1007 return Arc(id,id);
1008 }
1009 else{
1010 const index_type edgeId = id - (maxEdgeId() + 1);
1011 if( edgeFromId(edgeId)==lemon::INVALID)
1012 return Arc(lemon::INVALID);
1013 else
1014 return Arc(id,edgeId);
1015 }
1016 }
1017
1018
1019 inline AdjacencyListGraph::Edge
1020 AdjacencyListGraph::findEdge(
1021 const AdjacencyListGraph::Node & a,
1022 const AdjacencyListGraph::Node & b
1023 )const{
1024 if(a!=b){
1025 std::pair<index_type,bool> res = nodes_[id(a)].findEdge(id(b));
1026 if(res.second){
1027 return Edge(res.first);
1028 }
1029 }
1030 return Edge(lemon::INVALID);
1031 }
1032
1033
1034
1035 inline AdjacencyListGraph::Arc
1036 AdjacencyListGraph::findArc(
1037 const AdjacencyListGraph::Node & uNode,
1038 const AdjacencyListGraph::Node & vNode
1039 )const{
1040 const Edge e = findEdge(uNode,vNode);
1041 if(e==lemon::INVALID){
1042 return Arc(lemon::INVALID);
1043 }
1044 else{
1045 if(u(e)==uNode)
1046 return direct(e,true) ;
1047 else
1048 return direct(e,false) ;
1049 }
1050 }
1051
1052
1053 // iterators
1054
1055 inline AdjacencyListGraph::vertex_iterator
1056 AdjacencyListGraph::get_vertex_iterator()const{
1057 return NodeIt(0,nodeNum());
1058 }
1059
1060
1061 inline AdjacencyListGraph::vertex_iterator
1062 AdjacencyListGraph::get_vertex_end_iterator()const{
1063 return NodeIt(nodeNum(),nodeNum());
1064 }
1065
1066
1067
1068 inline AdjacencyListGraph::edge_iterator
1069 AdjacencyListGraph::get_edge_iterator()const{
1070 return EdgeIt(0,edgeNum());
1071 }
1072
1073
1074 inline AdjacencyListGraph::edge_iterator
1075 AdjacencyListGraph::get_edge_end_iterator()const{
1076 return EdgeIt(edgeNum(),edgeNum());
1077 }
1078
1079#endif //DOXYGEN
1080
1081//@}
1082
1083} // namespace vigra
1084
1085
1086// boost free functions specialized for adjacency list graph
1087 namespace boost{
1088
1089 ////////////////////////////////////
1090 // functions to get size of the graph
1091 ////////////////////////////////////
1092 inline vigra::AdjacencyListGraph::vertex_size_type
1093 num_vertices(const vigra::AdjacencyListGraph & g){
1094 return g.nodeNum();
1095 }
1096 inline vigra::AdjacencyListGraph::edge_size_type
1097 num_edges(const vigra::AdjacencyListGraph & g){
1098 return g.edgeNum();
1099 }
1100
1101
1102 ////////////////////////////////////
1103 // functions to get degrees of nodes
1104 // (degree / indegree / outdegree)
1105 ////////////////////////////////////
1106 inline vigra::AdjacencyListGraph::degree_size_type
1107 degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
1108 return g.degree(v);
1109 }
1110 // ??? check if this is the right impl. for undirected graphs
1111 inline vigra::AdjacencyListGraph::degree_size_type
1112 in_degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
1113 return g.degree(v);
1114 }
1115 // ??? check if this is the right impl. for undirected graphs
1116 inline vigra::AdjacencyListGraph::degree_size_type
1117 out_degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
1118 return g.degree(v);
1119 }
1120
1121
1122 ////////////////////////////////////
1123 // functions to u/v source/target
1124 ////////////////////////////////////
1125 inline vigra::AdjacencyListGraph::vertex_descriptor
1126 source(const vigra::AdjacencyListGraph::edge_descriptor & e , const vigra::AdjacencyListGraph & g){
1127 return g.u(e);
1128 }
1129
1130 inline vigra::AdjacencyListGraph::vertex_descriptor
1131 target(const vigra::AdjacencyListGraph::edge_descriptor & e , const vigra::AdjacencyListGraph & g){
1132 return g.v(e);
1133 }
1134
1135 ////////////////////////////////////
1136 // functions to get iterator pairs
1137 ////////////////////////////////////
1138 inline std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >
1139 vertices(const vigra::AdjacencyListGraph & g ){
1140 return std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >(
1141 g.get_vertex_iterator(), g.get_vertex_end_iterator());
1142 }
1143 inline std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >
1144 edges(const vigra::AdjacencyListGraph & g ){
1145 return std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >(
1146 g.get_edge_iterator(),g.get_edge_end_iterator());
1147 }
1148
1149
1150 inline std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >
1151 in_edges(const vigra::AdjacencyListGraph::vertex_descriptor & v, const vigra::AdjacencyListGraph & g ){
1152 return std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >(
1153 vigra::AdjacencyListGraph::in_edge_iterator(g,v),vigra::AdjacencyListGraph::in_edge_iterator(lemon::INVALID)
1154 );
1155 }
1156 inline std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >
1157 out_edges(const vigra::AdjacencyListGraph::vertex_descriptor & v, const vigra::AdjacencyListGraph & g ){
1158 return std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >(
1159 vigra::AdjacencyListGraph::out_edge_iterator(g,v),vigra::AdjacencyListGraph::out_edge_iterator(lemon::INVALID)
1160 );
1161 }
1162
1163} // namespace boost
1164
1165#endif /*VIGRA_ADJACENCY_LIST_GRAPH_HXX*/
vigra::AdjacencyListGraph
undirected adjacency list graph in the LEMON API
Definition adjacency_list_graph.hxx:228
vigra::AdjacencyListGraph::AdjacencyListGraph
AdjacencyListGraph(const size_t nodes=0, const size_t edges=0)
Constructor.
vigra::AdjacencyListGraph::Node
detail::GenericNode< index_type > Node
node descriptor
Definition adjacency_list_graph.hxx:247
vigra::AdjacencyListGraph::ArcIt
detail_adjacency_list_graph::ArcIt< GraphType > ArcIt
arc iterator
Definition adjacency_list_graph.hxx:257
vigra::AdjacencyListGraph::u
Node u(const Edge &edge) const
Get the start node of the given edge e (API: LEMON, the boost::graph API provides the free function ...
vigra::AdjacencyListGraph::findEdge
Edge findEdge(const Node &a, const Node &b) const
Get a descriptor for the edge connecting vertices u and v, or lemon::INVALID if no such edge exists (...
vigra::AdjacencyListGraph::edgeNum
index_type edgeNum() const
Get the number of edges in this graph (API: LEMON).
vigra::AdjacencyListGraph::runningNode
Node runningNode(const OutArcIt &iter) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
vigra::AdjacencyListGraph::direct
Arc direct(const Edge &edge, const bool forward) const
Create an arc for the given edge e, oriented along the edge's natural (forward = true) or reversed (f...
vigra::AdjacencyListGraph::v
Node v(const Edge &edge) const
Get the end node of the given edge e (API: LEMON, the boost::graph API provides the free function bo...
vigra::AdjacencyListGraph::InArcIt
detail::GenericIncEdgeIt< GraphType, NodeStorage, InFlter > InArcIt
incoming arc iterator
Definition adjacency_list_graph.hxx:262
vigra::AdjacencyListGraph::oppositeNode
Node oppositeNode(Node const &n, const Edge &e) const
Return the opposite node of the given node n along edge e (API: LEMON), or return lemon::INVALID if t...
vigra::AdjacencyListGraph::EdgeIt
detail_adjacency_list_graph::ItemIter< GraphType, Edge > EdgeIt
edge iterator
Definition adjacency_list_graph.hxx:253
vigra::AdjacencyListGraph::nodeFromId
Node nodeFromId(const index_type id) const
Get node descriptor for given node ID i (API: LEMON). Return Node(lemon::INVALID) when the ID does no...
vigra::AdjacencyListGraph::id
index_type id(const Node &node) const
Get the ID for node desciptor v (API: LEMON).
vigra::AdjacencyListGraph::target
Node target(const Arc &arc) const
Get the end node of the given arc a (API: LEMON).
vigra::AdjacencyListGraph::runningNode
Node runningNode(const IncEdgeIt &iter) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
vigra::AdjacencyListGraph::baseNode
Node baseNode(const OutArcIt &iter) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
vigra::AdjacencyListGraph::id
index_type id(const Edge &edge) const
Get the ID for edge desciptor v (API: LEMON).
vigra::AdjacencyListGraph::Edge
detail::GenericEdge< index_type > Edge
edge descriptor
Definition adjacency_list_graph.hxx:249
vigra::AdjacencyListGraph::source
Node source(const Arc &arc) const
Get the start node of the given arc a (API: LEMON).
vigra::AdjacencyListGraph::direction
bool direction(const Arc &arc) const
Return true when the arc is looking on the underlying edge in its natural (i.e. forward) direction,...
vigra::AdjacencyListGraph::maxArcId
index_type maxArcId() const
Get the maximum ID of any edge in arc graph (API: LEMON).
vigra::AdjacencyListGraph::OutBackArcIt
detail::GenericIncEdgeIt< GraphType, NodeStorage, BackOutFilter > OutBackArcIt
outgoing back arc iterator
Definition adjacency_list_graph.hxx:270
vigra::AdjacencyListGraph::baseNode
Node baseNode(const IncEdgeIt &iter) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
vigra::AdjacencyListGraph::direct
Arc direct(const Edge &edge, const Node &node) const
Create an arc for the given edge e oriented so that node n is the starting node of the arc (API: LEMO...
vigra::AdjacencyListGraph::maxNodeId
index_type maxNodeId() const
Get the maximum ID of any node in this graph (API: LEMON).
vigra::AdjacencyListGraph::arcNum
index_type arcNum() const
Get the number of arcs in this graph (API: LEMON).
vigra::AdjacencyListGraph::IncEdgeIt
detail::GenericIncEdgeIt< GraphType, NodeStorage, IncFilter > IncEdgeIt
incident edge iterator
Definition adjacency_list_graph.hxx:260
vigra::AdjacencyListGraph::NodeIt
detail_adjacency_list_graph::ItemIter< GraphType, Node > NodeIt
node iterator
Definition adjacency_list_graph.hxx:255
vigra::AdjacencyListGraph::nodeNum
index_type nodeNum() const
Get the number of nodes in this graph (API: LEMON).
vigra::AdjacencyListGraph::id
index_type id(const Arc &arc) const
Get the ID for arc desciptor v (API: LEMON).
vigra::AdjacencyListGraph::edgeFromId
Edge edgeFromId(const index_type id) const
Get edge descriptor for given node ID i (API: LEMON). Return Edge(lemon::INVALID) when the ID does no...
vigra::AdjacencyListGraph::OutArcIt
detail::GenericIncEdgeIt< GraphType, NodeStorage, OutFilter > OutArcIt
outgoing arc iterator
Definition adjacency_list_graph.hxx:264
vigra::AdjacencyListGraph::findArc
Arc findArc(const Node &u, const Node &v) const
Get a descriptor for the arc connecting vertices u and v, or lemon::INVALID if no such edge exists (A...
vigra::AdjacencyListGraph::Arc
detail::GenericArc< index_type > Arc
arc descriptor
Definition adjacency_list_graph.hxx:251
vigra::AdjacencyListGraph::arcFromId
Arc arcFromId(const index_type id) const
Get arc descriptor for given node ID i (API: LEMON). Return Arc(lemon::INVALID) when the ID does not ...
vigra::AdjacencyListGraph::maxEdgeId
index_type maxEdgeId() const
Get the maximum ID of any edge in this graph (API: LEMON).
vigra::RGBValue
Class for a single RGB value.
Definition rgbvalue.hxx:128
vigra
vigra::Int64
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition sized_int.hxx:177
vigra::AdjacencyListGraph::ArcMap
default arc map
Definition adjacency_list_graph.hxx:320
vigra::AdjacencyListGraph::EdgeMap
default edge map
Definition adjacency_list_graph.hxx:294
vigra::AdjacencyListGraph::NodeMap
default node map
Definition adjacency_list_graph.hxx:307

© 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.1