cmtool::CMergeBookKeeper Class Reference

#include <CMergeBookKeeper.h>

Inheritance diagram for cmtool::CMergeBookKeeper:

Public Member Functions
	CMergeBookKeeper (unsigned short nclusters=0)
	Default constructor. More...
void	Reset (unsigned short nclusters=0)
	Reset method. More...
void	ProhibitMerge (unsigned short index1, unsigned short index2)
	Method to set a pair of clusters to prohibit from merging. More...
bool	MergeAllowed (unsigned short index1, unsigned short index2)
	Method to inqury if a combination is prohibited to merge. More...
void	Merge (unsigned short index1, unsigned short index2)
	Method to merge 2 clusters via index numbers. More...
std::vector< unsigned short >	GetMergedSet (unsigned short index1) const
bool	IsMerged (unsigned short index1, unsigned short index2) const
void	PassResult (std::vector< std::vector< unsigned short > > &result) const
std::vector< std::vector < unsigned short > >	GetResult () const
void	Combine (const CMergeBookKeeper &another)
void	Report () const

Protected Attributes
std::vector< std::vector< bool > >	_prohibit_merge
size_t	_out_cluster_count
	Number of output clusters. More...

Additional Inherited Members
Public Attributes inherited from std::vector< T >
T	elements
	STL member. More...

Detailed Description

A utility class for CMergeManager which merge clusters using merging algorithms. One of major task for CMergeManager is to keep track of which clusters to be merged in the original input. CMergeBookKeeper handles this part. It works with indexes. The user (primarily CMergeManager) provides number of clusters to CMergeBookKeeper's constructor. Then it can ask CMergeBookKeeper to merge two specific clusters by specifying index number of the cluster which has to be smaller than the previously specified number of clusters. CMergeBookKeeper keeps track of which clusters are asked to merge together, and it can be asked to return a vector of merged cluster indexes.

Definition at line 32 of file CMergeBookKeeper.h.

Constructor & Destructor Documentation

cmtool::CMergeBookKeeper::CMergeBookKeeper

(

unsigned short

nclusters = 0

)

Default constructor.

Definition at line 10 of file CMergeBookKeeper.cxx.

  {
    Reset(nclusters);
  }

Member Function Documentation

void cmtool::CMergeBookKeeper::Combine

(

const CMergeBookKeeper &

another

)

Method to combine with another CMergeBookKeeper instance.

Definition at line 278 of file CMergeBookKeeper.cxx.

  {
    // Check length compatibility between this instance's result and "another"
    std::vector<std::vector<unsigned short> > my_result;
    this->PassResult(my_result);
    if(my_result.size() != another.size()) {
      throw CMTException(Form("Input has an incompatible size (%zu != %zu)",
                                   my_result.size(),
                                   another.size())
                              );
      return;
    }

    // Check if "another" result is different from input
    std::vector<std::vector<unsigned short> > another_result;
    another.PassResult(another_result);
    if(another_result.size() >= my_result.size())
      throw CMTException(Form("The input has equal or more number of output clusters (%zu>=%zu)",
                                   another_result.size(),
                                   my_result.size())
                              );

    // Combine
    for(auto const& ares : another_result) {

      if(ares.size()==1) continue;

      // Get one of cluster to be used for merging
      unsigned short target = my_result.at(ares.at(0)).at(0);

      for(auto const &res_index : ares) {

        for(auto const &orig_index : my_result.at(res_index)) {

          if(target == orig_index) continue;

          else this->Merge(target,orig_index);

        }

      }

    }

  }

std::vector< unsigned short > cmtool::CMergeBookKeeper::GetMergedSet

(

unsigned short

index1

)

const

Method to retrieve a vector of cluster indexes which is merged with the input cluster index. All indexes here are regarding the original cluster index.

Definition at line 253 of file CMergeBookKeeper.cxx.

  {

    if( index1 >= this->size() )
      throw CMTException(Form("Invalid cluster index: %d ",index1));

    auto out_index = this->at(index1);
    std::vector<unsigned short> result;

    for(size_t i=0; i<this->size(); ++i)
      if( this->at(i) == out_index ) result.push_back(i);

    return result;
  }

std::vector<std::vector<unsigned short> > cmtool::CMergeBookKeeper::GetResult ( ) const

inline

Definition at line 73 of file CMergeBookKeeper.h.

    {
      std::vector<std::vector<unsigned short> > result;
      PassResult(result);
      return result;
    }

bool cmtool::CMergeBookKeeper::IsMerged	(	unsigned short	index1,
		unsigned short	index2
	)		const

Method to ask if a given 2 clusters are already merged. This method is expected to be much faster than obtaining a merged cluster sets from GetMergedIndexes and check if two clusters are merged.

