Public Member Functions
Construction
template<typename MPSolution >
	GroupRoadmap (RobotGroup const _g, MPSolution const _solution)
	Construct a group roadmap.

Disabled Functions
Move and copy are disabled because the group cfgs and edges need to know their group roadmap pointer. To implement these, we'll need to update the pointer on every component.
	GroupRoadmap (const GroupRoadmap &)=delete

	GroupRoadmap (GroupRoadmap &&)=delete

GroupRoadmap &	operator= (const GroupRoadmap &)=delete

GroupRoadmap &	operator= (GroupRoadmap &&)=delete

Accessors
RobotGroup *	GetGroup ()
	Get the robot group.

IndividualRoadmap *	GetRoadmap (const size_t _index)

const IndividualRoadmap *	GetRoadmap (const size_t _index) const

size_t	GetNumRobots () const noexcept
	Get the number of robots for the group this roadmap is for.

Input/Output
virtual void	Write (const std::string &_filename, Environment *_env) const override

void	WriteCompositeGraph (const std::string &_filename, Environment *const _env) const

std::string	PrettyPrint () const

Modifiers
virtual VID	AddVertex (const Vertex &_v) noexcept override

virtual void	DeleteVertex (const VID _v) noexcept override

virtual void	AddEdge (const VID _source, const VID _target, const Edge &_w) noexcept override

virtual void	DeleteEdge (EI _iterator) noexcept override

Hooks
virtual void	ClearHooks () noexcept override

Equality
bool	operator== (const RoadmapGraph &_r) const noexcept

bool	operator!= (const RoadmapGraph &_r) const noexcept

Modifiers
virtual VID	AddDuplicateVertex (const Vertex &_v) noexcept

virtual void	AddEdge (const VID _source, const VID _target, const std::pair< Edge, Edge > &_w) noexcept

virtual void	DeleteEdge (const VID _source, const VID _target) noexcept

void	SetRobot (Robot *const _r) noexcept
	Set the robot pointer on all configurations in the map.

void	AppendRoadmap (const RoadmapGraph &_r)

void	SetCCTracker (StatClass *const _stats=nullptr)

Queries
size_t	Size () const noexcept
	Get the number of vertices in the roadmap.

bool	IsVertex (const VID _vid) const noexcept

bool	IsVertex (const Vertex &_v) const noexcept

bool	IsVertex (const Vertex &_v, CVI &_vi) const noexcept

bool	IsEdge (const VID _source, const VID _target) const noexcept

template<typename T >
VID	GetVID (const T &_t) const noexcept

VID	GetVID (const VI &_t) const noexcept

VID	GetVID (const Vertex &_t) const noexcept

const VertexSet &	GetPredecessors (const VID _vid) const noexcept

VID	GetLastVID () const noexcept
	Get the descriptor of the last vertex added to the graph.

size_t	GetTimestamp () const noexcept
	Each time the roadmap is modified, we update the timestamp.

const VertexSet &	GetAllVIDs () const noexcept
	Get the set of all VIDs in the roadmap.

Accessors
Robot *	GetRobot () const noexcept
	Get the robot represented by this roadmap.

CCTrackerType *	GetCCTracker () const noexcept
	Get the connected component tracker.

template<typename T >
VP &	GetVertex (T &_t) noexcept
	Retrieve a reference to a vertex property by descriptor or iterator.

VP &	GetVertex (VI &_t) noexcept

VP &	GetVertex (VID _t) noexcept

template<typename T >
const VP &	GetVertex (T &_t) const noexcept

const VP &	GetVertex (CVI &_t) const noexcept

const VP &	GetVertex (VID _t) const noexcept

std::vector< VID >	GetChildren (const VID _vid) const noexcept

bool	GetEdge (const VID _source, const VID _target, EI &_ei) noexcept

bool	GetEdge (const VID _source, const VID _target, CEI &_ei) const noexcept

EP &	GetEdge (const VID _source, const VID _target) noexcept

