Mercurial > lcfOS

comparison python/graph.py @ 277:046017431c6a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Started register allocator
author Windel Bouwman
date Thu, 26 Sep 2013 21:14:25 +0200
parents ea93e0a7a31e
children 9fca39eebe50
comparison
equal deleted inserted replaced
276:56d37ed4b4d2 277:046017431c6a
2 class Graph: 2 class Graph:
3 """ 3 """
4 Generic graph base class. 4 Generic graph base class.
5 Can dump to graphiz dot format for example! 5 Can dump to graphiz dot format for example!
6 """ 6 """
7 def __init__(self): 7 def __init__(self, directed):
8 self.nodes = [] 8 self.directed = directed
9 self.edges = [] 9 self.nodes = set()
10 self.edges = set()
10 11
11 def newNode(self): 12 def newNode(self):
12 n = Node(self) 13 n = Node(self)
13 self.nodes.append(n) 14 self.addNode(n)
14 return n 15 return n
16
17 def addNode(self, n):
18 self.nodes.add(n)
19
20 def delNode(self, n):
21 self.nodes.remove(n)
15 22
16 def addEdge(self, n, m): 23 def addEdge(self, n, m):
17 """ Add an edge from n to m """ 24 """ Add an edge from n to m """
18 if (n, m) not in self.edges and (m, n) not in self.edges: 25 if (n, m) not in self.edges and (m, n) not in self.edges:
19 self.edges.append((n, m)) 26 self.edges.add((n, m))
20 n.succ.append(m)
21 m.pred.append(n)
22 27
23 def delEdge(self): 28 def hasEdge(self, n, m):
24 # TODO 29 # This can be directional or not :)
25 pass 30 if self.directed:
31 return (n, m) in self.edges
32 else:
33 return (n, m) in self.edges or (m, n) in self.edges
34
35 def adjecent(self, n):
36 """ Return all nodes with edges to n """
37 return set(m for m in self.nodes if self.hasEdge(n, m))
38
39 def preceeding(self, n):
40 assert self.directed
41 return set(m for m in self.nodes if self.hasEdge(m, n))
42
43 def succeeding(self, n):
44 assert self.directed
45 return set(m for m in self.nodes if self.hasEdge(n, m))
26 46
27 def to_dot(self, f): 47 def to_dot(self, f):
28 """ Generate graphviz dot representation """ 48 """ Generate graphviz dot representation """
29 #print('digraph G {', file=f) 49 #print('digraph G {', file=f)
30 for node in self.nodes: 50 for node in self.nodes:
38 """ 58 """
39 Node in a graph. 59 Node in a graph.
40 """ 60 """
41 def __init__(self, g): 61 def __init__(self, g):
42 self.g = g 62 self.g = g
43 self.succ = [] 63
44 self.pred = [] 64 @property
65 def Succ(self):
66 return self.g.succeeding(self)
67
68 @property
69 def Pred(self):
70 """ Return a set of predecessors """
71 return self.g.preceeding(self)
45 72
46 @property 73 @property
47 def Adj(self): 74 def Adj(self):
48 return set(self.succ) | set(self.pred) 75 return self.g.adjecent(self)
76
77 @property
78 def Degree(self):
79 return len(self.Adj)
49 80
50 81