Definition at line 244 of file CMergeBookKeeper.cxx.

  {
    if( index1 >= this->size() || index2 >= this->size() )
      throw CMTException(Form("Invalid cluster index: %d or %d",index1,index2));

    return this->at(index1) == this->at(index2);
  }

void cmtool::CMergeBookKeeper::Merge	(	unsigned short	index1,
		unsigned short	index2
	)

Method to merge 2 clusters via index numbers.

Definition at line 77 of file CMergeBookKeeper.cxx.

  {

    if(index1 == index2)

      throw CMTException(Form("<<%s>> Two input clusters identical (%d)",__FUNCTION__,index1));


    if( index1 >= this->size() || index2 >= this->size() )

      throw CMTException(Form("Input cluster index (%d and/or %d) out of range",index1,index2));

    auto out_index1 = this->at(index1);
    auto out_index2 = this->at(index2);

    if(out_index1 == out_index2) return;

    if(out_index2 < out_index1) std::swap(out_index1,out_index2);

    if(_prohibit_merge.at(out_index1).at(out_index2-out_index1))

      throw CMTException(Form("Clusters (%d,%d) correspond to output (%d,%d) which is prohibited to merge",
                                   index1,index2,
                                   out_index1,out_index2));

    //
    // Merge cluster indexes
    //
    for(auto &v : (*this)) {

      if( v == out_index1 || v == out_index2 )
        v = out_index1;
      else if( v > out_index2 )
        v -= 1;
    }

    //
    // Merge prohibit rule
    //
    // (1) handle index < out_index1
    for(size_t index=0; index < out_index1; ++index) {

      size_t tmp_out_index1 = out_index1 - index;
      size_t tmp_out_index2 = out_index2 - index;

      _prohibit_merge.at(index).at(tmp_out_index1) = ( _prohibit_merge.at(index).at(tmp_out_index1)
                                                       ||
                                                       _prohibit_merge.at(index).at(tmp_out_index2)
                                                       );

      for(size_t in_index=tmp_out_index2;
          //in_index < _prohibit_merge.at(index).size() - 1;
          in_index < (_out_cluster_count - index - 1);
          ++in_index) {

        /*
        if(in_index >= (_out_cluster_count - 1 - index))

          _prohibit_merge.at(index).at(in_index) = false;

        else
        */
        _prohibit_merge.at(index).at(in_index) = _prohibit_merge.at(index).at(in_index+1);
      }

      //(*_prohibit_merge.at(index).rbegin()) = false;
      _prohibit_merge.at(index).at(_out_cluster_count - index - 1) = false;

    }

    // (2) handle index == out_index1
    for(size_t in_index = 1;
        //in_index < _prohibit_merge.at(out_index1).size() - 1;
        in_index < (_out_cluster_count - out_index1 - 1);
        ++in_index) {
      if( (in_index + out_index1) < out_index2 ) {
        /*
        std::cout<<Form("Inspecting1 : (%d,%zu) to (%zu,%zu)",
                        out_index1,in_index,
                        (in_index + out_index1),(out_index2 - (in_index+out_index1)))
                 << std::endl;
        */
        _prohibit_merge.at(out_index1).at(in_index) = ( _prohibit_merge.at(out_index1).at(in_index)
                                                        ||
                                                        _prohibit_merge.at(in_index + out_index1).at(out_index2 - (in_index+out_index1))
                                                        );
      }
      else {
        /*
        std::cout<<Form("Inspecting2 : (%d,%zu) to (%d,%zu) ...",
                        out_index1,in_index+1,
                        out_index2,(in_index+out_index1-out_index2));
        if(_prohibit_merge.at(out_index1).at(in_index+1)) std::cout<<"T";
        else std::cout<<"F";
        std::cout<<",";
        if(_prohibit_merge.at(out_index2).at(in_index+out_index1-out_index2)) std::cout<<"T";
        else std::cout<<"F";
        std::cout<<std::endl;
        */
        _prohibit_merge.at(out_index1).at(in_index) = ( _prohibit_merge.at(out_index1).at(in_index+1)
                                                        ||
                                                        _prohibit_merge.at(out_index2).at(in_index+1+out_index1-out_index2)
                                                        );

      }
    }
    //(*_prohibit_merge.at(out_index1).rbegin()) = false;
    _prohibit_merge.at(out_index1).at(_out_cluster_count - out_index1 - 1) = false;

    // (3) handle out_index1 < index < out_index2
    for(size_t index = out_index1+1;
        index < out_index2;
        ++index){
      for(size_t in_index = (out_index2 - index);
          //in_index < (_prohibit_merge.at(index).size() - 1);
          in_index < (_out_cluster_count - index - 1);
          ++in_index)

        _prohibit_merge.at(index).at(in_index) = _prohibit_merge.at(index).at(in_index+1);

      //(*_prohibit_merge.at(index).rbegin()) = false;
      _prohibit_merge.at(index).at(_out_cluster_count - index - 1) = false;
    }
    // (4) handle out_index2 <= index
    for(size_t index = out_index2;
        //index < (_prohibit_merge.size() - 1);
        index < (_out_cluster_count - 1);
        ++index) {

      for(size_t in_index = 0;
          in_index < _prohibit_merge.at(index).size();
          ++in_index)

        if(in_index < _prohibit_merge.at(index+1).size())
          _prohibit_merge.at(index).at(in_index) = _prohibit_merge.at(index+1).at(in_index);

        else
          _prohibit_merge.at(index).at(in_index) = false;

    }

    _out_cluster_count -=1;

  }

