Detailed Description

model the mapping of free-space intervals to nodes in a frechet::reach::Graph.

Maps reachability intervals (BoundarySegment*) to Graph vertices (indexes for rows/columns of adjacency matrix).

To create comparable Graphs, the boundary intervals must be unified. We use a prototype Structure that conains the "most refined" intervals.

TODO TODO TODO TODO

Test Cases (Google Test?)

Alternatively, we could calculate the prototype intervals by intersecting all Free-Space intervals (saves us the trouble of building a reach::Structure). But that would mainly duplicate code from Structure, so we leave it at that (yet)...

For each horizontal or vertical interval in free-space, there will be a node in the reachability graph.

The model is copmuted by overlaying all free-space intervals.

Accomodates double-free-space diagrams, too. We do not model the duplicated part of the free-space diagram, but the reachability graph does.

Author: Peter Schäfer

Definition at line 109 of file graph_boost.h.

#include <graph_boost.h>

Public Types
typedef boost::shared_ptr< GraphModel >	ptr
	smart pointer to a GraphModel object More...

Public Member Functions
	GraphModel ()

	GraphModel (Structure &prototype)

void	init (Structure &prototype)

int	count () const

void	refine (Structure &str, int i0) const

void	indexify (Structure &str, int i0) const

	GraphModel ()
	empty constructor More...

void	init (const FreeSpace::ptr fs)
	initialize from free-space intervals More...

bool	empty () const

int	dim1 (Orientation ori) const

int	dim2 (Orientation ori) const

int	lowerShiftedHorizontally (int hindex) const
	map a node index to its counterpart in the duplicated part of a double-free-space More...

IndexRange	shiftedHorizontally (const IndexRange &r) const
	map a node range to its counterpart in the duplicated part of a double-free-space More...

int	count2 (Orientation ori) const

int	count2 () const

IndexRange	map (Orientation ori, const Interval &, bool upperBoundInclusive) const
	map a free-space interval to a range of graph nodes More...

IndexRange	map (Pointer b) const
	map a reachability structure interval to a range of graph nodes More...

int	map_lower (Pointer p) const
	map the lower bound of a reachability structure interval More...

int	map_upper (Pointer p) const
	map the upper bound of a reachability structure interval More...

int	map_lower (Orientation ori, double x) const
	map an interval lower bound More...

int	map_upper (Orientation ori, double x, bool inclusive) const
	map an interval upper bound More...

IndexRange	mapClosest (Orientation ori, const Interval &ival) const
	map a free-space interval to the closest graph nodes More...

const std::vector< Interval > &	reverseMap (Orientation ori) const
	create a reverse map, mapping graph nodes to free-space interval More...

IndexRange	mergedHMask (const IndexRange &m1, const IndexRange &m2) const
	merged two node ranges representing the horizontal masks of reachability graph (see frechet::reach::Graph memory layout). More...

Private Member Functions
BoundaryList &	list (Orientation ori)

BoundaryList &	horiz ()

BoundaryList &	vert ()

const BoundaryList &	horiz () const

const BoundaryList &	vert () const

void	indexify (Structure &str, Orientation ori, const Pointer model) const

void	refine (Structure &str, Orientation ori, const Pointer model) const

void	initVertical (const FreeSpace::ptr fs)
	set up the mappings for vertical intervals More...

void	initHorizontal (const FreeSpace::ptr fs)
	set up the mappings for horizontal intervals More...

Private Attributes
BoundaryList	_model [2]

std::vector< Pointer >	_column_entry

int	_count

GraphModelAxis	axis [2]
	horizontal and vertical mapping More...

std::vector< Interval >	reversed [2]
	reverse mapping from nodes to intervals (horizontal and vertical) More...

Member Typedef Documentation

◆ ptr

typedef boost::shared_ptr<GraphModel> frechet::reach::GraphModel::ptr

smart pointer to a GraphModel object

Definition at line 307 of file graph_model.h.

Constructor & Destructor Documentation

◆ GraphModel() [1/3]

frechet::reach::GraphModel::GraphModel ( )

◆ GraphModel() [2/3]

frechet::reach::GraphModel::GraphModel ( Structure & prototype )

◆ GraphModel() [3/3]

frechet::reach::GraphModel::GraphModel ( )

inline

empty constructor

Definition at line 312 of file graph_model.h.

Member Function Documentation

◆ count()

int frechet::reach::GraphModel::count ( ) const

inline

