# pypy / pypy / tool / algo / color.py

 ``` 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 81 82 83 84 85``` ``` class DependencyGraph(object): def __init__(self): self._all_nodes = [] self.neighbours = {} def add_node(self, v): if v not in self.neighbours: self._all_nodes.append(v) self.neighbours[v] = set() def add_edge(self, v1, v2): assert v1 != v2 self.neighbours[v1].add(v2) self.neighbours[v2].add(v1) def coalesce(self, vold, vnew): """Remove vold from the graph, and attach all its edges to vnew.""" for n in self.neighbours.pop(vold): self.neighbours[n].remove(vold) assert vnew != n self.neighbours[n].add(vnew) self.neighbours[vnew].add(n) # we should remove vold from self._all_nodes, but it's too costly # so we rely on getnodes() to filter self._all_nodes. def getnodes(self): return [v for v in self._all_nodes if v in self.neighbours] def lexicographic_order(self): """Enumerate a lexicographic breadth-first ordering of the nodes.""" sigma = [self.getnodes()[::-1]] if not sigma[0]: return while sigma: v = sigma[0].pop() yield v newsigma = [] neighb = self.neighbours[v] for s in sigma: s1 = [] s2 = [] for x in s: if x in neighb: s1.append(x) else: s2.append(x) if s1: newsigma.append(s1) if s2: newsigma.append(s2) sigma = newsigma def size_of_largest_clique(self): """Assuming that the graph is chordal, compute the size of the largest clique in it.""" result = 0 seen = set() for v in self.lexicographic_order(): num = 1 for n in self.neighbours[v]: if n in seen: num += 1 if num > result: result = num seen.add(v) return result def find_node_coloring(self): """Return a random minimal node coloring, assuming that the graph is chordal. For non-chordal graphs this is just an approximately good answer (but still a valid one).""" result = {} for v in self.lexicographic_order(): forbidden = 0 # bitset for n in self.neighbours[v]: if n in result: forbidden |= (1 << result[n]) # find the lowest 0 bit num = 0 while forbidden & (1 << num): num += 1 result[v] = num return result ```