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

adjacency_list_graph.hxx VIGRA

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 
64  namespace detail_adjacency_list_graph{
65 
66  template<class G,class ITEM>
67  class ItemIter
68  : public ForwardIteratorFacade<
69  ItemIter<G,ITEM>,ITEM,true
70  >
71  {
72 
73  typedef vigra::GraphItemHelper<G,ITEM> ItemHelper;
74  typedef typename G::index_type index_type;
75 
76  public:
77  ItemIter(const lemon::Invalid & iv = lemon::INVALID)
78  : graph_(NULL),
79  id_(-1),
80  item_(lemon::INVALID)
81  {
82  }
83 
84  ItemIter(const G & g)
85  : graph_(&g),
86  id_(0),
87  item_(ItemHelper::itemFromId(*graph_,id_))
88  {
89  while( !isEnd() && item_==lemon::INVALID ){
90  ++id_;
91  item_ = ItemHelper::itemFromId(*graph_,id_);
92  }
93  }
94 
95  ItemIter(const G & g,const ITEM & item)
96  : graph_(&g),
97  id_(g.id(item)),
98  item_(item)
99  {
100 
101  }
102 
103  private:
104 
105  friend class vigra::IteratorFacadeCoreAccess;
106  bool isEnd( )const{
107  return graph_==NULL || ItemHelper::itemNum(*graph_)==0 || id_>ItemHelper::maxItemId(*graph_);
108  }
109  bool isBegin( )const{
110  return graph_!=NULL && id_ == 0 ;
111  }
112 
113  bool equal(const ItemIter & other) const{
114  return (isEnd() && other.isEnd() ) || (isEnd()==other.isEnd() && (id_ == other.id_) );
115  }
116 
117  void increment(){
118  ++id_;
119  item_ = ItemHelper::itemFromId(*graph_,id_);
120  while( !isEnd() && item_==lemon::INVALID ){
121  ++id_;
122  item_ = ItemHelper::itemFromId(*graph_,id_);
123  }
124  }
125  const ITEM & dereference()const{
126  return item_;
127  }
128  const G * graph_;
129  index_type id_;
130  ITEM item_;
131  };
132 
133 
134 
135  template<class GRAPH>
136  class ArcIt
137  : public ForwardIteratorFacade<
138  ArcIt<GRAPH>,
139  typename GRAPH::Arc,true
140  >
141  {
142  public:
143  typedef GRAPH Graph;
144  typedef typename Graph::Arc Arc;
145  typedef typename Graph::Edge Edge;
146  typedef typename Graph::EdgeIt EdgeIt;
147  ArcIt(const lemon::Invalid invalid = lemon::INVALID )
148  : graph_(NULL),
149  pos_(),
150  inFirstHalf_(false),
151  veryEnd_(true),
152  arc_(){
153  }
154  ArcIt(const GRAPH & g )
155  : graph_(&g),
156  pos_(g),
157  inFirstHalf_(true),
158  veryEnd_( g.edgeNum()==0 ? true : false),
159  arc_(){
160  }
161 
162  ArcIt(const GRAPH & g , const Arc & arc )
163  : graph_(&g),
164  pos_(g,arc.edgeId()),
165  inFirstHalf_(g.id(arc)<=g.maxEdgeId()),
166  veryEnd_(false),
167  arc_(){
168  }
169  private:
170  friend class vigra::IteratorFacadeCoreAccess;
171  bool isEnd()const{
172  return veryEnd_ || graph_==NULL;
173  }
174 
175  bool isBegin()const{
176  return graph_!=NULL && veryEnd_==false && pos_ == EdgeIt(*graph_);
177  }
178  void increment() {
179  if(inFirstHalf_){
180  ++pos_;
181  if(pos_ == lemon::INVALID ) {
182  pos_ = EdgeIt(*graph_);
183  inFirstHalf_=false;
184  }
185  return;
186  }
187  else{
188  ++pos_;
189  if(pos_ == lemon::INVALID){
190  veryEnd_=true;
191  }
192  return;
193  }
194 
195 
196  }
197  bool equal(ArcIt const& other) const{
198  return (
199  (
200  isEnd()==other.isEnd() &&
201  inFirstHalf_==other.inFirstHalf_
202  ) &&
203  (isEnd() || graph_==NULL || pos_==other.pos_ )
204  );
205 
206  }
207 
208  const Arc & dereference() const {
209  //std::cout<<graph_->id(*pos_)<<"\n";
210  arc_ = graph_->direct(*pos_,inFirstHalf_);
211  return arc_;
212  }
213 
214 
215  const GRAPH * graph_;
216  EdgeIt pos_;
217  bool inFirstHalf_;
218  bool veryEnd_;
219  mutable Arc arc_;
220  };
221 
222  }
223 
224 
225  /** \brief undirected adjacency list graph in the LEMON API
226 
227  */
229  {
230 
231  public:
232  // public typdedfs
233  typedef Int64 index_type;
234  private:
235  // private typedes which are needed for defining public typedes
237  typedef detail::GenericNodeImpl<index_type,false> NodeStorage;
238  typedef detail::GenericEdgeImpl<index_type > EdgeStorage;
239  typedef detail::NeighborNodeFilter<GraphType> NnFilter;
240  typedef detail::IncEdgeFilter<GraphType> IncFilter;
241  typedef detail::IsInFilter<GraphType> InFlter;
242  typedef detail::IsOutFilter<GraphType> OutFilter;
243  typedef detail::IsBackOutFilter<GraphType> BackOutFilter;
244  public:
245  // LEMON API TYPEDEFS (and a few more(NeighborNodeIt))
246 
247  /// node descriptor
248  typedef detail::GenericNode<index_type> Node;
249  /// edge descriptor
250  typedef detail::GenericEdge<index_type> Edge;
251  /// arc descriptor
252  typedef detail::GenericArc<index_type> Arc;
253  /// edge iterator
254  typedef detail_adjacency_list_graph::ItemIter<GraphType,Edge> EdgeIt;
255  /// node iterator
256  typedef detail_adjacency_list_graph::ItemIter<GraphType,Node> NodeIt;
257  /// arc iterator
258  typedef detail_adjacency_list_graph::ArcIt<GraphType> ArcIt;
259 
260  /// incident edge iterator
261  typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,IncFilter > IncEdgeIt;
262  /// incoming arc iterator
263  typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,InFlter > InArcIt;
264  /// outgoing arc iterator
265  typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,OutFilter > OutArcIt;
266 
267  typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,NnFilter > NeighborNodeIt;
268 
269 
270  /// outgoing back arc iterator
271  typedef detail::GenericIncEdgeIt<GraphType,NodeStorage,BackOutFilter > OutBackArcIt;
272 
273 
274  // BOOST GRAPH API TYPEDEFS
275  // - categories (not complete yet)
276  typedef boost::directed_tag directed_category;
277  // iterators
278  typedef NeighborNodeIt adjacency_iterator;
279  typedef EdgeIt edge_iterator;
280  typedef NodeIt vertex_iterator;
281  typedef IncEdgeIt in_edge_iterator;
282  typedef IncEdgeIt out_edge_iterator;
283 
284  // size types
285  typedef size_t degree_size_type;
286  typedef size_t edge_size_type;
287  typedef size_t vertex_size_type;
288  // item descriptors
289  typedef Edge edge_descriptor;
290  typedef Node vertex_descriptor;
291 
292 
293  /// default edge map
294  template<class T>
295  struct EdgeMap : DenseEdgeReferenceMap<GraphType,T> {
296  EdgeMap(): DenseEdgeReferenceMap<GraphType,T>(){
297  }
298  EdgeMap(const GraphType & g)
299  : DenseEdgeReferenceMap<GraphType,T>(g){
300  }
301  EdgeMap(const GraphType & g,const T & val)
302  : DenseEdgeReferenceMap<GraphType,T>(g,val){
303  }
304  };
305 
306  /// default node map
307  template<class T>
308  struct NodeMap : DenseNodeReferenceMap<GraphType,T> {
309  NodeMap(): DenseNodeReferenceMap<GraphType,T>(){
310  }
311  NodeMap(const GraphType & g)
312  : DenseNodeReferenceMap<GraphType,T>(g){
313  }
314  NodeMap(const GraphType & g,const T & val)
315  : DenseNodeReferenceMap<GraphType,T>(g,val){
316  }
317  };
318 
319  /// default arc map
320  template<class T>
321  struct ArcMap : DenseArcReferenceMap<GraphType,T> {
322  ArcMap(): DenseArcReferenceMap<GraphType,T>(){
323  }
324  ArcMap(const GraphType & g)
325  : DenseArcReferenceMap<GraphType,T>(g){
326  }
327  ArcMap(const GraphType & g,const T & val)
328  : DenseArcReferenceMap<GraphType,T>(g,val){
329  }
330  };
331 
332 
333 
334  // public member functions
335  public:
336  /// construct
337  /// @param nodes : reserve space for n nodes
338  /// @param edges : reserve space for n edges
339  AdjacencyListGraph(const size_t nodes=0,const size_t edges=0);
340 
341  /** \brief Get the number of edges in this graph (API: LEMON).
342  */
343  index_type edgeNum()const;
344 
345  /** \brief Get the number of nodes in this graph (API: LEMON).
346  */
347  index_type nodeNum()const;
348  /** \brief Get the number of arcs in this graph (API: LEMON).
349  */
350  index_type arcNum()const;
351 
352  /** \brief Get the maximum ID of any edge in this graph (API: LEMON).
353  */
354  index_type maxEdgeId()const;
355  /** \brief Get the maximum ID of any node in this graph (API: LEMON).
356  */
357  index_type maxNodeId()const;
358  /** \brief Get the maximum ID of any edge in arc graph (API: LEMON).
359  */
360  index_type maxArcId()const;
361 
362  /** \brief Create an arc for the given edge \a e, oriented along the
363  edge's natural (<tt>forward = true</tt>) or reversed
364  (<tt>forward = false</tt>) direction (API: LEMON).
365  */
366  Arc direct(const Edge & edge,const bool forward)const;
367 
368  /** \brief Create an arc for the given edge \a e oriented
369  so that node \a n is the starting node of the arc (API: LEMON), or
370  return <tt>lemon::INVALID</tt> if the edge is not incident to this node.
371  */
372  Arc direct(const Edge & edge,const Node & node)const;
373 
374  /** \brief Return <tt>true</tt> when the arc is looking on the underlying
375  edge in its natural (i.e. forward) direction, <tt>false</tt> otherwise (API: LEMON).
376  */
377  bool direction(const Arc & arc)const;
378  /** \brief Get the start node of the given edge \a e (API: LEMON,<br/>
379  the boost::graph API provides the free function <tt>boost::source(e, graph)</tt>).
380  */
381  Node u(const Edge & edge)const;
382  /** \brief Get the end node of the given edge \a e (API: LEMON,<br/>
383  the boost::graph API provides the free function <tt>boost::target(e, graph)</tt>).
384  */
385  Node v(const Edge & edge)const;
386  /** \brief Get the start node of the given arc \a a (API: LEMON).
387  */
388  Node source(const Arc & arc)const;
389  /** \brief Get the end node of the given arc \a a (API: LEMON).
390  */
391  Node target(const Arc & arc)const;
392  /** \brief Return the opposite node of the given node \a n
393  along edge \a e (API: LEMON), or return <tt>lemon::INVALID</tt>
394  if the edge is not incident to this node.
395  */
396  Node oppositeNode(Node const &n, const Edge &e) const;
397 
398  /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
399  */
400  Node baseNode(const IncEdgeIt & iter)const;
401  /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
402  */
403  Node baseNode(const OutArcIt & iter)const;
404 
405  /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
406  */
407  Node runningNode(const IncEdgeIt & iter)const;
408  /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
409  */
410  Node runningNode(const OutArcIt & iter)const;
411 
412 
413  /** \brief Get the ID for node desciptor \a v (API: LEMON).
414  */
415  index_type id(const Node & node)const;
416  /** \brief Get the ID for edge desciptor \a v (API: LEMON).
417  */
418  index_type id(const Edge & edge)const;
419  /** \brief Get the ID for arc desciptor \a v (API: LEMON).
420  */
421  index_type id(const Arc & arc )const;
422 
423  /** \brief Get edge descriptor for given node ID \a i (API: LEMON).
424  Return <tt>Edge(lemon::INVALID)</tt> when the ID does not exist in this graph.
425  */
426  Edge edgeFromId(const index_type id)const;
427 
428  /** \brief Get node descriptor for given node ID \a i (API: LEMON).
429  Return <tt>Node(lemon::INVALID)</tt> when the ID does not exist in this graph.
430  */
431  Node nodeFromId(const index_type id)const;
432  /** \brief Get arc descriptor for given node ID \a i (API: LEMON).
433  Return <tt>Arc(lemon::INVALID)</tt> when the ID does not exist in this graph.
434  */
435  Arc arcFromId(const index_type id)const;
436 
437 
438  /** \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).
439  */
440  Edge findEdge(const Node & a,const Node & b)const;
441  /** \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).
442  */
443  Arc findArc(const Node & u,const Node & v)const;
444 
445  /* \brief add a new node to the graph.
446  the next unused id will be assigned to the node
447  */
448  Node addNode();
449  /* \brief add a node to the graph with a given id.
450  If there is another node with this id, no
451  new node will be added.
452  */
453  Node addNode(const index_type id);
454  /* \brief add an edge to the graph.
455  If there is an other edge between u and v no new edge will be added.
456  */
457  Edge addEdge(const Node & u , const Node & v);
458  /* \brief add an edge to the graph.
459  If there is an other edge between u and v no new edge will be added.
460  If the nodes for the given id's are not in the graph, they will be added.
461  */
462  Edge addEdge(const index_type u ,const index_type v);
463 
464 
465  size_t maxDegree()const{
466  size_t md=0;
467  for(NodeIt it(*this);it!=lemon::INVALID;++it){
468  std::max(md, size_t( degree(*it) ) );
469  }
470  return md;
471  }
472 
473 
474  ////////////////////////
475  // BOOST API
476  /////////////////////////
477  // - sizes
478  // - iterators
479  vertex_iterator get_vertex_iterator()const;
480  vertex_iterator get_vertex_end_iterator()const ;
481  edge_iterator get_edge_iterator()const;
482  edge_iterator get_edge_end_iterator()const ;
483  degree_size_type degree(const vertex_descriptor & node)const{
484  return nodeImpl(node).numberOfEdges();
485  }
486 
487  static const bool is_directed = false;
488 
489  private:
490  // private typedefs
491  typedef std::vector<NodeStorage> NodeVector;
492  typedef std::vector<EdgeStorage> EdgeVector;
493 
494 
495  // needs acces to const nodeImpl
496  template<class G,class NIMPL,class FILT>
497  friend class detail::GenericIncEdgeIt;
498 
499  template<class G>
500  friend struct detail::NeighborNodeFilter;
501  template<class G>
502  friend struct detail::IncEdgeFilter;
503  template<class G>
504  friend struct detail::BackEdgeFilter;
505  template<class G>
506  friend struct detail::IsOutFilter;
507  template<class G>
508  friend struct detail::IsBackOutFilter;
509  template<class G>
510  friend struct detail::IsInFilter;
511 
512 
513  friend class detail_adjacency_list_graph::ItemIter<GraphType,Node>;
514  friend class detail_adjacency_list_graph::ItemIter<GraphType,Edge>;
515 
516 
517  const NodeStorage & nodeImpl(const Node & node)const{
518  return nodes_[node.id()];
519  }
520 
521  NodeStorage & nodeImpl(const Node & node){
522  return nodes_[node.id()];
523  }
524 
525 
526 
527 
528 
529  // graph
530  NodeVector nodes_;
531  EdgeVector edges_;
532 
533  size_t nodeNum_;
534  size_t edgeNum_;
535  };
536 
537 
538 
539 
540 
542  const size_t reserveNodes,
543  const size_t reserveEdges
544  )
545  : nodes_(),
546  edges_(),
547  nodeNum_(0),
548  edgeNum_(0)
549  {
550  nodes_.reserve(reserveNodes);
551  edges_.reserve(reserveEdges);
552  }
553 
554 
556  AdjacencyListGraph::addNode(){
557  const index_type id = nodes_.size();
558  nodes_.push_back(NodeStorage(id));
559  ++nodeNum_;
560  return Node(id);
561  }
562 
564  AdjacencyListGraph::addNode(const AdjacencyListGraph::index_type id){
565  if(id == nodes_.size()){
566  nodes_.push_back(NodeStorage(id));
567  ++nodeNum_;
568  return Node(id);
569  }
570  else if((std::size_t)id < nodes_.size()){
571  const Node node = nodeFromId(id);
572  if(node==lemon::INVALID){
573  nodes_[id]=NodeStorage(id);
574  ++nodeNum_;
575  return Node(id);
576  }
577  else{
578  return node;
579  }
580  }
581  else{
582  // refactor me
583  while(nodes_.size() < (std::size_t)id){
584  nodes_.push_back(NodeStorage(lemon::INVALID));
585  }
586  nodes_.push_back(NodeStorage(id));
587  ++nodeNum_;
588  return Node(id);
589  }
590  }
591 
593  AdjacencyListGraph::addEdge(
594  const AdjacencyListGraph::Node & u ,
595  const AdjacencyListGraph::Node & v
596  ){
597  const Edge foundEdge = findEdge(u,v);
598  if(foundEdge!=lemon::INVALID){
599  return foundEdge;
600  }
601  else if(u==lemon::INVALID || v==lemon::INVALID){
602  return Edge(lemon::INVALID);
603  }
604  else{
605  const index_type eid = edges_.size();
606  const index_type uid = u.id();
607  const index_type vid = v.id();
608  edges_.push_back(EdgeStorage(uid,vid,eid));
609  nodeImpl(u).insert(vid,eid);
610  nodeImpl(v).insert(uid,eid);
611  ++edgeNum_;
612  return Edge(eid);
613  }
614  }
615 
617  AdjacencyListGraph::addEdge(
618  const AdjacencyListGraph::index_type u ,
619  const AdjacencyListGraph::index_type v
620  ){
621  const Node uu = addNode(u);
622  const Node vv = addNode(v);
623  return addEdge(uu,vv);
624  }
625 
626 
627 
631  const bool forward
632  )const{
633  if(edge!=lemon::INVALID){
634  if(forward)
635  return Arc(id(edge),id(edge));
636  else
637  return Arc(id(edge)+maxEdgeId()+1,id(edge));
638  }
639  else
640  return Arc(lemon::INVALID);
641  }
642 
643 
647  const AdjacencyListGraph::Node & node
648  )const{
649  if(u(edge)==node){
650  return Arc(id(edge),id(edge));
651  }
652  else if(v(edge)==node){
653  return Arc(id(edge)+maxEdgeId()+1,id(edge));
654  }
655  else{
656  return Arc(lemon::INVALID);
657  }
658  }
659 
660 
661  inline bool
663  const AdjacencyListGraph::Arc & arc
664  )const{
665  return id(arc)<=maxEdgeId();
666  }
667 
668 
672  )const{
673  return Node(edges_[id(edge)].u());
674  }
675 
676 
680  )const{
681  return Node(edges_[id(edge)].v());
682  }
683 
684 
685 
688  const AdjacencyListGraph::Arc & arc
689  )const{
690  const index_type arcIndex = id(arc);
691  if (arcIndex > maxEdgeId() ){
692  const index_type edgeIndex = arc.edgeId();
693  const Edge edge = edgeFromId(edgeIndex);
694  return v(edge);
695  }
696  else{
697  const index_type edgeIndex = arcIndex;
698  const Edge edge = edgeFromId(edgeIndex);
699  return u(edge);
700  }
701  }
702 
703 
704 
707  const AdjacencyListGraph::Arc & arc
708  )const{
709  const index_type arcIndex = id(arc);
710  if (arcIndex > maxEdgeId() ){
711  const index_type edgeIndex = arc.edgeId();
712  const Edge edge = edgeFromId(edgeIndex);
713  return u(edge);
714  }
715  else{
716  const index_type edgeIndex = arcIndex;
717  const Edge edge = edgeFromId(edgeIndex);
718  return v(edge);
719  }
720  }
721 
722 
725  const AdjacencyListGraph::Node &n,
726  const AdjacencyListGraph::Edge &e
727  ) const {
728  const Node uNode = u(e);
729  const Node vNode = v(e);
730  if(id(uNode)==id(n)){
731  return vNode;
732  }
733  else if(id(vNode)==id(n)){
734  return uNode;
735  }
736  else{
737  return Node(-1);
738  }
739  }
740 
741 
742 
745  const AdjacencyListGraph::IncEdgeIt & iter
746  )const{
747  return u(*iter);
748  }
749 
750 
753  const AdjacencyListGraph::OutArcIt & iter
754  )const{
755  return source(*iter);
756  }
757 
758 
759 
762  const AdjacencyListGraph::IncEdgeIt & iter
763  )const{
764  return v(*iter);
765  }
766 
767 
770  const AdjacencyListGraph::OutArcIt & iter
771  )const{
772  return target(*iter);
773  }
774 
775 
776  inline AdjacencyListGraph::index_type
778  return edgeNum_;
779  }
780 
781 
782  inline AdjacencyListGraph::index_type
784  return nodeNum_;
785  }
786 
787 
788  inline AdjacencyListGraph::index_type
790  return edgeNum()*2;
791  }
792 
793 
794  inline AdjacencyListGraph::index_type
796  return edges_.back().id();
797  }
798 
799 
800  inline AdjacencyListGraph::index_type
802  return nodes_.back().id();
803  }
804 
805 
806  inline AdjacencyListGraph::index_type
808  return maxEdgeId()*2+1;
809  }
810 
811  // ids
812 
813  inline AdjacencyListGraph::index_type
815  const AdjacencyListGraph::Node & node
816  )const{
817  return node.id();
818  }
819 
820 
821  inline AdjacencyListGraph::index_type
824  )const{
825  return edge.id();
826  }
827 
828 
829  inline AdjacencyListGraph::index_type
831  const AdjacencyListGraph::Arc & arc
832  )const{
833  return arc.id();
834  }
835 
836  // get edge / node from id
837 
840  const AdjacencyListGraph::index_type id
841  )const{
842  if((std::size_t)id < edges_.size() && edges_[id].id() != -1)
843  return Edge(edges_[id].id());
844  else
845  return Edge(lemon::INVALID);
846  }
847 
848 
851  const AdjacencyListGraph::index_type id
852  )const{
853  if((std::size_t)id < nodes_.size() && nodes_[id].id() != -1)
854  return Node(nodes_[id].id());
855  else
856  return Node(lemon::INVALID);
857  }
858 
859 
862  const AdjacencyListGraph::index_type id
863  )const{
864  if(id<=maxEdgeId()){
865  if(edgeFromId(id)==lemon::INVALID)
866  return Arc(lemon::INVALID);
867  else
868  return Arc(id,id);
869  }
870  else{
871  const index_type edgeId = id - (maxEdgeId() + 1);
872  if( edgeFromId(edgeId)==lemon::INVALID)
873  return Arc(lemon::INVALID);
874  else
875  return Arc(id,edgeId);
876  }
877  }
878 
879 
882  const AdjacencyListGraph::Node & a,
883  const AdjacencyListGraph::Node & b
884  )const{
885  if(a!=b){
886  std::pair<index_type,bool> res = nodes_[id(a)].findEdge(id(b));
887  if(res.second){
888  return Edge(res.first);
889  }
890  }
891  return Edge(lemon::INVALID);
892  }
893 
894 
895 
898  const AdjacencyListGraph::Node & uNode,
899  const AdjacencyListGraph::Node & vNode
900  )const{
901  const Edge e = findEdge(uNode,vNode);
902  if(e==lemon::INVALID){
903  return Arc(lemon::INVALID);
904  }
905  else{
906  if(u(e)==uNode)
907  return direct(e,true) ;
908  else
909  return direct(e,false) ;
910  }
911  }
912 
913 
914  // iterators
915 
916  inline AdjacencyListGraph::vertex_iterator
917  AdjacencyListGraph::get_vertex_iterator()const{
918  return NodeIt(0,nodeNum());
919  }
920 
921 
922  inline AdjacencyListGraph::vertex_iterator
923  AdjacencyListGraph::get_vertex_end_iterator()const{
924  return NodeIt(nodeNum(),nodeNum());
925  }
926 
927 
928 
929  inline AdjacencyListGraph::edge_iterator
930  AdjacencyListGraph::get_edge_iterator()const{
931  return EdgeIt(0,edgeNum());
932  }
933 
934 
935  inline AdjacencyListGraph::edge_iterator
936  AdjacencyListGraph::get_edge_end_iterator()const{
937  return EdgeIt(edgeNum(),edgeNum());
938  }
939 
940 } // end namespace vigra
941 
942 
943 // boost free functions specialized for adjacency list graph
944 namespace boost{
945 
946  ////////////////////////////////////
947  // functions to get size of the graph
948  ////////////////////////////////////
949  inline vigra::AdjacencyListGraph::vertex_size_type
950  num_vertices(const vigra::AdjacencyListGraph & g){
951  return g.nodeNum();
952  }
953  inline vigra::AdjacencyListGraph::edge_size_type
954  num_edges(const vigra::AdjacencyListGraph & g){
955  return g.edgeNum();
956  }
957 
958 
959  ////////////////////////////////////
960  // functions to get degrees of nodes
961  // (degree / indegree / outdegree)
962  ////////////////////////////////////
963  inline vigra::AdjacencyListGraph::degree_size_type
964  degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
965  return g.degree(v);
966  }
967  // ??? check if this is the right impl. for undirected graphs
968  inline vigra::AdjacencyListGraph::degree_size_type
969  in_degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
970  return g.degree(v);
971  }
972  // ??? check if this is the right impl. for undirected graphs
973  inline vigra::AdjacencyListGraph::degree_size_type
974  out_degree(const vigra::AdjacencyListGraph::vertex_descriptor & v , const vigra::AdjacencyListGraph & g){
975  return g.degree(v);
976  }
977 
978 
979  ////////////////////////////////////
980  // functions to u/v source/target
981  ////////////////////////////////////
982  inline vigra::AdjacencyListGraph::vertex_descriptor
983  source(const vigra::AdjacencyListGraph::edge_descriptor & e , const vigra::AdjacencyListGraph & g){
984  return g.u(e);
985  }
986 
987  inline vigra::AdjacencyListGraph::vertex_descriptor
988  target(const vigra::AdjacencyListGraph::edge_descriptor & e , const vigra::AdjacencyListGraph & g){
989  return g.v(e);
990  }
991 
992  ////////////////////////////////////
993  // functions to get iterator pairs
994  ////////////////////////////////////
995  inline std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >
996  vertices(const vigra::AdjacencyListGraph & g ){
997  return std::pair< vigra::AdjacencyListGraph::vertex_iterator, vigra::AdjacencyListGraph::vertex_iterator >(
998  g.get_vertex_iterator(), g.get_vertex_end_iterator());
999  }
1000  inline std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >
1001  edges(const vigra::AdjacencyListGraph & g ){
1002  return std::pair< vigra::AdjacencyListGraph::edge_iterator, vigra::AdjacencyListGraph::edge_iterator >(
1003  g.get_edge_iterator(),g.get_edge_end_iterator());
1004  }
1005 
1006 
1007  inline std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >
1008  in_edges(const vigra::AdjacencyListGraph::vertex_descriptor & v, const vigra::AdjacencyListGraph & g ){
1009  return std::pair< vigra::AdjacencyListGraph::in_edge_iterator, vigra::AdjacencyListGraph::in_edge_iterator >(
1010  vigra::AdjacencyListGraph::in_edge_iterator(g,v),vigra::AdjacencyListGraph::in_edge_iterator(lemon::INVALID)
1011  );
1012  }
1013  inline std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >
1014  out_edges(const vigra::AdjacencyListGraph::vertex_descriptor & v, const vigra::AdjacencyListGraph & g ){
1015  return std::pair< vigra::AdjacencyListGraph::out_edge_iterator, vigra::AdjacencyListGraph::out_edge_iterator >(
1016  vigra::AdjacencyListGraph::out_edge_iterator(g,v),vigra::AdjacencyListGraph::out_edge_iterator(lemon::INVALID)
1017  );
1018  }
1019 
1020 //@}
1021 
1022 } // namespace vigra
1023 
1024 
1025 #endif /*VIGRA_ADJACENCY_LIST_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)