Mercurial > lcfOS
diff python/graph.py @ 278:9fca39eebe50
First implementation of regalloc with coalsesc
author | Windel Bouwman |
---|---|
date | Sun, 29 Sep 2013 14:08:15 +0200 |
parents | 046017431c6a |
children |
line wrap: on
line diff
--- a/python/graph.py Thu Sep 26 21:14:25 2013 +0200 +++ b/python/graph.py Sun Sep 29 14:08:15 2013 +0200 @@ -4,16 +4,10 @@ Generic graph base class. Can dump to graphiz dot format for example! """ - def __init__(self, directed): - self.directed = directed + def __init__(self): self.nodes = set() self.edges = set() - def newNode(self): - n = Node(self) - self.addNode(n) - return n - def addNode(self, n): self.nodes.add(n) @@ -22,36 +16,27 @@ def addEdge(self, n, m): """ Add an edge from n to m """ - if (n, m) not in self.edges and (m, n) not in self.edges: - self.edges.add((n, m)) + self.edges.add((n, m)) + self.edges.add((m, n)) def hasEdge(self, n, m): - # This can be directional or not :) - if self.directed: - return (n, m) in self.edges - else: - return (n, m) in self.edges or (m, n) in self.edges + return (n, m) in self.edges + + def delEdge(self, n, m): + self.edges.remove((n, m)) + self.edges.remove((m, n)) def adjecent(self, n): """ Return all nodes with edges to n """ - return set(m for m in self.nodes if self.hasEdge(n, m)) - - def preceeding(self, n): - assert self.directed - return set(m for m in self.nodes if self.hasEdge(m, n)) - - def succeeding(self, n): - assert self.directed + # TODO: this can be optimized for speed: return set(m for m in self.nodes if self.hasEdge(n, m)) def to_dot(self, f): """ Generate graphviz dot representation """ - #print('digraph G {', file=f) for node in self.nodes: print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) for n, m in self.edges: print('{} -> {};'.format(id(n), id(m)), file=f) - #print('}', file=f) class Node: @@ -60,22 +45,41 @@ """ def __init__(self, g): self.g = g - - @property - def Succ(self): - return self.g.succeeding(self) + self.addDegree = 0 # Hack to increase degree @property - def Pred(self): - """ Return a set of predecessors """ - return self.g.preceeding(self) - - @property - def Adj(self): + def Adjecent(self): return self.g.adjecent(self) @property def Degree(self): - return len(self.Adj) + return len(self.Adjecent) + self.addDegree +class DiGraph(Graph): + """ + Directed graph. + """ + def addEdge(self, n, m): + """ Add an edge from n to m """ + self.edges.add((n, m)) + + def hasEdge(self, n, m): + return (n, m) in self.edges + + def successors(self, n): + return set(m for m in self.nodes if self.hasEdge(n, m)) + + def predecessors(self, n): + return set(m for m in self.nodes if self.hasEdge(m, n)) + + +class DiNode(Node): + @property + def Succ(self): + return self.g.successors(self) + + @property + def Pred(self): + return self.g.predecessors(self) +