#include <Expander.h>

Collaboration diagram for DGtal::Expander< TObject >:

Public Types
typedef TObject	Object
typedef Object::Size	Size
typedef Object::Point	Point
typedef Object::Domain	Domain
typedef Object::DigitalSet	DigitalSet
typedef Object::ForegroundAdjacency	ForegroundAdjacency
typedef Domain::Space	Space
typedef DigitalSet::ConstIterator	ConstIterator
typedef DigitalSetDomain < DigitalSet >	ObjectDomain
typedef DigitalSetDomain < DigitalSet >	CoreDomain
typedef DomainAdjacency < ObjectDomain, ForegroundAdjacency >	ObjectAdjacency
typedef CoreDomain::Predicate	InCoreDomainPredicate
typedef NotPointPredicate < InCoreDomainPredicate >	NotInCoreDomainPredicate

Public Member Functions
	~Expander ()
	Expander (const Object &object, const Point &p)
template<typename PointInputIterator >
	Expander (const Object &object, PointInputIterator b, PointInputIterator e)
bool	finished () const
Size	distance () const
bool	nextLayer ()
const DigitalSet &	core () const
const DigitalSet &	layer () const
ConstIterator	begin () const
ConstIterator	end () const
void	selfDisplay (std::ostream &out) const
bool	isValid () const

Protected Member Functions
	Expander ()
void	computeNextLayer (const DigitalSet &src)
void	endLayer ()

Private Member Functions
	Expander (const Expander &other)
Expander &	operator= (const Expander &other)

Private Attributes
const Domain &	myEmbeddingDomain
const Object &	myObject
ObjectDomain	myObjectDomain
ObjectAdjacency	myObjectAdjacency
DigitalSet	myCore
DigitalSet	myLayer
Size	myDistance
bool	myFinished
InCoreDomainPredicate	myInCorePred
NotInCoreDomainPredicate	myNotInCorePred

Detailed Description

template<typename TObject>
class DGtal::Expander< TObject >

Aim: This class is useful to visit an object by adjacencies, layer by layer.

Description of template class 'Expander'

The expander implements a breadth-first algorithm on the graph of adjacencies. It can be used not only to detect connected component but also to identify the layers of the object located at a given distance of a starting set.

The core of the expander is at the beginning the set of points at distance 0. Each layer is at a different distance from the initial core. The expander move layer by layer but the user is free to navigate on each layer.

Template Parameters:

TObject the type of the digital object.

     Point p( ... );
     ObjectType object( ... );
     typedef Expander< ObjectType > ObjectExpander;
     ObjectExpander expander( object, p );
     while ( ! expander.finished() )
       {
         std::cout << "Layer " << expander.distance() << " :";
         // Visit the current layer.
         for ( ObjectExpander::ConstIterator it = expander.begin();
               it != expander.end();
               ++it )
            std::cout << " " << *it;
         std::cout << endl;
         // Move to next layer.
         expander.nextLayer();
       }

See also:: testExpander.cpp; testObject.cpp

Definition at line 96 of file Expander.h.

Member Typedef Documentation

template<typename TObject>

typedef DigitalSet::ConstIterator DGtal::Expander< TObject >::ConstIterator

Definition at line 107 of file Expander.h.

template<typename TObject>

typedef DigitalSetDomain<DigitalSet> DGtal::Expander< TObject >::CoreDomain

Definition at line 109 of file Expander.h.

template<typename TObject>

typedef Object::DigitalSet DGtal::Expander< TObject >::DigitalSet

Definition at line 104 of file Expander.h.

template<typename TObject>

typedef Object::Domain DGtal::Expander< TObject >::Domain

Definition at line 103 of file Expander.h.

template<typename TObject>

typedef Object::ForegroundAdjacency DGtal::Expander< TObject >::ForegroundAdjacency

Definition at line 105 of file Expander.h.

template<typename TObject>

typedef CoreDomain::Predicate DGtal::Expander< TObject >::InCoreDomainPredicate

Definition at line 111 of file Expander.h.

template<typename TObject>

typedef NotPointPredicate< InCoreDomainPredicate > DGtal::Expander< TObject >::NotInCoreDomainPredicate

Definition at line 112 of file Expander.h.

template<typename TObject>

typedef TObject DGtal::Expander< TObject >::Object

Definition at line 100 of file Expander.h.

template<typename TObject>

typedef DomainAdjacency< ObjectDomain, ForegroundAdjacency> DGtal::Expander< TObject >::ObjectAdjacency

Definition at line 110 of file Expander.h.

template<typename TObject>

typedef DigitalSetDomain<DigitalSet> DGtal::Expander< TObject >::ObjectDomain

Definition at line 108 of file Expander.h.

template<typename TObject>

typedef Object::Point DGtal::Expander< TObject >::Point

Definition at line 102 of file Expander.h.

template<typename TObject>

typedef Object::Size DGtal::Expander< TObject >::Size

Definition at line 101 of file Expander.h.

template<typename TObject>

typedef Domain::Space DGtal::Expander< TObject >::Space

Definition at line 106 of file Expander.h.

Constructor & Destructor Documentation

