bnb.hpp

#include <cstdint>
#include <vector>

#pragma once

#include <gp-bnb/graph.hpp>

namespace gp_bnb {

using partition_index = unsigned int;

// We use (-1) as an indicator for non-existing (or otherwise illegal) partition.
// Note that because this is cast to unsigned int, it becomes 0xFFFF... (i.e., the highest
// possible number). We do not use zero as that is a valid partition index.
static constexpr partition_index illegal_partition = static_cast<partition_index>(-1);

// Represents a partial assignment.
struct assignment_state {
	// Change the number of existing nodes.
	void resize_nodes(size_t count);

	// Assigns an node to a partition.
	void assign(vertex_id node, partition_index p, std::vector<unsigned int> neighbors);

	// Unassigns an node from its partition.
	void unassign(vertex_id node, std::vector<unsigned int> neigbors);

	partition_index assigned_partition_of(vertex_id node) const {
		return assigned_partition_[node];
	}

   
	unsigned int node_count_of(partition_index p) const {
		return node_count[p];
	}

	int current_objective() const {
		return current_objective_;
	}

private:
	// For each node: index of the partition it is placed into.
	std::vector<partition_index> assigned_partition_;

	// Value of objective function for current partial solution.
	int current_objective_ = 0;

	//for each partition: fill count
	std::vector<unsigned int> node_count;

	//number of partitions
	int partition_count_ = 2;
};

// Represents the current path throught the search tree.
struct trail_state {
private:
	struct decision {
		// Index of node that is assigned at a certain level of the search tree.
		vertex_id node;

		// Next alternative (or illegal_partition if no alternative exists).
		partition_index alt;
	};

public:
	// Extends the current path by adding another node.
	void push_node(vertex_id node, partition_index alt);

	// Reduces the current path by removing the last node.
	void pop();

	int length() const {
		return stack_.size();
	}

	vertex_id node_at(size_t n) const {
		return stack_[n].node;
	}

	partition_index alternative_at(size_t n) const {
		return stack_[n].alt;
	}

private:
	// Decision stack.
	std::vector<decision> stack_;
};

// Main solver structure. Puts everything together.
struct solver {
	// Read-only access to the nodes.
	const graph &nodes() const {
		return nodes_;
	}

	// Read-only access to the optimal solution.
	const std::vector<partition_index> &best_solution() const {
		return best_solution_;
	}

	// Change the number of existing nodes.
	void resize_nodes(size_t count);

	// Expand a search tree node, i.e., assigns an node to a partition and update all data structures.
	void expand(vertex_id node, partition_index p);

	//associates graph with the solver
	void define_graph(graph& g);

	// Performs backtracking after the solver ran into a dead end,
	// i.e., the current branch has been pruned.
	void backtrack();

	// Solves the gp problem and prints the solution.
	void solve();

private:
	partition_index next_possible_partition(vertex_id node, partition_index p);

	graph nodes_;
	assignment_state assignment_;
	trail_state trail_;

	// Value of best solution seen so far.
	std::vector<partition_index> best_solution_;
	int best_objective_ = 0;
};

} // namespace gp_bnb