Detailed Description

Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure, broken down to the most fine-grained intervals.

Represents a Reachability Graph. Vertices correspond to Boundary intervals that are connected to every reachable interval on the opposite side.

Graphs can be merged.

Transitive Closure: uses boost::Graph O(|V||E|) which is pretty good for sparse graphs (|E| << n^2) see https://www.boost.org/doc/libs/1_48_0/libs/graph/doc/transitive_closure.html

would profit somewhat from persisted condensation graphs

Theoretically, asymptotically better for dense Graphs: transitive closure based an Boolean Matrix Multiplication. However, implementation is more difficult.

strongly connected components form the condensation graph (persist!)
sort in topological order
divide & conquer recursively, see https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/transitiveClosure.pdf
finally, uses BMM. M4RI(E) is a good candidate for BMM, but it can't operate on sub-matrices; requires some copying. maybe, it would pay-off for large matrices.

We should also consider "dynamic" algorithms for transitive closure. Asymptotically similar, but may be more efficient in keeping data structures.

Mapping from reachability intervals to graph nodes is managed by GraphModel.

Graphs can be merged (transitive closure).

Memory layout of adjacancy matrixes is explained below. Boolean matrixes are modelled by M4RI.

Author: Peter Schäfer

Definition at line 39 of file graph_boost.h.

#include <graph_boost.h>

Inherited by frechet::reach::GraphCL.

Classes
struct	Origin
	How was this graph constructed? This info is useful for visualisation & debugging. And for constructing a topologoically sorted list of tasks. (see frechet::poly::AlgorithmTopoSort). More...

Public Types
typedef boost::shared_ptr< Graph >	ptr

typedef boost::shared_ptr< Graph >	ptr

Public Member Functions
	Graph (const GraphModel &model)

	Graph (const GraphModel &model, Structure &str, int i0)

	Graph (const Graph &)

	Graph (Graph &&)

	~Graph ()

int	vertices () const

int	edges () const

Graph &	operator= (const Graph &)

Graph &	operator= (Graph &&)

Graph &	operator+= (const Graph &)

Graph::ptr	transitiveClosure () const

void	transitiveClosureInPlace ()

void	add_edge (int i, int j)

void	clear ()

	Graph (const Graph &that)
	copy constructor More...

	Graph (Graph &&that)
	move constructor More...

virtual	~Graph ()
	destructor, releases memory More...

void	allocateAll ()
	allocate data for adjacenty matrixes (all four parts) More...

mzd_t *	allocate (Orientation o1, Orientation o2)
	allocate an adjacancy sub-matrix (one of four parts) More...

const IndexRange &	hmask () const
	horizontal range covered by this graph More...

Rect	rect (Orientation o1, Orientation o2) const
	range covered by this graph More...

const GraphModel::ptr	graphModel () const

void	setOriginPlacement (int di, int dj)
	this graph represents a set of valid placements More...

void	setOriginRG (int i)
	this graph represents a reachability graph, it was created from a reachability structure More...

void	setOriginMerge2 (Graph::ptr A, Graph::ptr B)
	this graph is the transitive closure of two other graphs. It is the result of a MERGE operation. More...

void	setOriginMerge3 (Graph::ptr A, Graph::ptr B)
	this graph is the transitive closure of two other graphs. It is the result of a final MERGE operation. More...

void	setOriginCombine (Graph::ptr P)
	a sub-set of valid placements is applied to the graph More...

void	printOrigin (std::ostream &out) const
	debug output More...

Graph &	operator= (const Graph &that)
	assigment operator More...

Graph &	operator= (Graph &&that)
	move assigment operator More...

bool	operator== (const Graph &that) const
	comparison operator More...

Edit and Query operations
void	add_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to)
	add an edge to the graph More...

void	add_range (IndexRange r_from, IndexRange r_to)
	add a set of edges to the graph, covering a range of nodes More...

bool	contains_edge (Orientation ori_from, int i_from, Orientation ori_to, int i_to) const
	check if an edge is present More...

bool	contains_edge (IndexRange r_from, IndexRange r_to) const
	check a range of edges More...

bool	empty (Orientation o1, Orientation o2) const
	empty test for one of the four sub-graphs More...

bool	zero (Orientation o1, Orientation o2) const
	empty test for one of the four sub-graphs More...

virtual void	finalize ()
	release memory that is not neeeded (empty sub-graphs) More...

void	releaseIfZero ()
	release memory that is not neeeded (empty sub-graphs) More...

virtual void	release ()
	release memory for all parts of the adjacancy matrix More...

virtual void	release (Orientation o1, Orientation o2)
	release memory for one part of the adjacancy matrix More...

