CCTracker< RoadmapType > Class Template Reference

Public Member Functions
Construction
	CCTracker (RoadmapType *const _r)
	~CCTracker ()
Move and Copy
Note If this object is moved/copied as part of a move/copy on the roadmap, we must also update the roadmap pointer and hooks. Move will retain stat class tracking but copying does not. This is because moving generally pertains to an internal re-organization of the same roadmap, while copying usually indicates moving a roadmap to another solution.
	CCTracker (const CCTracker &)
	CCTracker (CCTracker &&)
CCTracker &	operator= (const CCTracker &)
CCTracker &	operator= (CCTracker &&)
Modifiers
void	SetRoadmap (RoadmapType *const _r) noexcept
	Set the roadmap object.
void	SetStatClass (StatClass *const _stats) const noexcept
	Set the stat class pointer if we wish to do performance profiling.
Query Functions
These functions answer questions about the CCs in the graph.
size_t	GetNumCCs () const noexcept
	Get the number of connected components in the graph.
const VertexSet *	GetCC (const VID _vid) const noexcept
VertexSet	GetRepresentatives () const noexcept
bool	InSameCC (const VID _vid1, const VID _vid2) const noexcept
Iteration
Iterate over the CCs.
ComponentSet::const_iterator	begin () const noexcept
ComponentSet::const_iterator	end () const noexcept
Event Hooks
These functions install and manage hook functions which are called in response to changes in the components. Each has a unique label; duplicates will trigger exceptions.
void	InstallCreatedHook (const std::string &_label, const CreatedHook &_h)
void	InstallDeletedHook (const std::string &_label, const DeletedHook &_h)
void	InstallBrokenHook (const std::string &_label, const BrokenHook &_h)
void	InstallMergedHook (const std::string &_label, const MergedHook &_h)
Optimization
Updates can be disabled to optimize rewiring operations (where we change the graph without changing connectivity).
void	Disable ()
void	Enable ()
Debug
void	Print (std::ostream &_os, const std::string &_indent={}) const
Roadmap Callback Functions
These functions accept graph updates and adjust the internal CCs accordingly. They should be installed as hooks in the roadmap.
void	AddVertex (const vertex_iterator _vi) noexcept
void	DeleteVertex (const vertex_iterator _vi) noexcept
void	AddEdge (const edge_iterator _ei) noexcept
void	DeleteEdge (const edge_iterator _ei) noexcept

Public Types
Motion Planning Types
typedef RoadmapType::VID	VID
typedef RoadmapType::vertex_iterator	vertex_iterator
typedef RoadmapType::adj_edge_iterator	edge_iterator
typedef RoadmapType::VertexSet	VertexSet
Local Types
typedef CCTracker< RoadmapType >	CCTrackerType
typedef std::unordered_set< VertexSet * >	ComponentSet
typedef std::function< void(const CCTrackerType *const, const VertexSet *const)>	CreatedHook
typedef std::function< void(const CCTrackerType *const, const VertexSet *const)>	DeletedHook
typedef std::function< void(const CCTrackerType *const, const VertexSet *const, const VertexSet *const)>	BrokenHook
typedef std::function< void(const CCTrackerType *const, const VertexSet *const, const VertexSet *const)>	MergedHook

Detailed Description

template<typename RoadmapType>
class CCTracker< RoadmapType >

Track the set of CC's in a roadmap.

For directed graphs, we will compute weak connectivity because it describes the typical usage for RRT and nonholonomic robots. One should recall, however, that in such cases shared CC membership does not imply connectivity.

For this to work correctly with directed trees, one must ensure that the graph always remains a tree. For instance, if you rewire the tree by switching a vertex's parent, you must delete the old edge before adding the new one.

Warning

This class assumes that either all edges are bidirectional, or the roadmap is a single tree. It will not work correctly (silent errors) on a non-tree directed graph!

Todo:

Add support for non-tree directed graphs. We need to use predecessor information to do this, which we now have in the roadmap graph.

