carl::covering::heuristic Namespace Reference

Functions
std::optional< Bitset >	exact_of_size (const SetCover &sc, const Bitset &uncovered, const std::vector< std::size_t > &id_map, std::size_t size)
Bitset	exact (SetCover &sc)
	Exact "heuristic": Computes a minimum set cover. More...
Bitset	greedy (SetCover &sc)
	Simple greedy heuristic: Selects the largest remaining set until all elements are covered. More...
Bitset	greedy_bounded (SetCover &sc, std::size_t bound=12)
	Bounded greedy heuristic: Selects the largest remaining set until at most bound constraints remain. More...
Bitset	greedy_weighted (SetCover &sc, const std::vector< double > &weights, std::size_t bound=0)
	Weighted greedy heuristic: Selects the largest remaining set according to the given weight function until at most bound constraints remain. More...
template<typename T , typename F >
auto	greedy_weighted (TypedSetCover< T > &tsc, F &&weight, std::size_t bound=0)
	Weighted greedy heuristic: Selects the largest remaining set according to the given weight function until at most bound constraints remain. More...
Bitset	remove_duplicates (SetCover &sc)
	Preprocessing heuristic: Compresses the matrix by removing duplicate columns. More...
Bitset	select_essential (SetCover &sc)
	Preprocessing heuristic: Selects essential sets which are the only once covering some element. More...
Bitset	trivial (SetCover &sc)
	Trivial heuristic: select all sets. More...

Function Documentation

exact()

Bitset carl::covering::heuristic::exact

(

SetCover &

sc

)

Exact "heuristic": Computes a minimum set cover.

Definition at line 35 of file exact.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

exact_of_size()

std::optional<Bitset> carl::covering::heuristic::exact_of_size	(	const SetCover &	sc,
		const Bitset &	uncovered,
		const std::vector< std::size_t > &	id_map,
		std::size_t	size
	)

Definition at line 13 of file exact.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

greedy()

Bitset carl::covering::heuristic::greedy

(

SetCover &

sc

)

Simple greedy heuristic: Selects the largest remaining set until all elements are covered.

Definition at line 7 of file greedy.cpp.

Here is the call graph for this function:

greedy_bounded()

Bitset carl::covering::heuristic::greedy_bounded	(	SetCover &	sc,
		std::size_t	bound
	)

Bounded greedy heuristic: Selects the largest remaining set until at most bound constraints remain.

Definition at line 19 of file greedy.cpp.

Here is the call graph for this function:

greedy_weighted() [1/2]

Bitset carl::covering::heuristic::greedy_weighted	(	SetCover &	sc,
		const std::vector< double > &	weights,
		std::size_t	bound
	)

Weighted greedy heuristic: Selects the largest remaining set according to the given weight function until at most bound constraints remain.

Definition at line 31 of file greedy.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

greedy_weighted() [2/2]

template<typename T , typename F >

auto carl::covering::heuristic::greedy_weighted	(	TypedSetCover< T > &	tsc,
		F &&	weight,
		std::size_t	bound = 0
	)

Weighted greedy heuristic: Selects the largest remaining set according to the given weight function until at most bound constraints remain.

Definition at line 31 of file greedy.h.

Here is the call graph for this function:

remove_duplicates()

Bitset carl::covering::heuristic::remove_duplicates

(

SetCover &

sc

)

Preprocessing heuristic: Compresses the matrix by removing duplicate columns.

The order of the columns changes!

Definition at line 9 of file remove_duplicates.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

select_essential()

Bitset carl::covering::heuristic::select_essential

(

SetCover &

sc

)

Preprocessing heuristic: Selects essential sets which are the only once covering some element.

Definition at line 7 of file select_essential.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

trivial()

Bitset carl::covering::heuristic::trivial

(

SetCover &

sc

)

Trivial heuristic: select all sets.

Definition at line 8 of file trivial.cpp.

Here is the call graph for this function: