1 """
2 Helper queues for use in graph searching.
3
4 - LIFO: Last in first out queue (stack)
5 - FIFO: First in first out queue
6 - Priority(fcn): Priority queue with items are sorted by fcn
7 - Random: Random queue
8
9 - q.append(item) -- add an item to the queue
10 - q.extend(items) -- equivalent to: for item in items: q.append(item)
11 - q.pop() -- return the top item from the queue
12 - len(q) -- number of items in q (also q.__len())
13 """
14 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
15 __date__ = "$Date: 2005-03-30 16:56:28 -0700 (Wed, 30 Mar 2005) $"
16 __credits__ = """"""
17 __revision__ = "$Revision: 911 $"
18
19
20
21
22
23
24 import bisect
25 import random
26
32
34 """
35 """
39 item = list.pop(self,0)
40 return item
41
43 """
44 """
48 index=random.randint(0,len(self)-1)
49 item = list.pop(self,index)
50 return item
51
52
54 """
55 """
60 bisect.insort(self.L, (self.f(item), item))
64 for item in items: self.append(item)
66 return self.L.pop()[1]
68 return self.L.pop(0)[1]
69
70
71
72
73
74
76 """
77 Depth first search queue
78 """
81
83
84
85 (source, target)=item
86 olditem=[(u,v) for (u,v) in self if v==target][0]
87 list.remove(self,olditem)
88 list.append(self,item)
89
90
92 """
93 Breadth first search queue
94 """
97
101
102
104 """
105 Random search queue
106 """
109
113
115 import doctest
116 suite = doctest.DocFileSuite('tests/queues.txt',package='networkx')
117 return suite
118
119
120 if __name__ == "__main__":
121 import os
122 import sys
123 import unittest
124 if sys.version_info[:2] < (2, 4):
125 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
126 sys.exit(-1)
127
128 nxbase=sys.path[0]+os.sep+os.pardir
129 sys.path.insert(0,nxbase)
130 unittest.TextTestRunner().run(_test_suite())
131