The stat class tracking adds a lot of complication. Remove it once we're sure the performance is fast enough to forgo tracking.

Member Typedef Documentation

CreatedHook

template<typename RoadmapType >

typedef std::function<void(const CCTrackerType* const, const VertexSet* const)> CCTracker< RoadmapType >::CreatedHook

An event hook for component creation. Called after creation.

Parameters

Pointer	to this.
The	newly created component.

DeletedHook

template<typename RoadmapType >

typedef std::function<void(const CCTrackerType* const, const VertexSet* const)> CCTracker< RoadmapType >::DeletedHook

An event hook for component deletion. Called prior to deletion.

Parameters

Pointer	to this.
The	to-be deleted component.

BrokenHook

template<typename RoadmapType >

typedef std::function<void(const CCTrackerType* const, const VertexSet* const, const VertexSet* const)> CCTracker< RoadmapType >::BrokenHook

An event hook for component breaks. Called after breaking.

Parameters

Pointer	to this.
The	component which is now broken.
The	new component split off from the old (does not trigger a create event).

MergedHook

template<typename RoadmapType >

typedef std::function<void(const CCTrackerType* const, const VertexSet* const, const VertexSet* const)> CCTracker< RoadmapType >::MergedHook

An event hook for component merges. Called prior to merging.

Parameters

Pointer	to this.
The	component which will be merged into.
The	component which will be removed after merging (does not trigger a delete event).

Constructor & Destructor Documentation

CCTracker()

template<typename RoadmapType >

CCTracker< RoadmapType >::CCTracker

(

RoadmapType *const

_r

)

Constructor.

Parameters

_r	The roadmap for which we will track CCs.

Member Function Documentation

GetCC()

template<typename RoadmapType >

const CCTracker< RoadmapType >::VertexSet * CCTracker< RoadmapType >::GetCC ( const VID  _vid ) const

noexcept

Get the CC which contains a representative node.

Parameters

_vid	The representative's descriptor.

Returns

The CC which contains _vid.

GetRepresentatives()

template<typename RoadmapType >

CCTracker< RoadmapType >::VertexSet CCTracker< RoadmapType >::GetRepresentatives

noexcept

Get a set of representative VIDs for each CC.

Returns

The descriptor for one vertex from each CC.

InSameCC()

template<typename RoadmapType >

bool CCTracker< RoadmapType >::InSameCC ( const VID  _vid1, const VID  _vid2  ) const

noexcept

Check if two vertices are in the same CC.

Parameters

_vid1	The descriptor of the first vertex.
_vid2	The descriptor of the second vertex.

Returns

True if _vid1 and _vid2 are in the same CC.

Print()

template<typename RoadmapType >

void CCTracker< RoadmapType >::Print	(	std::ostream &	_os,
		const std::string &	_indent = {}
	)		const

Print the full set of CC information.

Parameters

_os	The ostream to print to.
_indent	A set of indent characters to print before each line.

AddVertex()

template<typename RoadmapType >

void CCTracker< RoadmapType >::AddVertex ( const vertex_iterator  _vi )

noexcept

Update for a vertex added to the graph.

Parameters

_vi	The vertex iterator.

DeleteVertex()

template<typename RoadmapType >

void CCTracker< RoadmapType >::DeleteVertex ( const vertex_iterator  _vi )

noexcept

Update for a vertex deleted from the graph.

Parameters

_vi	The vertex iterator.

AddEdge()

template<typename RoadmapType >

void CCTracker< RoadmapType >::AddEdge ( const edge_iterator  _ei )

noexcept

Update for an edge added to the graph.

Parameters

_ei	The edge iterator.

DeleteEdge()

template<typename RoadmapType >

void CCTracker< RoadmapType >::DeleteEdge ( const edge_iterator  _ei )

noexcept

Update for an edge deleted from the graph.

Parameters

_ei	The edge iterator.

---

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

• CCTracker.h