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)
+