virtual void	release (Orientation o1, Orientation o2, MatrixPool *pool)
	release memory for one part of the adjacancy matrix More...

Iterator methods
int	find_next1 (Orientation o1, int i, Orientation o2, int j) const
	find the next edge in a sub-graph More...

int	find_next0 (Orientation o1, int i, Orientation o2, int j) const
	find the next missing edge in a sub-graph More...

IndexRange	find_next_range (Orientation o1, int i, Orientation o2, int j) const
	find a range of consecutive edges in a sub-graph More...

Bulk operations
virtual void	combine (const Graph *P)
	apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV More...

Graph::ptr	merge2 (const Graph B, MatrixPool pool=nullptr) const
	apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (result)_VV = (this)_VV * that_VV More...

virtual void	merge2 (const Graph A, const Graph B, MatrixPool *pool=nullptr)
	apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (this)_VV = A_VV * *B_VV More...

Graph::ptr	merge3 (const Graph B, MatrixPool pool=nullptr) const
	apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (result)_HH = (this)_HV * that_VV * (*this)_VH More...

virtual void	merge3 (const Graph A, const Graph B, MatrixPool *pool=nullptr)
	apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH More...

virtual void	queryDiagonalElement () const
	find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU). More...

virtual int	foundDiagonalElement () const

stubs for derived classes
virtual void	synchToGpu ()
	implemented by GraphCL; copy matrix data to GPU memory More...

virtual void	synchFromGpu ()
	implemented by GraphCL; copy matrix data backt to CPU memory More...

virtual void	resetConditions ()
	implemented by GraphCL More...

Memory Diaganotics
double	memory (Orientation ori1, Orientation ori2) const
	compute the memory footprint of an adjacancy matrix More...

double	density (Orientation ori1, Orientation ori2) const
	compute the density (amount of set edges) of an adjacancy matrix More...

double	memory () const

double	density () const

Static Public Member Functions
static bool	is_adjacent_to (const Graph &A, const Graph &B)

for unit tests
static void	set_bits (mzd_t *M, int row, int i, int j)
	set some bits in a Boolean matrix More...

static bool	has_bits (mzd_t *M, int row, int i, int j)
	query bits in a Boolean matrix More...

static void	clear_row (mzd_t *M, int row)
	clear a row in a Boolean matrix More...

static void	and_row (mzd_t M, int r, mzd_t M2, int r2)
	apply bitwise and of two matrix rows More...

static int	find_next1 (mzd_t *M, int row, int i)
	find next set bit in a Boolean matrix More...

static int	find_next0 (mzd_t *M, int row, int i)
	find next cleared bit in a Boolean matrix More...

Public Attributes
struct frechet::reach::Graph::Origin	origin

Protected Member Functions
	Graph (const GraphModel::ptr amodel)
	empty constructor More...

	Graph (const GraphModel::ptr amodel, IndexRange range)
	constructor with column range More...

	Graph (const GraphModel::ptr amodel, Structure &str)
	constructor from reachability structure More...

void	copy (const Graph &that)
	copy graph More...

void	swap (Graph &that)
	swap graph More...

void	copy (const Structure &str, Orientation ori)
	copy reachability info from Structure to Graph More...

Static Protected Member Functions
static void	print (std::ostream &out, const mzd_t *M)
	print a Boolean matrix More...

Protected Attributes
mzd_t *	mtx [2][2]
	adjacency matrix (M4RI structure) split into four parts to allow for memory savings. More...

IndexRange	mask [2]

const GraphModel::ptr	model

int	diagonalElement
	result of call to searchDiagonalElement More...

Private Types
typedef boost::property< boost::vertex_name_t, int >	Name

typedef boost::property< boost::vertex_index_t, std::size_t, Name >	Index

typedef boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Index >	graph_t

typedef boost::graph_traits< graph_t >::vertex_descriptor	vertex_t

typedef boost::unordered_map< int, vertex_t >	Index2VertexMap

typedef boost::property_map< graph_t, boost::vertex_index_t >::type	Vertex2IndexMap

Private Member Functions
	Graph (const GraphModel &model, graph_t *ag)

void	copy (const Graph &)

void	swap (Graph &)

vertex_t	vertex (int i)

void	copy (const Structure &str, Pointer i1, Pointer i2)

Private Attributes
graph_t *	g

Index2VertexMap	i2v

const GraphModel &	model

Friends
GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model)
	static, empty constructor More...

GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model, IndexRange hmask)
	static constructor with column range More...

GraphPtr	frechet::reach::newGraph (const GraphModel::ptr model, Structure &str)
	static constructor from reachability structure More...

