source: trunk/CONSENSUS_TREE/CT_ctree.hxx

// ============================================================= //
//                                                               //
//   File      : CT_ctree.hxx                                    //
//   Purpose   : interface to consensus tree calculation         //
//                                                               //
//   Institute of Microbiology (Technical University Munich)     //
//   http://www.arb-home.de/                                     //
//                                                               //
// ============================================================= //

#ifndef CT_CTREE_HXX
#define CT_CTREE_HXX

#ifndef CT_COMMON_HXX
#include <CT_common.hxx>
#endif
#ifndef ARBTOOLS_H
#include <arbtools.h>
#endif
#ifndef ARBDBT_H
#include <arbdbt.h>
#endif
#ifndef _GLIBCXX_STRING
#include <string>
#endif
#ifndef TRIANGULAR_H
#include <triangular.h>
#endif

struct NT_NODE;
class  RB_INFO;

// -----------------------
//      ConsensusTree
//
// (Note: used directly from DIST/DI_matr.cxx)

class ConsensusTree : public SpeciesSpace, public DeconstructedTree { // derived from Noncopyable
    struct RB_INFO *rbtree(const NT_NODE *tree, TreeRoot *root);
    SizeAwareTree  *rb_gettree(const NT_NODE *tree);

public:
    ConsensusTree(const CharPtrArray& names_);

    __ATTR__USERESULT GB_ERROR insert_tree_weighted(const TreeNode *tree, int leafs, double weight, bool provideProgress);

    SizeAwareTree *get_consensus_tree(GB_ERROR& error);
};

// ------------------------------
//      ConsensusTreeBuilder

class ConsensusTreeBuilder : public TreeContainer {
    // wrapper for ConsensusTree
    // - automatically collects species occurring in added trees (has to be done by caller of ConsensusTree)
    // - uses much more memory than using ConsensusTree directly, since it stores all added trees
    //
    // Not helpful for consensing thousands of trees like bootstrapping does

    typedef std::vector<double> Weights;

    Weights weights;

public:
    void add(SizeAwareTree*& tree, const char *treename, double weight) {
        tree->get_tree_root()->find_innermost_edge().set_root(); // only wanted when building consensus tree

        // (currently) reordering trees before deconstructing no longer
        // affects the resulting consense tree (as performed as unit tests).
        //
        // tree->reorder_tree(BIG_BRANCHES_TO_TOP);
        // tree->reorder_tree(BIG_BRANCHES_TO_BOTTOM);
        // tree->reorder_tree(BIG_BRANCHES_TO_EDGE);

        TreeContainer::add(tree, treename);
        weights.push_back(weight);
    }

    SizeAwareTree *get(size_t& different_species, GB_ERROR& error) {
        arb_assert(!error);

        ConstStrArray species_names;
        get_species_names(species_names);

        different_species = get_species_count();

        double phase1_fraction;
        {
            size_t source_species_count = 0; // number of species added (all source trees; species counted once for each tree)
            for (size_t i = 0; i<get_tree_count();++i) {
                const TreeInfo& treeInfo  = get_tree_info(i);
                source_species_count     += treeInfo.species_count();
            }
            size_t target_edge_count = leafs_2_edges(different_species, UNROOTED);

            size_t common_species_count    = source_species_count-different_species;
            size_t noncommon_species_count = source_species_count-common_species_count;

            double O_deconstruct   = 3.0*noncommon_species_count*noncommon_species_count + target_edge_count*target_edge_count;
            double O_reconstruct   = (10.0*noncommon_species_count + target_edge_count) * 1.0e7;
            phase1_fraction = O_deconstruct / (O_deconstruct+O_reconstruct);
        }

        arb_progress progress(WEIGHTED, phase1_fraction);

        ConsensusTree ctree(species_names);
        {
            arb_progress deconstruct("deconstructing", get_tree_count());

            for (size_t i = 0; i<get_tree_count() && !error; ++i) {
                const TreeInfo&      treeInfo = get_tree_info(i);
                const SizeAwareTree *tree     = get_tree(i);

                error = ctree.insert_tree_weighted(tree, treeInfo.species_count(), weights[i], true);
                ++deconstruct;
                if (error) {
                    error = GBS_global_string("Failed to deconstruct '%s' (Reason: %s)", treeInfo.name(), error);
                }
                else {
                    error = deconstruct.error_if_aborted();
                }
            }
            if (error) deconstruct.done();
            ++progress;
        }

        if (error) return NULp;

#if defined(DEBUG)
        // if class ConsensusTree does depend on any local data,
        // instanciating another instance will interfere:
        ConsensusTree influence(species_names);
#endif

        {
            arb_progress reconstruct("reconstructing");
            SizeAwareTree *sat = ctree.get_consensus_tree(error);
            ++progress;
            return sat;
        }
    }

    char *get_tree_remark() const;
};


#else
#error CT_ctree.hxx included twice
#endif // CT_CTREE_HXX