Changeset 9026:eb10e37b9a8a in orange
 Timestamp:
 09/27/11 11:56:41 (3 years ago)
 Branch:
 default
 Convert:
 474cbd080b07746da1ca1e835a91f1e0c2f65321
 Location:
 source/orange
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

source/orange/hclust.cpp
r8077 r9026 560 560 */ 561 561 562 struct 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 574 struct 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 562 588 m_element::m_element(THierarchicalCluster * _cluster, int _left, int _right): 563 589 cluster(_cluster), left(_left), right(_right) … … 585 611 } 586 612 613 bool m_element::operator== (const m_element & other) const 614 { 615 return cluster == other.cluster && left == other.left && right == other.right; 616 } 617 618 struct 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 587 626 ordering_element::ordering_element(): 588 627 left(NULL), u(1), m(1), … … 605 644 {} 606 645 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 607 667 // Return the minimum distance between elements in matrix 608 668 // … … 615 675 { 616 676 // 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; 618 679 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; 622 684 } 623 685 … … 640 702 }; 641 703 704 705 //#include <iostream> 706 //#include <cassert> 707 642 708 // This needs to be called with all left, right pairs to 643 709 // update all scores for cluster. 644 #include <iostream>645 #include <cassert>646 647 710 void partial_opt_ordering( 648 711 THierarchicalCluster & cluster, … … 666 729 w_iter++) 667 730 { 668 u = *u_iter; w = *w_iter; 731 u = *u_iter; 732 w = *w_iter; 669 733 float curr_min = std::numeric_limits<float>::infinity(); 670 734 int curr_k = 0, curr_m = 0; … … 694 758 695 759 if (M[m_left] + M[m_right_k0] + C >= curr_min){ 696 // M[m_element(&cluster, u, w)] = curr_min;697 760 break; 698 761 } … … 719 782 M[m_element(&cluster, w, u)] = curr_min; 720 783 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); 723 786 724 787 // assert(ordering.find(m_element(&cluster, u, w)) == ordering.end()); … … 730 793 } 731 794 732 void THierarchicalClusterOrdering::order_clusters(795 void order_clusters( 733 796 THierarchicalCluster & cluster, 734 797 TSymMatrix &matrix, 735 798 join_scores & M, 736 cluster_ordering & ordering) 799 cluster_ordering & ordering, 800 TProgressCallback * callback) 737 801 { 738 802 if (cluster.size() == 1) … … 741 805 return; 742 806 } 743 744 807 else if (cluster.branches>size() == 2) 745 808 { … … 747 810 PHierarchicalCluster right = cluster.branches>at(1); 748 811 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); 751 814 752 815 PHierarchicalCluster left_left = (!left>branches) ? left : left>branches>at(0); … … 755 818 PHierarchicalCluster right_right = (!right>branches) ? right : right>branches>at(1); 756 819 820 // 1.) 757 821 partial_opt_ordering(cluster, 758 822 left.getReference(), right.getReference(), … … 761 825 matrix, M, ordering); 762 826 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); 780 852 } 853 if (callback) 854 // TODO: count the number of already processed nodes. 855 callback>operator()(0.0, PHierarchicalCluster(&cluster)); 781 856 } 782 857 … … 788 863 } 789 864 790 void THierarchicalClusterOrdering::optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering)865 void optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering) 791 866 { 792 867 if (cluster>branches) … … 804 879 assert(!contains(mapping.begin() + left_right>first, 805 880 mapping.begin() + left_right>last, ord.m)); 806 std::cout << "Swapping left " << ord.m << endl;807 881 ord.left>swap(); 808 882 left_right = ord.left>branches>at(1); … … 820 894 assert(!contains(mapping.begin() + right_left>first, 821 895 mapping.begin() + right_left>last, ord.k)); 822 std::cout << "Swapping right " << ord.k << endl;823 896 ord.right>swap(); 824 897 right_left = ord.right>branches>at(0); … … 842 915 join_scores M; // scores 843 916 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()); 845 919 846 920 int u = 0, w = 0; 
source/orange/hclust.hpp
r8077 r9026 94 94 */ 95 95 96 struct m_element {97 THierarchicalCluster * cluster;98 int left;99 int right;100 96 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 index106 107 struct ordering_element {108 THierarchicalCluster * left;109 unsigned int u; // the left most (outer) index of left luster110 unsigned m; // the rightmost (inner) index of left cluster111 THierarchicalCluster * right;112 unsigned int w; // the right most (outer) index of the right cluster113 unsigned int k; // the left most (inner) index of the right cluster114 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;123 97 124 98 class ORANGE_API THierarchicalClusterOrdering: public TOrange { … … 126 100 __REGISTER_CLASS 127 101 128 PProgressCallback progress Callback; //P progress callback function102 PProgressCallback progress_callback; //P progress callback function 129 103 130 104 PHierarchicalCluster operator() (PHierarchicalCluster root, PSymMatrix matrix); 131 105 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);135 106 }; 136 107
Note: See TracChangeset
for help on using the changeset viewer.