Changeset 4608 for icGREP/icgrepdevel/icgrep
 Timestamp:
 Jun 18, 2015, 12:36:38 AM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4603 r4608 123 123 RECORD_TIMESTAMP(start_create_multiplex_graph); 124 124 am.createMultiplexSetGraph(); 125 const bool multiplex = am.generateMultiplexSets(rng );125 const bool multiplex = am.generateMultiplexSets(rng, 1); 126 126 RECORD_TIMESTAMP(end_create_multiplex_graph); 127 127 LOG("GenerateMultiplexSets: " << (end_create_multiplex_graph  start_create_multiplex_graph)); … … 130 130 131 131 RECORD_TIMESTAMP(start_mwis); 132 am. approxMaxWeightIndependentSet(rng);132 am.selectMultiplexSets(rng); 133 133 RECORD_TIMESTAMP(end_mwis); 134 LOG(" MaxWeightIndependentSet:" << (end_mwis  start_mwis));134 LOG("SelectMultiplexSets: " << (end_mwis  start_mwis)); 135 135 136 136 RECORD_TIMESTAMP(start_subset_constraints); … … 577 577 * @param RNG random number generator 578 578 **  */ 579 bool AutoMultiplexing::generateMultiplexSets(RNG & rng ) {579 bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) { 580 580 581 581 using Vertex = ConstraintGraph::vertex_descriptor; … … 592 592 N.reserve(15); 593 593 594 // Push all source nodes into the new independent set N595 for (auto v : make_iterator_range(vertices(mConstraintGraph))) { 596 const auto d = in_degree(v, mConstraintGraph);597 D[v] = d;598 if (d == 0) {599 N.push_back(v);600 }601 }602 603 for (;;) {604 605 // If we have at least 3 vertices in our two sets, try adding them to our multiplexing set.606 if ((N.size() + M.size()) >= 3) { 594 while (k) { 595 596 // Push all source nodes into the new independent set N 597 for (auto v : make_iterator_range(vertices(mConstraintGraph))) { 598 const auto d = in_degree(v, mConstraintGraph); 599 D[v] = d; 600 if (d == 0) { 601 N.push_back(v); 602 } 603 } 604 605 for (;;) { 606 607 607 addMultiplexSet(N, M); 608 } 609 610 if (remainingVerticies == 0) { 608 609 if (remainingVerticies == 0) { 610 break; 611 } 612 613 assert (N.size() > 0); 614 615 // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing 616 // at least one element from N, this will prevent us from adding the same multiplexing set again. 617 M.insert(M.end(), N.begin(), N.end()); N.clear(); 618 619 do { 620 // Randomly choose a vertex in S and discard it. 621 assert (!M.empty()); 622 const auto i = M.begin() + IntDistribution(0, M.size()  1)(rng); 623 const Vertex u = *i; 624 M.erase(i); 625 remainingVerticies; 626 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) { 627 const Vertex v = target(e, mConstraintGraph); 628 if ((D[v]) == 0) { 629 N.push_back(v); 630 } 631 } 632 } 633 while (N.empty() && remainingVerticies != 0); 634 } 635 636 if (k == 0) { 611 637 break; 612 638 } 613 639 614 // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing 615 // at least one element from N, this will prevent us from adding the same multiplexing set again. 616 M.insert(M.end(), N.begin(), N.end()); N.clear(); 617 618 do { 619 // Randomly choose a vertex in S and discard it. 620 assert (!M.empty()); 621 const auto i = M.begin() + RNGDistribution(0, M.size()  1)(rng); 622 const Vertex u = *i; 623 M.erase(i); 624 remainingVerticies; 625 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) { 626 const Vertex v = target(e, mConstraintGraph); 627 if ((D[v]) == 0) { 628 N.push_back(v); 629 } 630 } 631 } 632 while (N.empty() && remainingVerticies != 0); 640 N.clear(); 641 M.clear(); 633 642 } 634 643 635 644 return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph); 636 }637 638 /**  *639 * @brief is_power_of_2640 * @param n an integer641 **  */642 static inline bool is_power_of_2(const size_t n) {643 return ((n & (n  1)) == 0) ;644 645 } 645 646 … … 654 655 // between the "set vertex" and its members. We obtain these from "generateMultiplexSets". 655 656 656 // Note: this computes (âi=1 to N C(N,i)) * [1 + (âi=1 to M C(M,i))] = (2^N  1) * (2^M) combinations. 657 658 ChosenSet S; 659 for (int i = 0; i < N.size(); ++i) { 660 S.insert(N[i]); 661 addMultiplexSet(N, i + 1, M, 0, S); 662 S.erase(S.find(N[i])); 663 } 664 } 665 666 /**  * 667 * @brief addMultiplexSet 668 * @param N an independent set 669 * @param S an independent set 670 **  */ 671 void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const int i, 672 const IndependentSet & M, const int j, 673 ChosenSet & S) { 674 675 // TODO: Instead of building a graph, construct a trie of all members. 676 677 // Add S to the multiplex set if S >= 3 and not equal to 2^n for any n. 678 if (S.size() >= 3 && !is_power_of_2(S.size())) { 679 const auto v = add_vertex(mMultiplexSetGraph); 680 for (auto u : S) { 681 add_edge(v, u, mMultiplexSetGraph); 682 } 683 } 684 685 for (int ii = i; ii < N.size(); ++ii) { 686 S.insert(N[ii]); 687 addMultiplexSet(N, ii + 1, M, j, S); 688 S.erase(S.find(N[ii])); 689 } 690 691 for (int jj = j; jj < M.size(); ++jj) { 692 S.insert(M[jj]); 693 addMultiplexSet(N, i + 1, M, jj + 1, S); 694 S.erase(S.find(M[jj])); 695 } 696 697 } 698 699 /**  * 700 * @brief cardinalityWeight 701 * @param x the input number 702 * 703 * Returns 0 if x < 0; otherwise x^2. 704 **  */ 705 static inline ssize_t cardinalityWeight(const ssize_t x) { 706 const ssize_t xx = std::max<ssize_t>(x, 0); 707 return xx * xx; 708 } 709 710 /**  * 711 * @brief approxMaxWeightIndependentSet 657 if ((N.size() + M.size()) >= 3) { 658 const auto u = add_vertex(mMultiplexSetGraph); 659 for (const auto x : N) { 660 add_edge(u, x, mMultiplexSetGraph); 661 } 662 for (const auto y : M) { 663 add_edge(u, y, mMultiplexSetGraph); 664 } 665 } 666 } 667 668 /**  * 669 * @brief is_power_of_2 670 * @param n an integer 671 **  */ 672 static inline bool is_power_of_2(const size_t n) { 673 return ((n & (n  1)) == 0) ; 674 } 675 676 /**  * 677 * @brief log2_plus_one 678 **  */ 679 static inline size_t log2_plus_one(const size_t n) { 680 return std::log2<size_t>(n) + 1; // use a faster builtin function for this? 681 } 682 683 /**  * 684 * @brief approxMinWeightExactSubsetCover 712 685 * @param RNG random number generator 713 686 **  */ 714 void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) { 715 716 // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting 717 // from contracting one advance node edge with an adjacent vertex 718 719 const unsigned m = num_vertices(mConstraintGraph); 720 const unsigned n = num_vertices(mMultiplexSetGraph)  m; 721 722 IndependentSetGraph G(n); 723 724 MultiplexSetGraph::vertex_descriptor i = m; 725 graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end; 726 for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) { 727 G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), 0); 728 } 729 730 // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M. 731 // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent 732 // to two or more set vertices, add an edge between the corresponding vertices in G. 733 // I.e., make all vertices in G adjacent if their corresponding sets intersect. 734 735 for (i = 0; i != m; ++i) { 736 if (in_degree(i, mMultiplexSetGraph) > 1) { 737 graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end; 738 std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph); 739 for (auto ei = ei_begin; ei != ei_end; ++ei) { 740 for (auto ej = ei_begin; ej != ei; ++ej) { 741 // Note: ei and ej are incoming edges. The source is the set vertex, 742 add_edge(source(*ei, mMultiplexSetGraph)  m, source(*ej, mMultiplexSetGraph)  m, G); 743 } 744 } 745 } 746 } 747 748 boost::container::flat_set<IndependentSetGraph::vertex_descriptor> indices; 749 indices.reserve(n); 750 751 for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) { 752 int neighbourhoodWeight = 0; 753 int neighbours = 1; 754 graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end; 755 for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) { 756 ++neighbours; 757 neighbourhoodWeight += std::get<0>(G[*ai]); 758 } 759 std::get<1>(G[*vi]) = (std::get<0>(G[*vi]) * neighbours)  neighbourhoodWeight; 760 indices.insert(*vi); 761 } 762 // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem" 763 // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.) 764 765 while (!indices.empty()) { 766 767 // Select a vertex vi whose weight as greater than the average weight of its neighbours ... 768 ssize_t totalWeight = 0; 769 for (auto vi = indices.begin(); vi != indices.end(); ++vi) { 770 const ssize_t prevWeight = totalWeight; 771 totalWeight += cardinalityWeight(std::get<1>(G[*vi])); 772 assert (totalWeight >= prevWeight); 773 } 774 775 IndependentSetGraph::vertex_descriptor v = 0; 776 ssize_t remainingWeight = RNGDistribution(0, totalWeight  1)(rng); 777 assert (remainingWeight >= 0 && remainingWeight < totalWeight); 778 for (auto vi = indices.begin(); vi != indices.end(); ++vi) { 779 remainingWeight = cardinalityWeight(std::get<1>(G[*vi])); 780 if (remainingWeight < 0) { 781 v = *vi; 782 break; 783 } 784 } 785 assert (remainingWeight < 0); 786 787 // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively 788 // choose the set refered to by vi as one of our chosen independent sets. 789 790 for (auto u : make_iterator_range(adjacent_vertices(v, G))) { 791 assert (indices.count(u)); 792 indices.erase(indices.find(u)); 793 clear_out_edges(u + m, mMultiplexSetGraph); 794 const auto Wj = std::get<0>(G[u]); 795 for (auto w : make_iterator_range(adjacent_vertices(u, G))) { 796 797 // Let Vi be vertex i, Wi = weight of Vi, Di = degree of Vi, Ni = sum of the weights of vertices 798 // adjacent to Vi, and Ai be the weight difference of Vi w.r.t. its neighbours. Initially, 799 800 // Ai = (Wi * (Di + 1))  Ni 801 802 // Suppose Vj is removed from G and is adjacent to Vi. Then, 803 804 // Ai' = (Wi * (Di + 1  1))  (Ni  Wj) = (Ai  Wi + Wj) 805 806 const auto Wi = std::get<0>(G[w]); 807 auto & Ai = std::get<1>(G[w]); 808 Ai = Ai  Wi + Wj; 809 remove_edge(u, w, G); 810 } 811 remove_edge(v, u, G); 812 } 813 indices.erase(indices.find(v)); 687 void AutoMultiplexing::selectMultiplexSets(RNG &) { 688 689 using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator; 690 using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator; 691 using degree_t = MultiplexSetGraph::degree_size_type; 692 using vertex_t = MultiplexSetGraph::vertex_descriptor; 693 694 const size_t m = num_vertices(mConstraintGraph); 695 const size_t n = num_vertices(mMultiplexSetGraph)  m; 696 697 std::vector<degree_t> remaining(n, 0); 698 std::vector<vertex_t> chosen_set(m, 0); 699 700 for (unsigned i = 0; i != n; ++i) { 701 remaining[i] = out_degree(i + m, mMultiplexSetGraph); 702 } 703 704 for (;;) { 705 706 vertex_t k = 0; 707 degree_t w = 0; 708 for (vertex_t i = 0; i != n; ++i) { 709 const degree_t r = remaining[i]; 710 if (w < r) { 711 k = i; 712 w = r; 713 } 714 } 715 716 if (w < 3) { 717 break; 718 } 719 720 degree_t count = 0; 721 OutEdgeIterator ei, ei_end; 722 for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) { 723 const vertex_t j = target(*ei, mMultiplexSetGraph); 724 if (chosen_set[j] == 0) { 725 chosen_set[j] = (k + m); 726 InEdgeIterator ej, ej_end; 727 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) { 728 remaining[source(*ej, mMultiplexSetGraph)  m]; 729 ++count; 730 } 731 } 732 } 733 734 // If this contains 2^n elements for any n, return the one with the greatest number of unvisited sets. 735 if (is_power_of_2(count)) { 736 vertex_t j = 0; 737 degree_t w = 0; 738 for (vertex_t i = 0; i != m; ++i) { 739 if (chosen_set[i] == (k + m)) { 740 InEdgeIterator ej, ej_end; 741 degree_t r = 1; 742 for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) { 743 r += remaining[source(*ej, mMultiplexSetGraph)  m]; 744 } 745 if (w < r) { 746 j = i; 747 w = r; 748 } 749 } 750 } 751 assert (w > 0); 752 chosen_set[j] = 0; 753 InEdgeIterator ej, ej_end; 754 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) { 755 remaining[source(*ej, mMultiplexSetGraph)  m]++; 756 } 757 } 758 } 759 760 for (unsigned i = 0; i != m; ++i) { 761 InEdgeIterator ei, ei_end; 762 std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph); 763 for (auto next = ei; ei != ei_end; ei = next) { 764 ++next; 765 if (source(*ei, mMultiplexSetGraph) != chosen_set[i]) { 766 remove_edge(*ei, mMultiplexSetGraph); 767 } 768 } 814 769 } 815 770 … … 962 917 963 918 /**  * 964 * @brief log2_plus_one965 **  */966 static inline size_t log2_plus_one(const size_t n) {967 return std::log2<size_t>(n) + 1; // use a faster builtin function for this?968 }969 970 /**  *971 919 * @brief multiplexSelectedIndependentSets 972 920 **  */ 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4601 r4608 24 24 using ConstraintGraph = boost::adjacency_matrix<boost::directedS>; 25 25 using PathGraph = boost::adjacency_matrix<boost::undirectedS>; 26 using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 26 using RNG = std::mt19937; 27 using IntDistribution = std::uniform_int_distribution<RNG::result_type>; 28 using RealDistribution = std::uniform_real_distribution<double>; 29 using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, boost::no_property, double>; 27 30 using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>; 28 31 using ChosenSet = boost::container::flat_set<MultiplexSetGraph::vertex_descriptor>; 29 32 using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 30 33 using Advances = std::vector<Advance *>; 31 using RNG = std::mt19937;32 using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;33 34 using IndependentSet = std::vector<ConstraintGraph::vertex_descriptor>; 34 35 … … 40 41 bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const; 41 42 void createMultiplexSetGraph(); 42 bool generateMultiplexSets(RNG & rng );43 bool generateMultiplexSets(RNG & rng, unsigned k = 1); 43 44 void addMultiplexSet(const IndependentSet & N, const IndependentSet & M); 44 void addMultiplexSet(const IndependentSet & N, int i, const IndependentSet & M, int j, ChosenSet & S); 45 void approxMaxWeightIndependentSet(RNG & rng); 45 void selectMultiplexSets(RNG &); 46 46 void applySubsetConstraints(); 47 47 void multiplexSelectedIndependentSets() const;
Note: See TracChangeset
for help on using the changeset viewer.