3 from __future__
import generators
8 def update_graph(self
,graph
):
9 'save nodes and edges of graph to self'
10 for node
,d
in graph
.iteritems():
13 for target
,edge
in d
.iteritems():
14 saveDict
[target
] = edge
18 """Internal representation for storing both nodes and edges as list
19 So filter functions can see both nodes and edges"""
20 def __init__(self
,nodes
=None,edges
=None):
22 list.__init
__(self
,nodes
)
35 list.extend(self
,l
) # EXTEND TOP-LEVEL LIST AS USUAL
36 try: # EXTEND OUR EDGE LIST AS WELL
37 self
.edge
.extend(l
.edge
)
38 except AttributeError: #IF l HAS NO EDGES, PAD OUR EDGE LIST WITH Nones
39 self
.edge
.extend(len(l
)*[None])
44 "Interface to edge information."
46 def __init__(self
,graph
,nodes
,edgeInfo
):
49 self
.edgeInfo
=edgeInfo
50 list.__init
__(self
,nodes
) # SAVE NODES AS TUPLE
53 def __getattr__(self
,attr
):
55 return getattr(self
.edgeInfo
,attr
)
56 except AttributeError:
57 if isinstance(self
.edgeInfo
,types
.DictType
):
58 return self
.edgeInfo
[attr
] # TREAT edgeInfo AS ATTRIBUTE DICTIONARY
59 raise AttributeError(attr
)
61 # SHOULD WE DEFINE A setattr HERE TOO, TO ALLOW USER TO ADD NEW ATTRIBUTE VALUES??
62 # setattr IS PAINFUL TO IMPLEMENT, BECAUSE OF THE RECURSIVE REFERENCE PROBLEM
64 def __cmp__(self
,other
): # DO WE NEED TO COMPARE EDGE INFO??
65 if not isinstance(other
,Edge
): # CAN ONLY COMPARE A PAIR OF EDGES
67 diff
=cmp(self
.graph
,other
.graph
)
68 if diff
: # NOT IN THE SAME GRAPH...
70 elif self
.isDirected
: # IF DIRECTED, JUST COMPARE IN CURRENT ORDER
71 return tuple.__cmp
__(self
,other
)
72 else: # UNDIRECTED COMPARISON REQUIRES PUTTING BOTH IN SAME ORDER
74 you
=[i
for i
in other
]
79 # NEEDS SCHEMA SUPPORT: RETURN A SINGLE SCHEMA TUPLE DESCRIBING THIS EDGE.
81 class DirectedEdge(Edge
):
85 # need a class to provide access to the edges in a graph
86 # iterator, membership test
92 """2nd layer graph interface implemenation using dict.
95 def __init__(self
,graph
,fromNode
):
97 self
.fromNode
=fromNode
98 self
.dictClass
.__init
__(self
) # INITIALIZE TOPLEVEL DICTIONARY
100 def __iadd__(self
,target
):
101 "Add edge from fromNode to target with no edge-info"
103 return self
# THIS IS REQUIRED FROM iadd()!!
105 def __setitem__(self
,target
,edgeInfo
):
106 "Add edge from fromNode to target with edgeInfo"
107 self
.dictClass
.__setitem
__(self
,target
,edgeInfo
)
108 if target
not in self
.graph
: # ADD NEW NODE TO THE NODE DICT
111 _setitem_
=dict.__setitem
__ # INTERNAL INTERFACE FOR SAVING AN ENTRY
113 def __delitem__(self
,target
):
114 "Delete edge from fromNode to target"
116 self
.dictClass
.__delitem
__(self
,target
)
117 except KeyError: # GENERATE A MORE INFORMATIVE ERROR MESSAGE
118 raise KeyError('No edge from node to target')
120 def __isub__(self
,target
):
121 "Delete edge from fromNode to target"
122 self
.__delitem
__(target
)
123 return self
# THIS IS REQUIRED FROM iadd()!!
126 "Return iterator for accessing edges from fromNode"
127 for target
,edgeInfo
in self
.items():
128 if isinstance(edgeInfo
,Edge
):
131 yield Edge(self
.graph
,(self
.fromNode
,target
,edgeInfo
),edgeInfo
)
135 class dictGraph(dict):
136 """Top layer graph interface implemenation using dict.
139 edgeDictClass
=dictEdge
140 def __init__(self
,schema
=None,domain
=None,range=None):
141 if schema
and domain
and range:
142 if domain
not in schema
:
143 schema
+= domain
#ADD DOMAIN AS NODE TO schema GRAPH
144 schema
[domain
][range]=self
145 self
.dictClass
.__init
__(self
) # INITIALIZE TOPLEVEL DICTIONARY
147 def __iadd__(self
,node
,ruleSet
=False):
148 "Add node to graph with no edges"
150 self
.dictClass
.__setitem
__(self
,node
,self
.edgeDictClass(self
,node
))
152 ruleSet
=getschema(node
,graph
=self
)
154 if isinstance(rule
[1],types
.StringType
): # ATTRIBUTE BINDING!
155 setattr(node
,rule
[1],self
[node
]) # BIND DIRECTLY TO ATTRIBUTE
156 return self
# THIS IS REQUIRED FROM iadd()!!
158 def __setitem__(self
,node
,target
):
159 "This method exists only to support g[n]+=o. Do not use as g[n]=foo."
160 if self
[node
]!=target
:
161 raise ValueError('Incorrect usage. Add edges using g[n]+=o or g[n][o]=edge.')
163 def __delitem__(self
,node
):
164 "Delete node from graph."
165 # GRR, WE REALLY NEED TO FIND ALL EDGES THAT GO TO THIS NODE, DELETE THEM TOO
167 self
.dictClass
.__delitem
__(self
,node
) # DO STUFF TO REMOVE IT HERE...
169 raise KeyError('Node not present in mapping.')
170 for rule
in getschema(node
,graph
=self
):
171 if isinstance(rule
[1],types
.StringType
): # ATTRIBUTE BINDING!
172 delattr(node
,rule
[1]) # REMOVE ATTRIBUTE BINDING
174 def __isub__(self
,node
):
175 "Delete node from graph"
176 self
.__delitem
__(node
)
177 return self
# THIS IS REQUIRED FROM isub()!!
179 def __hash__(self
): # SO SCHEMA CAN INDEX ON GRAPHS...
183 "Return iterator for all edges in this graph"
184 for edgedict
in self
.values():
185 for edge
in edgedict
.edges():
187 update
= update_graph
193 class dictEdgeFB(dictEdge
):
194 "dictEdge subclass that saves both forward and backward edges"
195 def __setitem__(self
,target
,edgeInfo
):
196 "Save edge in both forward and backward dicts."
197 dictEdge
.__setitem
__(self
,target
,edgeInfo
) # FORWARD EDGE
199 d
=self
.graph
._inverse
[target
]
202 self
.graph
._inverse
[target
]=d
203 d
[self
.fromNode
]=edgeInfo
# SAVE BACKWARD EDGE
205 def __invert__(self
):
206 "Get nodes with edges to this node"
207 return self
.graph
._inverse
[self
.fromNode
]
209 class dictGraphFB(dictGraph
):
210 "Graph that saves both forward and backward edges"
211 def __init__(self
,**kwargs
):
212 dictGraph
.__init
__(self
,**kwargs
)
213 self
._inverse
=self
.dictClass()
214 __invert__
= classutil
.standard_invert
215 def __delitem__(self
,node
):
216 "Delete node from the graph"
218 fromNodes
=self
._inverse
[node
] #
219 del self
._inverse
[node
] # REMOVE FROM _inverse DICT
222 else: # DELETE EDGES TO THIS NODE
225 dictGraph
.__delitem
__(self
,node
)
229 def listUnion(ivals
):
230 'merge all items using union operator'
240 class DictQueue(dict):
241 'each index entry acts like a queue; setitem PUSHES, and delitem POPS'
242 def __setitem__(self
,k
,val
):
244 dict.__getitem
__(self
,k
).append(val
)
246 dict.__setitem
__(self
,k
,[val
])
247 def __getitem__(self
,k
):
248 return dict.__getitem
__(self
,k
)[0]
249 def __delitem__(self
,k
):
250 l
=dict.__getitem
__(self
,k
)
253 dict.__delitem
__(self
,k
)
258 ################################ PYGR.DATA.SCHEMA - AWARE CLASSES BELOW
261 def close_if_possible(self
):
262 'close storage to ensure any pending data is written'
264 do_close
= self
.d
.close
265 except AttributeError:
273 class Collection(object):
274 'flexible storage mapping ID --> OBJECT'
275 def __init__(self
,saveDict
=None,dictClass
=dict,**kwargs
):
276 '''saveDict, if not None, is the internal mapping to use as our storage.
277 filename: if provided, is a file path to a shelve (BerkeleyDB) file to
279 dictClass: if provided, is the class to use for storage of the dict data.'''
280 if saveDict
is not None:
282 elif 'filename' in kwargs
: # USE A SHELVE (BERKELEY DB)
284 if kwargs
['intKeys']: # ALLOW INT KEYS, HAVE TO USE IntShelve
285 self
.__class
__ = IntShelve
289 self
.__class
__ = PicklableShelve
290 return self
.__init
__(**kwargs
)
293 classutil
.apply_itemclass(self
,kwargs
)
294 def __getitem__(self
,k
): return self
.d
[k
]
295 def __setitem__(self
,k
,v
): self
.d
[k
] = v
296 def __delitem__(self
,k
): del self
.d
[k
]
297 def __len__(self
): return len(self
.d
)
298 def __contains__(self
,k
): return k
in self
.d
299 def __iter__(self
): return iter(self
.d
)
300 def __getattr__(self
,attr
):
301 if attr
=='__setstate__' or attr
=='__dict__': # PREVENT INFINITE RECURSE IN UNPICKLE
303 try: # PROTECT AGAINST INFINITE RECURSE IF NOT FULLY __init__ED...
304 return getattr(self
.__dict
__['d'],attr
)
306 raise AttributeError('Collection has no subdictionary')
307 close
= close_if_possible
309 'must ensure that shelve object is closed to save pending data'
312 except classutil
.FileAlreadyClosedError
:
315 class PicklableShelve(Collection
):
316 'persistent storage mapping ID --> OBJECT'
317 def __init__(self
,filename
,mode
=None,writeback
=False,unpicklingMode
=False,
318 verbose
=True,**kwargs
):
319 '''Wrapper for a shelve object that can be pickled. Ideally, you
320 should specify a TWO letter mode string: the first letter to
321 indicate what mode the shelve should be initially opened in, and
322 the second to indicate the mode to open the shelve during unpickling.
323 e.g. mode='nr': to create an empty shelve (writable),
324 which in future will be re-opened read-only.
325 Also, mode=None makes it first attempt to open read-only, but if the file
326 does not exist will create it using mode 'c'. '''
327 self
.filename
= classutil
.SourceFileName(str(filename
)) # MARKS THIS STR AS A FILE PATH
328 self
.writeback
= writeback
329 if unpicklingMode
or mode
is None or mode
=='r': # JUST USE mode AS GIVEN
331 elif mode
=='n' or mode
=='c' or mode
=='w': # AMBIGUOUS MODES, WARN & SET DEFAULT
334 print >>sys
.stderr
,'''Warning: you opened shelve file %s
335 in mode '%s' but this is ambiguous for how the shelve should be
336 re-opened later during unpickling. By default it will be
337 re-opened in mode 'r' (read-only). To make it be re-opened
338 writable, create it in mode '%sw', or call its method
339 reopen('w'), which will make it be re-opened in mode 'w' now and
340 in later unpickling. To suppress this warning message, use the
341 verbose=False option.''' % (filename
,mode
,mode
)
343 else: # PROCESS UNAMBIGUOUS TWO-LETTER mode STRING
345 if len(mode
)==2 and mode
[0] in 'ncwr' and mode
[1] in 'cwr':
346 self
.mode
= mode
[1] # IN FUTURE OPEN IN THIS MODE
347 mode
= mode
[0] # OPEN NOW IN THIS MODE
349 raise ValueError('invalid mode string: '+mode
)
351 raise ValueError('file mode must be a string!')
353 self
.d
= classutil
.open_shelve(filename
,mode
,writeback
,allowReadOnly
=True)
355 self
.d
= classutil
.open_shelve(filename
,mode
,writeback
)
356 classutil
.apply_itemclass(self
,kwargs
)
357 __getstate__
= classutil
.standard_getstate
############### PICKLING METHODS
358 __setstate__
= classutil
.standard_setstate
359 _pickleAttrs
= dict(filename
=0,mode
=0,writeback
=0)
361 '''close our shelve index file. '''
363 def __setitem__(self
,k
,v
):
367 raise TypeError('to allow int keys, you must pass intKeys=True to constructor!')
368 def reopen(self
,mode
='r'):
369 're-open shelve in the specified mode, and save mode on self'
371 self
.d
= classutil
.open_shelve(self
.filename
,mode
,writeback
=self
.writeback
)
375 class IntShelve(PicklableShelve
):
376 'provides an interface to shelve that can use int as key'
378 'convert to string key'
379 if isinstance(i
,int):
381 elif isinstance(i
,str):
384 return 'int:%s'%int
(i
)
387 raise KeyError('IntShelve can only save int or str as key')
389 "convert back to key's original format"
390 if k
.startswith('int:'):
394 def __getitem__(self
,k
):
395 return self
.d
[self
.saveKey(k
)]
396 def __setitem__(self
,k
,v
):
397 self
.d
[self
.saveKey(k
)]=v
398 def __delitem__(self
,k
): del self
.d
[self
.saveKey(k
)]
399 def __contains__(self
,k
):
400 return self
.saveKey(k
) in self
.d
401 def __iter__(self
): ################ STANDARD ITERATOR METHODS
403 yield self
.trueKey(k
)
404 def keys(self
): return [k
for k
in self
]
406 for k
,v
in self
.d
.iteritems():
407 yield self
.trueKey(k
),v
408 def items(self
): return [k
for k
in self
.iteritems()]
412 ## PACKING / UNPACKING METHODS FOR SEPARATING INTERNAL VS. EXTERNAL
413 ## REPRESENTATIONS OF GRAPH NODES AND EDGES
414 ## 1. ID-BASED PACKING: USE obj.id AS INTERNAL REPRESENTATION
416 ## 2. TRIVIAL: INTERNAL AND EXTERNAL REPRESENTATIONS IDENTICAL
417 ## WORKS WELL FOR STRING OR INT NODES / EDGES.
419 ## 3. PICKLE PACKING: USE PICKLE AS INTERNAL REPRESENTATION
420 def pack_id(self
,obj
):
421 'extract id attribute from obj'
424 except AttributeError:
429 def unpack_source(self
,objID
):
430 return self
.sourceDB
[objID
]
431 def unpack_target(self
,objID
):
432 return self
.targetDB
[objID
]
433 def unpack_edge(self
,objID
):
435 return self
.edgeDB
[objID
]
441 def add_standard_packing_methods(localDict
):
442 localDict
['pack_source'] = pack_id
443 localDict
['pack_target'] = pack_id
444 localDict
['pack_edge'] = pack_id
445 localDict
['unpack_source'] = unpack_source
446 localDict
['unpack_target'] = unpack_target
447 localDict
['unpack_edge'] = unpack_edge
449 def add_trivial_packing_methods(localDict
):
450 for name
in ('pack_source','pack_target','pack_edge',
451 'unpack_source','unpack_target','unpack_edge'):
452 localDict
[name
] = lambda self
,obj
:obj
455 def pack_pickle(self
,obj
):
456 'get pickle string for obj'
458 return pickle
.dumps(obj
)
460 def unpack_pickle(self
,s
):
461 'unpickle string to get obj'
463 return pickle
.loads(s
)
466 class MappingInverse(object):
467 def __init__(self
,db
):
469 self
.attr
=db
.inverseAttr
470 def __getitem__(self
,k
):
471 return self
._inverse
.sourceDB
[getattr(k
,self
.attr
)]
472 __invert__
= classutil
.standard_invert
474 class Mapping(object):
475 '''dict-like class suitable for persistent usages. Extracts ID values from
476 keys and values passed to it, and saves IDs into its internal dictionary
477 instead of the actual objects. Thus, the external interface is objects,
478 but the internal storage is ID values.'''
479 def __init__(self
,sourceDB
,targetDB
,saveDict
=None,IDAttr
='id',targetIDAttr
='id',
480 itemAttr
=None,multiValue
=False,inverseAttr
=None,**kwargs
):
481 '''sourceDB: dictionary that maps key ID values to key objects
482 targetDB: dictionary that maps value IDs to value objects
483 saveDict, if not None, is the internal mapping to use as our storage
484 IDAttr: attribute name to obtain an ID from a key object
485 targetIDAttr: attribute name to obtain an ID from a value object
486 itemAttr, if not None, the attribute to obtain target (value) ID
487 from an internal storage value
488 multiValue: if True, treat each value as a list of values.
489 filename: if provided, is a file path to a shelve (BerkeleyDB) file to
491 dictClass: if not None, is the class to use for storage of the dict data'''
493 self
.d
=classutil
.get_shelve_or_dict(**kwargs
)
497 self
.targetIDAttr
=targetIDAttr
498 self
.itemAttr
=itemAttr
499 self
.multiValue
=multiValue
500 self
.sourceDB
=sourceDB
501 self
.targetDB
=targetDB
502 if inverseAttr
is not None:
503 self
.inverseAttr
=inverseAttr
504 def __getitem__(self
,k
):
505 kID
=getattr(k
,self
.IDAttr
)
506 return self
.getTarget(self
.d
[kID
])
507 def getTarget(self
,vID
):
508 if self
.itemAttr
is not None:
509 vID
=getattr(vID
,self
.itemAttr
)
511 return [self
.targetDB
[j
] for j
in vID
]
513 return self
.targetDB
[vID
]
514 def __setitem__(self
,k
,v
):
516 v
=[getattr(x
,self
.targetIDAttr
) for x
in v
]
518 v
=getattr(v
,self
.targetIDAttr
)
519 self
.d
[getattr(k
,self
.IDAttr
)]=v
520 def __delitem__(self
,k
):
521 del self
.d
[getattr(k
,self
.IDAttr
)]
522 def __contains__(self
,k
):
523 return getattr(k
,self
.IDAttr
) in self
.d
524 def __len__(self
): return len(self
.d
)
525 def clear(self
): self
.d
.clear()
527 return Mapping(self
.sourceDB
,self
.targetDB
,self
.d
.copy(),self
.IDAttr
,
528 self
.targetIDAttr
,self
.itemAttr
,self
.multiValue
)
530 for k
,v
in b
.iteritems():
532 def get(self
,k
,v
=None):
537 def setdefault(self
,k
,v
=None):
543 def pop(self
,k
,v
=None):
551 kID
,vID
=self
.d
.popitem()
552 return kID
,self
.getTarget(vID
)
553 def __iter__(self
): ######################## ITERATORS
555 yield self
.sourceDB
[kID
]
556 def keys(self
): return [k
for k
in self
]
557 def itervalues(self
):
558 for vID
in self
.d
.itervalues():
559 yield self
.getTarget(vID
)
560 def values(self
): return [v
for v
in self
]
562 for kID
,vID
in self
.d
.iteritems():
563 yield self
.sourceDB
[kID
],self
.getTarget(vID
)
564 def items(self
): return [x
for x
in self
.iteritems()]
565 __invert__
= classutil
.standard_invert
566 _inverseClass
= MappingInverse
567 close
= close_if_possible
569 close_if_possible(self
)
572 def graph_cmp(self
,other
):
573 'compare two graph dictionaries'
575 diff
= cmp(len(self
),len(other
))
577 print >>sys
.stderr
,'len diff:',len(self
),len(other
)
579 for node
,d
in self
.iteritems():
583 print >>sys
.stderr
,'other missing key'
587 print >>sys
.stderr
,'value diff',d
,d2
593 class IDNodeDict(object):
594 """2nd layer graph interface implementation using proxy dict.
597 def __init__(self
,graph
,fromNode
):
599 self
.fromNode
=fromNode
601 def __getitem__(self
,target
): ############# ACCESS METHODS
602 edgeID
=self
.graph
.d
[self
.fromNode
][self
.graph
.pack_target(target
)]
603 return self
.graph
.unpack_edge(edgeID
)
605 def __setitem__(self
,target
,edgeInfo
):
606 "Add edge from fromNode to target with edgeInfo"
607 self
.graph
.d
[self
.fromNode
][self
.graph
.pack_target(target
)] \
608 = self
.graph
.pack_edge(edgeInfo
)
609 if not hasattr(self
.graph
,'sourceDB') or \
610 (hasattr(self
.graph
,'targetDB') and self
.graph
.sourceDB
==self
.graph
.targetDB
):
611 self
.graph
+=target
# ADD NEW NODE TO THE NODE DICT
613 def __delitem__(self
,target
):
614 "Delete edge from fromNode to target"
616 del self
.graph
.d
[self
.fromNode
][self
.graph
.pack_target(target
)]
617 except KeyError: # GENERATE A MORE INFORMATIVE ERROR MESSAGE
618 raise KeyError('No edge from node to target')
619 ######### CONVENIENCE METHODS THAT USE THE ACCESS METHODS ABOVE
620 def __iadd__(self
,target
):
621 "Add edge from fromNode to target with no edge-info"
623 return self
# THIS IS REQUIRED FROM iadd()!!
625 def __isub__(self
,target
):
626 "Delete edge from fromNode to target"
627 self
.__delitem
__(target
)
628 return self
# THIS IS REQUIRED FROM iadd()!!
631 "Return iterator for accessing edges from fromNode"
632 for target
,edgeInfo
in self
.graph
.d
[self
.fromNode
].items():
633 yield (self
.graph
.unpack_source(self
.fromNode
),
634 self
.graph
.unpack_target(target
),
635 self
.graph
.unpack_edge(edgeInfo
))
637 return len(self
.graph
.d
[self
.fromNode
])
638 def keys(self
): return [k
[1] for k
in self
.edges()] ##### ITERATORS
639 def values(self
): return [k
[2] for k
in self
.edges()]
640 def items(self
): return [k
[1:3] for k
in self
.edges()]
642 for source
,target
,edgeInfo
in self
.edges():
644 def itervalues(self
):
645 for source
,target
,edgeInfo
in self
.edges():
648 for source
,target
,edgeInfo
in self
.edges():
649 yield target
,edgeInfo
653 class IDNodeDictWriteback(IDNodeDict
):
654 'forces writing of subdictionary in shelve opened without writeback=True'
655 def __setitem__(self
,target
,edgeInfo
):
656 d
= self
.graph
.d
[self
.fromNode
]
657 d
[self
.graph
.pack_target(target
)] = self
.graph
.pack_edge(edgeInfo
)
658 self
.graph
.d
[self
.fromNode
] = d
# WRITE IT BACK... REQUIRED FOR SHELVE
659 self
.graph
+= target
# ADD NEW NODE TO THE NODE DICT
660 def __delitem__(self
,target
):
661 d
= self
.graph
.d
[self
.fromNode
]
662 del d
[self
.graph
.pack_target(target
)]
663 self
.graph
.d
[self
.fromNode
] = d
# WRITE IT BACK... REQUIRED FOR SHELVE
665 class IDNodeDictWriteNow(IDNodeDictWriteback
):
666 'opens shelve for writing, writes an item, immediately reopens'
667 def __setitem__(self
,target
,edgeInfo
):
668 self
.graph
.d
.reopen('w')
669 IDNodeDictWriteback
.__setitem
__(self
,target
,edgeInfo
)
670 self
.graph
.d
.reopen('w')
671 def __delitem__(self
,target
):
672 self
.graph
.d
.reopen('w')
673 IDNodeDictWriteback
.__delitem
__(self
,target
)
674 self
.graph
.d
.reopen('w')
676 class IDGraphEdges(object):
677 '''provides iterator over edges as (source,target,edge) tuples
678 and getitem[edge] --> [(source,target),...]'''
679 def __init__(self
,g
):
682 for d
in self
.g
.itervalues():
683 for edge
in d
.edges():
685 def __getitem__(self
,edge
):
687 for sourceID
,targetID
in self
.d
[edge
.id]:
688 l
.append((self
.g
.sourceDB
[sourceID
],self
.g
.targetDB
[targetID
]))
693 class IDGraphEdgeDescriptor(object):
694 'provides interface to edges on demand'
695 def __get__(self
,obj
,objtype
):
696 return IDGraphEdges(obj
)
699 def save_graph_db_refs(self
,sourceDB
=None,targetDB
=None,edgeDB
=None,
700 simpleKeys
=False,unpack_edge
=None,
701 edgeDictClass
=None,graph
=None,**kwargs
):
702 'apply kwargs to reference DB objects for this graph'
703 if sourceDB
is not None:
704 self
.sourceDB
=sourceDB
706 simpleKeys
= True # NO SOURCE DB, SO STORE KEYS AS INTERNAL REPRESENTATION
707 if targetDB
is not None:
708 self
.targetDB
=targetDB
709 if edgeDB
is not None:
711 else: # just save the edge object as itself (not its ID)
712 self
.pack_edge
= self
.unpack_edge
= lambda edge
:edge
713 if simpleKeys
: # SWITCH TO USING TRIVIAL PACKING: OBJECT IS ITS OWN ID
714 self
.__class
__ = self
._IDGraphClass
715 if unpack_edge
is not None:
716 self
.unpack_edge
= unpack_edge
# UNPACKING METHOD OVERRIDES DEFAULT
717 if graph
is not None:
719 if edgeDictClass
is not None:
720 self
.edgeDictClass
= edgeDictClass
722 def graph_db_inverse_refs(self
,edgeIndex
=False):
723 'return kwargs for inverse of this graph, or edge index of this graph'
724 if edgeIndex
: # TO CONSTRUCT AN EDGE INDEX
725 db
= ('edgeDB','sourceDB','targetDB')
726 else: # DEFAULT: TO CONSTRUCT AN INVERSE MAPPING OF THE GRAPH
727 db
= ('targetDB','sourceDB','edgeDB')
729 d
= dict(sourceDB
=getattr(self
,db
[0]),targetDB
=getattr(self
,db
[1]))
731 d
['edgeDB'] = getattr(self
,db
[2]) # EDGE INFO IS OPTIONAL
732 except AttributeError:
734 except AttributeError:
735 d
= dict(simpleKeys
=True) # NO SOURCE / TARGET DB, SO USE IDs AS KEYS
736 try: # COPY THE LOCAL UNPACKING METHOD, IF ANY
738 d
['unpack_edge'] = self
.__dict
__['unpack_edge']
744 def graph_setitem(self
,node
,target
):
745 "This method exists only to support g[n]+=o. Do not use as g[n]=foo."
746 node
=self
.pack_source(node
)
748 if node
==target
.fromNode
:
750 except AttributeError:
752 raise ValueError('Incorrect usage. Add edges using g[n]+=o or g[n][o]=edge.')
756 """Top layer graph interface implemenation using proxy dict.
757 Works with dict, shelve, any mapping interface."""
758 edgeDictClass
=IDNodeDict
# DEFAULT EDGE DICT
759 def __init__(self
,saveDict
=None,dictClass
=dict,writeNow
=False,**kwargs
):
760 if saveDict
is not None: # USE THE SUPPLIED STORAGE
762 elif 'filename' in kwargs
: # USE A SHELVE (BERKELEY DB)
764 if kwargs
['intKeys']: # ALLOW INT KEYS, HAVE TO USE IntShelve
765 self
.d
= IntShelve(writeback
=False,**kwargs
)
769 self
.d
= PicklableShelve(writeback
=False,**kwargs
)
771 self
.edgeDictClass
= IDNodeDictWriteNow
# WRITE IMMEDIATELY
773 self
.edgeDictClass
= IDNodeDictWriteback
# USE OUR OWN WRITEBACK
776 save_graph_db_refs(self
,**kwargs
)
777 __getstate__
= classutil
.standard_getstate
############### PICKLING METHODS
778 __setstate__
= classutil
.standard_setstate
779 _pickleAttrs
= dict(d
='saveDict',sourceDB
=0,targetDB
=0,edgeDB
=0,
781 add_standard_packing_methods(locals()) ############ PACK / UNPACK METHODS
783 '''If possible, close our dict. '''
785 do_close
= self
.d
.close
786 except AttributeError:
794 yield self
.unpack_source(node
)
795 def keys(self
): return [k
for k
in self
]
796 def itervalues(self
):
798 yield self
.edgeDictClass(self
,node
)
799 def values(self
): return [v
for v
in self
.itervalues()]
802 yield self
.unpack_source(node
),self
.edgeDictClass(self
,node
)
803 def items(self
): return [v
for v
in self
.iteritems()]
804 edges
=IDGraphEdgeDescriptor()
806 def __iadd__(self
,node
):
807 "Add node to graph with no edges"
808 node
=self
.pack_source(node
)
809 if node
not in self
.d
:
810 self
.d
[node
]={} # INITIALIZE TOPLEVEL DICTIONARY
811 return self
# THIS IS REQUIRED FROM iadd()!!
813 def __contains__(self
,node
):
814 return self
.pack_source(node
) in self
.d
815 def __getitem__(self
,node
):
817 return self
.edgeDictClass(self
,self
.pack_source(node
))
818 raise KeyError('node not in graph')
819 __setitem__
= graph_setitem
820 def __delitem__(self
,node
):
821 "Delete node from graph."
822 node
=self
.pack_source(node
)
823 # GRR, WE REALLY NEED TO FIND ALL EDGES THAT GO TO THIS NODE, DELETE THEM TOO
825 del self
.d
[node
] # DO STUFF TO REMOVE IT HERE...
827 raise KeyError('Node not present in mapping.')
829 def __isub__(self
,node
):
830 "Delete node from graph"
831 self
.__delitem
__(node
)
832 return self
# THIS IS REQUIRED FROM isub()!!
833 update
= update_graph
838 except classutil
.FileAlreadyClosedError
:
842 # NEED TO PROVIDE A REAL INVERT METHOD!!
843 ## def __invert__(self):
844 ## 'get an interface to the inverse graph mapping'
846 ## return self._inverse
847 ## except AttributeError: # NEED TO CONSTRUCT INVERSE MAPPING
848 ## self._inverse=IDGraph(~(self.d),self.targetDB,self.sourceDB,self.edgeDB)
849 ## self._inverse._inverse=self
850 ## return self._inverse
851 def __hash__(self
): # SO SCHEMA CAN INDEX ON GRAPHS...
855 class IDGraph(Graph
):
856 add_trivial_packing_methods(locals())
858 Graph
._IDGraphClass
= IDGraph
860 class KeepUniqueDict(dict):
861 'dict that blocks attempts to overwrite an existing key'
862 def __setitem__(self
,k
,v
):
865 return # ALREADY SAVED. NOTHING TO DO!
866 except KeyError: # NOT PRESENT, SO JUST SAVE THE VALUE
867 dict.__setitem
__(self
,k
,v
)
869 raise KeyError('attempt to overwrite existing key!')
871 'ALLOW THIS OBJECT TO BE USED AS A KEY IN DICTS...'