EP &	GetEdge (const EID _descriptor) noexcept

Hooks
Hooks are arbitrary functions that are attached to roadmap events. I.e., whenever a vertex is added, a set of functions should be called (hooks). There is a set of hooks for each of the four modifying actions (add/delete a vertex/edge). IMPORTANT: Hooks for 'add' events execute immediately after the event, while hooks for 'delete' events execute immediately prior. This ensures that the iterator and neighbor information are valid in both cases. IMPORTANT: Dependencies between hooks create data races. To avoid problems, any piece of data that is modified by one hook should not be read or modified by any other hook.
bool	IsHook (const HookType, const std::string &_label) const

void	InstallHook (const HookType _type, const std::string &_label, const VertexHook &_h)

void	InstallHook (const HookType _type, const std::string &_label, const EdgeHook &_h)

void	RemoveHook (const HookType _type, const std::string &_label)

void	DisableHooks () noexcept

void	EnableHooks () noexcept
	Enable the hook functions (default).

Public Types
Local Types
typedef RoadmapGraph< Vertex, Edge >	BaseType

typedef BaseType::EID	ED

typedef Vertex::IndividualCfg	IndividualCfg

typedef Edge::IndividualEdge	IndividualEdge

typedef Vertex::VIDSet	VIDSet

typedef RoadmapGraph< IndividualCfg, IndividualEdge >	IndividualRoadmap

typedef BaseType::adj_edge_iterator	adj_edge_iterator

typedef BaseType::edge_descriptor	edge_descriptor

typedef BaseType::vertex_iterator	vertex_iterator

typedef BaseType::vertex_descriptor	vertex_descriptor

typedef STAPLGraph::const_vertex_iterator	CVI

typedef STAPLGraph::vertex_iterator	VI

typedef STAPLGraph::adj_edge_iterator	EI

typedef STAPLGraph::vertex_descriptor	VID

using	STAPLGraph = stapl::sequential::graph< stapl::DIRECTED, stapl::NONMULTIEDGES, Vertex, Edge >

Local Types
enum class	HookType { AddVertex , DeleteVertex , AddEdge , DeleteEdge }

typedef STAPLGraph::edge_descriptor	EID

typedef EID::edge_id_type	EdgeID

typedef std::unordered_set< VID >	VertexSet

typedef STAPLGraph::const_adj_edge_iterator	CEI

typedef STAPLGraph::vertex_property	VP

typedef STAPLGraph::edge_property	EP

typedef Vertex	CfgType

typedef Edge	EdgeType

typedef stapl::sequential::vector_property_map< STAPLGraph, size_t >	ColorMap

typedef std::function< void(VI)>	VertexHook

typedef std::function< void(EI)>	EdgeHook

typedef CCTracker< RoadmapGraph< Vertex, Edge > >	CCTrackerType

Protected Member Functions
Helpers
void	ExecuteAddVertexHooks (const VI _iterator) noexcept

void	ExecuteDeleteVertexHooks (const VI _iterator) noexcept

void	ExecuteAddEdgeHooks (const EI _iterator) noexcept

void	ExecuteDeleteEdgeHooks (const EI _iterator) noexcept

std::string	ToString (const HookType &_t) const noexcept

Protected Attributes
Internal State
RobotGroup *const	m_group
	The robot group.

std::vector< IndividualRoadmap * >	m_roadmaps
	The individual roadmaps.

size_t	m_timestamp
	Tracks the number of changes to the graph.

Internal State
Robot *	m_robot {nullptr}
	The robot this roadmap is for.

bool	m_enableHooks {true}
	Use hook functions?

std::unordered_map< std::string, VertexHook >	m_addVertexHooks
	Hook functions to call when adding a vertex.

std::unordered_map< std::string, VertexHook >	m_deleteVertexHooks
	Hook functions to call when deleting a vertex.

std::unordered_map< std::string, EdgeHook >	m_addEdgeHooks
	Hook functions to call when adding an edge.

