greedy_packing.hpp

#ifndef GREEDYPACKING_H_
#define GREEDYPACKING_H_

#include <queue>
#include <vector>
#include <gp-bnb/graph.hpp>


class greedy_packing{
public:

    greedy_packing(const graph& g, std::vector<node_id> a, std::vector<node_id> b);

    void run();

    int get_max_flow() const{
        return flow_;
    };

private:

    void bfs();

    const graph& graph_;

    unsigned int a_count;

    //partial partition into blocks a and b
    //x is block with the neighbors of B
    std::vector<node_id> a, b, x;

    std::vector<std::vector<node_id>> partitioning;

    int flow_;

    std::queue<node_id> q;

    std::vector<bool> visited;

    unsigned int max_a;

};

#endif /* GREEDY_PACKING_H_ */