Definition at line 124 of file graph_boost.h.

◆ count2() [1/2]

int GraphModel::count2 ( Orientation ori ) const

Parameters

ori	horizontal or vertical

Returns: total number of graph nodes in a dimension

Definition at line 237 of file graph_model.cpp.

◆ count2() [2/2]

int GraphModel::count2 ( ) const

Returns: total number of graph nodes, horizontal and vertical

Definition at line 247 of file graph_model.cpp.

◆ dim1()

int GraphModel::dim1 ( Orientation ori ) const

Parameters

ori	horizontal or vertical

Returns: width or height of single free-space diagram

Definition at line 217 of file graph_model.cpp.

◆ dim2()

int GraphModel::dim2 ( Orientation ori ) const

Parameters

ori	horizontal or vertical

Returns: width or height of double free-space diagram

Definition at line 227 of file graph_model.cpp.

◆ empty()

bool GraphModel::empty ( ) const

Returns: true, if there is no mapping

Definition at line 373 of file graph_model.cpp.

◆ horiz() [1/2]

BoundaryList& frechet::reach::GraphModel::horiz ( )

inlineprivate

Definition at line 136 of file graph_boost.h.

◆ horiz() [2/2]

const BoundaryList& frechet::reach::GraphModel::horiz ( ) const

inlineprivate

Definition at line 139 of file graph_boost.h.

◆ indexify() [1/2]

void frechet::reach::GraphModel::indexify	(	Structure &	str,
		int	i0
	)		const

◆ indexify() [2/2]

void frechet::reach::GraphModel::indexify	(	Structure &	str,
		Orientation	ori,
		const Pointer	model
	)		const

private

◆ init() [1/2]

void frechet::reach::GraphModel::init ( Structure & prototype )

◆ init() [2/2]

void GraphModel::init ( const FreeSpace::ptr fs )

initialize from free-space intervals

Parameters

fs	a free-space diagram

Definition at line 353 of file graph_model.cpp.

◆ initHorizontal()

void GraphModel::initHorizontal ( const FreeSpace::ptr fs )

private

set up the mappings for horizontal intervals

Parameters

fs	a free-space

Definition at line 421 of file graph_model.cpp.

◆ initVertical()

void GraphModel::initVertical ( const FreeSpace::ptr fs )

private

set up the mappings for vertical intervals

Parameters

fs	a free-space

Definition at line 377 of file graph_model.cpp.

◆ list()

BoundaryList& frechet::reach::GraphModel::list ( Orientation ori )

inlineprivate

Definition at line 134 of file graph_boost.h.

◆ lowerShiftedHorizontally()

int frechet::reach::GraphModel::lowerShiftedHorizontally ( int hindex ) const

inline

map a node index to its counterpart in the duplicated part of a double-free-space

Parameters

hindex a reachability graph node index

Returns: the node that represents the same interval shifted to the right part of a double-free-space diagram

Definition at line 342 of file graph_model.h.

◆ map() [1/2]

IndexRange frechet::reach::GraphModel::map	(	Orientation	ori,
		const Interval &	,
		bool	upperBoundInclusive
	)		const

map a free-space interval to a range of graph nodes

Parameters

ori	horizontal or vertical
upperBoundInclusive	is the upper interval bound inclusive?

Returns: a range of graph nodes

◆ map() [2/2]

IndexRange GraphModel::map ( Pointer b ) const

map a reachability structure interval to a range of graph nodes

Parameters

b	pointer to a reachability structure interval

Returns: a range of graph nodes

Definition at line 305 of file graph_model.cpp.

◆ map_lower() [1/2]

int GraphModel::map_lower ( Pointer p ) const

map the lower bound of a reachability structure interval

Parameters

p	pointer to a reachability structure interval

Returns: a graph node

Definition at line 311 of file graph_model.cpp.

◆ map_lower() [2/2]

int GraphModel::map_lower	(	Orientation	ori,
		double	x
	)		const

map an interval lower bound

Parameters

ori	horizontal or vertical
x	a lower bound of a free-space interval

Returns: the associated reachability graph node

Definition at line 321 of file graph_model.cpp.

◆ map_upper() [1/2]

int GraphModel::map_upper ( Pointer p ) const

map the upper bound of a reachability structure interval

Parameters

p	pointer to a reachability structure interval

Returns: a graph node

Definition at line 316 of file graph_model.cpp.

◆ map_upper() [2/2]

