Mercurial > hg > WSGraph
annotate wsgraph/model.py @ 41:194ea1428156
from http://k0s.org/portfolio/directed-graph.txt
| author | Jeff Hammel <jhammel@mozilla.com> |
|---|---|
| date | Thu, 11 Apr 2013 15:31:38 -0700 |
| parents | d1e9602145fa |
| children |
| rev | line source |
|---|---|
| 28 | 1 |
| 2 import sys | |
| 0 | 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 | 5 from utils import isiterable |
| 0 | 6 |
| 25 | 7 class Graph(object): |
| 28 | 8 """ |
| 9 abstract base class for WSGraph model of a graph | |
| 10 | |
| 11 WSGraph is interacted with by implementing | |
| 12 wsgraph.model.Graph object for a desired interface | |
| 13 """ | |
| 0 | 14 |
| 15 @abstractmethod | |
| 32 | 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 | 23 # TODO: values should not be **kwargs as you could conceivably want |
| 24 # to set a node or edge to an empty dict | |
| 25 # Instead, should be (self, name, values=None) | |
| 0 | 26 |
| 27 @abstractmethod | |
| 28 def nodes(self): | |
| 29 """returns a list of all nodes""" | |
| 30 | |
| 31 @abstractmethod | |
| 32 | 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 | 38 def edges(self): |
| 39 """returns a list of all edges""" | |
| 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 | 65 def __getitem__(self, key): |
| 66 """ | |
| 67 if key is a basestring, return the node of that name; | |
| 68 if key is a 2-tuple/list, return the edge of that name | |
| 69 """ | |
| 70 | |
| 15 | 71 if isinstance(key, basestring) or (not isiterable(key)): |
| 8 | 72 return self.node(key) |
| 73 else: | |
| 74 return self.edge(*key) | |
| 75 | |
| 31 | 76 def __setitem__(self, key, value): |
| 77 if isinstance(key, basestring) or (not isiterable(key)): | |
| 78 self.node(key, value) | |
| 79 else: | |
| 80 key1, key2 = key | |
| 81 self.edge(key1, key2, value) | |
| 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 | 90 def __contains__(self, key): |
| 91 """ | |
| 92 if key is ..., returns if that node is in the graph | |
| 93 if key is a 2-tuple/list, returns if the edge is in the graph | |
| 94 """ | |
| 95 # XXX not necessarily the best implementation! | |
| 15 | 96 if isinstance(key, basestring) or (not isiterable(key)): |
| 8 | 97 return key in self.nodes() |
| 98 else: | |
| 99 return tuple(key) in self.edges() | |
| 0 | 100 |
| 15 | 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 |
|
39
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
107 class MemoryCache(Graph): # TODO -> MemoryCacheGraph |
| 15 | 108 """volatile in-memory representation of a graph""" |
| 0 | 109 |
|
39
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
110 # TODO: a subclass that pegs the type(s?) to something specific |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
111 |
|
37
f17a6577cc0d
make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents:
34
diff
changeset
|
112 def __init__(self, node_type=dict): |
| 0 | 113 self._edges = {} |
| 114 self._nodes = {} | |
|
37
f17a6577cc0d
make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents:
34
diff
changeset
|
115 self.node_type = node_type |
| 0 | 116 |
| 32 | 117 def node(self, name, value=None): |
| 118 if value is not None: | |
| 0 | 119 # setter |
| 32 | 120 self._nodes[name] = deepcopy(value) |
| 0 | 121 else: |
| 122 # getter | |
|
9
0affca1f4dc0
start using deepcopy since lord knows we cant trust users
Jeff Hammel <jhammel@mozilla.com>
parents:
8
diff
changeset
|
123 # TODO: deepcopy |
| 34 | 124 return deepcopy(self._nodes.get(name, None)) |
| 0 | 125 |
| 126 def nodes(self): | |
| 127 return self._nodes.keys() | |
| 128 | |
| 32 | 129 def edge(self, node1, node2, value=None): |
| 130 if value is not None: | |
| 0 | 131 # setter |
| 32 | 132 self._edges[(node1, node2)] = deepcopy(value) |
| 133 for node in node1, node2: | |
|
37
f17a6577cc0d
make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents:
34
diff
changeset
|
134 self._nodes.setdefault(node, self.node_type()) |
| 0 | 135 else: |
| 136 # getter | |
|
9
0affca1f4dc0
start using deepcopy since lord knows we cant trust users
Jeff Hammel <jhammel@mozilla.com>
parents:
8
diff
changeset
|
137 # TODO: deepcopy |
| 34 | 138 return deepcopy(self._edges.get((node1, node2), None)) |
| 0 | 139 |
| 140 def edges(self): | |
| 141 return self._edges.keys() | |
| 25 | 142 |
|
39
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
143 def delete(self, node1, node2=None): |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
144 if node2 is not None: |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
145 # delete an edge |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
146 key = node1, node2 |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
147 del self._edges[key] |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
148 return |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
149 |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
150 # delete a node |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
151 # TODO: if a node is deleted, all edges to it should be deleted |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
152 del self._nodes[node1] |
|
d1e9602145fa
rudimentary deletion and notes to self
Jeff Hammel <jhammel@mozilla.com>
parents:
38
diff
changeset
|
153 |
|
37
f17a6577cc0d
make default type configurable
Jeff Hammel <jhammel@mozilla.com>
parents:
34
diff
changeset
|
154 |
| 25 | 155 class FileCache(MemoryCache): |
| 156 """on-disk JSON file cache""" | |
| 157 | |
| 158 def __init__(self, filename): | |
| 159 self.filename = filename | |
| 160 raise NotImplementedError | |
| 161 | |
| 162 # TODO: CLI entry point to convert from one model to another | |
| 28 | 163 # def main(args=sys.argv[1:]): |