The MaximalSetSet Class

          First in thread      Previous in thread

I've been making heavy use of the MaximalSetSet class without providing very much information on it. This class is the workhorse of the split approach and deserves some attention. Since nearly all of the time in the code is spent in this class and the Set class, it is a prime candidate for improvement.

The purpose of the MaximalSetSet class is to maintain a set of sets that are maximal. A set is maximal with respect to a collection if it is not a subset of any other set in the collection.

For tonight, I'll present the non-experimental public methods for the class and discuss what they're supposed to do. I already see some things that I'll probably want to change a bit.

I intend to publish the source for this class and several other classes, currently written in C++, but it will take a fair amount of time and work to get them ready to share.

Public methods

class MaximalSetSet
{
    static
    bool
    GetFileHeader( const string &   filePathName,
                   int &            lowestElement,
                   int &            maxElements );

    static
    bool
    IsClique( Set &               candidateSet,
              const vector<Set>   augmentedAdjacencySets ) const;

    MaximalSetSet( const string &   label,
                   const int        lowestElement,
                   const int        maxSetSize,
                   const int        numBuckets,
                   const bool       ownerOfSets );

    ~MaximalSetSet();

    void
    AddSet( Set &   newSet );

    void
    AddSet( Set *        newSet,
            const bool   performSubsetSupersetTesting = true );

    void
    AddSets( MaximalSetSet &   otherMaximalSetSet,
             const bool        stealSets = false );

    void
    AddSets( vector<Set *>   sets,
             const bool      performSubsetSupersetTesting = true );

    void
    AddSetsStolenFrom( MaximalSetSet &   otherMaximalSetSet );

    void
    AddSetsWithoutSubsetSupersetTesting( vector<Set *>   sets,
                                         const bool      stealSets = false );

    void
    Complement();

    bool
    Contains( const Set &   set ) const;

    string
    GetLabel() const;

    void
    GetLargestSet( Set &   largestSet ) const;

    int
    GetLargestSetSize() const;

    int
    GetMaxSetSize() const;

    int
    GetNumMaximalSetSets() const;

    int
    GetNumMaximalSetSetsOfSize( const int   size ) const;

    bool
    GetOwnerOfSets() const;

    int
    GetRetentionThreshold() const;

    void
    GetVectorOfSetPointers( vector<Set *> &   vectorOfSets,
                            const int         minSize    =  -1,
                            const int         maxSize    =  -1,
                            const bool        stealSets  =  false );

    void
    GetVectorsOfSetPointers( const int         element1,
                             const int         element2,
                             vector<Set *> &   vectorOfSetsContainingBothElements,
                             vector<Set *> &   vectorOfOtherSets );

    bool
    ReadFromFile( const string &   filePathName );

    void
    RemoveAllSets( const bool   deleteSetsIfOwner  =  true );

    void
    RemoveSplittableSets( const int         element1,
                          const int         element2,
                          vector<Set *> &   vectorOfSplittableSets );

    void
    SetLabel( const string &   label );

    void
    SetOwnerOfSets( const bool   ownerOfSets );

    void
    SetRetentionThreshold( const int   retentionThreshold );

    bool
    WriteToFile( const string &   filePathName ) const;

    friend
    ostream &
    operator << ( ostream &               outStream,
                  const MaximalSetSet &   maximalSetSet );
}

Discussion

A MaximalSetSet instance has the following properties:

    string   label;
    int      lowestElement;
    int      maxSetSize;
    int      numBuckets;
    bool     ownerOfSets;
    int      retentionThreshold;

label is a name given to the MaximalSetSet. It is only used for display purposes.

lowestElement is either 0 or 1 and is 0 iff 0 is a valid element in a set.

maxSetSize is the maximum number of elements in a set, whether it is 0-based or 1-based

numBuckets is an implementation-dependent value but can be set to be the same as maxSetSize for now.

ownerOfSets is true of the instance is the owner of the sets that it contains and should delete them on destruction.

retentionThreshold is the minimum cardinality that a set must have to be retained within the instance.

