A class to get the best subset by taking the element with the highest quality indicator and throwing away all incompatible ones. More...
#include <SubsetSimple.h>
Public Member Functions | |
| template<class GetQI , class AreCompatible > | |
| void | calculateBestSet (AreCompatible areCompatible, GetQI getQI) |
| Calculates the best set using a very simple method. More... | |
 Public Member Functions inherited from KiTrack::Subset< T > | |
| void | add (T newElement) |
| Adds an element. | |
| void | add (std::vector< T > newElements) |
| Adds a vector of elements. | |
| std::vector< T > | getAccepted () |
| std::vector< T > | getRejected () |
Additional Inherited Members | |
| Protected Attributes inherited from KiTrack::Subset< T > | |
| std::vector< T > | _elements |
| std::vector< T > | _acceptedElements |
| std::vector< T > | _rejectedElements |
Detailed Description
template<class T>
class KiTrack::SubsetSimple< T >
A class to get the best subset by taking the element with the highest quality indicator and throwing away all incompatible ones.
On the remaining elements repeat the procedure.
Member Function Documentation
| void KiTrack::SubsetSimple< T >::calculateBestSet | ( | AreCompatible | areCompatible, |
| GetQI | getQI | ||
| ) |
Calculates the best set using a very simple method.
After this the results can be accessed with the getAccepted() and getRejected() methods (provided by the baseclass Subset).
This is a templated class to allow the reuse with objects from different. The goal is this: if you have a set of things that are somehow compatible or incompatible with each other and you want a subset that only contains compatible ones and has a high quality, to find this subset.
For example: you plan a concert where a lot of different artists shall perform together. You have 20 that you are interested in asking. BUT: not all of them get along together very well. So artist 1 might be incompatible with artist 2 and 7 for some arbitrary reasons. And artist 2 is incompatible with artist 1,3 and 13 and so on. In order not to completely mess up the concert you can only invite artists who are entirely compatible with each other. AND: not all artists are equal: some are really famous and some are pretty mediocre. So you want to find a set of artists with the highest possible quality which is completely compatible.
This is done by this class.
The algorithm used for it is this: take the element with the highest quality and accept it. Reject all other elements that are incompatible with it. From the remaining elements redo the same with the next best element. In our artist example: take the biggest star and throw out all he doesn't get allong with. From the remaining artists (those who do get along with the biggest star) pick next famous one. Once again kick out all that don't get along with him and so on.
In order to work it needs to know two things: how to calculate the quality of an element and how to determine if two elements are compatible. These are of course things the user has to provide. For both a functor object is needed.
Here is how it could look like in the artist example:
class AristQI{
public:
// returns the quality of an artist (a value between 0 and 1, 0 being bad and 1 being fantastic)
inline double operator()( Artist artist ){
return artist.numberOfFans()/nPeopleOnEarth; // a number between 0 and 1
}
};
class ArtistCompatibility{
public:
// returns whether two artists are compatible
inline bool operator()( Artist artistA, Artist artistB ){
if( artistA.hates( artistB ) ) return false;
else return true;
}
};
//Somewhere within the program:
ArtistCompatibility comp;
ArtistQI qi;
SubsetHopfieldNN< Artist > subset;
subset.add( vecOfArtists );
subset.calculateBestSet( comp, qi );
std::vector< Artist > artistsToInvite = subset.getAccepted();
std::vector< Artist > artistsToStayAtHome = subset.getRejected(); @param areCompatible a functor of type bool( T, T ) that should tell whether two elements are compatible
or not.
@param getQI a functor of type double( T ) that returns the quality of an element and should range between 0 and 1.
The documentation for this class was generated from the following file:
