MRS  1.0
A C++ Class Library for Statistical Set Processing
Classes | Public Types | Public Member Functions
subpavings::MultiTreeManager Class Reference

A class which can look into the state space of SPSnode trees. More...

List of all members.

Classes

class  VertexInfo

Public Types

typedef std::set< VertexInfo > vertex_info_set
typedef std::map< size_t,
vertex_info_set > 		level_vertex_info_map

Public Member Functions

 MultiTreeManager ()
 default constructor
 ~MultiTreeManager ()
 Destructor.
void mapPavings ()
void makeAndMapOutcomeSpace (int toLevel, int maxDepth=0)
void makeOutcomeSpace (int toLevel, int maxDepth=0)
void makeFinalOutcomeSpace (int toLevel, int maxDepth=0)
void makeAndGraphOutcomeSpace (int toLevel, int maxDepth=0)
level_vertex_info_map makeLevelStringSumCountsMap (int toLevel)

Detailed Description

A class which can look into the state space of SPSnode trees.

Primary method graphOutcomeSpace creates a collection of all the different possible SPSnode trees down to a specified number of splits.

The number of distinct full binary SPStrees after k splits is the Catalan number Ck.

Member Function Documentation

void MultiTreeManager::makeAndGraphOutcomeSpace ( int  toLevel,
int  maxDepth = 0 
)

Make and graph outcome space from continual splitting to level toLevel

The outcome space is all the possible results of up to and including toLevel splits starting from a single root node, ie the number of trees in the outcome space for toLevel = k is the Catalan number Ck.

Pointers to the trees which result from the splitting are put into the data member pavings.

The method makes a dot graph showing all the unique leaf level patterns in the outcome space and the relationship between them, ie. which pattern can lead to which other patterns.

Parameters:
toLevelis the number of splits to go up to.
Postcondition:
the data member pavings will contain pointers to all the trees in the outcome space. 
{

  if (maxDepth == 0) maxDepth = toLevel;
  
    // clear the pavings
    pavings.clear();

    std::cout << "Making and graphing the outcome space" << std::endl;

    //Make a node with a dummy box
    ivector pavingBox(1);
    interval pavingInterval(0,1);
    pavingBox[1] = pavingInterval;
    SPSnode* root = new SPSnode(pavingBox);

    int i = 0;
    string baseFileName = "outputGraph";
    string suffix = ".dot";
    string s = getUniqueFilename(baseFileName, suffix);
    outputFile(s, "digraph G {"); // opening line

    // add it to the pavings data member collection
    pavings.push_back(root);

    // Send it into addtoOutComeSpace
    bool done = false;
    set<string> lines; // to check on uniqueness of lines for graph
    done = addToOutcomeSpaceAndGraph(s, toLevel, 1, root, maxDepth, lines);
    while (!done) {}

    outputFile(s, "}"); // closing line

    // make the image of the graph
    makeDotImage(s);

}
void MultiTreeManager::makeAndMapOutcomeSpace ( int  toLevel,
int  maxDepth = 0 
)

Get and map the outcome space resulting from splitting to level toLevel.

The outcome space is all the possible results of up to and including toLevel splits starting from a single root node, ie the number of trees in the outcome space for toLevel = k is the Catalan number Ck.

The map creates a summary of the frequencies of each leaf level pattern in the outcome space as a collection of ordered maps, one map for each number of leaves of any tree in the outcome space collection. A map for leaves L has keys the unique leaf level pattern summaries with L leaves and values the number of trees in the outcome space that has that leaf level pattern summary.

Console output and txt file output both give a summary of the frequencies and relative frequencies of each leaf level pattern, grouped by number of leaves.

Parameters:
toLevelis the number of splits to go up to.
Postcondition:
output file in tab delimited txt format of summary of the frequencies and relative frequencies of each leaf level pattern, grouped by number of leaves. 
{
  if (maxDepth == 0) maxDepth = toLevel;
  
    makeOutcomeSpace(toLevel, maxDepth);
    mapPavings();

}
void MultiTreeManager::makeFinalOutcomeSpace ( int  toLevel,
int  maxDepth = 0 
)

Make the final outcome space from continual splitting to level toLevel.

The outcome space is all the results with exactly toLevel splits starting from a single root node. The number of trees in the outcome space for toLevel = k is the Catalan number Ck but this method will produce as many copies of a tree as there are paths to that tree.

Pointers to the trees which result from the splitting are put into the data member pavings.

Parameters:
toLevelis the number of splits to go up to.
Postcondition:
the data member pavings will contain pointers to all the trees in the outcome space with toLevel splits, with multiple copies of each tree where there are multiple paths to it. 
{

  if (maxDepth == 0) maxDepth = toLevel;
  
    // clear the pavings
    pavings.clear();

    std::cout << "Making the outcome space" << std::endl;

    //Make a node with a dummy box
    ivector pavingBox(1);
    interval pavingInterval(0,1);
    pavingBox[1] = pavingInterval;
    SPSnode* root = new SPSnode(pavingBox);

    int i = 0;
    // add it to the pavings data member collection
    pavings.push_back(root);

    // Send it into addtoOutComeSpace
    bool done = false;
    done = getFinalLevelOutcomeSpace(toLevel, 1, root, maxDepth);
    

}
void MultiTreeManager::makeOutcomeSpace ( int  toLevel,
int  maxDepth = 0 
)