int GraphModel::map_upper	(	Orientation	ori,
		double	x,
		bool	inclusive
	)		const

map an interval upper bound

Parameters

ori	horizontal or vertical
x	a lower bound of a free-space interval
inclusive	is the upper bound inclusive?

Returns: the associated reachability graph node

Definition at line 327 of file graph_model.cpp.

◆ mapClosest()

IndexRange GraphModel::mapClosest	(	Orientation	ori,
		const Interval &	ival
	)		const

map a free-space interval to the closest graph nodes

Parameters

ori	horizontal or vertical
ival	a free-space interval

Returns: a range of graph nodes

Definition at line 290 of file graph_model.cpp.

◆ mergedHMask()

IndexRange GraphModel::mergedHMask	(	const IndexRange &	m1,
		const IndexRange &	m2
	)		const

merged two node ranges representing the horizontal masks of reachability graph (see frechet::reach::Graph memory layout).

Parameters

m1	horizontal range of a graph
m2	adjacent horizontal range of another graph

Returns: merged range

Definition at line 339 of file graph_model.cpp.

◆ refine() [1/2]

void frechet::reach::GraphModel::refine	(	Structure &	str,
		int	i0
	)		const

◆ refine() [2/2]

void frechet::reach::GraphModel::refine	(	Structure &	str,
		Orientation	ori,
		const Pointer	model
	)		const

private

◆ reverseMap()

const std::vector<Interval>& frechet::reach::GraphModel::reverseMap ( Orientation ori ) const

inline

create a reverse map, mapping graph nodes to free-space interval

Parameters

ori	horizontal or vertical

Returns: a list of free-space intervals

Definition at line 432 of file graph_model.h.

◆ shiftedHorizontally()

IndexRange frechet::reach::GraphModel::shiftedHorizontally ( const IndexRange & r ) const

inline

map a node range to its counterpart in the duplicated part of a double-free-space

Parameters

r	a range of node indexes

Returns: the range that represents the same interval shifted to the right part of a double-free-space diagram

Definition at line 355 of file graph_model.h.

◆ vert() [1/2]

BoundaryList& frechet::reach::GraphModel::vert ( )

inlineprivate

Definition at line 137 of file graph_boost.h.

◆ vert() [2/2]

const BoundaryList& frechet::reach::GraphModel::vert ( ) const

inlineprivate

Definition at line 140 of file graph_boost.h.

Member Data Documentation

◆ _column_entry

std::vector<Pointer> frechet::reach::GraphModel::_column_entry

private

Definition at line 114 of file graph_boost.h.

◆ _count

int frechet::reach::GraphModel::_count

private

Definition at line 117 of file graph_boost.h.

◆ _model

BoundaryList frechet::reach::GraphModel::_model[2]

private

Definition at line 112 of file graph_boost.h.

◆ axis

GraphModelAxis frechet::reach::GraphModel::axis[2]

private

horizontal and vertical mapping

Definition at line 301 of file graph_model.h.

◆ reversed

std::vector<Interval> frechet::reach::GraphModel::reversed[2]

private

reverse mapping from nodes to intervals (horizontal and vertical)

Definition at line 303 of file graph_model.h.

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

include/frechet/reachability/graph_boost.h
include/frechet/reachability/graph_model.h
src/frechet/reachability/graph_model.cpp

Detailed Description

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ ptr

Constructor & Destructor Documentation

◆ GraphModel() [1/3]

◆ GraphModel() [2/3]

◆ GraphModel() [3/3]

Member Function Documentation

◆ count()

◆ count2() [1/2]

◆ count2() [2/2]

◆ dim1()

◆ dim2()

◆ empty()

◆ horiz() [1/2]

◆ horiz() [2/2]

◆ indexify() [1/2]

◆ indexify() [2/2]

◆ init() [1/2]

◆ init() [2/2]

◆ initHorizontal()

◆ initVertical()

◆ list()

◆ lowerShiftedHorizontally()

◆ map() [1/2]

◆ map() [2/2]

◆ map_lower() [1/2]

◆ map_lower() [2/2]

◆ map_upper() [1/2]

◆ map_upper() [2/2]

◆ mapClosest()

◆ mergedHMask()

◆ refine() [1/2]

◆ refine() [2/2]

◆ reverseMap()

◆ shiftedHorizontally()

◆ vert() [1/2]

◆ vert() [2/2]

Member Data Documentation

◆ _column_entry

◆ _count

◆ _model

◆ axis

◆ reversed