Debugging
void	clear ()
	remove all edges More...

void	clear (Orientation ori1, Orientation ori2)
	remove all edges of a sub-graph More...

bool	is_upper_triangular (Orientation ori1, Orientation ori2) const

void	print (std::ostream &out, Orientation o1, Orientation o2) const
	print a sub-adjacancy matrix More...

static bool	is_upper_triangular (const mzd_t *mzd)

Member Typedef Documentation

◆ graph_t

typedef boost::adjacency_list< boost::setS, boost::listS, boost::directedS, Index > frechet::reach::Graph::graph_t

private

Definition at line 44 of file graph_boost.h.

◆ Index

typedef boost::property<boost::vertex_index_t, std::size_t, Name> frechet::reach::Graph::Index

private

Definition at line 43 of file graph_boost.h.

◆ Index2VertexMap

typedef boost::unordered_map<int,vertex_t> frechet::reach::Graph::Index2VertexMap

private

Definition at line 49 of file graph_boost.h.

◆ Name

typedef boost::property<boost::vertex_name_t, int> frechet::reach::Graph::Name

private

Definition at line 42 of file graph_boost.h.

◆ ptr [1/2]

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

Definition at line 41 of file graph_m4ri.h.

◆ ptr [2/2]

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

Definition at line 59 of file graph_boost.h.

◆ Vertex2IndexMap

typedef boost::property_map<graph_t,boost::vertex_index_t>::type frechet::reach::Graph::Vertex2IndexMap

private

Definition at line 50 of file graph_boost.h.

◆ vertex_t

typedef boost::graph_traits< graph_t >::vertex_descriptor frechet::reach::Graph::vertex_t

private

Definition at line 46 of file graph_boost.h.

Constructor & Destructor Documentation

◆ Graph() [1/10]

frechet::reach::Graph::Graph	(	const GraphModel &	model,
		graph_t *	ag
	)

private

Definition at line 10 of file graph_boost.cpp.

◆ Graph() [2/10]

frechet::reach::Graph::Graph ( const GraphModel & model )

Definition at line 16 of file graph_boost.cpp.

◆ Graph() [3/10]

frechet::reach::Graph::Graph	(	const GraphModel &	model,
		Structure &	str,
		int	i0
	)

Definition at line 21 of file graph_boost.cpp.

◆ Graph() [4/10]

frechet::reach::Graph::Graph ( const Graph & that )

Definition at line 37 of file graph_boost.cpp.

◆ Graph() [5/10]

frechet::reach::Graph::Graph ( Graph && that )

Definition at line 43 of file graph_boost.cpp.

◆ ~Graph() [1/2]

frechet::reach::Graph::~Graph ( )

Definition at line 49 of file graph_boost.cpp.

◆ Graph() [6/10]

Graph::Graph ( const GraphModel::ptr amodel )

protected

empty constructor

Parameters

amodel maps intervals to nodes

Definition at line 23 of file graph_m4ri.cpp.

◆ Graph() [7/10]

Graph::Graph	(	const GraphModel::ptr	amodel,
		IndexRange	range
	)

protected

constructor with column range

Parameters

amodel	maps intervals to nodes
range	column range covered by the graph

Definition at line 35 of file graph_m4ri.cpp.

◆ Graph() [8/10]

Graph::Graph	(	const GraphModel::ptr	amodel,
		Structure &	str
	)

protected

constructor from reachability structure

Parameters

amodel	maps intervals to nodes
str	a reachability structure

Definition at line 45 of file graph_m4ri.cpp.

◆ Graph() [9/10]

Graph::Graph ( const Graph & that )

copy constructor

Parameters

that	graph to copy from

Definition at line 67 of file graph_m4ri.cpp.

◆ Graph() [10/10]

Graph::Graph ( Graph && that )

move constructor

Parameters

that	graph to copy from, empty on return

Definition at line 73 of file graph_m4ri.cpp.

◆ ~Graph() [2/2]

Graph::~Graph ( )

virtual

destructor, releases memory

Definition at line 99 of file graph_m4ri.cpp.

Member Function Documentation

◆ add_edge() [1/2]

void frechet::reach::Graph::add_edge	(	int	i,
		int	j
	)

Definition at line 147 of file graph_boost.cpp.

◆ add_edge() [2/2]

void frechet::reach::Graph::add_edge	(	Orientation	ori_from,
		int	i_from,
		Orientation	ori_to,
		int	i_to
	)

add an edge to the graph

Parameters