Make the outcome space from continual splitting to level toLevel.

The outcome space is all the possible results of up to and including toLevel splits starting from a single root node. The number of trees in the outcome space for toLevel = k is the Catalan number Ck but this method will produce as many copies of a tree as there are paths to that tree.

Pointers to the trees which result from the splitting are put into the data member pavings.

Parameters:
toLevelis the number of splits to go up to.
Postcondition:
the data member pavings will contain pointers to all the trees in the outcome space. 
{

  if (maxDepth == 0) maxDepth = toLevel;
  
    // clear the pavings
    pavings.clear();

    std::cout << "Making the outcome space" << std::endl;

    //Make a node with a dummy box
    ivector pavingBox(1);
    interval pavingInterval(0,1);
    pavingBox[1] = pavingInterval;
    SPSnode* root = new SPSnode(pavingBox);

    int i = 0;
    // add it to the pavings data member collection
    pavings.push_back(root);

    // Send it into addtoOutComeSpace
    bool done = false;
    done = addToOutcomeSpace(toLevel, 1, root, maxDepth);
    

}
void MultiTreeManager::mapPavings ( )

Map the leaf levels of trees currently in the pavings collection

Creates a collection of ordered maps, one map for each number of leaves of any tree in the pavings collection. A map for leaves L has keys the unique leaf level pattern summaries with L leaves and values the number of trees in the pavings collection that has that leaf level pattern summary.

Console output gives a summary of the frequencies and relative frequencies of each leaf level pattern, grouped by number of leaves. 

{
    // don't clear the current pavings! - that's what we use here

    // go through the pavings and record into the vector of shape count maps
    if (!pavings.empty()) {

         size_t numberPavings = pavings.size();

        cout << " mapping outcomes... there are " << numberPavings
                        << " outcomes " << endl;

        std::pair< OrdLeafDepthsMap::iterator, bool > mapBool;

        // what is the maximum number of leaves we have?
        set<size_t> leafSet;
        size_t count = 0;
        for (SPSnodePtrsItr sit = pavings.begin(); sit < pavings.end(); ++sit) {
            leafSet.insert((*sit)->getNumberLeaves());
            count ++;
        }

        size_t uniqueLeaves = leafSet.size();

        vector< OrdLeafDepthsMap > vecMaps(uniqueLeaves); // vector of maps

        for (SPSnodePtrsItr it = pavings.begin(); it < pavings.end(); ++it) {

            size_t thisLeaves = (*it)->getNumberLeaves();

            IntVec thisLevels;
            thisLevels  = (*it)->getLeafNodeLevels(thisLevels);

            int indexer = 0; // need to find index for maps with this no. leaves
            for (int j = 1; j < thisLeaves; ++j) {
                if (leafSet.count(j)) indexer++;
            }

            mapBool = vecMaps[indexer].insert(pair<IntVec, int> (thisLevels,1));

            if(!(mapBool.second)) // if its a new one, add
                (mapBool.first)->second +=1; // else increment count
        }

        string basefilename = "multimanager";
        string filename = getUniqueFilename (basefilename);

        outputFile(filename,
            "tree shape frequencies and relative frequencies in outcomes");
        std::ostringstream stm;
        stm << numberPavings << " outcomes altogether";
        outputFile(filename, stm.str());

        // print out the results
        std::cout << "tree shape frequencies (relative frequencies) in outcomes"
                << "\n";

        vector< OrdLeafDepthsMap >::iterator vecMapsIt = vecMaps.begin();

        for (set<size_t>::iterator lit = leafSet.begin(); lit != leafSet.end();
                                        ++lit) {

            OrdLeafDepthsMap::iterator mapIt;

            cout << "Leaves : " << "\t" << *lit << "\t("
                            << (*vecMapsIt).size() << " unique outcomes)\n";

            std::ostringstream stm1;
            stm1 << "Leaves : \t" << (*lit) << "\t" << (*vecMapsIt).size()
                            << "\tunique outcomes";
            outputFile(filename, stm1.str());

            for(mapIt = (*vecMapsIt).begin(); mapIt != (*vecMapsIt).end();
                                        ++mapIt) {

                IntVec levels = mapIt->first;

                size_t freq = (mapIt->second);
                double relfreq = (1.0*(mapIt->second))/numberPavings;

                cout << freq << " : " << "(\t"
                    << relfreq << ")\t";

                std::ostringstream stm2;
                stm2 << "\t\t\t\t" << freq << "\t"
                    << relfreq << "\t";
                string thisline =  stm2.str();

                outputFile(filename, thisline, levels);

                copy (levels.begin(), levels.end(),
                      ostream_iterator<int>(cout, ";"));
                cout << '\n';
            }
            vecMapsIt++; // move the iterator to the vec maps in step
        }
        std::cout << "Output file in " << filename << std::endl;
    }
    else std::cout << "There are no pavings in the outcome space to map"
                << std::endl;

}
The documentation for this class was generated from the following files:
 All Classes Namespaces Functions Variables Typedefs Enumerations Friends