blob: e700cb05d8e12a1dc650c35ad7e270c5fcc6acc0 (
plain) (
blame)
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
package nl.camilstaps.cs;
import nl.camilstaps.cs.graphs.Graph;
import nl.camilstaps.cs.graphs.Node;
import java.util.*;
import java.util.stream.Collectors;
/**
* The garbage collection map is simply a Graph with extended functionality.
*
* @author Camil Staps
*/
class GarbageCollectionMap extends Graph {
public GarbageCollectionMap() {
super();
}
private GarbageCollectionMap(Graph g) {
super(g);
}
/**
* We want to choose a node with few neighbours, to minimise the branching factor at each reduction step.
* @return the node with the fewest neighbours
*/
protected Node bestNode() {
Node best = null;
for (Node n : nodes)
if (best == null || best.getNeighbours().size() > n.getNeighbours().size())
best = n;
return best;
}
/**
* Check if we can place N bins in this map.
*
* - Choose the {@link #bestNode} and try if we can place N-1 bins if we remove this node and all its neighbours
* - If not, remove the node and try for all its neighbours the same thing.
* - If it doesn't work for the best node or for one of its neighbours, it is impossible to place N bins.
*
* @param bins the number of bins we want to place
* @return whether this is possible
*/
protected boolean canPlaceNBins(int bins) {
if (this.nodes.size() < bins)
return false;
if (bins < 1)
return true;
// A queue with the nodes we want to check
Queue<Node> q = new LinkedList<>();
boolean first_go = true;
q.add(bestNode());
while (!q.isEmpty()) {
Node n = q.remove();
removeNode(n);
// Recursively check the subgraph without the node we're checking and its children
GarbageCollectionMap gcm = new GarbageCollectionMap(this);
gcm.removeNodes(n.getNeighbours());
if (gcm.canPlaceNBins(bins - 1))
return true;
// Check children
if (first_go)
q.addAll(n.getNeighbours().stream().filter(nodes::contains).collect(Collectors.toList()));
// Restore graph
addNode(n);
nodes.remove(n);
first_go = false;
}
return false;
}
}
|
