greedy_packing.cpp

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

bool do_swap = true;

greedy_packing::greedy_packing(graph& g, incremental_bfs& ibfs, bool with_flow)
    : graph_(g), i_bfs(ibfs), with_flow_(with_flow){
        max_a = (graph_.num_nodes())/2;
};

void greedy_packing::reset(std::vector<node_id>& a, std::vector<node_id>& b) {
	a_ = &a;
	b_ = &b;
	x_.clear();
	flow_edges.clear();
	partitioning.clear();
	a_count = 0;

    visited.assign(graph_.num_nodes() +1, false);

	if(do_swap && a.size() > b.size()){
    	std::swap(a_, b_);
    }
}

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

    for (unsigned int i = 0; i < b_->size(); ++i) {
		node_id node = b_->operator[](i);
        q.push(node);
        visited[node] = true;
    }

    for (unsigned int i = 0; i < a_->size(); ++i) {
        visited[a_->operator[](i)] = 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) {
            node_id v = partition.back();
            for (node_id node : graph_.get_adjacency(v)) {
                if (!visited[node]) {
                    if(!(with_flow_ && (std::find(flow_edges.begin(), flow_edges.end(), graph_.get_edge_id(node, v)) != flow_edges.end()))){
                        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> x, std::vector<node_id> y) {
        return x.size() > y.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;
};