ori_from	source orientention (horizontal or vertical)
i_from	source node (=column or row)
ori_to	destination orientation (horizontal or vertical)
i_to	destination node (=column or row)

◆ add_range()

void Graph::add_range	(	IndexRange	r_from,
		IndexRange	r_to
	)

add a set of edges to the graph, covering a range of nodes

Parameters

r_from	source nodes
r_to	destination nodes

Definition at line 506 of file graph_m4ri.cpp.

◆ allocate()

mzd_t * Graph::allocate	(	Orientation	o1,
		Orientation	o2
	)

allocate an adjacancy sub-matrix (one of four parts)

Parameters

o1	horizontal part
o2	vertical part

Returns: pointer to a M4RI boolean matrix

Definition at line 85 of file graph_m4ri.cpp.

◆ allocateAll()

void Graph::allocateAll ( )

allocate data for adjacenty matrixes (all four parts)

Definition at line 79 of file graph_m4ri.cpp.

◆ and_row()

static void frechet::reach::Graph::and_row	(	mzd_t *	M,
		int	r,
		mzd_t *	M2,
		int	r2
	)

static

apply bitwise and of two matrix rows

Parameters

M	source Boolean matrix in M4RI format
r	matrix row
M2	a Boolean matrix in M4RI format
r2	matrix row

◆ clear() [1/3]

void frechet::reach::Graph::clear ( )

Definition at line 94 of file graph_boost.cpp.

◆ clear() [2/3]

void Graph::clear ( )

remove all edges

Definition at line 649 of file graph_m4ri.cpp.

◆ clear() [3/3]

void frechet::reach::Graph::clear	(	Orientation	ori1,
		Orientation	ori2
	)

remove all edges of a sub-graph

Parameters

ori1	horizontal part
ori2	vertical part

◆ clear_row()

static void frechet::reach::Graph::clear_row	(	mzd_t *	M,
		int	row
	)

static

clear a row in a Boolean matrix

Parameters

M	a Boolean matrix in M4RI format
row	matrix row

◆ combine()

void Graph::combine ( const Graph * P )

virtual

apply the COMBINE operation, filtering edges with valid placements. Effectively performs a Boolean AND oepration: (*this)_VV &= that_VV

Parameters

P	a set of valid placements

Reimplemented in frechet::reach::GraphCL.

Definition at line 419 of file graph_m4ri.cpp.

◆ contains_edge() [1/2]

bool frechet::reach::Graph::contains_edge	(	Orientation	ori_from,
		int	i_from,
		Orientation	ori_to,
		int	i_to
	)		const

check if an edge is present

Parameters

ori_from	source orientention (horizontal or vertical)
i_from	source node (=column or row)
ori_to	destination orientation (horizontal or vertical)
i_to	destination node (=column or row)

Returns: true, if the edge is present

◆ contains_edge() [2/2]

bool frechet::reach::Graph::contains_edge	(	IndexRange	r_from,
		IndexRange	r_to
	)		const

check a range of edges

Parameters

r_from	source nodes
r_to	destination nodes

Returns: true, if at least one is edge is present in the queries range

◆ copy() [1/4]

void frechet::reach::Graph::copy ( const Graph & B )

private

Definition at line 102 of file graph_boost.cpp.

◆ copy() [2/4]

void frechet::reach::Graph::copy	(	const Structure &	str,
		Pointer	i1,
		Pointer	i2
	)

private

Definition at line 117 of file graph_boost.cpp.

◆ copy() [3/4]

void Graph::copy ( const Graph & that )

protected

copy graph

Parameters

that	graph to copy from

Definition at line 258 of file graph_m4ri.cpp.

◆ copy() [4/4]

void Graph::copy	(	const Structure &	str,
		Orientation	ori
	)

protected

copy reachability info from Structure to Graph

Parameters

str	a reachability structure
ori	horizontal or vertical

Definition at line 299 of file graph_m4ri.cpp.

◆ density() [1/2]

double Graph::density	(	Orientation	ori1,
		Orientation	ori2
	)		const

compute the density (amount of set edges) of an adjacancy matrix

Parameters

ori1	horizontal part
ori2	vertical part

Returns: relative density

Definition at line 619 of file graph_m4ri.cpp.

◆ density() [2/2]

double Graph::density ( ) const

Returns: the density (amount of set edges) of all adjacancy matrixes

Definition at line 636 of file graph_m4ri.cpp.

◆ edges()

int frechet::reach::Graph::edges ( ) const

Definition at line 59 of file graph_boost.cpp.

◆ empty()

bool Graph::empty	(	Orientation	o1,
		Orientation	o2
	)		const

empty test for one of the four sub-graphs

Parameters

