CMR  1.3.0
Classes | Functions
tu::detail Namespace Reference

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
permutationPermutation to return
mappingThe 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
matrixA given matrix
vectorVector to be filled
columnIndex of the column
first_rowIndex of the first row
beyond_rowIndex 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
matrixA given matrix
vectorVector to be filled
rowIndex of the row
first_columnIndex of the first column
beyond_columnIndex 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
matroidThe given matroid
matrixRepresentation matrix for the given matroid
worker_matrixMatrix to work on with the right permutation
row_mappingMapping vector for rows
column_mappingMapping vector for columns
minor_sizeSize of the current minor in the sequence of nested minors
ext_heightHeight of the extension
ext_widthWidth of the extension
separationSeparation to be returned
extra_elementsSet of matroid-elements to be filled with pivot-elements
enumerationIteration step in the whole enumeration.
next_enumerationNext enumeration
max_enumerationsTotal number of enumerations
next_percentNext percent value for a percent-jump
logLogger
cutLength 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
matroidThe original matrix
matrixA representation matrix for the original matroid
worker_matrixMatrix for the partition algorithm to work on
top_left_sizeSize of the first part of the minor-separation
bottom_right_sizeSize of the second part of the minor-separation
separationSeparation to return
extra_elementsSet 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
matroidGiven matroid
matrixA representation matrix for the matroid
splitSplit 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

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_minorsGiven sequence of nested minors
minor_sizeSize 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
matroidGiven matroid
matrixA representation matrix for the matroid
splitSplit 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

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
matroidA given matroid
matrixA representation matrix for the matroid
splitSplit of the 3-separation
extra_elementsSet 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
matroidGiven matroid
matrixA representation matrix for the matroid
splitSplit of a given (3|4)-separation
ranksRank 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
matroidGiven matroid
matrixA representation matrix for the matroid
splitSplit 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
matroidGiven matroid
matrixRepresenation matrix of the given matroid
splitSplit 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 
)