operations_research::sat::SubsetsDetector< Storage > Class Template Reference

#include <inclusion.h>

Public Member Functions
	SubsetsDetector (const Storage &storage, TimeLimit *time_limit)
void	SetWorkLimit (uint64_t work_limit)
void	StopProcessingCurrentSubset ()
void	StopProcessingCurrentSuperset ()
void	Stop ()
uint64_t	work_done () const
bool	Stopped () const
	process () can call StopProcessingCurrentSuperset() to abort early - process() can call StopProcessingCurrentSubset() to never consider void IndexAllStorageAsSubsets()
void	FindSubsets (absl::Span< const int > superset, int *next_index_to_try, const std::function< void(int subset)> &process)

Detailed Description

template<class Storage>
class operations_research::sat::SubsetsDetector< Storage >

Similar API and purpose to InclusionDetector. But this one is a bit simpler and faster if it fit your usage. This assume an initial given set of potential subsets, that will be queried against supersets one by one.

Definition at line 171 of file inclusion.h.

Constructor & Destructor Documentation

SubsetsDetector()

template<class Storage>

operations_research::sat::SubsetsDetector< Storage >::SubsetsDetector ( const Storage & storage, TimeLimit * time_limit )

inline

Definition at line 173 of file inclusion.h.

Member Function Documentation

FindSubsets()

template<typename Storage>

void operations_research::sat::SubsetsDetector< Storage >::FindSubsets ( absl::Span< const int > superset, int * next_index_to_try, const std::function< void(int subset)> & process )

inline

We check each time our work_done_ has increased by more than this.

Compute the signature and also resize vector if needed. We want a signature that is order invariant and is compatible with inclusion.

Find any subset included in current superset.

Bitset should be cleared.

Do a bunch of quick checks. The second one is optimized for size 2 which happens a lot in our usage of merging clique with implications.

Long check with bitset.

Todo

(user): Technically we do not need to check the watched position or the "other element" position, we could do that by permuting them first or last and iterating on a subspan. However, in many slow situation, we have millions of size 2 sets, and the time is dominated by the first check.

Todo

(user): Remove this and the more complex API need once we move class.

Cleanup.

Definition at line 480 of file inclusion.h.

process()

template<class Storage>

operations_research::sat::SubsetsDetector< Storage >::process

(

)

Different API than InclusionDetector. 1/ Add all potential subset to the storage_. 2/ Call IndexAllStorageAsSubsets() 3/ Call one or more time FindSubsets(). that subset again. 4/ Call Stop() to reclaim some memory.

Optimization: next_index_to_try is an index in superset that can be used to skip some position for which we already called FindSubsets().

SetWorkLimit()

template<class Storage>

void operations_research::sat::SubsetsDetector< Storage >::SetWorkLimit ( uint64_t work_limit )

inline

Definition at line 176 of file inclusion.h.

Stop()

template<class Storage>

void operations_research::sat::SubsetsDetector< Storage >::Stop ( )

inline

Definition at line 179 of file inclusion.h.

Stopped()

template<class Storage>

bool operations_research::sat::SubsetsDetector< Storage >::Stopped ( ) const

inline

Definition at line 186 of file inclusion.h.

StopProcessingCurrentSubset()

template<class Storage>

void operations_research::sat::SubsetsDetector< Storage >::StopProcessingCurrentSubset ( )

inline

Definition at line 177 of file inclusion.h.

StopProcessingCurrentSuperset()

template<class Storage>

void operations_research::sat::SubsetsDetector< Storage >::StopProcessingCurrentSuperset ( )

inline

Definition at line 178 of file inclusion.h.

work_done()

template<class Storage>

uint64_t operations_research::sat::SubsetsDetector< Storage >::work_done ( ) const

inline

Definition at line 185 of file inclusion.h.

---

The documentation for this class was generated from the following file:

• ortools/sat/inclusion.h