|
269
|
1
|
|
|
2 class Graph:
|
|
|
3 """
|
|
|
4 Generic graph base class.
|
|
|
5 Can dump to graphiz dot format for example!
|
|
|
6 """
|
|
277
|
7 def __init__(self, directed):
|
|
|
8 self.directed = directed
|
|
|
9 self.nodes = set()
|
|
|
10 self.edges = set()
|
|
269
|
11
|
|
|
12 def newNode(self):
|
|
|
13 n = Node(self)
|
|
277
|
14 self.addNode(n)
|
|
269
|
15 return n
|
|
|
16
|
|
277
|
17 def addNode(self, n):
|
|
|
18 self.nodes.add(n)
|
|
|
19
|
|
|
20 def delNode(self, n):
|
|
|
21 self.nodes.remove(n)
|
|
|
22
|
|
269
|
23 def addEdge(self, n, m):
|
|
|
24 """ Add an edge from n to m """
|
|
|
25 if (n, m) not in self.edges and (m, n) not in self.edges:
|
|
277
|
26 self.edges.add((n, m))
|
|
|
27
|
|
|
28 def hasEdge(self, n, m):
|
|
|
29 # This can be directional or not :)
|
|
|
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
|
|
269
|
34
|
|
277
|
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))
|
|
269
|
46
|
|
|
47 def to_dot(self, f):
|
|
|
48 """ Generate graphviz dot representation """
|
|
274
|
49 #print('digraph G {', file=f)
|
|
269
|
50 for node in self.nodes:
|
|
|
51 print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f)
|
|
|
52 for n, m in self.edges:
|
|
|
53 print('{} -> {};'.format(id(n), id(m)), file=f)
|
|
274
|
54 #print('}', file=f)
|
|
269
|
55
|
|
|
56
|
|
|
57 class Node:
|
|
|
58 """
|
|
|
59 Node in a graph.
|
|
|
60 """
|
|
|
61 def __init__(self, g):
|
|
|
62 self.g = g
|
|
277
|
63
|
|
|
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)
|
|
269
|
72
|
|
270
|
73 @property
|
|
|
74 def Adj(self):
|
|
277
|
75 return self.g.adjecent(self)
|
|
|
76
|
|
|
77 @property
|
|
|
78 def Degree(self):
|
|
|
79 return len(self.Adj)
|
|
270
|
80
|
|
|
81
|
