greedy_packing.cpp

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

bool do_swap = true;

greedy_packing::greedy_packing(graph& g, std::vector<node_id> A, std::vector<node_id> B, incremental_bfs& ibfs, bool with_flow)
    : graph_(g), a(A), b(B), i_bfs(ibfs), with_flow_(with_flow){
        if(do_swap && A.size() > B.size()){
            std::swap(a, b);
        }

        visited.resize(graph_.num_nodes() +1, false);
        
        max_a = (graph_.num_nodes()+1)/2;
};

//breadth-first-search to determine neighbors of B
void greedy_packing::bfs(){
    
    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){
                //falls nicht(mit_flow angegeben und knoten unter den flow_edges ist)dann push in zu x
                if(!(with_flow_ && (std::find(flow_edges.begin(), flow_edges.end(), graph_.get_edge_id(node, v)) != flow_edges.end())))
                    x.push_back(v);
            }
            visited[v] = true;
        }
    }

    return;
};

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

    if(with_flow_){
        //get all flow edges and the flow
        i_bfs.reset(a, b);
        i_bfs.run();
        flow_ = i_bfs.get_max_flow();
        flow_edges = i_bfs.get_flow_edges();
    }

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

    //x per bfs konstruieren
    bfs();

    //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();
    });
    
    // behandle von B aus unnerreichbare Knoten
    for (node_id i = 1; i <= graph_.num_nodes(); i++) {
        if (!visited[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_++;
        a_count += partition.size();
        if (a_count >= max_a){
            return;
        }
    }

    return;
};