Mercurial > lcfOS

comparison python/ppci/codegen/graph.py @ 323:e9fe6988497c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Used burg for generating expressions
author Windel Bouwman
date Thu, 30 Jan 2014 19:03:24 +0100
parents 2c9768114877
children b00219172a42
comparison
equal deleted inserted replaced
322:44f336460c2a 323:e9fe6988497c
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):
8 self.nodes = set() 8 self.nodes = set()
9 self.edges = set() 9 self.edges = set()
10 self.adj_map = {}
10 11
11 def addNode(self, n): 12 def addNode(self, n):
12 self.nodes.add(n) 13 self.nodes.add(n)
14 if n not in self.adj_map:
15 self.adj_map[n] = set()
13 16
14 def delNode(self, n): 17 def delNode(self, n):
15 self.nodes.remove(n) 18 self.nodes.remove(n)
16 19
17 def addEdge(self, n, m): 20 def addEdge(self, n, m):
18 """ Add an edge from n to m """ 21 """ Add an edge from n to m """
19 self.edges.add((n, m)) 22 self.edges.add((n, m))
20 self.edges.add((m, n)) 23 self.edges.add((m, n))
24 self.adj_map[n].add(m)
25 self.adj_map[m].add(n)
21 26
22 def hasEdge(self, n, m): 27 def hasEdge(self, n, m):
23 return (n, m) in self.edges 28 return (n, m) in self.edges
24 29
25 def delEdge(self, n, m): 30 def delEdge(self, n, m):
26 self.edges.remove((n, m)) 31 self.edges.remove((n, m))
27 self.edges.remove((m, n)) 32 self.edges.remove((m, n))
28 33
29 def adjecent(self, n): 34 def adjecent(self, n):
30 """ Return all nodes with edges to n """ 35 """ Return all nodes with edges to n """
31 # TODO: this can be optimized for speed: 36 return self.adj_map[n] & self.nodes
32 return set(m for m in self.nodes if self.hasEdge(n, m))
33 37
34 def to_dot(self, f): 38 def to_dot(self, f):
35 """ Generate graphviz dot representation """ 39 """ Generate graphviz dot representation """
36 for n in self.nodes: 40 for n in self.nodes:
37 print(' {} [label="{}" shape=box3d];'.format(id(n), n), file=f) 41 print(' {} [label="{}" shape=box3d];'.format(id(n), n), file=f)
55 def Degree(self): 59 def Degree(self):
56 return len(self.Adjecent) + self.addDegree 60 return len(self.Adjecent) + self.addDegree
57 61
58 62
59 class DiGraph(Graph): 63 class DiGraph(Graph):
60 """ 64 """ Directed graph. """
61 Directed graph. 65 def __init__(self):
62 """ 66 super().__init__()
67 self.suc_map = {}
68 self.pre_map = {}
69
63 def addEdge(self, n, m): 70 def addEdge(self, n, m):
64 """ Add an edge from n to m """ 71 """ Add a directed edge from n to m """
72 assert n in self.nodes
73 assert m in self.nodes
65 self.edges.add((n, m)) 74 self.edges.add((n, m))
75 self.suc_map[n].add(m)
76 self.pre_map[m].add(n)
77 self.adj_map[n].add(m)
78 self.adj_map[m].add(n)
79
80 def addNode(self, n):
81 super().addNode(n)
82 if n not in self.suc_map:
83 self.suc_map[n] = set()
84 if n not in self.pre_map:
85 self.pre_map[n] = set()
66 86
67 def hasEdge(self, n, m): 87 def hasEdge(self, n, m):
68 return (n, m) in self.edges 88 return (n, m) in self.edges
69 89
70 def successors(self, n): 90 def successors(self, n):
71 return set(m for m in self.nodes if self.hasEdge(n, m)) 91 return self.suc_map[n] & self.nodes
72 92
73 def predecessors(self, n): 93 def predecessors(self, n):
74 return set(m for m in self.nodes if self.hasEdge(m, n)) 94 return self.pre_map[n] & self.nodes
75 95
76 96
77 class DiNode(Node): 97 class DiNode(Node):
78 @property 98 @property
79 def Succ(self): 99 def Succ(self):