DGtal 1.3.0
Loading...
Searching...
No Matches
ObjectBoostGraphInterface.h
1
17#pragma once
18
31#if defined(ObjectBoostGraphInterface_RECURSES)
32#error Recursive header files inclusion detected in ObjectBoostGraphInterface.h
33#else // defined(ObjectBoostGraphInterface_RECURSES)
35#define ObjectBoostGraphInterface_RECURSES
36
37#if !defined ObjectBoostGraphInterface_h
39#define ObjectBoostGraphInterface_h
40
42// Inclusions
43#include <iostream>
44#include <vector>
45#include <boost/iterator/iterator_facade.hpp>
46#include <boost/graph/graph_traits.hpp>
47#include <boost/graph/properties.hpp>
48#include <boost/property_map/property_map.hpp>
49#include "DGtal/base/Common.h"
50#include "DGtal/base/CountedPtr.h"
51#include "DGtal/topology/Object.h"
53
54
55// The interface to the Boost Graph should be defined in namespace boost.
56namespace boost
57{
58
85 template < class TDigitalTopology, class TDigitalSet >
86 struct graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
87 {
91 typedef undirected_tag directed_category;
95 typedef disallow_parallel_edge_tag edge_parallel_category;
96
103
105 typedef typename Adapted::Vertex Vertex;
109 typedef typename Adapted::Edge Edge;
115
117 typedef std::vector< vertex_descriptor > AdjacentVertexContainer;
120
121
125 static
126 inline
128 {
129 return vertex_descriptor();
130 }
131
165 class adjacency_iterator
166 : public iterator_facade< adjacency_iterator,
167 Vertex,
168 bidirectional_traversal_tag,
169 const Vertex & >
170 {
171 public:
173 inline
175 : myIterator(), myVertices( 0 ) {}
176
186 inline
187 adjacency_iterator( typename AdjacentVertexContainer::const_iterator it,
189 : myIterator( it ), myVertices( vertices ) {}
190
191 private:
196 inline
197 const Vertex & dereference() const
198 {
199 ASSERT( myIterator != myVertices->end() );
200 return *myIterator;
201 }
202
211 inline
212 bool equal(const adjacency_iterator& other) const
213 {
214 bool thisAtEnd = ( myIterator == myVertices->end() );
215 bool otherAtEnd = ( other.myIterator == other.myVertices->end() );
216 if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
217 else return *myIterator == *other.myIterator;
218 }
219
224 inline
225 void increment() { ++myIterator; }
226
231 inline
232 void decrement() { --myIterator; }
233
234 // ///////////// Data Members ////////////////
235
237 typename AdjacentVertexContainer::const_iterator myIterator;
244
246 friend class iterator_core_access;
247 }; // end class adjacency_iterator
248
282 class out_edge_iterator
283 : public iterator_facade< out_edge_iterator,
284 Edge,
285 bidirectional_traversal_tag,
286 const Edge & >
287 {
288 public:
290 inline
292 : myIterator(), myOutEdges( 0 ) {}
302 inline
303 out_edge_iterator( typename OutEdgeContainer::const_iterator it,
304 const DGtal::CountedPtr< OutEdgeContainer > & out_edges )
305 : myIterator( it ), myOutEdges( out_edges ) {}
306 private:
311 inline
312 const Edge & dereference() const
313 {
314 ASSERT( myIterator != myOutEdges->end() );
315 return *myIterator;
316 }
317
326 inline
327 bool equal(const out_edge_iterator & other) const
328 {
329 bool thisAtEnd = ( myIterator == myOutEdges->end() );
330 bool otherAtEnd = ( other.myIterator == other.myOutEdges->end() );
331 if ( thisAtEnd || otherAtEnd ) return thisAtEnd && otherAtEnd;
332 else return *myIterator == *other.myIterator;
333 }
334
339 inline
340 void increment() { ++myIterator; }
345 inline
346 void decrement() { --myIterator; }
347
349 typename OutEdgeContainer::const_iterator myIterator;
355
357 friend class iterator_core_access;
358 }; // end class out_edge_iterator
359
364 using in_edge_iterator = out_edge_iterator ;
365
398 class edge_iterator
399 : public iterator_facade< edge_iterator,
400 Edge,
401 forward_traversal_tag,
402 const Edge & >
403 {
404 public:
418 edge_iterator( const Adapted & graph,
419 const vertex_iterator & itB, const vertex_iterator & itE );
420
421 private:
426 const Edge & dereference() const;
435 bool equal(const edge_iterator & other) const;
440 void increment();
441
442 // /////////// Data Members //////////////
446 std::pair< vertex_iterator, vertex_iterator > myVertexRange;
448 std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange;
449
451 friend class iterator_core_access;
452 }; // end class out_edge_iterator
453
454 }; // end struct graph_traits< >
455
456
458 // Functions for the boost graph interface to Object<TDigitalTopology, TDigitalSet>.
459
465 template < class TDigitalTopology, class TDigitalSet >
466 inline
467 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
468 source( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
470 {
471 return obj.tail( edge );
472 }
478 template < class TDigitalTopology, class TDigitalSet >
479 inline
480 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor
481 target( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_descriptor edge,
483 {
484 return obj.head( edge );
485 }
486
492 template < class TDigitalTopology, class TDigitalSet >
493 std::pair<
494 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator,
495 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_iterator
496 >
498
503 template < class TDigitalTopology, class TDigitalSet >
504 inline
505 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertices_size_type
507 {
508 return obj.size();
509 }
510
518 template < class TDigitalTopology, class TDigitalSet >
519 inline
520 std::pair<
521 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator,
522 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::adjacency_iterator
523 >
524 adjacent_vertices( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
526 {
527 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
528 ::adjacency_iterator Iterator;
529 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
530 ::AdjacentVertexContainer Container;
531 DGtal::CountedPtr<Container> ptrAdjVertices( new Container );
532 std::back_insert_iterator< Container > outIt = std::back_inserter( *ptrAdjVertices );
533 obj.writeNeighbors( outIt, u );
534 return std::make_pair( Iterator( ptrAdjVertices->begin(), ptrAdjVertices ),
535 Iterator( ptrAdjVertices->end(), ptrAdjVertices ) );
536 }
537
538
547 template < class TDigitalTopology, class TDigitalSet >
548 inline
549 std::pair<
550 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator,
551 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::out_edge_iterator
552 >
553 out_edges( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
555 {
556 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
557 ::out_edge_iterator Iterator;
558 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >
559 ::OutEdgeContainer Container;
560 DGtal::CountedPtr<Container> ptrEdges( new Container( obj.outEdges( u ) ) );
561 return std::make_pair( Iterator( ptrEdges->begin(), ptrEdges ),
562 Iterator( ptrEdges->end(), ptrEdges ) );
563 }
564
565
572 template < class TDigitalTopology, class TDigitalSet >
573 inline
574 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::degree_size_type
575 out_degree( typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::vertex_descriptor u,
577 {
578 return obj.degree( u );
579 }
580
587 template < class TDigitalTopology, class TDigitalSet >
588 inline
589 std::pair<
590 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator,
591 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
592 >
594 {
595 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
596 edge_iterator;
597 return std::make_pair( edge_iterator( obj, obj.begin(), obj.end() ),
598 edge_iterator( obj, obj.end(), obj.end() ) );
599 }
600
605 template < class TDigitalTopology, class TDigitalSet >
606 inline
607 typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
609 {
610 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edge_iterator
611 edge_iterator;
612 typedef typename graph_traits< DGtal::Object< TDigitalTopology, TDigitalSet > >::edges_size_type
613 edges_size_type;
614 edges_size_type nbEdges = 0;
615 for ( std::pair< edge_iterator, edge_iterator > ve = boost::edges( obj );
616 ve.first != ve.second; ++ve.first )
617 ++nbEdges;
618 return nbEdges;
619 }
620
621} // namespace Boost
622
623
625// Includes inline functions.
626#include "DGtal/graph/ObjectBoostGraphInterface.ih"
627
628// //
630
631#endif // !defined ObjectBoostGraphInterface_h
632
633#undef ObjectBoostGraphInterface_RECURSES
634#endif // else defined(ObjectBoostGraphInterface_RECURSES)
Aim: An object (or digital object) represents a set in some digital space associated with a digital t...
Definition: Object.h:120
DigitalSet::Size Size
Definition: Object.h:140
std::vector< Edge > EdgeRange
Definition: Object.h:222
DigitalSet::Point Vertex
Definition: Object.h:157
DigitalSet::ConstIterator ConstIterator
Definition: Object.h:162
AdjacentVertexContainer::const_iterator myIterator
The iterator pointing in the container of adjacent vertices.
adjacency_iterator(typename AdjacentVertexContainer::const_iterator it, const DGtal::CountedPtr< AdjacentVertexContainer > &vertices)
std::pair< out_edge_iterator, out_edge_iterator > myOutEdgeRange
Local pair of out_edge_iterator. Created within this iterator.
std::pair< vertex_iterator, vertex_iterator > myVertexRange
Vertex Range to iterator from. Set at constructor.
edge_iterator(const Adapted &graph, const vertex_iterator &itB, const vertex_iterator &itE)
out_edge_iterator(typename OutEdgeContainer::const_iterator it, const DGtal::CountedPtr< OutEdgeContainer > &out_edges)
OutEdgeContainer::const_iterator myIterator
The iterator pointing in the container of out edges.
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition: Boost.dox:28
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type num_edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator > adjacent_vertices(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type num_vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::degree_size_type out_degree(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator > out_edges(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator > vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Go to http://www.sgi.com/tech/stl/Container.html.
Definition: Boost.dox:104
DGtal::Object< TDigitalTopology, TDigitalSet > Adapted
the adapted DGtal graph class.
Adapted::Size degree_size_type
the type for counting out or in edges
disallow_parallel_edge_tag edge_parallel_category
the graph does not allow parallel edges.
Object_graph_traversal_category traversal_category
the graph satisfies AdjacencyListGraph and VertexListGraph concepts.
Adapted::EdgeRange OutEdgeContainer
This is the intermediate data structure that is used for storing out edges.
std::vector< vertex_descriptor > AdjacentVertexContainer
This is the intermediate data structure that is used for visiting adjacent vertices.