template<typename TObject >

DGtal::Expander< TObject >::~Expander ( )

inline

Destructor.

Definition at line 46 of file Expander.ih.

{

}

template<typename TObject >

DGtal::Expander< TObject >::Expander	(	const Object &	object,
		const Point &	p
	)

inline

Constructor from a point. This point provides the initial core of the expander.

Parameters:

object	the digital object in which the expander expands.
p	any point in the given object.

Definition at line 60 of file Expander.ih.

References DGtal::Expander< TObject >::computeNextLayer(), DGtal::false, DGtal::DigitalSetDomain< TDigitalSet >::isInside(), DGtal::Expander< TObject >::myCore, and DGtal::Expander< TObject >::myObjectDomain.

  : myEmbeddingDomain( object.pointSet().domain() ),
    myObject( object ),
    myObjectDomain( object.pointSet() ),
    myObjectAdjacency( myObjectDomain, object.adjacency() ),
    myCore( myEmbeddingDomain ), 
    myLayer( myEmbeddingDomain ),
    myDistance( 0 ), myFinished( false ),
    myInCorePred( myCore ), 
    myNotInCorePred( myInCorePred )
{
  ASSERT( myObjectDomain.isInside( p ) );
  myCore.insertNew( p );
  computeNextLayer( myCore );
}

template<typename TObject >

template<typename PointInputIterator >

DGtal::Expander< TObject >::Expander	(	const Object &	object,
		PointInputIterator	b,
		PointInputIterator	e
	)

inline

Constructor from iterators. All points visited between the iterators should be distinct two by two. The so specified set of points provides the initial core of the expander.

Template Parameters:

the	type of an InputIterator pointing on a Point.

Parameters:

object	the digital object in which the expander expands.
b	the begin point in a set.
e	the end point in a set.

Definition at line 91 of file Expander.ih.

References DGtal::Expander< TObject >::computeNextLayer(), and DGtal::Expander< TObject >::myCore.

  : myEmbeddingDomain( object.pointSet().domain() ),
    myObject( object ),
    myObjectDomain( object.pointSet() ),
    myObjectAdjacency( myObjectDomain, object.adjacency() ),
    myCore( myEmbeddingDomain ), 
    myLayer( myEmbeddingDomain ),
    myDistance( 0 ), myFinished( false ),
    myInCorePred( myCore ),
    myNotInCorePred( myInCorePred )
{
  myCore.insertNew( b, e );  
  computeNextLayer( myCore );
}

template<typename TObject>

DGtal::Expander< TObject >::Expander ( )

protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

template<typename TObject>

DGtal::Expander< TObject >::Expander ( const Expander< TObject > & other )

private

Copy constructor.

Parameters:

other the object to clone. Forbidden by default.

Member Function Documentation

template<typename TObject >

DGtal::Expander< TObject >::ConstIterator DGtal::Expander< TObject >::begin ( ) const

inline

Returns:: the iterator on the first element of the layer.

Definition at line 257 of file Expander.ih.

References DGtal::Expander< TObject >::begin().

Referenced by DGtal::Expander< TObject >::begin(), and DGtal::Expander< TObject >::computeNextLayer().

{
  return myLayer.begin();
}

template<typename TObject >

void DGtal::Expander< TObject >::computeNextLayer ( const DigitalSet & src )

inlineprotected

Computes the next layer just around [src]. The member 'm_core' must be up to date (i.e, [src] is a subset of 'm_core'). 'm_layer' is cleared in this method. At first call, [src] should be 'm_core', then [src] should be 'm_layer'.

Parameters:

src	the set around which the new layer is computed.

Definition at line 175 of file Expander.ih.

References DGtal::andBF2, and DGtal::Expander< TObject >::begin().

Referenced by DGtal::Expander< TObject >::Expander().

{
  if ( finished() ) return;
  ConstIterator p = src.begin();
  ConstIterator pEnd = src.end();
  typedef std::set<Point> SetContainer;
  typedef std::insert_iterator< SetContainer > Inserter;
  typedef std::vector<Point> VectorContainer;
  typedef std::back_insert_iterator< VectorContainer > VectorInserter;
  SetContainer newLayer;
  Inserter inserter( newLayer, newLayer.begin() );
  
  // const ObjectDomainPredicate & objectPred = myObjectDomain.predicate();
  typedef typename ObjectDomain::Predicate ObjectDomainPredicate; 
  typedef BinaryPointPredicate< ObjectDomainPredicate, 
    NotInCoreDomainPredicate > Predicate;
  Predicate cPred( myObjectDomain.predicate(), 
                           myNotInCorePred,
                           andBF2 );
  // Computes the 1-neighborhood of the core.
  for ( ; p != pEnd; ++p )
    {
      myObjectAdjacency.writeNeighbors
        ( inserter, *p, cPred );
      // std::cerr << *p;
      // for ( unsigned int i = 0; i < v.size(); ++i )
      //   {
      //     std::cerr << " " << v[ i ];
      //     newLayer.insert( v[ i ] );
      //   }
      // std::cerr << std::endl;
      // v.clear();
    }
  // std::cerr << "Core.size=" << myCore.size() 
  //       << " prevLayer.size=" << src.size()
  //       << " nextLayer.size=" << newLayer.size()
  //       << std::endl;
  // Termination test.
  if ( newLayer.empty() )
    myFinished = true;
  else
    {
      myDistance++;
      myLayer.clear();
      myLayer.insertNew( newLayer.begin(), newLayer.end() );
    }
}

