annotate wsgraph/model.py @ 38:df2a719a9b6e

stubbing deletion of nodes + edges
author Jeff Hammel <jhammel@mozilla.com>
date Mon, 24 Dec 2012 22:57:02 -0800
parents f17a6577cc0d
children d1e9602145fa
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
28
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
1
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
2 import sys
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
3 from abc import abstractmethod
9
0affca1f4dc0 start using deepcopy since lord knows we cant trust users
Jeff Hammel <jhammel@mozilla.com>
parents: 8
diff changeset
4 from copy import deepcopy
15
ee45f44394a0 i need a name, Bastian
Jeff Hammel <jhammel@mozilla.com>
parents: 11
diff changeset
5 from utils import isiterable
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
6
25
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
7 class Graph(object):
28
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
8 """
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
9 abstract base class for WSGraph model of a graph
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
10
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
11 WSGraph is interacted with by implementing
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
12 wsgraph.model.Graph object for a desired interface
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
13 """
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
14
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
15 @abstractmethod
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
16 def node(self, name, value=None):
10
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
17 """
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
18 get or set a node
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
19
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
20 When setting a node, a value of `None` will pop the value from
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
21 the nodal values
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
22 """
11
7b8e40eda563 more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 10
diff changeset
23 # TODO: values should not be **kwargs as you could conceivably want
7b8e40eda563 more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 10
diff changeset
24 # to set a node or edge to an empty dict
7b8e40eda563 more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 10
diff changeset
25 # Instead, should be (self, name, values=None)
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
26
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
27 @abstractmethod
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
28 def nodes(self):
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
29 """returns a list of all nodes"""
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
30
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
31 @abstractmethod
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
32 def edge(self, node1, node2, value=None):
10
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
33 """
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
34 get or set edge from node1 to node2
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
35 """
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
36
81d68388ec97 some nonsense about how this model is full of holes and how it should be better
Jeff Hammel <jhammel@mozilla.com>
parents: 9
diff changeset
37 @abstractmethod
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
38 def edges(self):
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
39 """returns a list of all edges"""
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
40
38
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
41 @abstractmethod
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
42 def delete(self, node1, node2=None):
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
43 """
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
44 delete a node or edge if node2 is given
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
45 If a node is deleted, all edges to it should be deleted
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
46 """
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
47
23
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
48 def __call__(self):
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
49 """
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
50 returns JSGN format of graph:
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
51 {'nodes': {'node1': {},
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
52 'node2': {}, ...},
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
53 'edges': {'node1': {'node2': {},
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
54 'node3': {}, ...},
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
55 'node2': {'node1': {}, ...}}
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
56 }
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
57 """
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
58 retval = {'nodes': {}, 'edges': {}}
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
59 for node in self.nodes():
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
60 retval['nodes'][node] = self.node(node)
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
61 for node1, node2 in self.edges():
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
62 retval['edges'].setdefault(node1, {})[node2] = self.edge(node1, node2)
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
63 return retval
24d57daaca21 well, now the request dispatches
Jeff Hammel <jhammel@mozilla.com>
parents: 15
diff changeset
64
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
65 def __getitem__(self, key):
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
66 """
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
67 if key is a basestring, return the node of that name;
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
68 if key is a 2-tuple/list, return the edge of that name
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
69 """
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
70
15
ee45f44394a0 i need a name, Bastian
Jeff Hammel <jhammel@mozilla.com>
parents: 11
diff changeset
71 if isinstance(key, basestring) or (not isiterable(key)):
8
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
72 return self.node(key)
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
73 else:
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
74 return self.edge(*key)
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
75
31
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
76 def __setitem__(self, key, value):
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
77 if isinstance(key, basestring) or (not isiterable(key)):
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
78 self.node(key, value)
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
79 else:
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
80 key1, key2 = key
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
81 self.edge(key1, key2, value)
5f14a4183bf2 fix things
Jeff Hammel <jhammel@mozilla.com>
parents: 28
diff changeset
82
38
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
83 def __delitem__(self, key):
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
84 if isinstance(key, basestring) or (not isiterable(key)):
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
85 self.delete(key)
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
86 else:
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
87 key1, key2 = key
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
88 self.delete(key1, key2)
df2a719a9b6e stubbing deletion of nodes + edges
Jeff Hammel <jhammel@mozilla.com>
parents: 37
diff changeset
89
8
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
90 def __contains__(self, key):
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
91 """
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
92 if key is ..., returns if that node is in the graph
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
93 if key is a 2-tuple/list, returns if the edge is in the graph
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
94 """
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
95 # XXX not necessarily the best implementation!
15
ee45f44394a0 i need a name, Bastian
Jeff Hammel <jhammel@mozilla.com>
parents: 11
diff changeset
96 if isinstance(key, basestring) or (not isiterable(key)):
8
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
97 return key in self.nodes()
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
98 else:
f1f7a505e0d0 __contains__ method
Jeff Hammel <jhammel@mozilla.com>
parents: 0
diff changeset
99 return tuple(key) in self.edges()
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
100
15
ee45f44394a0 i need a name, Bastian
Jeff Hammel <jhammel@mozilla.com>
parents: 11
diff changeset
101
37
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
102 class DirectedGraph(Graph):
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
103 """mix-in class for directed graphs"""
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
104 # TODO: is this possible without super or other black magicks?
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
105
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
106
25
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
107 class MemoryCache(Graph):
15
ee45f44394a0 i need a name, Bastian
Jeff Hammel <jhammel@mozilla.com>
parents: 11
diff changeset
108 """volatile in-memory representation of a graph"""
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
109
37
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
110 def __init__(self, node_type=dict):
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
111 self._edges = {}
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
112 self._nodes = {}
37
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
113 self.node_type = node_type
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
114
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
115 def node(self, name, value=None):
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
116 if value is not None:
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
117 # setter
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
118 self._nodes[name] = deepcopy(value)
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
119 else:
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
120 # getter
9
0affca1f4dc0 start using deepcopy since lord knows we cant trust users
Jeff Hammel <jhammel@mozilla.com>
parents: 8
diff changeset
121 # TODO: deepcopy
34
16673636dcb6 wow, testing is fun!
Jeff Hammel <jhammel@mozilla.com>
parents: 32
diff changeset
122 return deepcopy(self._nodes.get(name, None))
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
123
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
124 def nodes(self):
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
125 return self._nodes.keys()
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
126
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
127 def edge(self, node1, node2, value=None):
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
128 if value is not None:
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
129 # setter
32
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
130 self._edges[(node1, node2)] = deepcopy(value)
943a4b7097af fix tests
Jeff Hammel <jhammel@mozilla.com>
parents: 31
diff changeset
131 for node in node1, node2:
37
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
132 self._nodes.setdefault(node, self.node_type())
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
133 else:
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
134 # getter
9
0affca1f4dc0 start using deepcopy since lord knows we cant trust users
Jeff Hammel <jhammel@mozilla.com>
parents: 8
diff changeset
135 # TODO: deepcopy
34
16673636dcb6 wow, testing is fun!
Jeff Hammel <jhammel@mozilla.com>
parents: 32
diff changeset
136 return deepcopy(self._edges.get((node1, node2), None))
0
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
137
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
138 def edges(self):
cfcfa093e4b4 initial commit
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
139 return self._edges.keys()
25
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
140
37
f17a6577cc0d make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents: 34
diff changeset
141
25
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
142 class FileCache(MemoryCache):
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
143 """on-disk JSON file cache"""
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
144
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
145 def __init__(self, filename):
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
146 self.filename = filename
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
147 raise NotImplementedError
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
148
d1a8c1436ded notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 23
diff changeset
149 # TODO: CLI entry point to convert from one model to another
28
4bed1424bb3f more notes to self
Jeff Hammel <jhammel@mozilla.com>
parents: 25
diff changeset
150 # def main(args=sys.argv[1:]):