std::unordered_map< std::string, EdgeHook >	m_deleteEdgeHooks
	Hook functions to call when deleting an edge.

std::unique_ptr< CCTrackerType >	m_ccTracker
	Tracks weak CCs within the roadmap.

std::unordered_map< VID, VertexSet >	m_predecessors

VertexSet	m_allVIDs

Detailed Description

template<typename Vertex, typename Edge>
class GroupRoadmap< Vertex, Edge >

Represents a roadmap for a robot group.

Rather than duplicating the data for each robot, this object refers to an individual roadmap for each robot. This object however does not own the individual roadmaps - it merely points to them.

Note that VIDs in this object refer to GROUP configuration VIDs.

Member Function Documentation

◆ GetRoadmap()

template<typename Vertex , typename Edge >

GroupRoadmap< Vertex, Edge >::IndividualRoadmap * GroupRoadmap< Vertex, Edge >::GetRoadmap ( const size_t _index )

Get the individual roadmap for a robot in the group.

Parameters

_index The index of the desired robot.

◆ Write()

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::Write	(	const std::string &	_filename,
		Environment *	_env
	)		const

overridevirtual

Write the roadmap using the current standard output rule.

Parameters

_filename	The file to write to.
_env	The environment, to place in the roadmap.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ WriteCompositeGraph()

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::WriteCompositeGraph	(	const std::string &	_filename,
		Environment *const	_env
	)		const

Write the roadmap as a Vizmo-compatible composite C-Space path.

Parameters

_filename	The file to write to.
_env	The environment, to place in the roadmap.

◆ AddVertex()

template<typename Vertex , typename Edge >

GroupRoadmap< Vertex, Edge >::VID GroupRoadmap< Vertex, Edge >::AddVertex ( const Vertex & _v )

overridevirtualnoexcept

Add a new unique vertex to the graph. If it already exists, a warning will be printed to cerr.

Parameters

_v	The vertex to add.

Returns: A new VID of the added vertex, or the VID of the existing vertex.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ DeleteVertex()

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::DeleteVertex ( const VID _v )

overridevirtualnoexcept

Remove a vertex (and attached edges) from the graph if it exists.

Parameters

_v	The vertex descriptor.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ AddEdge() [1/2]

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::AddEdge	(	const VID	_source,
		const VID	_target,
		const Edge &	_w
	)

overridevirtualnoexcept

Add an edge from source to target.

Parameters

_source	The source vertex.
_target	The target vertex.
_w	The edge property.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ DeleteEdge() [1/2]

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::DeleteEdge ( EI _iterator )

overridevirtualnoexcept

Remove an edge from the graph if it exists.

Parameters

_iterator An iterator to the edge.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ ClearHooks()

template<typename Vertex , typename Edge >

void GroupRoadmap< Vertex, Edge >::ClearHooks

overridevirtualnoexcept

Uninstall all hooks from each individual roadmap. Should only be used at the end of a library run to clean the roadmap object.

Reimplemented from RoadmapGraph< Vertex, Edge >.

◆ operator==()

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::operator== ( const RoadmapGraph< Vertex, Edge > & _r ) const

noexceptinherited

Check if the current and given roadmaps are equal.

Parameters

_r	The given roadmap.

Returns: True is equal, false otherwise.

◆ operator!=()

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::operator!= ( const RoadmapGraph< Vertex, Edge > & _r ) const

noexceptinherited

Check if the current and given roadmaps are unequal.

Parameters

_r	The given roadmap.

Returns: True is unequal, false otherwise.

◆ AddDuplicateVertex()

template<typename Vertex , typename Edge >

RoadmapGraph< Vertex, Edge >::VID RoadmapGraph< Vertex, Edge >::AddDuplicateVertex ( const Vertex & _v )

virtualnoexceptinherited

Add a vertex to the graph without checking for uniqueness.

Parameters

_v	The vertex to add.

Returns: A new VID of the added vertex, or the VID of the existing vertex.

◆ AddEdge() [2/2]

template<class Vertex , class Edge >

