bnb.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <time.h>

#include <gp-bnb/bnb.hpp>

static constexpr bool verbose = false;
int visited_nodes = 0;

namespace gp_bnb {

// --------------------------------------------------------------------------------------
// trail_state implementation.
// --------------------------------------------------------------------------------------

void trail_state::push_node(node_id node, subgraph alt) {
	stack_.push_back({node, alt});
}

void trail_state::pop() {
	stack_.pop_back();
}

// --------------------------------------------------------------------------------------
// solver implementation.
// --------------------------------------------------------------------------------------

solver::solver(graph& g, lb lb_algorithm) : graph_(g), partition_(partition{g}), lb_algorithm_(lb_algorithm), i_bfs_(incremental_bfs(g)), gp_(greedy_packing(g, i_bfs_, true)) {
}

unsigned int solver::get_lower(){
    if (sources_.empty() || sinks_.empty()) {
        return partition_.current_objective();
    }

    

	if(lb_algorithm_ == lb::ek){
		auto ek = edmonds_karp(graph_, sources_, sinks_);
		ek.run();
	    return ek.get_max_flow();
	}
	else if(lb_algorithm_ == lb::ibfs){
		i_bfs_.reset(sources_, sinks_);
		i_bfs_.run();
		return i_bfs_.get_max_flow(); 
	}
	else if(lb_algorithm_ == lb::pr){
        auto pr = push_relabel(graph_, sources_, sinks_);
        pr.run();
        return pr.get_max_flow();
	}
	else if(lb_algorithm_ == lb::gp){
		bool with_flow = true;
		gp_.reset(sources_, sinks_);
		gp_.run();
		if(with_flow)
			return gp_.get_max_flow();
		return gp_.get_max_flow() + partition_.current_objective();
	}
    return partition_.current_objective();
}

void solver::solve() {
	//anfangs lower bound?
	best_objective_ = graph_.num_nodes();
	clock_t begin = clock();

    // builds a vector of node ids with descending degree
    std::vector<node_id> sorted_nodes;
    for (node_id i = 1; i <= graph_.num_nodes(); ++i) {
        sorted_nodes.push_back(i);
    }
    std::sort(sorted_nodes.begin(), sorted_nodes.end(), [this](node_id a, node_id b) {
        return graph_.get_adjacency(a).size() > graph_.get_adjacency(b).size();
    });

	while(true) {
		//falls current sol schlechter als bisher beste lösung: 
		//zähle schritte bis zur nächsten alternative und
		

		if(get_lower() >= best_objective_) {
			int i = trail_.length() - 1;
			while(true) {
				if(i < 0){
					std::cerr << "visited nodes: " << visited_nodes << std::endl;
					return;
				}
				// Only backtrack to assignments that have an alternative.
				if(trail_.alternative_at(i) != subgraph::none)
					break;
				i--;
			}

			auto node = trail_.node_at(i);
			auto alt = trail_.alternative_at(i);
			//backtracke soviele schritte und
			while((int)trail_.length() > i){
				backtrack();
			}
			//wende dann die entsprechende alternative an
			expand(node, alt);
		}else if(trail_.length() == graph_.num_nodes()) {
			//falls wir an einem blatt im suchbaum sind
			// Memorize the new solution.
			best_solution_.resize(graph_.num_nodes());
			for(node_id node = 0; node < graph_.num_nodes(); node++){
				best_solution_[node] = partition_.assigned_subgraph_of(node+1);
			}
			best_objective_ = partition_.current_objective();
			clock_t end = clock();
			double time = (double)(end -begin) / CLOCKS_PER_SEC;
			std::cerr << "Solution improved to k = " << best_objective_ << " after : " << time << " seconds and: " << visited_nodes << " besuchten knoten" << std::endl;
		}else{
			//sonst expandiere suchbaum weiter
			int next_node;

			//sort after degree
			/*int node_deg = 0;
			for(node_id node = 1; node <= graph_.num_nodes(); node++){
				if(partition_.assigned_subgraph_of(node) == subgraph::none){
					if(graph_.get_adjacency(node).size() > node_deg){
						node_deg = graph_.get_adjacency(node).size();
						next_node = node;
					}
				}
			}
			*/
			

			next_node = sorted_nodes[trail_.length()];

			expand(next_node, next_possible_subgraph(next_node, subgraph::sg_a));
		}
	}
}

void solver::expand(node_id node, subgraph sg) {
	assert(sg == subgraph::sg_a || sg == subgraph::sg_b);
	// Search for an alternative BEFORE assigning the node.
	// Because the node is not assigned, this calculation is easy.
	subgraph alt;
	bool fa = true;

	visited_nodes++;
	if(partition_.num_nodes_of(subgraph::none) == graph_.num_nodes()){
		alt = subgraph::none;
	}else{
		alt = next_possible_subgraph(node, static_cast<subgraph>(sg+1));
	}

	if(lb_algorithm_ == lb::gp && fa && !(sources_.empty() || sinks_.empty())){
		auto x = gp_.forced_assignment(node);
		if(x.second){
			if(x.first > best_objective_){
				sg = subgraph::sg_b;
				alt = subgraph::none;
			}
		}
		else{
			if(!(x.first > best_objective_)){
				sg = subgraph::sg_b;
			}
			//else{
			//alt = subgraph::none;
			//}			
		}
	}
	
	if(verbose) {
		std::cerr << "Assign node " << node << " to subgraph " << sg << std::endl;
		std::cerr << "    Alternative " << alt << std::endl;
	}

	//std::cerr << "expand: " << node << " to: " << sg << std::endl;
	partition_.assign_node(node, sg);
	trail_.push_node(node, alt);
	if(sg == subgraph::sg_a) sources_.push_back(node);
	else sinks_.push_back(node);

}

void solver::backtrack() {
	assert(trail_.length());

	auto node = trail_.node_at(trail_.length() - 1);
	if(verbose)
		std::cout << "Unassign node " << node << std::endl;	

	trail_.pop();
	partition_.unassign_node(node);
	if (sources_.back() == node) sources_.erase(sources_.begin() + sources_.size() - 1);
	else if (sinks_.back() == node) sinks_.erase(sinks_.begin() + sinks_.size() - 1);
	//std::cerr << "backtrack" << std::endl;
}

// Finds the next partition in which the given node can be placed.
subgraph solver::next_possible_subgraph(node_id node, subgraph m) {
	// This function is only correct if the node is not assigned yet.
	assert(partition_.assigned_subgraph_of(node) == subgraph::none);

	subgraph sg = m;

	while(sg <= 1){
		if((partition_.num_nodes_of(sg) * 2) < graph_.num_nodes())
			return sg;
		else
		{
			sg = static_cast<subgraph>(sg+1);
		}
	}

	return subgraph::none;
}

} // namespace gp_bnb