Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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_;
//end of neighbors determines index of x where the nodes
//aren't neighbors of B anymore
unsigned int a_count, end_of_neighbors;
//partial partition into blocks a and b
//x is block which starts with the neighbors of B
//following the other unpartitioned nodes
std::vector<node_id> a, b, x;
std::vector<std::vector<node_id>> partitioning;
int flow_;
std::queue<node_id> q;
};
#endif /* GREEDY_PACKING_H_ */