#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