allpy: 88631907f23d allpy/graph.py

allpy

view allpy/graph.py @ 306:88631907f23d

Allow user to specify gap characters when parsing alignment

author	Daniil Alexeyevsky <me.dendik@gmail.com>
date	Thu, 16 Dec 2010 19:24:22 +0300
parents	73f9779491ef
children	799a60f2c70a

line source

1 # -*- coding: utf-8 -*-

3 from datetime import datetime, timedelta

4 from copy import copy

6 class TimeoutError(Exception):

7 pass

11 class Graph(object):

12 """ Undirected weighted graph

14 Data:

15 nodes -- set of elements

16 lines -- {line: cost}.

17 line is frozenset([e1, e2])

18 cost is float in (0, 1] or 1 (if all lines are equal)

20 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1})

21 >>> g.fast_cliques()

22 Fast algorithm started

23 [frozenset([1, 2]), frozenset([3])]

24 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1, frozenset([1,1]): 1})

25 >>> g.fast_cliques()

26 Fast algorithm started

27 [frozenset([1, 2]), frozenset([3])]

28 >>> g = Graph(set([1,2,3,4]), {frozenset([1,2]): 0.98, frozenset([1,3]): 0.98,

29 ... frozenset([2,3]): 0.1, frozenset([1,1]): 1})

30 >>> g.fast_cliques()

31 Fast algorithm started

32 [frozenset([1, 2, 3]), frozenset([4])]

33 >>> g.bron_kerbosh()

34 Bron and Kerbosh algorithm started

35 [frozenset([1, 2, 3]), frozenset([4])]

36 >>> g.cliques()

37 Bron and Kerbosh algorithm started

38 [frozenset([1, 2, 3])]

39 """

41 def __init__(self, nodes=None, lines=None):

42 if not nodes:

43 nodes = set()

44 if not lines:

45 lines = dict()

46 self.nodes = set(nodes) # copy

47 self.lines = {}

48 for line, cost in lines.items():

49 if len(line) == 2 and line.issubset(self.nodes):

50 self.lines[line] = cost

52 @staticmethod

53 def line(k1, k2):

54 """ Construct object, representing line of graph """

55 return frozenset([k1, k2])

57 def bounded(self, k1, k2):

58 """ Return if these two nodes of the graph are bounded with line """

59 return k1 == k2 or Graph.line(k1, k2) in self.lines

61 def count_one(self, node):

62 """ Returns number of connections of this node """

63 return len([node1 for node1 in self.nodes if self.bounded(node, node1)]) - 1

65 def cost_one(self, node):

66 """ Returns sum of costs of all connections of this node """

67 return sum([self.lines.get(Graph.line(node, node1), 0)

68 for node1 in self.nodes if node != node1])

70 def count_all(self):

71 """ Returns {node: number of connections of this node} """

72 c = dict([(node, 0) for node in self.nodes])

73 for line in self.lines:

74 for node in line:

75 c[node] += 1

76 return c

79 def drop_node(self, node):

80 """ Remove node and all involved lines """

81 for node1 in self.nodes:

82 self.lines.pop(Graph.line(node, node1), None)

83 self.nodes.discard(node)

85 def add_node(self, node, parent_graph):

86 """ Add node and corresponding lines from parent_graph

88 Added lines should be contained in self graph

89 (takes care of hanging lines)

90 """

91 self.nodes.add(node)

92 for node1 in self.nodes:

93 line = Graph.line(node, node1)

94 if line in parent_graph.lines:

95 self.lines[line] = parent_graph.lines[line]

97 def drop_nodes(self, nodes):

98 """ Run drop_node for each of given nodes

100 Returns if nodes was not empty (ugly beauty)

101 """

102 for node in nodes:

103 self.drop_node(node)

104 return bool(nodes)

105

106 def drop_if_count(self, minsize):

107 """ Run drop_node for each node, that has less than minsize lines """

108 while True:

109 if not self.drop_nodes([node for (node, count)

110 in self.count_all().items() if count < minsize]):

111 break

112

113 def bron_kerbosh(self, timeout=-1, minsize=1):

114 """ Bron and Kerboch algorithm implementation

115

116 returns list of cliques

117 clique is frozenset

118 if timeout=-1, it means infinity

119 if timeout has happened, raises TimeoutError

120

121 lava flow

122 """

123 print 'Bron and Kerbosh algorithm started'

124 cliques = []

125

126 depth = 0

127 list_candidates = [copy(self.nodes)]

128 list_used = [set()]

129 compsub = []

130

131 start_time = datetime.now()

132 timeout_timedelta = timedelta(timeout)

133

134 while True: # ????????...

135 if depth == -1:

136 break # ??????! ?????? ???????????????? (????????????????) ????????????????

137 candidates = copy(list_candidates[depth])

