Changeset 4608


Ignore:
Timestamp:
Jun 18, 2015, 12:36:38 AM (4 years ago)
Author:
nmedfort
Message:

Replaced independent set approximation for multiplex set selection with the greedy set cover algorithm.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4603 r4608  
    123123    RECORD_TIMESTAMP(start_create_multiplex_graph);
    124124    am.createMultiplexSetGraph();
    125     const bool multiplex = am.generateMultiplexSets(rng);
     125    const bool multiplex = am.generateMultiplexSets(rng, 1);
    126126    RECORD_TIMESTAMP(end_create_multiplex_graph);
    127127    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
     
    130130
    131131        RECORD_TIMESTAMP(start_mwis);
    132         am.approxMaxWeightIndependentSet(rng);
     132        am.selectMultiplexSets(rng);
    133133        RECORD_TIMESTAMP(end_mwis);
    134         LOG("MaxWeightIndependentSet: " << (end_mwis - start_mwis));
     134        LOG("SelectMultiplexSets:    " << (end_mwis - start_mwis));
    135135
    136136        RECORD_TIMESTAMP(start_subset_constraints);
     
    577577 * @param RNG random number generator
    578578 ** ------------------------------------------------------------------------------------------------------------- */
    579 bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
     579bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) {
    580580
    581581    using Vertex = ConstraintGraph::vertex_descriptor;
     
    592592    N.reserve(15);
    593593
    594     // Push all source nodes into the new independent set N
    595     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
    607607            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) {
    611637            break;
    612638        }
    613639
    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();
    633642    }
    634643
    635644    return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
    636 }
    637 
    638 /** ------------------------------------------------------------------------------------------------------------- *
    639  * @brief is_power_of_2
    640  * @param n an integer
    641  ** ------------------------------------------------------------------------------------------------------------- */
    642 static inline bool is_power_of_2(const size_t n) {
    643     return ((n & (n - 1)) == 0) ;
    644645}
    645646
     
    654655    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    655656
    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 ** ------------------------------------------------------------------------------------------------------------- */
     672static 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 ** ------------------------------------------------------------------------------------------------------------- */
     679static 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
    712685 * @param RNG random number generator
    713686 ** ------------------------------------------------------------------------------------------------------------- */
    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));
     687void 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        }
    814769    }
    815770
     
    962917
    963918/** ------------------------------------------------------------------------------------------------------------- *
    964  * @brief log2_plus_one
    965  ** ------------------------------------------------------------------------------------------------------------- */
    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 /** ------------------------------------------------------------------------------------------------------------- *
    971919 * @brief multiplexSelectedIndependentSets
    972920 ** ------------------------------------------------------------------------------------------------------------- */
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4601 r4608  
    2424    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    2525    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>;
    2730    using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
    2831    using ChosenSet = boost::container::flat_set<MultiplexSetGraph::vertex_descriptor>;
    2932    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3033    using Advances = std::vector<Advance *>;
    31     using RNG = std::mt19937;
    32     using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
    3334    using IndependentSet = std::vector<ConstraintGraph::vertex_descriptor>;
    3435
     
    4041    bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const;
    4142    void createMultiplexSetGraph();
    42     bool generateMultiplexSets(RNG & rng);   
     43    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
    4344    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 &);
    4646    void applySubsetConstraints();
    4747    void multiplexSelectedIndependentSets() const;
Note: See TracChangeset for help on using the changeset viewer.