Public Member Functions
Construction
	RoadmapGraph (Robot *const _r)

Move and Copy
Move and copy operations do not copy hook functions.
	RoadmapGraph (const RoadmapGraph &_r)

	RoadmapGraph (RoadmapGraph &&_r)

RoadmapGraph &	operator= (const RoadmapGraph &_r)

RoadmapGraph &	operator= (RoadmapGraph &&_r)

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

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

Modifiers
virtual VID	AddVertex (const Vertex &_v) noexcept

virtual VID	AddDuplicateVertex (const Vertex &_v) noexcept

virtual void	DeleteVertex (const VID _v) noexcept

virtual void	AddEdge (const VID _source, const VID _target, const Edge &_w) 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

virtual void	DeleteEdge (EI _iterator) 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).

virtual void	ClearHooks () noexcept

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

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

typedef STAPLGraph::vertex_descriptor	VID

typedef STAPLGraph::edge_descriptor	EID

typedef EID::edge_id_type	EdgeID

typedef std::unordered_set< VID >	VertexSet

typedef STAPLGraph::vertex_iterator	VI

typedef STAPLGraph::adj_edge_iterator	EI

typedef STAPLGraph::const_vertex_iterator	CVI

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
Robot *	m_robot {nullptr}
	The robot this roadmap is for.

size_t	m_timestamp {0}
	Tracks the number of changes to the graph.

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

I/O
virtual void	Write (const std::string &_filename, Environment *_env) const

template<typename RG >
void	Read (RG *_g, const std::string &_filename)

template<typename RG >
void	ReadMessage (RG *_g, const std::string &_msg)

Detailed Description

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

Graph data structure of robot configurations (vertices) connected by local plans (edges).

We often want to do some extra stuff whenever the roadmap is modified. To support that, this object can install hook functions for each of the four modifying events (add/delete a vertex/edge). Note that there is no particular ordering to the hook execution - this is deliberate because we will create a maintenance nightmare if hooks are allowed to depend on each other. As such, no two hooks should modify the same data. Terrible and unpredictable things will happen if you do this!

Template Parameters

Vertex	The vertex or configuration type.
Edge	The edge or local plan type.

Constructor & Destructor Documentation

◆ RoadmapGraph() [1/3]

template<typename Vertex , typename Edge >

RoadmapGraph< Vertex, Edge >::RoadmapGraph ( Robot *const _r )

Construct a roadmap for a given robot.

Parameters

_r	The given robot.

◆ RoadmapGraph() [2/3]

template<typename Vertex , typename Edge >

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

Construct a copy of the given roadmap.

Parameters

_r	The given roadmap.

◆ RoadmapGraph() [3/3]

template<typename Vertex , typename Edge >

RoadmapGraph< Vertex, Edge >::RoadmapGraph ( RoadmapGraph< Vertex, Edge > && _r )

Construct a copy of the given roadmap.

Parameters

_r	The given roadmap.

Member Function Documentation

◆ operator=() [1/2]

template<typename Vertex , typename Edge >

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

Copy the given roadmap into the current.

Parameters

_r	The given roadmap.

◆ operator=() [2/2]

template<typename Vertex , typename Edge >

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

Copy the given roadmap into the current.

Parameters

_r	The given roadmap.

◆ operator==()

template<typename Vertex , typename Edge >

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

noexcept

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

noexcept

Check if the current and given roadmaps are unequal.

Parameters

_r	The given roadmap.

Returns: True is unequal, false otherwise.

◆ AddVertex()

template<typename Vertex , typename Edge >

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

virtualnoexcept

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 in GroupRoadmap< Vertex, Edge >.

◆ AddDuplicateVertex()

template<typename Vertex , typename Edge >

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

virtualnoexcept

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.

◆ DeleteVertex()

template<typename Vertex , typename Edge >

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

virtualnoexcept

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

Parameters

_v	The vertex descriptor.

Reimplemented in GroupRoadmap< Vertex, Edge >.

◆ AddEdge() [1/2]

template<class Vertex , class Edge >

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

virtualnoexcept

Add an edge from source to target.

Parameters

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

Reimplemented in GroupRoadmap< Vertex, Edge >.

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