o1	source orientention (horizontal or vertical)
o2	destination orientation (horizontal or vertical)

Returns: true if the sub-graph is missing

Definition at line 496 of file graph_m4ri.cpp.

◆ finalize()

void Graph::finalize ( )

virtual

release memory that is not neeeded (empty sub-graphs)

Reimplemented in frechet::reach::GraphCL.

Definition at line 199 of file graph_m4ri.cpp.

◆ find_next0() [1/2]

int Graph::find_next0	(	Orientation	o1,
		int	i,
		Orientation	o2,
		int	j
	)		const

find the next missing edge in a sub-graph

Parameters

o1	horizontal part
i	start column
o2	vertical part
j	start row

Returns: the next missing edge in the sub-graph, or INT_MAX if there is none

Definition at line 695 of file graph_m4ri.cpp.

◆ find_next0() [2/2]

static int frechet::reach::Graph::find_next0	(	mzd_t *	M,
		int	row,
		int	i
	)

static

find next cleared bit in a Boolean matrix

Parameters

M	a Boolean matrix in M4RI format
row	matrix row
i	column

Returns: column of next cleared bit in row, or INT_MAX if there is none

◆ find_next1() [1/2]

int Graph::find_next1	(	Orientation	o1,
		int	i,
		Orientation	o2,
		int	j
	)		const

find the next edge in a sub-graph

Parameters

o1	horizontal part
i	start column
o2	vertical part
j	start row

Returns: the next edge in the sub-graph, or INT_MAX if there is none

Definition at line 679 of file graph_m4ri.cpp.

◆ find_next1() [2/2]

static int frechet::reach::Graph::find_next1	(	mzd_t *	M,
		int	row,
		int	i
	)

static

find next set bit in a Boolean matrix

Parameters

M	a Boolean matrix in M4RI format
row	matrix row
i	column

Returns: column of next set bit in row, or INT_MAX if there is none

◆ find_next_range()

IndexRange Graph::find_next_range	(	Orientation	o1,
		int	i,
		Orientation	o2,
		int	j
	)		const

find a range of consecutive edges in a sub-graph

Parameters

o1	horizontal part
i	start column
o2	vertical part
j	start row

Returns: next consecutive range of edges, or an empty range if there are none

Definition at line 710 of file graph_m4ri.cpp.

◆ foundDiagonalElement()

int Graph::foundDiagonalElement ( ) const

virtual

Returns: the result of the last call to queryDiagonalElement. Or -1 if the diagonal is empty.

Reimplemented in frechet::reach::GraphCL.

Definition at line 450 of file graph_m4ri.cpp.

◆ graphModel()

const GraphModel::ptr frechet::reach::Graph::graphModel ( ) const

inline

Returns: model that maps reachability intervals for graph nodes

Definition at line 198 of file graph_m4ri.h.

◆ has_bits()

bool Graph::has_bits	(	mzd_t *	M,
		int	row,
		int	i,
		int	j
	)

static

query bits in a Boolean matrix

Parameters

M	a Boolean matrix in M4RI format
row	matrix row
i	first column
j	last column (exclusive)

Returns: true if at least one bit is set

Definition at line 585 of file graph_m4ri.cpp.

◆ hmask()

const IndexRange& frechet::reach::Graph::hmask ( ) const

inline

horizontal range covered by this graph

Returns: range of nodes that is covered by this graph

Definition at line 187 of file graph_m4ri.h.

◆ is_adjacent_to()

bool Graph::is_adjacent_to	(	const Graph &	A,
		const Graph &	B
	)

static

Parameters

A	a graph
B	another graph

Returns: true if the column ranges of both graphs are adjacent

Definition at line 775 of file graph_m4ri.cpp.

◆ is_upper_triangular() [1/2]

bool Graph::is_upper_triangular	(	Orientation	ori1,
		Orientation	ori2
	)		const

Parameters

ori1	horizontal part
ori2	vertical part

Returns: true if the sub-adjancy matrix is an upper triangular matrix

Definition at line 662 of file graph_m4ri.cpp.

◆ is_upper_triangular() [2/2]

static bool frechet::reach::Graph::is_upper_triangular ( const mzd_t * mzd )

static

Parameters

mzd	a boolean matrix (in M4RI format)

Returns: true if the matrix is an upper triangular matrix

◆ memory() [1/2]

double Graph::memory	(	Orientation	ori1,
		Orientation	ori2
	)		const

compute the memory footprint of an adjacancy matrix

Parameters

ori1	horizontal part
ori2	vertical part

Returns: memory, in Bytes, used by a (sub-)adjacancy matrix

