Classes
struct	empty_bottom_left_modifier

class	Range

struct	transpose_orientation
	Helper struct to manage orientation tags. More...

struct	transpose_orientation< boost::numeric::ublas::row_major_tag >
	Helper struct to manage orientation tags. More...

struct	transpose_orientation< boost::numeric::ublas::column_major_tag >
	Helper struct to manage orientation tags. More...

class	violator_strategy

class	single_violator_strategy

class	greedy_violator_strategy

Functions
template<typename MatroidType , typename MatrixType >
void	find_column_witnesses (MatroidType &matroid, MatrixType &matrix, size_pair_t split, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
void	find_row_witnesses (MatroidType &matroid, MatrixType &matrix, size_pair_t split, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
separation	find_witnesses (MatroidType &matroid, MatrixType &matrix, size_pair_t split, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
void	pivot_top_right (MatroidType &matroid, MatrixType &matrix, size_pair_t &split, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
void	pivot_bottom_left (MatroidType &matroid, MatrixType &matrix, size_pair_t &split, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
void	normalize_3_4_separation (MatroidType &matroid, MatrixType &matrix, size_pair_t &split, rank_distribution ranks, matroid_element_set &extra_elements)

template<typename MatroidType , typename MatrixType >
bool	extend_to_3_4_separation (MatroidType &matroid, MatrixType &matrix, matrix_permuted< const integer_matrix > &worker_matrix, size_pair_t top_left_size, size_pair_t bottom_right_size, separation &separation, matroid_element_set &extra_elements)

template<typename MappingValue >
size_pair_t	apply_mapping (permutation &permutation, std::vector< MappingValue > &mapping)

template<typename NestedMinorSequence >
size_t	find_first_7_element_minor (const NestedMinorSequence &nested_minors, size_pair_t &minor_size)

template<typename MatroidType , typename MatrixType , typename MappingValue >
bool	enumerate_extension (MatroidType &matroid, MatrixType &matrix, matrix_permuted< const integer_matrix > &worker_matrix, std::vector< MappingValue > &row_mapping, std::vector< MappingValue > &column_mapping, size_pair_t minor_size, size_t ext_height, size_t ext_width, separation &separation, matroid_element_set &extra_elements, unsigned long long &enumeration, unsigned long long &next_enumeration, unsigned long long max_enumerations, unsigned int &next_percent, logger &log, size_t cut)

template<typename MatrixType , typename VectorType >
void	copy_partial_row (const MatrixType &matrix, VectorType &vector, size_t row, size_t first_column, size_t beyond_column)

template<typename MatrixType , typename VectorType >
void	copy_partial_column (const MatrixType &matrix, VectorType &vector, size_t column, size_t first_row, size_t beyond_row)

matroid_element_set	find_smallest_irregular_minor (const decomposed_matroid *decomposition, bool collect_extra_elements=true)

template<typename InputIterator , typename OutputIterator1 , typename OutputIterator2 >
std::pair< OutputIterator1, OutputIterator2 >	split_elements (InputIterator first, InputIterator beyond, OutputIterator1 rows, OutputIterator2 columns)

template<typename MatrixType >
void	create_indirect_matroid (const MatrixType &input_matrix, const matroid_element_set &row_elements, const matroid_element_set &column_elements, integer_matroid &sub_matroid, submatrix_indices &sub_indices)

Function Documentation

◆ apply_mapping()

template<typename MappingValue >

size_pair_t tu::detail::apply_mapping	(	permutation &	permutation,
		std::vector< MappingValue > &	mapping
	)

inline

Creates a permutation which sorts a given vector. It further counts the number of positive and negativ values.

Parameters

permutation	Permutation to return
mapping	The given vector

Returns: (positive entries, negativ entries)

◆ copy_partial_column()

template<typename MatrixType , typename VectorType >

void tu::detail::copy_partial_column	(	const MatrixType &	matrix,
		VectorType &	vector,
		size_t	column,
		size_t	first_row,
		size_t	beyond_row
	)

inline

Copies a partial column of a matrix into a vector.

Parameters

matrix	A given matrix
vector	Vector to be filled
column	Index of the column
first_row	Index of the first row
beyond_row	Index of the row beyond the partial column

◆ copy_partial_row()

template<typename MatrixType , typename VectorType >

void tu::detail::copy_partial_row	(	const MatrixType &	matrix,
		VectorType &	vector,
		size_t	row,
		size_t	first_column,
		size_t	beyond_column
	)

inline

Copies a partial row of a matrix into a vector.

Parameters

matrix	A given matrix
vector	Vector to be filled
row	Index of the row
first_column	Index of the first column
beyond_column	Index of the column beyond the partial row

◆ create_indirect_matroid()

template<typename MatrixType >

void tu::detail::create_indirect_matroid	(	const MatrixType &	input_matrix,
		const matroid_element_set &	row_elements,
		const matroid_element_set &	column_elements,
		integer_matroid &	sub_matroid,
		submatrix_indices &	sub_indices
	)

◆ enumerate_extension()

template<typename MatroidType , typename MatrixType , typename MappingValue >

bool tu::detail::enumerate_extension	(	MatroidType &	matroid,
		MatrixType &	matrix,
		matrix_permuted< const integer_matrix > &	worker_matrix,
		std::vector< MappingValue > &	row_mapping,
		std::vector< MappingValue > &	column_mapping,
		size_pair_t	minor_size,
		size_t	ext_height,
		size_t	ext_width,
		separation &	separation,
		matroid_element_set &	extra_elements,
		unsigned long long &	enumeration,
		unsigned long long &	next_enumeration,
		unsigned long long	max_enumerations,
		unsigned int &	next_percent,
		logger &	log,
		size_t	cut
	)

inline

Enumerates all necessary partitions for a fixed extension inside a sequence of nested minors. It works on a separate matrix with mapping vectors. Those contain either entries +1 and -1 to show to which part of the minor-separation a row or column belongs and a 0 to designate a row or column to be unspecified.

Parameters

matroid	The given matroid
matrix	Representation matrix for the given matroid
worker_matrix	Matrix to work on with the right permutation
row_mapping	Mapping vector for rows
column_mapping	Mapping vector for columns
minor_size	Size of the current minor in the sequence of nested minors
ext_height	Height of the extension
ext_width	Width of the extension
separation	Separation to be returned
extra_elements	Set of matroid-elements to be filled with pivot-elements
enumeration	Iteration step in the whole enumeration.
next_enumeration	Next enumeration
max_enumerations	Total number of enumerations
next_percent	Next percent value for a percent-jump
log	Logger
cut	Length of the line to cut off the progress-part

Returns: true if and only if the partitioning algorithm was successful

Type and index of enumerated element in smaller minor

Set all mappings to 1 at first

Set minor enumerated to -1

Iterator over extension bits and set row/column mapping to -1 if the bit is set

Transform the mappings into row/column permutations.

◆ extend_to_3_4_separation()

template<typename MatroidType , typename MatrixType >

bool tu::detail::extend_to_3_4_separation	(	MatroidType &	matroid,
		MatrixType &	matrix,
		matrix_permuted< const integer_matrix > &	worker_matrix,
		size_pair_t	top_left_size,
		size_pair_t	bottom_right_size,
		separation &	separation,
		matroid_element_set &	extra_elements
	)

inline

Calls the partition algorithm to extend a given separation of a minor to the whole matroid.

Parameters

matroid	The original matrix
matrix	A representation matrix for the original matroid
worker_matrix	Matrix for the partition algorithm to work on
top_left_size	Size of the first part of the minor-separation
bottom_right_size	Size of the second part of the minor-separation
separation	Separation to return
extra_elements	Set of matroid elements to be filled with pivot-elements

Returns: true if and only if The partitioning was successful

Now we really found a separation. We apply the worker-matrix-permutation to the orginal matrix.

Normalize it

Make the witnesses visible.

◆ find_column_witnesses()

template<typename MatroidType , typename MatrixType >

void tu::detail::find_column_witnesses	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t	split,
		matroid_element_set &	extra_elements
	)

inline

Finds paths in the top-left BFS graph between two bottom-left independet columns, shortens them and swaps rows and columns such that the columns and the connecting row are near the split point.

Parameters

matroid	Given matroid
matrix	A representation matrix for the matroid
split	Split of a given (3\|4)-separation.

Set up matrix for BFS

Try to find path from type 1 to the 2 and 3. If no path is found, try between 2 and 3.

Find reached node

We now have a path between two columns of different type and apply the path shortening technique to make it short.

Swap everything to be near split point.

◆ find_first_7_element_minor()

template<typename NestedMinorSequence >

size_t tu::detail::find_first_7_element_minor	(	const NestedMinorSequence &	nested_minors,
		size_pair_t &	minor_size
	)

inline

Finds the index of the first minor in a given sequence of nested minors which has at least 7 elements.

Parameters

nested_minors	Given sequence of nested minors
minor_size	Size of the minor found

Returns: Index of the minor found

◆ find_row_witnesses()

template<typename MatroidType , typename MatrixType >

void tu::detail::find_row_witnesses	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t	split,
		matroid_element_set &	extra_elements
	)

inline

Finds paths in the bottom-right BFS graph between two bottom-left independet rows, shortens them and swaps rows and columns such that the rows and the connecting column are near the split point.

Parameters

matroid	Given matroid
matrix	A representation matrix for the matroid
split	Split of a given (3\|4)-separation.

Set up matrix for BFS

Try to find path from type 1 to the 2 and 3. If no path is found, try between 2 and 3.

Find reached node

We now have a path between two columns of different type and apply the path shortening technique to make it short.

◆ find_smallest_irregular_minor()

matroid_element_set tu::detail::find_smallest_irregular_minor	(	const decomposed_matroid *	decomposition,
		bool	collect_extra_elements = `true`
	)

inline

◆ find_witnesses()

template<typename MatroidType , typename MatrixType >

separation tu::detail::find_witnesses	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t	split,
		matroid_element_set &	extra_elements
	)

inline

Finds witnesses for a 3-separation.

Parameters

matroid	A given matroid
matrix	A representation matrix for the matroid
split	Split of the 3-separation
extra_elements	Set of matroid elements to be filled with pivot-elements

Returns: The final separation

◆ normalize_3_4_separation()

template<typename MatroidType , typename MatrixType >

void tu::detail::normalize_3_4_separation	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t &	split,
		rank_distribution	ranks,
		matroid_element_set &	extra_elements
	)

inline

Modifies a (3|4)-separation to have rank 2 in bottom-left area and top-right non-degenerate.

Parameters

matroid	Given matroid
matrix	A representation matrix for the matroid
split	Split of a given (3\|4)-separation
ranks	Rank distribution of the given separation

If top-right has few rows, mirror the matrix, swapping bottom-left with top-right

Now as top-right has enough rows, we can pivot without degenerating it.

◆ pivot_bottom_left()

template<typename MatroidType , typename MatrixType >

void tu::detail::pivot_bottom_left	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t &	split,
		matroid_element_set &	extra_elements
	)

