bnb.hpp

#include <cstdint>
#include <vector>

#pragma once

#include <gp-bnb/graph.hpp>
#include <gp-bnb/partition.hpp>
#include <gp-bnb/edmonds_karp.hpp>
#include <gp-bnb/incremental_bfs.hpp>
#include <gp-bnb/push_relabel.hpp>
#include <gp-bnb/greedy_packing.hpp>

namespace gp_bnb {

using subgraph = partition::subgraph;

enum class lb : char { ek, ibfs, pr, gp, none };

// 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.
		node_id node;

		// Next alternative (or none if no alternative exists).
		subgraph alt;
	};

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

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

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

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

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

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

// Main solver structure. Puts everything together.
class solver {
public: 
    // Constructor
    solver(graph& g, lb lb_algorithm);

	// Read-only access to the nodes.
	const graph &nodes() const {
		return graph_;
	}

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

	unsigned int get_lower();

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

	// 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:
	subgraph next_possible_subgraph(node_id node, subgraph sg);

	graph graph_;

    partition partition_;
	trail_state trail_;

    lb lb_algorithm_;
    incremental_bfs i_bfs_;
	edmonds_karp ek_;
	push_relabel pr_;
	greedy_packing gp_;
	std::vector<node_id> current_sources_;
	std::vector<node_id> current_sinks_;

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

} // namespace gp_bnb