138 used = copy(list_used[depth])

139 if not candidates: # ???????? candidates ???? ??????????

140 depth -= 1

141 if compsub:

142 compsub.pop()

143 continue

144

145 # ?? used ???? ???????????????? ??????????????, ?????????????????????? ???? ?????????? ?????????????????? ???? candidates

146 # (?????? ???? used ???? ?????????????????? ???????? ???? ?? 1 ???? candidates)

147 used_candidates = False

148

149 for used1 in used:

150 for candidates1 in candidates:

151 if not self.bounded(used1, candidates1):

152 break

153 else:

154 used_candidates = True

155

156 if used_candidates:

157 depth -= 1

158

159 if compsub:

160 compsub.pop()

161 continue

162

163 # ???????????????? ?????????????? v ???? candidates ?? ?????????????????? ???? ?? compsub

164 v = candidates.pop()

165 candidates.add(v)

166 compsub.append(v)

167 # ?????????????????? new_candidates ?? new_used, ???????????? ???? candidates ?? used ??????????????, ???? ?????????????????????? ?? v

168 # (???? ????????, ???????????????? ???????????? ?????????????????????? ?? v)

169 new_candidates = set()

170 for candidates1 in candidates:

171 if self.bounded(candidates1, v) and candidates1 != v:

172 new_candidates.add(candidates1)

173

174 new_used = set()

175 for used1 in used:

176 if self.bounded(used1, v) and used1 != v:

177 new_used.add(used1)

178

179 # ?????????????? v ???? candidates ?? ???????????????? ?? used

180 list_candidates[depth].remove(v)

181 list_used[depth].add(v)

182 # ???????? new_candidates ?? new_used ??????????

183 if not new_candidates and not new_used:

184 # compsub ??? ??????????

185 if len(compsub) >= minsize:

186 cliques.append(frozenset(compsub))

187 else:

188 # ?????????? ???????????????????? ???????????????? bron_kerbosh(new_candidates, new_used)

189 depth += 1

190

191 # TIMEOUT check start

192 if timeout != -1:

193 if datetime.now() - start_time > timeout_timedelta:

194 raise TimeoutError

195 # TIMEOUT check end

196

197 if depth >= len(list_candidates):

198 list_candidates.append(set())

199 list_used.append(set())

200

201 list_candidates[depth] = copy(new_candidates)

202 list_used[depth] = copy(new_used)

203

204 continue

205

206 # ?????????????? v ???? compsub

207 if compsub:

208 compsub.pop()

209

210 return cliques

211

212

213 def fast_cliques(self, minsize=1):

214 """ returns list of cliques

215

216 clique is frozenset

217 """

218 print 'Fast algorithm started'

219 cliques = []

220

221 while True:

222 graph = Graph(self.nodes, self.lines)

223 for clique in cliques:

224 graph.drop_nodes(clique)

225 if not graph.nodes:

226 break

227

228 while True:

229 # drop nodes, while its is possible

230 if len(graph.nodes) == 1:

231 break

232 c = graph.count_all()

233 min_count = min(c.values())

234 bad_nodes = [node for (node, count) in c.items() if count == min_count]

235 if len(bad_nodes) == len(graph.nodes) and min_count != 0:

236 break

237

238 costs = dict([(node, graph.cost_one(node)) for node in bad_nodes])

239 min_cost = min(costs.values())

240 for node, cost in costs.items():

241 if cost == min_cost:

242 graph.drop_node(node)

243 break

244

245 while True:

246 # add nodes, while its is possible

247 candidats = {}

248 for node in self.nodes:

249 c = len([i for i in graph.nodes if self.bounded(node, i)])

250 if c == len(self.nodes):

251 graph1 = Graph(graph.nodes, graph.lines)

252 graph1.add_node(node, self)

253 candidats[node] = graph1.cost_one(node)

254 if not candidats:

255 break

256

257 max_cost = max(candidats.values())

258 node = [node for (node, cost) in candidats.items() if cost == max_cost][0]

259 graph.add_node(node, self)

260

261 cliques.append(frozenset(graph.nodes))

262

263 return cliques

264

265

266 def cliques(self, timeout=-1, minsize=1):

267 """ returns length-sorted list of cliques

268

269 clique is frozenset

270

271 can change self!

272

273 try to execute bron_kerbosh

274 if it raises TimeoutError, executes fast_cliques

275 """

276

277 self.drop_if_count(minsize)

278

279 try:

280 cliques = self.bron_kerbosh(timeout, minsize)

281 cliques.sort(key=lambda clique: len(clique), reverse=True)

282 except TimeoutError:

283 cliques = self.fast_cliques(minsize)

284 return cliques

285

286 if __name__ == "__main__":

287 import doctest

288 doctest.testmod()