Changeset 9026:eb10e37b9a8a in orange


Ignore:
Timestamp:
09/27/11 11:56:41 (3 years ago)
Author:
ales_erjavec <ales.erjavec@…>
Branch:
default
Convert:
474cbd080b07746da1ca1e835a91f1e0c2f65321
Message:

Fixed an error in HierarchicalClusterOrdering. Using tr1::unordered_map instead of std::map for scores

Location:
source/orange
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orange/hclust.cpp

    r8077 r9026  
    560560 */ 
    561561 
     562struct m_element { 
     563    THierarchicalCluster * cluster; 
     564    int left; 
     565    int right; 
     566 
     567    m_element(THierarchicalCluster * cluster, int left, int right); 
     568    m_element(const m_element & other); 
     569 
     570    bool operator< (const m_element & other) const; 
     571    bool operator== (const m_element & other) const; 
     572}; // cluster joined at left and right index 
     573 
     574struct ordering_element { 
     575    THierarchicalCluster * left; 
     576    unsigned int u; // the left most (outer) index of left luster 
     577    unsigned m; // the rightmost (inner) index of left cluster 
     578    THierarchicalCluster * right; 
     579    unsigned int w; // the right most (outer) index of the right cluster 
     580    unsigned int k; // the left most (inner) index of the right cluster 
     581 
     582    ordering_element(); 
     583    ordering_element(THierarchicalCluster * left, unsigned int u, unsigned m, 
     584            THierarchicalCluster * right, unsigned int w, unsigned int k); 
     585    ordering_element(const ordering_element & other); 
     586}; 
     587 
    562588m_element::m_element(THierarchicalCluster * _cluster, int _left, int _right): 
    563589    cluster(_cluster), left(_left), right(_right) 
     
    585611} 
    586612 
     613bool m_element::operator== (const m_element & other) const 
     614{ 
     615    return cluster == other.cluster && left == other.left && right == other.right; 
     616} 
     617 
     618struct m_element_hash 
     619{ 
     620    size_t operator()(const m_element & m) const 
     621    { 
     622        return ((size_t) m.cluster) * m.left * (m.right << 16); 
     623    } 
     624}; 
     625 
    587626ordering_element::ordering_element(): 
    588627    left(NULL), u(-1), m(-1), 
     
    605644{} 
    606645 
     646#define USE_TR1 1 
     647 
     648#if USE_TR1 
     649    #if _MSC_VER 
     650        #define HAVE_TR1_DIR 0 
     651    #else 
     652        #define HAVE_TR1_DIR 1 
     653    #endif 
     654    // Diffrent includes required  
     655    #if HAVE_TR1_DIR 
     656        #include <tr1/unordered_map> 
     657    #else 
     658        #include <unordered_map> 
     659    #endif 
     660    typedef std::tr1::unordered_map<m_element, double, m_element_hash> join_scores; 
     661    typedef std::tr1::unordered_map<m_element, ordering_element, m_element_hash> cluster_ordering; 
     662#else 
     663    typedef std::map<m_element, double> join_scores; 
     664    typedef std::map<m_element, ordering_element> cluster_ordering; 
     665#endif 
     666 
    607667// Return the minimum distance between elements in matrix 
    608668// 
     
    615675{ 
    616676//  TIntList::iterator iter1 = indices1.begin(), iter2 = indices2.begin(); 
    617     float mininum = std::numeric_limits<float>::infinity(); 
     677    float minimum = std::numeric_limits<float>::infinity(); 
     678    TIntList::iterator indices2; 
    618679    for (; indices1_begin != indices1_end; indices1_begin++) 
    619         for (; indices2_begin != indices2_end; indices2_begin++) 
    620             mininum = std::min(matrix.getitem(*indices1_begin, *indices2_begin), mininum); 
    621     return mininum; 
     680        for (indices2 = indices2_begin; indices2 != indices2_end; indices2++){ 
     681            minimum = std::min(matrix.getitem(*indices1_begin, *indices2), minimum); 
     682        } 
     683    return minimum; 
    622684} 
    623685 
     
    640702}; 
    641703 
     704 
     705//#include <iostream> 
     706//#include <cassert> 
     707 
    642708// This needs to be called with all left, right pairs to 
    643709// update all scores for cluster. 
    644 #include <iostream> 
    645 #include <cassert> 
    646  
    647710void partial_opt_ordering( 
    648711        THierarchicalCluster & cluster, 
     
    666729                w_iter++) 
    667730        { 
    668             u = *u_iter; w = *w_iter; 
     731            u = *u_iter; 
     732            w = *w_iter; 
    669733            float curr_min = std::numeric_limits<float>::infinity(); 
    670734            int curr_k = 0, curr_m = 0; 
     
    694758 
    695759                if (M[m_left] + M[m_right_k0] + C >= curr_min){ 
    696 //                  M[m_element(&cluster, u, w)] = curr_min; 
    697760                    break; 
    698761                } 
     
    719782            M[m_element(&cluster, w, u)] = curr_min; 
    720783 
    721             assert(M[m_element(&cluster, u, w)] == M[m_element(&cluster, u, w)]); 
    722             assert(M[m_element(&cluster, u, w)] == curr_min); 
     784//          assert(M[m_element(&cluster, u, w)] == M[m_element(&cluster, u, w)]); 
     785//          assert(M[m_element(&cluster, u, w)] == curr_min); 
    723786 
    724787//          assert(ordering.find(m_element(&cluster, u, w)) == ordering.end()); 
     
    730793} 
    731794 
    732 void THierarchicalClusterOrdering::order_clusters( 
     795void order_clusters( 
    733796        THierarchicalCluster & cluster, 
    734797        TSymMatrix &matrix, 
    735798        join_scores & M, 
    736         cluster_ordering & ordering) 
     799        cluster_ordering & ordering, 
     800        TProgressCallback * callback) 
    737801{ 
    738802    if (cluster.size() == 1) 
     
    741805        return; 
    742806    } 
    743  
    744807    else if (cluster.branches->size() == 2) 
    745808    { 
     
    747810        PHierarchicalCluster right = cluster.branches->at(1); 
    748811 
    749         order_clusters(left.getReference(), matrix, M, ordering); 
    750         order_clusters(right.getReference(), matrix, M, ordering); 
     812        order_clusters(left.getReference(), matrix, M, ordering, callback); 
     813        order_clusters(right.getReference(), matrix, M, ordering, callback); 
    751814 
    752815        PHierarchicalCluster  left_left = (!left->branches) ? left : left->branches->at(0); 
     
    755818        PHierarchicalCluster  right_right = (!right->branches) ? right : right->branches->at(1); 
    756819 
     820        // 1.) 
    757821        partial_opt_ordering(cluster, 
    758822                left.getReference(), right.getReference(), 
     
    761825                matrix, M, ordering); 
    762826 
    763         partial_opt_ordering(cluster, 
    764                 left.getReference(), right.getReference(), 
    765                 left_left.getReference(), left_right.getReference(), 
    766                 right_right.getReference(), right_left.getReference(), 
    767                 matrix, M, ordering); 
    768  
    769         partial_opt_ordering(cluster, 
    770                 left.getReference(), right.getReference(), 
    771                 left_right.getReference(), left_left.getReference(), 
    772                 right_left.getReference(), right_right.getReference(), 
    773                 matrix, M, ordering); 
    774  
    775         partial_opt_ordering(cluster, 
    776                 left.getReference(), right.getReference(), 
    777                 left_right.getReference(), left_left.getReference(), 
    778                 right_right.getReference(), right_left.getReference(), 
    779                 matrix, M, ordering); 
     827        if (right->branches) 
     828            // 2.) Switch right branches. 
     829            // (if there are no right branches the ordering has already been evaluated in 1.) 
     830            partial_opt_ordering(cluster, 
     831                    left.getReference(), right.getReference(), 
     832                    left_left.getReference(), left_right.getReference(), 
     833                    right_right.getReference(), right_left.getReference(), 
     834                    matrix, M, ordering); 
     835 
     836        if (left->branches) 
     837            // 3.) Switch left branches. 
     838            // (if there are no left branches the ordering has already been evaluated in 1. and 2.) 
     839            partial_opt_ordering(cluster, 
     840                    left.getReference(), right.getReference(), 
     841                    left_right.getReference(), left_left.getReference(), 
     842                    right_left.getReference(), right_right.getReference(), 
     843                    matrix, M, ordering); 
     844 
     845        if (left->branches && right->branches) 
     846            // 4.) Switch both branches. 
     847            partial_opt_ordering(cluster, 
     848                    left.getReference(), right.getReference(), 
     849                    left_right.getReference(), left_left.getReference(), 
     850                    right_right.getReference(), right_left.getReference(), 
     851                    matrix, M, ordering); 
    780852    } 
     853    if (callback) 
     854        // TODO: count the number of already processed nodes. 
     855        callback->operator()(0.0, PHierarchicalCluster(&cluster)); 
    781856} 
    782857 
     
    788863} 
    789864 
    790 void THierarchicalClusterOrdering::optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering) 
     865void optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering) 
    791866{ 
    792867    if (cluster->branches) 
     
    804879            assert(!contains(mapping.begin() + left_right->first, 
    805880                             mapping.begin() + left_right->last, ord.m)); 
    806             std::cout << "Swapping left " << ord.m << endl; 
    807881            ord.left->swap(); 
    808882            left_right = ord.left->branches->at(1); 
     
    820894            assert(!contains(mapping.begin() + right_left->first, 
    821895                             mapping.begin() + right_left->last, ord.k)); 
    822             std::cout << "Swapping right " << ord.k << endl; 
    823896            ord.right->swap(); 
    824897            right_left = ord.right->branches->at(0); 
     
    842915    join_scores M; // scores 
    843916    cluster_ordering ordering; 
    844     order_clusters(root.getReference(), matrix.getReference(), M, ordering); 
     917    order_clusters(root.getReference(), matrix.getReference(), M, ordering, 
     918            progress_callback.getUnwrappedPtr()); 
    845919 
    846920    int u = 0, w = 0; 
  • source/orange/hclust.hpp

    r8077 r9026  
    9494 */ 
    9595 
    96 struct m_element { 
    97     THierarchicalCluster * cluster; 
    98     int left; 
    99     int right; 
    10096 
    101     m_element(THierarchicalCluster * cluster, int left, int right); 
    102     m_element(const m_element & other); 
    103  
    104     bool operator< (const m_element & other) const; 
    105 }; // cluster joined at left and right index 
    106  
    107 struct ordering_element { 
    108     THierarchicalCluster * left; 
    109     unsigned int u; // the left most (outer) index of left luster 
    110     unsigned m; // the rightmost (inner) index of left cluster 
    111     THierarchicalCluster * right; 
    112     unsigned int w; // the right most (outer) index of the right cluster 
    113     unsigned int k; // the left most (inner) index of the right cluster 
    114  
    115     ordering_element(); 
    116     ordering_element(THierarchicalCluster * left, unsigned int u, unsigned m, 
    117             THierarchicalCluster * right, unsigned int w, unsigned int k); 
    118     ordering_element(const ordering_element & other); 
    119 }; 
    120  
    121 typedef std::map<m_element, double> join_scores; 
    122 typedef std::map<m_element, ordering_element> cluster_ordering; 
    12397 
    12498class ORANGE_API THierarchicalClusterOrdering: public TOrange { 
     
    126100    __REGISTER_CLASS 
    127101 
    128     PProgressCallback progressCallback; //P progress callback function 
     102    PProgressCallback progress_callback; //P progress callback function 
    129103 
    130104    PHierarchicalCluster operator() (PHierarchicalCluster root, PSymMatrix matrix); 
    131105 
    132 private: 
    133     void order_clusters(THierarchicalCluster & cluster, TSymMatrix &matrix, join_scores & M, cluster_ordering & ordering); 
    134     void optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering); 
    135106}; 
    136107 
Note: See TracChangeset for help on using the changeset viewer.