void RoadmapGraph< Vertex, Edge >::AddEdge	(	const VID	_source,
		const VID	_target,
		const std::pair< Edge, Edge > &	_w
	)

virtualnoexceptinherited

Add edges both ways between source and target vertices.

Parameters

_source	The source vertex.
_target	The target vertex.
_w	The edge properties (source to target first).

◆ DeleteEdge() [2/2]

template<class Vertex , class Edge >

void RoadmapGraph< Vertex, Edge >::DeleteEdge	(	const VID	_source,
		const VID	_target
	)

virtualnoexceptinherited

Remove an edge from the graph if it exists.

Parameters

_source	The source vertex.
_target	The target vertex.

◆ AppendRoadmap()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::AppendRoadmap ( const RoadmapGraph< Vertex, Edge > & _r )

inherited

Copy the nodes and edges from another roadmap and append them to this. Assumes the configurations are compatible with this roadmap's robot.

Parameters

_r	The roadmap to copy from.

◆ SetCCTracker()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::SetCCTracker ( StatClass *const _stats = nullptr )

inherited

Set the CC tracker.

Parameters

_stats Optional stat class for performance profiling.

◆ IsVertex() [1/3]

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::IsVertex ( const VID _vid ) const

noexceptinherited

Check if a vertex is present in the graph.

Parameters

_vid	The vertex descriptor

Returns: True if the vertex descriptor was found in the graph.

◆ IsVertex() [2/3]

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::IsVertex ( const Vertex & _v ) const

noexceptinherited

Check if a vertex is present in the graph.

Parameters

_v	The vertex property to seek.

Returns: True if the vertex property was found in the graph.

◆ IsVertex() [3/3]

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::IsVertex	(	const Vertex &	_v,
		CVI &	_vi
	)		const

noexceptinherited

Check if a vertex is present in the graph and retrieve a const iterator to it if so.

Parameters

_v	The vertex property to seek.
_vi	A vertex iterator, set to the located vertex or end if not found.

Returns: True if the vertex property was found in the graph.

◆ IsEdge()

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::IsEdge	(	const VID	_source,
		const VID	_target
	)		const

noexceptinherited

Check if an edge is present between two vertices.

Parameters

_source	The source vertex.
_target	The target vertex.

Returns: True if an edge exists from source to target.

◆ GetVID()

template<typename Vertex , typename Edge >

template<typename T >

RoadmapGraph< Vertex, Edge >::VID RoadmapGraph< Vertex, Edge >::GetVID ( const T & _t ) const

noexceptinherited

Get the descriptor of a vertex property if it exists in the graph, or INVALID_VID otherwise.

◆ GetPredecessors()

template<typename Vertex , typename Edge >

const RoadmapGraph< Vertex, Edge >::VertexSet & RoadmapGraph< Vertex, Edge >::GetPredecessors ( const VID _vid ) const

noexceptinherited

Get the set of predecessors for a given vertex.

Parameters

_vid	The vertex descriptor.

Returns: The set of VIDs which have _vid as a child node.

◆ GetVertex()

template<typename Vertex , typename Edge >

template<typename T >

const RoadmapGraph< Vertex, Edge >::VP & RoadmapGraph< Vertex, Edge >::GetVertex ( T & _t ) const

noexceptinherited

Retrieve a constant reference to a vertex property by descriptor or iterator.

◆ GetChildren()

template<typename Vertex , typename Edge >

std::vector< typename RoadmapGraph< Vertex, Edge >::VID > RoadmapGraph< Vertex, Edge >::GetChildren ( const VID _vid ) const

noexceptinherited

Get the set of VIDs which are children of a given vertex.

Parameters

_vid	The VID of the given vertex.

Returns: The VIDs of each node u for which and edge (_vid, u) exists.

◆ GetEdge() [1/2]

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::GetEdge	(	const VID	_source,
		const VID	_target,
		EI &	_ei
	)

noexceptinherited

Retrieve an edge from the graph.

Parameters

