#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; };