#include <CCTracker.h>

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

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. More...

void	SetStatClass (StatClass *const _stats) const noexcept
	Set the stat class pointer if we wish to do performance profiling. More...

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. More...

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

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

◆ 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).

◆ CCTrackerType

template<typename RoadmapType >

typedef CCTracker<RoadmapType> CCTracker< RoadmapType >::CCTrackerType

◆ ComponentSet

template<typename RoadmapType >

typedef std::unordered_set<VertexSet*> CCTracker< RoadmapType >::ComponentSet

◆ 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.

◆ edge_iterator

template<typename RoadmapType >

typedef RoadmapType::adj_edge_iterator CCTracker< RoadmapType >::edge_iterator

◆ 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).

◆ vertex_iterator

template<typename RoadmapType >

typedef RoadmapType::vertex_iterator CCTracker< RoadmapType >::vertex_iterator

◆ VertexSet

template<typename RoadmapType >

typedef RoadmapType::VertexSet CCTracker< RoadmapType >::VertexSet

◆ VID

template<typename RoadmapType >

typedef RoadmapType::VID CCTracker< RoadmapType >::VID

Constructor & Destructor Documentation

◆ CCTracker() [1/3]

template<typename RoadmapType >

CCTracker< RoadmapType >::CCTracker ( RoadmapType *const _r )

Constructor.

Parameters

_r	The roadmap for which we will track CCs.

◆ ~CCTracker()

template<typename RoadmapType >

CCTracker< RoadmapType >::~CCTracker

◆ CCTracker() [2/3]

template<typename RoadmapType >

CCTracker< RoadmapType >::CCTracker ( const CCTracker< RoadmapType > & _other )

◆ CCTracker() [3/3]

template<typename RoadmapType >

CCTracker< RoadmapType >::CCTracker ( CCTracker< RoadmapType > && _other )

Member Function Documentation

◆ 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.

Note: This is linear in the size of the smaller CC if a merge occurs or constant amortized otherwise.

◆ 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.

◆ begin()

template<typename RoadmapType >

CCTracker< RoadmapType >::ComponentSet::const_iterator CCTracker< RoadmapType >::begin

inlinenoexcept

◆ 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.

◆ 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.

◆ Disable()

template<typename RoadmapType >

void CCTracker< RoadmapType >::Disable

◆ Enable()

template<typename RoadmapType >

void CCTracker< RoadmapType >::Enable

◆ end()

template<typename RoadmapType >

CCTracker< RoadmapType >::ComponentSet::const_iterator CCTracker< RoadmapType >::end

inlinenoexcept

◆ 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.

◆ GetNumCCs()

template<typename RoadmapType >

size_t CCTracker< RoadmapType >::GetNumCCs

inlinenoexcept

Get the number of connected components in the graph.

◆ 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

inlinenoexcept

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.

◆ InstallBrokenHook()

template<typename RoadmapType >

void CCTracker< RoadmapType >::InstallBrokenHook	(	const std::string &	_label,
		const BrokenHook &	_h
	)

◆ InstallCreatedHook()

template<typename RoadmapType >

void CCTracker< RoadmapType >::InstallCreatedHook	(	const std::string &	_label,
		const CreatedHook &	_h
	)

◆ InstallDeletedHook()

template<typename RoadmapType >

void CCTracker< RoadmapType >::InstallDeletedHook	(	const std::string &	_label,
		const DeletedHook &	_h
	)

◆ InstallMergedHook()

template<typename RoadmapType >

void CCTracker< RoadmapType >::InstallMergedHook	(	const std::string &	_label,
		const MergedHook &	_h
	)

◆ operator=() [1/2]

template<typename RoadmapType >

CCTracker< RoadmapType > & CCTracker< RoadmapType >::operator= ( CCTracker< RoadmapType > && _other )

◆ operator=() [2/2]

template<typename RoadmapType >

CCTracker< RoadmapType > & CCTracker< RoadmapType >::operator= ( const CCTracker< RoadmapType > & _other )

◆ 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.

◆ SetRoadmap()

template<typename RoadmapType >

void CCTracker< RoadmapType >::SetRoadmap ( RoadmapType *const _r )

inlinenoexcept

Set the roadmap object.

◆ SetStatClass()

template<typename RoadmapType >

void CCTracker< RoadmapType >::SetStatClass ( StatClass *const _stats ) const

inlinenoexcept

Set the stat class pointer if we wish to do performance profiling.

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

/opt/actions-runner/_work/open-ppl/open-ppl/src/Utilities/CCTracker.h

Public Types

Public Member Functions

Detailed Description

template<typename RoadmapType> class CCTracker< RoadmapType >

Member Typedef Documentation

◆ BrokenHook

◆ CCTrackerType

◆ ComponentSet

◆ CreatedHook

◆ DeletedHook

◆ edge_iterator

◆ MergedHook

◆ vertex_iterator

◆ VertexSet

◆ VID

Constructor & Destructor Documentation

◆ CCTracker() [1/3]

◆ ~CCTracker()

◆ CCTracker() [2/3]

◆ CCTracker() [3/3]

Member Function Documentation

◆ AddEdge()

◆ AddVertex()

◆ begin()

◆ DeleteEdge()

◆ DeleteVertex()

◆ Disable()

◆ Enable()

◆ end()

◆ GetCC()

◆ GetNumCCs()

◆ GetRepresentatives()

◆ InSameCC()

◆ InstallBrokenHook()

◆ InstallCreatedHook()

◆ InstallDeletedHook()

◆ InstallMergedHook()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ Print()

◆ SetRoadmap()

◆ SetStatClass()

template<typename RoadmapType>
class CCTracker< RoadmapType >