The following methods are used to get and set these properties:

    MaximalSetSet( const string &   label,
                   const int        lowestElement,
                   const int        maxSetSize,
                   const int        numBuckets,
                   const bool       ownerOfSets );

    string
    GetLabel() const;

    int
    GetMaxSetSize() const;

    bool
    GetOwnerOfSets() const;

    int
    GetRetentionThreshold() const;

    void
    SetLabel( const string &   label );

    void
    SetOwnerOfSets( const bool   ownerOfSets );

    void
    SetRetentionThreshold( const int   retentionThreshold );

A MaximalSetSet object may be written to a file or read from a file. Since my Set implementation needs to be initialized with the maximum number of elements before any Set instance is created, it is necessary to peek into a MaximalSetSet file to determine maxSetSize and lowestElement and use those to initialize the Set class prior to reading a MaximalSetSet from a file into an instance.

These methods are used for working with files:

    static
    bool
    GetFileHeader( const string &   filePathName,
                   int &            lowestElement,
                   int &            maxElements );

    bool
    ReadFromFile( const string &   filePathName );

    bool
    WriteToFile( const string &   filePathName ) const;

When a set is added to a MaximalSetSet instance, subset testing needs to be performed to determine whether the new set is a subset of a set already in the collection (it will be discarded if this is so), and superset testing needs to be performed to determine whether the new set is a superset of any sets already in the collection (they will be discarded if this is so).

If we know for certain that the sets in a vector of sets are neither supersets or subsets of each other or of the sets in a MaximalSetSet instance, we can turn off superset/subset testing when we add these sets to the collection.

When adding sets from another MaximalSetSet instance, we may simply want to steal that other instance's sets rather than duplicate them.

The following methods are used to add sets to a MaximalSetSet instance:

    void
    AddSet( Set &   newSet );

    void
    AddSet( Set *        newSet,
            const bool   performSubsetSupersetTesting = true );

    void
    AddSets( MaximalSetSet &   otherMaximalSetSet,
             const bool        stealSets = false );

    void
    AddSets( vector<Set *>   sets,
             const bool      performSubsetSupersetTesting = true );

    void
    AddSetsStolenFrom( MaximalSetSet &   otherMaximalSetSet );

    void
    AddSetsWithoutSubsetSupersetTesting( vector<Set *>   sets,
                                         const bool      stealSets = false );

The Contains method is used to determine whether a MaximalSetSet instance contains a specified set:

    bool
    Contains( const Set &   set ) const;

These methods provide information on the sets in the collection having the largest cardinality. GetLargestSet retrieves a single exemplar set from what may be several having the largest cardinality.

    int
    GetLargestSetSize() const;

    int
    GetMaxSetSize() const;

These methods provide information on the number of maximal sets in the collection and in the collection that have the specified cardinality:

    int
    GetNumMaximalSetSets() const;

    int
    GetNumMaximalSetSetsOfSize( const int   size ) const;

This method is used to determine whether a set is a clique of the graph represented by the vector of augmented adjacency sets:

    static
    bool
    IsClique( Set &               candidateSet,
              const vector<Set>   augmentedAdjacencySets );

On occasion, we may want to retrieve sets from the collection without removing them from the collection. These methods perform this task. Note that the first method does have a stealSets parameter, so that it can also be used to remove sets from the collection.

    void
    GetVectorOfSetPointers( vector<Set *> &   vectorOfSets,
                            const int         minSize    =  -1,
                            const int         maxSize    =  -1,
                            const bool        stealSets  =  false );

    void
    GetVectorsOfSetPointers( const int         element1,
                             const int         element2,
                             vector<Set *> &   vectorOfSetsContainingBothElements,
                             vector<Set *> &   vectorOfOtherSets );

The split approach requires the removal of sets from a collection, after which they are split and their split children may be added back to the collection. This method is used to remove all sets that contain both specified elements (e.g. the end-nodes of a non-edge).

    void
    RemoveSplittableSets( const int         element1,
                          const int         element2,
                          vector<Set *> &   vectorOfSplittableSets );

Complementing a set is an easy task. Complementing a MaximalSetSet for graph G - constructing the MaximalSetSet instance for the complement of graph G - is not an easy task. This method is used to complement a MaximalSetSet:

    void
    Complement();

The following method is used to insert a MaximalSetSet instance into an output stream:

    friend
    ostream &
    operator << ( ostream &               outStream,
                  const MaximalSetSet &   maximalSetSet );

I'll discuss the implementation of this class within a few days.

          First in thread      Previous in thread

Copyright and Legal Notices

All Rights Reserved.