virtualnoexcept

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() [1/2]

template<class Vertex , class Edge >

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

virtualnoexcept

Remove an edge from the graph if it exists.

Parameters

_source	The source vertex.
_target	The target vertex.

◆ DeleteEdge() [2/2]

template<class Vertex , class Edge >

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

virtualnoexcept

Remove an edge from the graph if it exists.

Parameters

_iterator An iterator to the edge.

Reimplemented in GroupRoadmap< Vertex, Edge >.

◆ AppendRoadmap()

template<typename Vertex , typename Edge >

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

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 )

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

noexcept

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

noexcept

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

noexcept

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

noexcept

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

noexcept

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

noexcept

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

noexcept

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

noexcept

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
	)

noexcept

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

noexcept

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

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
	)

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
	)

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
	)

Remove a hook.

Parameters

_type	The hook type.
_label	The unique label.

◆ DisableHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::DisableHooks

noexcept

Disable the hooks. This is useful for making temporary additions and deletions to the roadmap without triggering the hook functions. Be sure to re-enable them after, and to only use this in isolated code segments where you are sure that we won't miss any real nodes.

◆ ClearHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::ClearHooks

virtualnoexcept

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

Reimplemented in GroupRoadmap< Vertex, Edge >.

◆ Write()

template<typename Vertex , typename Edge >

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

virtual

Write the current roadmap out to a roadmap (.map) file.

Parameters

_filename	The name of the map file to write to.
_env	The environment for which this map was constructed.

Reimplemented in GroupRoadmap< Vertex, Edge >.

◆ ExecuteAddVertexHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::ExecuteAddVertexHooks ( const VI _iterator )

protectednoexcept

Execute the AddVertex hooks.

Parameters

_iterator An iterator to the newly added vertex.

◆ ExecuteDeleteVertexHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::ExecuteDeleteVertexHooks ( const VI _iterator )

protectednoexcept

Execute the DeleteVertex hooks.

Parameters

_iterator An iterator to the to-be-deleted vertex.

◆ ExecuteAddEdgeHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::ExecuteAddEdgeHooks ( const EI _iterator )

protectednoexcept

Execute the AddEdge hooks.

Parameters

_iterator An iterator to the newly added edge.

◆ ExecuteDeleteEdgeHooks()

template<typename Vertex , typename Edge >

void RoadmapGraph< Vertex, Edge >::ExecuteDeleteEdgeHooks ( const EI _iterator )

protectednoexcept

Execute the DeleteEdge hooks.

Parameters

_iterator An iterator to the to-be-deleted edge.

◆ ToString()

template<typename Vertex , typename Edge >

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

protectednoexcept

Helper for printing hook type names.

Parameters

_t	A hook type.

Returns: The string representation of _t.

Friends And Related Function Documentation

◆ Read

template<typename Vertex , typename Edge >

template<typename RG >

void Read	(	RG *	_g,
		const std::string &	_filename
	)

friend

Read in a roadmap (.map) file.

Parameters

_filename The name of the map file to read.

Note: Temporarily moved to non-member function.

Member Data Documentation

◆ m_predecessors

template<typename Vertex , typename Edge >

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

protected

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

protected

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:

RoadmapGraph.h

Public Member Functions

Public Types

Protected Member Functions

Protected Attributes

I/O

Detailed Description

Constructor & Destructor Documentation

◆ RoadmapGraph() [1/3]

◆ RoadmapGraph() [2/3]

◆ RoadmapGraph() [3/3]

Member Function Documentation

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator!=()

◆ AddVertex()

◆ AddDuplicateVertex()

◆ DeleteVertex()

◆ AddEdge() [1/2]

◆ AddEdge() [2/2]

◆ DeleteEdge() [1/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()

◆ ClearHooks()

◆ Write()

◆ ExecuteAddVertexHooks()

◆ ExecuteDeleteVertexHooks()

◆ ExecuteAddEdgeHooks()

◆ ExecuteDeleteEdgeHooks()

◆ ToString()

Friends And Related Function Documentation

◆ Read

Member Data Documentation

◆ m_predecessors

◆ m_allVIDs