tu Namespace Reference

Classes
class	binary_linear_space
struct	bipartite_graph_bfs_node
struct	bipartite_graph_dimensions

Functions
template<typename MatroidType , typename MatrixType >
std::pair< bool, decomposed_matroid * >	decompose_binary_matroid (MatroidType &matroid, MatrixType &matrix, matroid_element_set extra_elements, bool construct_decomposition, logger &log)
	Forward declaration. More...
template<typename MatroidType , typename MatrixType >
std::pair< bool, decomposed_matroid * >	decompose_with_minor_sequence (matroid_permuted< MatroidType > &permuted_matroid, matrix_permuted< MatrixType > &permuted_matrix, nested_minor_sequence &nested_minors, matroid_element_set extra_elements, bool construct_decomposition, logger &log)
template<typename MatroidType , typename MatrixType >
matroid_graph *	construct_small_matroid_graph (MatroidType &matroid, MatrixType &matrix)
std::ostream &	operator<< (std::ostream &stream, const binary_linear_space &space)
template<typename MatrixType , typename StartNodesContainerType , typename EndNodesContainerType >
bool	bipartite_graph_bfs (const MatrixType &matrix, const bipartite_graph_dimensions &dimensions, const StartNodesContainerType &start_nodes, const EndNodesContainerType &end_nodes, bool reach_all, std::vector< bipartite_graph_bfs_node > &result)

Function Documentation

bipartite_graph_bfs()

template<typename MatrixType , typename StartNodesContainerType , typename EndNodesContainerType >

bool tu::bipartite_graph_bfs ( const MatrixType &  matrix, const bipartite_graph_dimensions &  dimensions, const StartNodesContainerType &  start_nodes, const EndNodesContainerType &  end_nodes, bool  reach_all, std::vector< bipartite_graph_bfs_node > &  result  )

inline

Does a breadth-first-search on the bipartite graph defined by a submatrix of a given matrix. Running time: O(height * width)

Parameters

matrix	Given matrix
dimensions	Object for row/column-to-index calculations
start_nodes	Set of starting nodes for search
end_nodes	Set of nodes to be found
reach_all	Whether we'd like to find all end nodes, or just one
result	Whether all resp. one end node was found.

Returns

true iff enough of the target nodes were found.

Initialize datastructure

Start bfs

row -> columns

column -> rows

construct_small_matroid_graph()

template<typename MatroidType , typename MatrixType >

matroid_graph* tu::construct_small_matroid_graph	(	MatroidType &	matroid,
		MatrixType &	matrix
	)

Create the graph for 2 x w or h x 2 matrices.

Parameters

matroid
matrix

Returns

Created graph

0 1

1 0

1 1

decompose_binary_matroid()

template<typename MatroidType , typename MatrixType >

std::pair< bool, decomposed_matroid * > tu::decompose_binary_matroid	(	MatroidType &	matroid,
		MatrixType &	matrix,
		matroid_element_set	extra_elements,
		bool	construct_decomposition,
		logger &	log
	)

Forward declaration.

Decomposes a given binary matroid.

Parameters

matroid
matrix
construct_decomposition

Returns

Identifies a W_3 minor in the upper left corner or finds a separation

Separation case

Filter or copy extra_elements depending on type of separation

Identifies a W_3 minor in the upper left corner or finds a separation

Separation case

Filter or copy extra_elements depending on type of separation

decompose_with_minor_sequence()

template<typename MatroidType , typename MatrixType >

std::pair<bool, decomposed_matroid*> tu::decompose_with_minor_sequence	(	matroid_permuted< MatroidType > &	permuted_matroid,
		matrix_permuted< MatrixType > &	permuted_matrix,
		nested_minor_sequence &	nested_minors,
		matroid_element_set	extra_elements,
		bool	construct_decomposition,
		logger &	log
	)

Filter or copy extra_elements depending on type of separation

operator<<()

std::ostream& tu::operator<< ( std::ostream &  stream, const binary_linear_space &  space  )

inline

Streams a binary linear vector space.

Parameters

stream	Output stream
space	The given vector space

Returns

The output stream after processing