Definition at line 612 of file graph_m4ri.cpp.

◆ memory() [2/2]

double Graph::memory ( ) const

Returns: the memory footprint for all adjacancy matrixes

Definition at line 627 of file graph_m4ri.cpp.

◆ merge2() [1/2]

Graph::ptr frechet::reach::Graph::merge2	(	const Graph *	B,
		MatrixPool *	pool = `nullptr`
	)		const

apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_VV = (*this)_VV * that_VV

Parameters

B	another graph
pool	pool of re-cycled matrixes (optional)

Returns: a newly created graph representing the result of the MERGE operation

◆ merge2() [2/2]

virtual void frechet::reach::Graph::merge2	(	const Graph *	A,
		const Graph *	B,
		MatrixPool *	pool = `nullptr`
	)

virtual

apply the MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*this)_VV = *A_VV * *B_VV

Parameters

A	a graph
B	another graph
pool	pool of re-cycled matrixes (optional)

Reimplemented in frechet::reach::GraphCL.

◆ merge3() [1/2]

Graph::ptr frechet::reach::Graph::merge3	(	const Graph *	B,
		MatrixPool *	pool = `nullptr`
	)		const

apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: (*result)_HH = (*this)_HV * that_VV * (*this)_VH

Parameters

B	another graph
pool

Returns: a newly created graph representing the result of the MERGE operation

◆ merge3() [2/2]

virtual void frechet::reach::Graph::merge3	(	const Graph *	A,
		const Graph *	B,
		MatrixPool *	pool = `nullptr`
	)

virtual

apply the final MERGE operation, computing the transitive closure of two graphs. Effectively performs a matrix multiplication: this_HH = A_HV * B_VV * A_VH

Parameters

A	a graph
B	another graph
pool	pool of re-cycled matrixes (optional)

Reimplemented in frechet::reach::GraphCL.

◆ operator+=()

frechet::reach::Graph & frechet::reach::Graph::operator+= ( const Graph & B )

Definition at line 77 of file graph_boost.cpp.

◆ operator=() [1/4]

frechet::reach::Graph & frechet::reach::Graph::operator= ( const Graph & that )

Definition at line 64 of file graph_boost.cpp.

◆ operator=() [2/4]

frechet::reach::Graph & frechet::reach::Graph::operator= ( Graph && that )

Definition at line 71 of file graph_boost.cpp.

◆ operator=() [3/4]

Graph & Graph::operator= ( const Graph & that )

assigment operator

Parameters

that	graph to copy from

Returns: reference to this, after assignment

Definition at line 227 of file graph_m4ri.cpp.

◆ operator=() [4/4]

Graph & Graph::operator= ( Graph && that )

move assigment operator

Parameters

that	graph to copy from; empty on return

Returns: reference to this, after assignment

Definition at line 234 of file graph_m4ri.cpp.

◆ operator==()

bool Graph::operator== ( const Graph & that ) const

comparison operator

Parameters

that	graph to compare with

Returns: true if both graphs are equal

Definition at line 240 of file graph_m4ri.cpp.

◆ print() [1/2]

void Graph::print	(	std::ostream &	out,
		Orientation	o1,
		Orientation	o2
	)		const

print a sub-adjacancy matrix

Parameters

out	output stream
o1	horizontal part
o2	vertical part

Definition at line 781 of file graph_m4ri.cpp.

◆ print() [2/2]

void Graph::print	(	std::ostream &	out,
		const mzd_t *	M
	)

staticprotected

print a Boolean matrix

Parameters

out	output stream
M	a boolean matrix (in M4RI format)

Definition at line 786 of file graph_m4ri.cpp.

◆ printOrigin()

void Graph::printOrigin ( std::ostream & out ) const

debug output

Definition at line 162 of file graph_m4ri.cpp.

◆ queryDiagonalElement()

void Graph::queryDiagonalElement ( ) const

virtual

find an edge on the diagonal of the adjacancy matrix. Does not return a result. To query the result of this method, call foundDiagonalElement. (reason: we also want to perform this query asynchronously on a GPU).

Reimplemented in frechet::reach::GraphCL.

Definition at line 437 of file graph_m4ri.cpp.

◆ rect()

frechet::Rect Graph::rect	(	Orientation	o1,
		Orientation	o2
	)		const

range covered by this graph

Parameters

o1	horizontal part
o2	vertical part

Returns: range of nodes that is covered by this one part of the adjacancy matrix

Definition at line 94 of file graph_m4ri.cpp.

◆ release() [1/3]

void Graph::release ( )

virtual

release memory for all parts of the adjacancy matrix