bool cmtool::CMergeBookKeeper::MergeAllowed	(	unsigned short	index1,
		unsigned short	index2
	)

Method to inqury if a combination is prohibited to merge.

Definition at line 53 of file CMergeBookKeeper.cxx.

  {

    if(index1 == index2)

      throw CMTException(Form("<<%s>> Two input clusters identical (%d)",__FUNCTION__,index1));


    if( index1 >= this->size() || index2 >= this->size() )

      throw CMTException(Form("Input cluster index (%d and/or %d) out of range",index1,index2));

    auto out_index1 = this->at(index1);
    auto out_index2 = this->at(index2);

    if(out_index1 == out_index2) return true;

    if(out_index2 < out_index1) std::swap(out_index1,out_index2);

    return !(_prohibit_merge.at(out_index1).at(out_index2-out_index1));

  }

void cmtool::CMergeBookKeeper::PassResult

(

std::vector< std::vector< unsigned short > > &

result

)

const

A method to get the full result. The return is a vector of merged cluster indexes (which is a vector of original cluster indexes).

Definition at line 268 of file CMergeBookKeeper.cxx.

  {

    result.clear();
    result.resize(_out_cluster_count, std::vector<unsigned short>());

    for(size_t i=0; i<this->size(); ++i)
      result.at(this->at(i)).push_back(i);
  }

void cmtool::CMergeBookKeeper::ProhibitMerge	(	unsigned short	index1,
		unsigned short	index2
	)

Method to set a pair of clusters to prohibit from merging.

Definition at line 30 of file CMergeBookKeeper.cxx.

  {
    if(index1 == index2)

      throw CMTException(Form("<<%s>> Two input clusters identical (%d)",__FUNCTION__,index1));


    if( index1 >= this->size() || index2 >= this->size() )

      throw CMTException(Form("Input cluster index (%d and/or %d) out of range",index1,index2));

    auto out_index1 = this->at(index1);
    auto out_index2 = this->at(index2);

    if(out_index1 == out_index2)
      throw CMTException(Form("Cluster %d and %d already merged!",index1,index2));

    if(out_index2 < out_index1) std::swap(out_index1,out_index2);

    _prohibit_merge.at(out_index1).at(out_index2-out_index1) = true;

  }

void cmtool::CMergeBookKeeper::Report

(

)

const

Definition at line 222 of file CMergeBookKeeper.cxx.

  {
    std::cout<<"Merge Result:"<<std::endl;
    for(auto const& v : *this)
      std::cout<<v<< " ";
    std::cout<<std::endl<<std::endl;

    std::cout<<"Prohibit Status:"<<std::endl;
    for(auto const &bs : _prohibit_merge) {

      for(auto const &b : bs) {

        if(b) std::cout<<"\033[93mT\033[00m ";
        else std::cout<<"\033[95mF\033[00m ";

      }
      std::cout<<std::endl;
    }
    std::cout<<std::endl;

  }

void cmtool::CMergeBookKeeper::Reset

(

unsigned short

nclusters = 0

)

Reset method.

Definition at line 15 of file CMergeBookKeeper.cxx.

  {
    _prohibit_merge.clear();
    _prohibit_merge.reserve(nclusters);
    std::vector<unsigned short>::clear();
    std::vector<unsigned short>::reserve(nclusters);

    for(size_t i=0; i<nclusters; ++i) {
      this->push_back(i);
      _prohibit_merge.push_back(std::vector<bool>(nclusters-i,false));
    }
    _out_cluster_count = nclusters;

  }

Member Data Documentation

size_t cmtool::CMergeBookKeeper::_out_cluster_count

protected

Number of output clusters.

Definition at line 96 of file CMergeBookKeeper.h.

std::vector<std::vector<bool> > cmtool::CMergeBookKeeper::_prohibit_merge

protected

A 2D-map vector that stores pair of clusters for which merging is prohibited

Definition at line 93 of file CMergeBookKeeper.h.

---

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

• CMergeBookKeeper.h
• CMergeBookKeeper.cxx