Newer
Older
#include <gp-bnb/greedy_packing.hpp>
#include <iostream>
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(){
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();
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;