1 ovy 1.1 package harpoon.Analysis.MemOpt;
2 ovy 1.1
3 ovy 1.1 /* This colors a graph with as few colors as possible, returning
4 ovy 1.1 the resulting color classes (similar to GraphColoring.UnboundedGraphColorer,
5 ovy 1.1 qbut with much better results).
6 ovy 1.1
7 ovy 1.1 It does not currently implement GraphColoring, instead gets the graph as
8 ovy 1.1 a collection of nodes and a "contains edge" relation (MultiMap) and
9 ovy 1.1 returns the classes not the colors. We use it in IncompatibilityAnalysis
10 ovy 1.1 on what is conceptually a symmetric relation, not a graph. IMHO, it
11 ovy 1.1 should stay this way since we really don't need the extra complication
12 ovy 1.1 of ColorableGraph and friends in IncompatibilityAnalysis. But I could
13 ovy 1.1 change it if needed.
14 ovy 1.1
15 ovy 1.1 Uses a Most-saturated-node heuristic, with O(E + N log N) complexity.
16 ovy 1.1
17 ovy 1.1 FIXME: add comments
18 ovy 1.1 FIXME: maybe change to GraphColoring semantics.
19 ovy 1.1 */
20 ovy 1.1
21 ovy 1.1 import harpoon.Util.MaxPriorityQueue;
22 ovy 1.1 import harpoon.Util.BinHeapPriorityQueue;
23 cananian 1.3 import net.cscott.jutil.MultiMap;
24 ovy 1.1
25 ovy 1.1 import java.util.Collection;
26 ovy 1.1 import java.util.Iterator;
27 ovy 1.1 import java.util.LinkedList;
28 ovy 1.1
29 ovy 1.1
30 ovy 1.1 public final class MyGraphColorer {
31 ovy 1.1
32 ovy 1.1 public static Collection colorGraph(Collection nodes,
33 ovy 1.1 MultiMap edges) {
34 ovy 1.1
35 ovy 1.1 MaxPriorityQueue pqueue = new BinHeapPriorityQueue(nodes.size());
36 ovy 1.1
37 ovy 1.1 // this could be optimized by implementing a custom addAll in pqueue
38 ovy 1.1 // then building would take O(n) instead of O(n log n)
39 ovy 1.1 // but this is really too insignificant to matter
40 ovy 1.1 for (Iterator it = nodes.iterator(); it.hasNext(); ) {
41 ovy 1.1 Object node = it.next();
42 ovy 1.1 pqueue.insert(node, edges.getValues(node).size());
43 ovy 1.1 }
44 ovy 1.1
45 ovy 1.1 Collection classes = new LinkedList();
46 ovy 1.1
47 ovy 1.1 while (!pqueue.isEmpty()) {
48 ovy 1.1 Object candidate = pqueue.deleteMax();
49 ovy 1.1
50 ovy 1.1 boolean assigned = false;
51 ovy 1.1
52 ovy 1.1 for (Iterator it = classes.iterator();
53 ovy 1.1 it.hasNext() && !assigned; ) {
54 ovy 1.1 Collection members = (Collection) it.next();
55 salcianu 1.2
56 ovy 1.1 boolean compatible = true;
57 ovy 1.1 for (Iterator it2 = members.iterator();
58 ovy 1.1 it2.hasNext() && compatible; ) {
59 ovy 1.1 Object member = it2.next();
60 ovy 1.1
61 ovy 1.1 compatible &= !edges.contains(candidate, member);
62 ovy 1.1 }
63 ovy 1.1
64 ovy 1.1 if (compatible) {
65 ovy 1.1 members.add(candidate);
66 ovy 1.1 assigned = true;
67 ovy 1.1 }
68 ovy 1.1 }
69 ovy 1.1
70 ovy 1.1 if (!assigned) {
71 ovy 1.1 Collection newClass = new LinkedList();
72 ovy 1.1 newClass.add(candidate);
73 ovy 1.1
74 ovy 1.1 classes.add(newClass);
75 ovy 1.1 }
76 ovy 1.1
77 ovy 1.1 // now decrease priorities for this guys neighbours
78 ovy 1.1 for (Iterator it = edges.getValues(candidate).iterator();
79 ovy 1.1 it.hasNext(); ) {
80 ovy 1.1 Object neighbour = it.next();
81 ovy 1.1 if (pqueue.contains(neighbour)) {
82 ovy 1.1 pqueue.changePriority(neighbour, -1);
83 ovy 1.1 }
84 ovy 1.1 }
85 ovy 1.1 }
86 ovy 1.1 return classes;
87 ovy 1.1 }
88 ovy 1.1 }