inline

Does a pivot in bottom-left part of a given (3|4)-separation to shift the rank.

Parameters

matroid	Given matroid
matrix	A representation matrix for the matroid
split	Split of a given (3\|4)-separation

◆ pivot_top_right()

template<typename MatroidType , typename MatrixType >

void tu::detail::pivot_top_right	(	MatroidType &	matroid,
		MatrixType &	matrix,
		size_pair_t &	split,
		matroid_element_set &	extra_elements
	)

inline

Does a pivot in top-right part of a given (3|4)-separation to shift the rank.

Parameters

matroid	Given matroid
matrix	Represenation matrix of the given matroid
split	Split of a given (3\|4)-separation

◆ split_elements()

template<typename InputIterator , typename OutputIterator1 , typename OutputIterator2 >

std::pair<OutputIterator1, OutputIterator2> tu::detail::split_elements	(	InputIterator	first,
		InputIterator	beyond,
		OutputIterator1	rows,
		OutputIterator2	columns
	)

Classes

Functions

Function Documentation

◆ apply_mapping()

◆ copy_partial_column()

◆ copy_partial_row()

◆ create_indirect_matroid()

◆ enumerate_extension()

◆ extend_to_3_4_separation()

◆ find_column_witnesses()

◆ find_first_7_element_minor()

◆ find_row_witnesses()

◆ find_smallest_irregular_minor()

◆ find_witnesses()

◆ normalize_3_4_separation()

◆ pivot_bottom_left()

◆ pivot_top_right()

◆ split_elements()