TMBad::graph Struct Reference

Operator graph in compressed row storage. More...

#include <global.hpp>

Public Member Functions
void	bfs (const std::vector< Index > &start, std::vector< bool > &visited, std::vector< Index > &result)
	Perform a breadth-first search. More...
std::vector< Index >	boundary (const std::vector< Index > &subgraph)
	Find boundary of subgraph. More...
std::vector< Index >	colcounts ()
	Number of row indices by column, i.e. number of ingoing edges.
	graph (size_t num_nodes, const std::vector< IndexPair > &edges)
	Construct a graph. More...
std::vector< Index >	rowcounts ()
	Number of column indices by row, i.e. number of outgoing edges.
void	search (std::vector< Index > &start, bool sort_input=true, bool sort_output=true)
	Find sub graph. More...
void	search (std::vector< Index > &start, std::vector< bool > &visited, bool sort_input=true, bool sort_output=true)
	Find sub graph. More...

Public Attributes
std::vector< Index >	dep2op
	Used to lookup operator (node) of a dependent variable.
std::vector< Index >	inv2op
	Used to lookup operator (node) of an independent variable.
std::vector< bool >	mark
	Private workspace used by graph::search. Must either be empty or filled with false when not in use.

Detailed Description

Operator graph in compressed row storage.

Definition at line 617 of file global.hpp.

Constructor & Destructor Documentation

graph()

TMBad::graph::graph	(	size_t	num_nodes,
		const std::vector< IndexPair > &	edges
	)

Construct a graph.

Parameters

num_nodes	Number of nodes
edges	Graph edges represented as node pairs

Definition at line 878 of file TMBad.cpp.

Member Function Documentation

bfs()

void TMBad::graph::bfs	(	const std::vector< Index > &	start,
		std::vector< bool > &	visited,
		std::vector< Index > &	result
	)

Perform a breadth-first search.

Parameters

start	Nodes that initiate the search
visited	On input contains boolean mask of already visited nodes which should be skipped from the search. On output the result of the search has been marked as visited.
result	The result of the search is appended to this vector.

Note

start and result are allowed to be references to the same object.

Definition at line 829 of file TMBad.cpp.

boundary()

std::vector< Index > TMBad::graph::boundary

(

const std::vector< Index > &

subgraph

)

Find boundary of subgraph.

Parameters

subgraph

Nodes of the subgraph

Returns the set of nodes outside the subgraph which are connected to some node in the subgraph.

Definition at line 863 of file TMBad.cpp.

search() [1/2]

void TMBad::graph::search	(	std::vector< Index > &	start,
		bool	sort_input = true,
		bool	sort_output = true
	)

Find sub graph.

Parameters

start	On input contains the nodes from which to perform the search. On output contains the sorted result of the search.
sort_input	Remove duplicates before searching? Can be set to false if start is unique.
sort_output	Sort the result of the search? Output must be sorted in order to work as a valid subgraph (!)

Warning

start really is nodes and not variables.

• To initiate a search from an independent variable i use inv2op[i] to lookup the corresponding node !
• To initiate a search from a dependent variable i use dep2op[i] to lookup the corresponding node !

Definition at line 843 of file TMBad.cpp.

Referenced by TMBad::ADFun<>::Jacobian(), TMBad::autopar::max_tree_depth(), TMBad::sequential_reduction::reorder_random(), and TMBad::sequential_reduction::update().

search() [2/2]

void TMBad::graph::search	(	std::vector< Index > &	start,
		std::vector< bool > &	visited,
		bool	sort_input = true,
		bool	sort_output = true
	)

Find sub graph.

Parameters

start	On input contains the nodes from which to perform the search. On output contains the sorted result of the search.
sort_input	Remove duplicates before searching? Can be set to false if start is unique.
sort_output	Sort the result of the search? Output must be sorted in order to work as a valid subgraph (!)

Warning

start really is nodes and not variables.

• To initiate a search from an independent variable i use inv2op[i] to lookup the corresponding node !
• To initiate a search from a dependent variable i use dep2op[i] to lookup the corresponding node !

Parameters

visited

On input contains boolean mask of already visited nodes which should be skipped from the search. On output the result of the search has been marked as visited.

Note

To perform the search along a restricted graph one can pass the complement of the restriction as 'already visited'.

Definition at line 852 of file TMBad.cpp.

---

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

• global.hpp
• TMBad.cpp