_source	The source node VID.
_target	The target node VID.
_ei	An edge iterator, set to the specified edge if found or end otherwise.

Returns: True if the edge was located.

◆ GetEdge() [2/2]

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::GetEdge	(	const VID	_source,
		const VID	_target,
		CEI &	_ei
	)		const

noexceptinherited

Retrieve an edge from the graph.

Parameters

_source	The source node VID.
_target	The target node VID.
_ei	An edge iterator, set to the specified edge if found or end otherwise.

Returns: True if the edge was located. This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ IsHook()

template<typename Vertex , typename Edge >

bool RoadmapGraph< Vertex, Edge >::IsHook	(	const HookType	_type,
		const std::string &	_label
	)		const

inherited

Check if a hook with a given type and label is installed.

Parameters

_type	The hook type.
_label	The unique label.

Returns: True if a hook of the specified type and label is present.

◆ InstallHook() [1/2]

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::InstallHook	(	const HookType	_type,
		const std::string &	_label,
		const VertexHook &	_h
	)

inherited

Install a vertex hook. It will be called each time a new vertex is added.

Parameters

_type	The hook type (vertex add/delete).
_label	The unique label.
_h	The hook function.

◆ InstallHook() [2/2]

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::InstallHook	(	const HookType	_type,
		const std::string &	_label,
		const EdgeHook &	_h
	)

inherited

Install an edge hook. It will be called each time a new edge is added.

Parameters

_type	The hook type (edge add/delete).
_label	The unique label.
_h	The hook function.

◆ RemoveHook()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::RemoveHook	(	const HookType	_type,
		const std::string &	_label
	)

inherited

Remove a hook.

Parameters

_type	The hook type.
_label	The unique label.

std::string RoadmapGraph< Vertex, Edge >::ToString ( const HookType & _t ) const

protectednoexceptinherited

Helper for printing hook type names.

Parameters

_t	A hook type.

Returns: The string representation of _t.

Member Data Documentation

◆ m_predecessors

template<typename Vertex , typename Edge >

std::unordered_map<VID, VertexSet> RoadmapGraph< Vertex, Edge >::m_predecessors

protectedinherited

Tracks predecessor information. We use this instead of switching to a STAPL directed_preds graph because (a) directed_preds uses a vector for storage of VIDs, making all changes linear-time operations in the in-degree of each vertex, and (b) the STAPL API is not interchangable as it should be, so switching causes ridiculous compiler errors.

◆ m_allVIDs

template<typename Vertex , typename Edge >

VertexSet RoadmapGraph< Vertex, Edge >::m_allVIDs

protectedinherited

A set of all VIDs in the roadmap. We track this to make nearest-neighbor queries more efficient.

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

GroupRoadmap.h

Public Member Functions

Public Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ GetRoadmap()

◆ Write()

◆ WriteCompositeGraph()

◆ AddVertex()

◆ DeleteVertex()

◆ AddEdge() [1/2]

◆ DeleteEdge() [1/2]

◆ ClearHooks()

◆ operator==()

◆ operator!=()

◆ AddDuplicateVertex()

◆ AddEdge() [2/2]

◆ DeleteEdge() [2/2]

◆ AppendRoadmap()

◆ SetCCTracker()

◆ IsVertex() [1/3]

◆ IsVertex() [2/3]

◆ IsVertex() [3/3]

◆ IsEdge()

◆ GetVID()

◆ GetPredecessors()

◆ GetVertex()

◆ GetChildren()

◆ GetEdge() [1/2]

◆ GetEdge() [2/2]

◆ IsHook()

◆ InstallHook() [1/2]

◆ InstallHook() [2/2]

◆ RemoveHook()

◆ DisableHooks()

◆ ExecuteAddVertexHooks()

◆ ExecuteDeleteVertexHooks()

◆ ExecuteAddEdgeHooks()

◆ ExecuteDeleteEdgeHooks()

◆ ToString()

Member Data Documentation

◆ m_predecessors

◆ m_allVIDs