Definition at line 203 of file graph_m4ri.cpp.

◆ release() [2/3]

void Graph::release	(	Orientation	o1,
		Orientation	o2
	)

virtual

release memory for one part of the adjacancy matrix

Parameters

o1	horizontal part
o2	vertical part

Reimplemented in frechet::reach::GraphCL.

Definition at line 218 of file graph_m4ri.cpp.

◆ release() [3/3]

void Graph::release	(	Orientation	o1,
		Orientation	o2,
		MatrixPool *	pool
	)

virtual

release memory for one part of the adjacancy matrix

Parameters

o1	horizontal part
o2	vertical part
pool	a pool of re-cycled matrix data

Reimplemented in frechet::reach::GraphCL.

Definition at line 798 of file graph_m4ri.cpp.

◆ releaseIfZero()

void Graph::releaseIfZero ( )

release memory that is not neeeded (empty sub-graphs)

Definition at line 210 of file graph_m4ri.cpp.

◆ resetConditions()

virtual void frechet::reach::Graph::resetConditions ( )

inlinevirtual

implemented by GraphCL

Reimplemented in frechet::reach::GraphCL.

Definition at line 434 of file graph_m4ri.h.

◆ set_bits()

void Graph::set_bits	(	mzd_t *	M,
		int	row,
		int	i,
		int	j
	)

static

set some bits in a Boolean matrix

Parameters

M	a Boolean matrix in M4RI format
row	matrix row
i	first column
j	last column (exclusive)

Definition at line 556 of file graph_m4ri.cpp.

◆ setOriginCombine()

void Graph::setOriginCombine ( Graph::ptr P )

a sub-set of valid placements is applied to the graph

Parameters

P	a set of valid placements

Definition at line 157 of file graph_m4ri.cpp.

◆ setOriginMerge2()

void Graph::setOriginMerge2	(	Graph::ptr	A,
		Graph::ptr	B
	)

this graph is the transitive closure of two other graphs. It is the result of a MERGE operation.

Parameters

A	first successor
B	seocnd succssor

Definition at line 128 of file graph_m4ri.cpp.

◆ setOriginMerge3()

void Graph::setOriginMerge3	(	Graph::ptr	A,
		Graph::ptr	B
	)

this graph is the transitive closure of two other graphs. It is the result of a final MERGE operation.

Parameters

A	first successor
B	seocnd succssor

Definition at line 142 of file graph_m4ri.cpp.

◆ setOriginPlacement()

void Graph::setOriginPlacement	(	int	di,
		int	dj
	)

this graph represents a set of valid placements

Parameters

di	first diagonal endpoint
dj	second diagonal endpoint

Definition at line 104 of file graph_m4ri.cpp.

◆ setOriginRG()

void Graph::setOriginRG ( int i )

this graph represents a reachability graph, it was created from a reachability structure

Parameters

i	free-space column

Definition at line 116 of file graph_m4ri.cpp.

◆ swap() [1/2]

void frechet::reach::Graph::swap ( Graph & that )

private

Definition at line 108 of file graph_boost.cpp.

◆ swap() [2/2]

void Graph::swap ( Graph & that )

protected

swap graph

Parameters

that	grap to swap with; holds *this on return

Definition at line 290 of file graph_m4ri.cpp.

◆ synchFromGpu()

virtual void frechet::reach::Graph::synchFromGpu ( )

inlinevirtual

implemented by GraphCL; copy matrix data backt to CPU memory

Reimplemented in frechet::reach::GraphCL.

Definition at line 432 of file graph_m4ri.h.

◆ synchToGpu()

virtual void frechet::reach::Graph::synchToGpu ( )

inlinevirtual

implemented by GraphCL; copy matrix data to GPU memory

Reimplemented in frechet::reach::GraphCL.

Definition at line 430 of file graph_m4ri.h.

◆ transitiveClosure()

frechet::reach::Graph::ptr frechet::reach::Graph::transitiveClosure ( ) const

Definition at line 157 of file graph_boost.cpp.

◆ transitiveClosureInPlace()

void frechet::reach::Graph::transitiveClosureInPlace ( )

Definition at line 164 of file graph_boost.cpp.

◆ vertex()

frechet::reach::Graph::vertex_t frechet::reach::Graph::vertex ( int i )

private

Definition at line 131 of file graph_boost.cpp.

◆ vertices()

int frechet::reach::Graph::vertices ( ) const

Definition at line 54 of file graph_boost.cpp.

◆ zero()

bool Graph::zero	(	Orientation	o1,
		Orientation	o2
	)		const

empty test for one of the four sub-graphs

Parameters

