Mercurial > lcfOS
comparison python/ppci/codegen/graph.py @ 301:6753763d3bec
merge codegen into ppci package
| author | Windel Bouwman |
|---|---|
| date | Thu, 05 Dec 2013 17:02:38 +0100 |
| parents | python/codegen/graph.py@9417caea2eb3 |
| children | 2c9768114877 |
comparison
equal
deleted
inserted
replaced
| 300:158068af716c | 301:6753763d3bec |
|---|---|
| 1 | |
| 2 class Graph: | |
| 3 """ | |
| 4 Generic graph base class. | |
| 5 Can dump to graphiz dot format for example! | |
| 6 """ | |
| 7 def __init__(self): | |
| 8 self.nodes = set() | |
| 9 self.edges = set() | |
| 10 | |
| 11 def addNode(self, n): | |
| 12 self.nodes.add(n) | |
| 13 | |
| 14 def delNode(self, n): | |
| 15 self.nodes.remove(n) | |
| 16 | |
| 17 def addEdge(self, n, m): | |
| 18 """ Add an edge from n to m """ | |
| 19 self.edges.add((n, m)) | |
| 20 self.edges.add((m, n)) | |
| 21 | |
| 22 def hasEdge(self, n, m): | |
| 23 return (n, m) in self.edges | |
| 24 | |
| 25 def delEdge(self, n, m): | |
| 26 self.edges.remove((n, m)) | |
| 27 self.edges.remove((m, n)) | |
| 28 | |
| 29 def adjecent(self, n): | |
| 30 """ Return all nodes with edges to n """ | |
| 31 # TODO: this can be optimized for speed: | |
| 32 return set(m for m in self.nodes if self.hasEdge(n, m)) | |
| 33 | |
| 34 def to_dot(self, f): | |
| 35 """ Generate graphviz dot representation """ | |
| 36 for n in self.nodes: | |
| 37 print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f) | |
| 38 for n, m in self.edges: | |
| 39 print('{} -> {};'.format(id(n), id(m)), file=f) | |
| 40 | |
| 41 | |
| 42 class Node: | |
| 43 """ | |
| 44 Node in a graph. | |
| 45 """ | |
| 46 def __init__(self, g): | |
| 47 self.g = g | |
| 48 self.addDegree = 0 # Hack to increase degree | |
| 49 | |
| 50 @property | |
| 51 def Adjecent(self): | |
| 52 return self.g.adjecent(self) | |
| 53 | |
| 54 @property | |
| 55 def Degree(self): | |
| 56 return len(self.Adjecent) + self.addDegree | |
| 57 | |
| 58 | |
| 59 class DiGraph(Graph): | |
| 60 """ | |
| 61 Directed graph. | |
| 62 """ | |
| 63 def addEdge(self, n, m): | |
| 64 """ Add an edge from n to m """ | |
| 65 self.edges.add((n, m)) | |
| 66 | |
| 67 def hasEdge(self, n, m): | |
| 68 return (n, m) in self.edges | |
| 69 | |
| 70 def successors(self, n): | |
| 71 return set(m for m in self.nodes if self.hasEdge(n, m)) | |
| 72 | |
| 73 def predecessors(self, n): | |
| 74 return set(m for m in self.nodes if self.hasEdge(m, n)) | |
| 75 | |
| 76 | |
| 77 class DiNode(Node): | |
| 78 @property | |
| 79 def Succ(self): | |
| 80 return self.g.successors(self) | |
| 81 | |
| 82 @property | |
| 83 def Pred(self): | |
| 84 return self.g.predecessors(self) |