template<typename TObject >

const DGtal::Expander< TObject >::DigitalSet & DGtal::Expander< TObject >::core ( ) const

inline

Returns:: a const reference on the (current) core set of points.; the iterator on the first element of the layer.

Definition at line 233 of file Expander.ih.

{
  return myCore;
}

template<typename TObject >

DGtal::Expander< TObject >::Size DGtal::Expander< TObject >::distance ( ) const

inline

Returns:: the current distance to the initial core, or equivalently the index of the current layer.

Definition at line 126 of file Expander.ih.

{
  return myDistance;
}

template<typename TObject >

DGtal::Expander< TObject >::ConstIterator DGtal::Expander< TObject >::end ( ) const

inline

Returns:: the iterator after the last element of the layer.

Definition at line 269 of file Expander.ih.

References DGtal::Expander< TObject >::end().

Referenced by DGtal::Expander< TObject >::end().

{
  return myLayer.end();
}

template<typename TObject >

void DGtal::Expander< TObject >::endLayer ( )

inlineprotected

Push the layer into the current core and clear it. Must be called before computeNewLayer.

Push the layer into the current core. Must be called before computeNextLayer.

Definition at line 158 of file Expander.ih.

{
  myCore.insertNew( myLayer.begin(), myLayer.end() );
}

template<typename TObject >

bool DGtal::Expander< TObject >::finished ( ) const

inline

Returns:: 'true' if all possible elements have been visited.

Definition at line 114 of file Expander.ih.

{
  return myFinished;
}

template<typename TObject >

bool DGtal::Expander< TObject >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns:: 'true' if the object is valid, 'false' otherwise.

Definition at line 300 of file Expander.ih.

{
    return true;
}

template<typename TObject >

const DGtal::Expander< TObject >::DigitalSet & DGtal::Expander< TObject >::layer ( ) const

inline

Returns:: a const reference on the (current) layer set of points.

Definition at line 245 of file Expander.ih.

{
  return myLayer;
}

template<typename TObject >

bool DGtal::Expander< TObject >::nextLayer ( )

inline

Extract next layer. You might used begin() and end() to access all the elements of the new layer.

Returns:: 'true' if there was another layer, or 'false' if it was the last (ie. reverse of finished() ).

Definition at line 143 of file Expander.ih.

{
  endLayer();
  computeNextLayer( myLayer );
  return ! finished();
}

template<typename TObject>

Expander& DGtal::Expander< TObject >::operator= ( const Expander< TObject > & other )

private

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'. Forbidden by default.

template<typename TObject >

void DGtal::Expander< TObject >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 285 of file Expander.ih.

{
  out << "[Expander layer=" << myDistance 
      << " layer.size=" << myLayer.size()
      << " finished=" << myFinished
      << " ]";
}

Field Documentation

template<typename TObject>

DigitalSet DGtal::Expander< TObject >::myCore

private

Set representing the core of the expansion: the expansion should not enter the core.

Definition at line 234 of file Expander.h.

Referenced by DGtal::Expander< TObject >::Expander().

template<typename TObject>

Size DGtal::Expander< TObject >::myDistance

private

Current distance to origin.

Definition at line 244 of file Expander.h.

template<typename TObject>

const Domain& DGtal::Expander< TObject >::myEmbeddingDomain

private

The domain in which the object is lying.

Definition at line 213 of file Expander.h.

template<typename TObject>

bool DGtal::Expander< TObject >::myFinished

private

Boolean stating whether the expansion is over or not.

Definition at line 249 of file Expander.h.

template<typename TObject>

InCoreDomainPredicate DGtal::Expander< TObject >::myInCorePred

private

Predicate in-core.

Definition at line 254 of file Expander.h.

template<typename TObject>

DigitalSet DGtal::Expander< TObject >::myLayer

private

Set representing the current layer.

Definition at line 239 of file Expander.h.

template<typename TObject>

NotInCoreDomainPredicate DGtal::Expander< TObject >::myNotInCorePred

private

Predicate ensuring the not-in-core expansion.

Definition at line 259 of file Expander.h.

template<typename TObject>

const Object& DGtal::Expander< TObject >::myObject

private

The object where the expansion takes place.

Definition at line 218 of file Expander.h.

template<typename TObject>

ObjectAdjacency DGtal::Expander< TObject >::myObjectAdjacency

private

The adjacency that is used in myObjectDomain.

Definition at line 228 of file Expander.h.

template<typename TObject>

ObjectDomain DGtal::Expander< TObject >::myObjectDomain

private

The domain corresponding to the object.

Definition at line 223 of file Expander.h.

Referenced by DGtal::Expander< TObject >::Expander().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename TObject> class DGtal::Expander< TObject >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TObject>
class DGtal::Expander< TObject >