Method InitSolution

Algorithms/azp.cpp:911–1045

}

void MaxpRegionMaker::InitSolution()
{
    // init unassigned areas
    for (int i=0; i<n; ++i) {
        unassignedAreas[i] = true;
    }

    // mark neighborless areas
    AssignAreasNoNeighs();

    // get max-p regions
    // get starting position: either from init_areas or randomly selected
    std::set<int> start_areas;
    for (int i=0; i<init_areas.size(); ++i) {
        start_areas.insert(init_areas[i]);
    }
    std::vector<int> _candidates;
    for (int i=0; i < n; i++) {
        if (start_areas.empty() || start_areas.find(i) == start_areas.end()) {
            _candidates.push_back(i);
        }
    }
    DataUtils::Shuffle(_candidates, rng);
    for (int i=0; i<init_areas.size(); ++i) {
        _candidates.insert(_candidates.begin(), init_areas[i]);
    }
    std::list<int> candidates;
    boost::unordered_map<int, bool> candidates_dict;
    for (int i=0; i<n;i++) {
        candidates.push_back( _candidates[i] );
        candidates_dict[ _candidates[i] ] = false;
    }

    // grow p regions using the starting positions above
    int r = 0;
    bool satisfy_lower_bound = false;

    while (!candidates.empty()) {
        int seed = candidates.front();
        candidates.pop_front();

        // try to grow it till threshold constraint is satisfied
        bool is_growing = true;
        bool reach_ub = false;
        bool reach_lb = false;
        std::set<int>::iterator it;

        // assign this seed with a new region
        boost::unordered_map<int, bool> region;
        region[seed] = true;
        candidates_dict[seed] = true;

        while (is_growing && !reach_ub && !reach_lb) {
            // each time, grow just one area, to avoid dominant grow
            // if two seeds are next to each other
            bool has_assign = false;
            std::set<int> buffer_areas = getBufferingAreas(region);
            for (it = buffer_areas.begin(); !has_assign && it != buffer_areas.end(); ++it) {