o1	source orientention (horizontal or vertical)
o2	destination orientation (horizontal or vertical)

Returns: true if the sub-graph is missing, or empty

Definition at line 501 of file graph_m4ri.cpp.

Friends And Related Function Documentation

◆ frechet::reach::newGraph [1/3]

GraphPtr frechet::reach::newGraph ( const GraphModel::ptr model )

friend

static, empty constructor

Parameters

model maps intervals to nodes

Returns: a newly created, empty graph

◆ frechet::reach::newGraph [2/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		IndexRange	hmask
	)

friend

static constructor with column range

Parameters

model	maps intervals to nodes
hmask	column range covered by the graph

Returns: a newly created, empty graph

◆ frechet::reach::newGraph [3/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		Structure &	str
	)

friend

static constructor from reachability structure

Parameters

model	maps intervals to nodes
str	a reachability structure

Returns: a newly created graph that represents the reachability structure

Member Data Documentation

◆ diagonalElement

int frechet::reach::Graph::diagonalElement

mutableprotected

result of call to searchDiagonalElement

Definition at line 78 of file graph_m4ri.h.

◆ g

graph_t* frechet::reach::Graph::g

private

Definition at line 52 of file graph_boost.h.

◆ i2v

Index2VertexMap frechet::reach::Graph::i2v

private

Definition at line 53 of file graph_boost.h.

◆ mask

IndexRange frechet::reach::Graph::mask[2]

protected

RG(i,j) describes only a curve segment of P (and possibly all of Q). Adjacacency matrices are somewhat sparse, like this:

        +--+            +-----------------------
        |//|            |//////////////////////
        +--+            +-----------------------
                        |
                        |
--------+--+------------+-----------------------
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /
        |//|            | / / / / / / / / / / /

RG(i,i+1) is only about 25% dense. Later, RG(i,j) become denser.

Merge operations (transitive closure) are ony between adjacent ranges of (i,j) - (j,h)

We can save storage space, multiplication must be adjusted accordingly

Definition at line 72 of file graph_m4ri.h.

◆ model [1/2]

const GraphModel& frechet::reach::Graph::model

private

Definition at line 55 of file graph_boost.h.

◆ model [2/2]

const GraphModel::ptr frechet::reach::Graph::model

protected

mapping from intervals -> graph nodes = rows and columns of the adjacancy matrix

Definition at line 76 of file graph_m4ri.h.

◆ mtx

mzd_t* frechet::reach::Graph::mtx[2][2]

protected

adjacency matrix (M4RI structure) split into four parts to allow for memory savings.

Definition at line 45 of file graph_m4ri.h.

◆ origin

struct frechet::reach::Graph::Origin frechet::reach::Graph::origin

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

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

Detailed Description

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

Friends

Debugging

Member Typedef Documentation

◆ graph_t

◆ Index

◆ Index2VertexMap

◆ Name

◆ ptr [1/2]

◆ ptr [2/2]

◆ Vertex2IndexMap

◆ vertex_t

Constructor & Destructor Documentation

◆ Graph() [1/10]

◆ Graph() [2/10]

◆ Graph() [3/10]

◆ Graph() [4/10]

◆ Graph() [5/10]

◆ ~Graph() [1/2]

◆ Graph() [6/10]

◆ Graph() [7/10]

◆ Graph() [8/10]

◆ Graph() [9/10]

◆ Graph() [10/10]

◆ ~Graph() [2/2]

Member Function Documentation

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_range()

◆ allocate()

◆ allocateAll()

◆ and_row()

◆ clear() [1/3]

◆ clear() [2/3]

◆ clear() [3/3]

◆ clear_row()

◆ combine()

◆ contains_edge() [1/2]

◆ contains_edge() [2/2]

◆ copy() [1/4]

◆ copy() [2/4]

◆ copy() [3/4]

◆ copy() [4/4]

◆ density() [1/2]

◆ density() [2/2]

◆ edges()

◆ empty()

◆ finalize()

◆ find_next0() [1/2]

◆ find_next0() [2/2]

◆ find_next1() [1/2]

◆ find_next1() [2/2]

◆ find_next_range()

◆ foundDiagonalElement()

◆ graphModel()

◆ has_bits()

◆ hmask()

◆ is_adjacent_to()

◆ is_upper_triangular() [1/2]

◆ is_upper_triangular() [2/2]

◆ memory() [1/2]

◆ memory() [2/2]

◆ merge2() [1/2]

◆ merge2() [2/2]

◆ merge3() [1/2]

◆ merge3() [2/2]

◆ operator+=()

◆ operator=() [1/4]

◆ operator=() [2/4]