greedy_packing.cpp

#include <algorithm>
#include <gp-bnb/greedy_packing.hpp>
#include <iostream>

bool do_swap = true;

greedy_packing::greedy_packing(const graph& g, std::vector<node_id> A, std::vector<node_id> B)
    : graph_(g), a(A), b(B){
        if(do_swap && A.size() > B.size()){
            std::swap(a, b);
        }
        
    max_a = (graph_.num_nodes()+1)/2;
};

//breadth-first-search to determine neighbors of B
void greedy_packing::bfs(){

    visited.resize(graph_.num_nodes() +1, false);
    
    for(node_id node : b){
        q.push(node);
        visited[node] = true;
    }

    for(node_id node: a){
        visited[node] = true;
    }

    while(!q.empty()){
        node_id node = q.front();
        q.pop();

        std::vector<node_id> neighbors = graph_.get_adjacency(node);

        for(node_id v : neighbors){
            if(visited[v] == false){
                x.push_back(v);
            }
            visited[v] = true;
        }
    }

    return;
};


void greedy_packing::run(){
    flow_ = 0;

    //x per bfs konstruieren
    bfs();

    a_count = a.size();
    if(a_count >= max_a)
        return;

    //P konstruieren
    partitioning.resize(x.size());
    
    //dafür für jeden nachbarn von B einen eigenen Block
    for(unsigned int i = 0; i <x.size(); i++){
        partitioning[i].push_back(x[i]);
    }

    //dann jeweils kleinsten block um einen nachbarn erweitern
    //baue mit B zusammenhängende Partitionen (noch ohne lokale Suche) und sortiere nach Größe absteigend
    bool found_new_element = true;
    while (found_new_element) {
        found_new_element = false;
        for (std::vector<node_id> partition : partitioning) {
            for (node_id node : graph_.get_adjacency(partition.back())) {
                if (!visited[node]) {
                    partition.push_back(node);
                    visited[node] = true;
                    found_new_element = true;
                    break;
                }
            }
        }
    }


    //danach lokale suche um balance zu verbessern ?

    std::sort(partitioning.begin(), partitioning.end(), [](std::vector<node_id> a, std::vector<node_id> b) {
        return a.size() > b.size();
    });


    //füge von B unerreichbar knoten zu a hinzu (sind die knoten die
    //bei konstruktion von P "übrig bleiben")
    //danach füge Knoten aus größtem Block hinzu bis A* < n/2
    
    // behandle von B aus unnerreichbare Knoten
    for (node_id i = 1; i <= graph_.num_nodes(); i++) {
        if (!visited[i]) {
            a.push_back(i);
            a_count++;
            if (a_count >= max_a){
                return;
            }
        }
    }
    // packe greedy (erst hier wird flow erhöht)
    for (std::vector<node_id> partition : partitioning) {
        flow_++;
        for (node_id node : partition) {
            a.push_back(node);
            a_count++;
            if (a_count >= max_a){
                return;
            }
        }
    }

    return;

};