allpy: lib/graph.py annotate

allpy

annotate lib/graph.py @ 147:db9d116e979f

documentation improvements

author	boris <bnagaev@gmail.com>
date	Sun, 24 Oct 2010 23:12:15 +0400
parents	0903179f8c34
children	f7dead025719

rev	line source
bnagaev@116	1 # -- coding: utf-8 --
bnagaev@116	2
bnagaev@121	3 from datetime import datetime, timedelta
bnagaev@116	4 from copy import copy
bnagaev@116	5
bnagaev@116	6 class TimeoutError(Exception):
bnagaev@116	7 pass
bnagaev@116	8
bnagaev@116	9
bnagaev@116	10
bnagaev@116	11 class Graph(object):
bnagaev@147	12 """ Undirected weighted graph
bnagaev@147	13
bnagaev@116	14 Data:
bnagaev@116	15 nodes -- set of elements
bnagaev@116	16 lines -- {line: cost}.
bnagaev@116	17 line is frozenset([e1, e2])
bnagaev@116	18 cost is float in (0, 1] or 1 (if all lines are equal)
bnagaev@116	19
bnagaev@116	20 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1})
bnagaev@116	21 >>> g.fast_cliques()
bnagaev@116	22 Fast algorithm started
bnagaev@116	23 [frozenset([1, 2]), frozenset([3])]
bnagaev@119	24 >>> g = Graph(set([1,2,3]), {frozenset([1,2]): 1, frozenset([1,1]): 1})
bnagaev@119	25 >>> g.fast_cliques()
bnagaev@119	26 Fast algorithm started
bnagaev@119	27 [frozenset([1, 2]), frozenset([3])]
bnagaev@116	28 >>> g = Graph(set([1,2,3,4]), {frozenset([1,2]): 0.98, frozenset([1,3]): 0.98,
bnagaev@119	29 ... frozenset([2,3]): 0.1, frozenset([1,1]): 1})
bnagaev@116	30 >>> g.fast_cliques()
bnagaev@116	31 Fast algorithm started
bnagaev@116	32 [frozenset([1, 2, 3]), frozenset([4])]
bnagaev@116	33 >>> g.bron_kerbosh()
bnagaev@116	34 Bron and Kerbosh algorithm started
bnagaev@116	35 [frozenset([1, 2, 3]), frozenset([4])]
bnagaev@119	36 >>> g.cliques()
bnagaev@119	37 Bron and Kerbosh algorithm started
bnagaev@119	38 [frozenset([1, 2, 3])]
bnagaev@116	39 """
bnagaev@116	40
bnagaev@116	41 def __init__(self, nodes=None, lines=None):
bnagaev@116	42 if not nodes:
bnagaev@116	43 nodes = set()
bnagaev@116	44 if not lines:
bnagaev@116	45 lines = dict()
bnagaev@121	46 self.nodes = set(nodes) # copy
bnagaev@119	47 self.lines = {}
bnagaev@119	48 for line, cost in lines.items():
bnagaev@119	49 if len(line) == 2 and line.issubset(self.nodes):
bnagaev@119	50 self.lines[line] = cost
bnagaev@119	51
bnagaev@117	52 @staticmethod
bnagaev@117	53 def line(k1, k2):
bnagaev@117	54 return frozenset([k1, k2])
bnagaev@116	55
bnagaev@116	56 def bounded(self, k1, k2):
bnagaev@117	57 return k1 == k2 or Graph.line(k1, k2) in self.lines
bnagaev@116	58
bnagaev@116	59 def count_one(self, node):
bnagaev@147	60 """ Returns number of connections of this node """
bnagaev@117	61 return len([node1 for node1 in self.nodes if self.bounded(node, node1)]) - 1
bnagaev@116	62
bnagaev@116	63 def cost_one(self, node):
bnagaev@147	64 """ Returns sum of costs of all connections of this node """
bnagaev@121	65 return sum([self.lines.get(Graph.line(node, node1), 0)
bnagaev@121	66 for node1 in self.nodes if node != node1])
bnagaev@116	67
bnagaev@116	68 def count_all(self):
bnagaev@147	69 """ Returns {node: number of connections of this node} """
bnagaev@116	70 c = dict([(node, 0) for node in self.nodes])
bnagaev@116	71 for line in self.lines:
bnagaev@116	72 for node in line:
bnagaev@116	73 c[node] += 1
bnagaev@116	74 return c
bnagaev@116	75
bnagaev@116	76
bnagaev@116	77 def drop_node(self, node):
bnagaev@147	78 """ Remove node and all involved lines """
bnagaev@116	79 for node1 in self.nodes:
bnagaev@117	80 self.lines.pop(Graph.line(node, node1), None)
bnagaev@116	81 self.nodes.discard(node)
bnagaev@116	82
bnagaev@116	83 def add_node(self, node, parent_graph):
bnagaev@147	84 """ Add node and corresponding lines from parent_graph
bnagaev@147	85
bnagaev@118	86 Added lines should be contained in self graph
bnagaev@118	87 (takes care of hanging lines)
bnagaev@118	88 """
bnagaev@116	89 self.nodes.add(node)
bnagaev@116	90 for node1 in self.nodes:
bnagaev@117	91 line = Graph.line(node, node1)
bnagaev@116	92 if line in parent_graph.lines:
bnagaev@117	93 self.lines[line] = parent_graph.lines[line]
bnagaev@116	94
bnagaev@116	95 def drop_nodes(self, nodes):
bnagaev@147	96 """ Run drop_node for each of given nodes
bnagaev@118	97 Returns if nodes was not empty (ugly beauty)
bnagaev@118	98 """
bnagaev@116	99 for node in nodes:
bnagaev@116	100 self.drop_node(node)
bnagaev@116	101 return bool(nodes)
bnagaev@116	102
bnagaev@116	103 def drop_if_count(self, minsize):
bnagaev@147	104 """ Run drop_node for each node, that has less than minsize lines """
bnagaev@116	105 while True:
bnagaev@121	106 if not self.drop_nodes([node for (node, count)
bnagaev@121	107 in self.count_all().items() if count < minsize]):
bnagaev@116	108 break
bnagaev@116	109
bnagaev@116	110 def bron_kerbosh(self, timeout=-1, minsize=1):
bnagaev@147	111 """ Bron and Kerboch algorithm implementation
bnagaev@147	112
bnagaev@116	113 returns list of cliques
bnagaev@116	114 clique is frozenset
bnagaev@116	115 if timeout=-1, it means infinity
bnagaev@116	116 if timeout has happened, raises TimeoutError
bnagaev@116	117
bnagaev@116	118 lava flow
bnagaev@116	119 """
bnagaev@116	120 print 'Bron and Kerbosh algorithm started'
bnagaev@116	121 cliques = []
bnagaev@116	122
bnagaev@116	123 depth = 0
bnagaev@116	124 list_candidates = [copy(self.nodes)]
bnagaev@116	125 list_used = [set()]
bnagaev@116	126 compsub = []
bnagaev@116	127
bnagaev@116	128 start_time = datetime.now()
bnagaev@121	129 timeout_timedelta = timedelta(timeout)
bnagaev@121	130
bnagaev@116	131 while True: # ????????...
bnagaev@116	132 if depth == -1:
bnagaev@116	133 break # ??????! ?????? ???????????????? (????????????????) ????????????????
bnagaev@116	134 candidates = copy(list_candidates[depth])
bnagaev@116	135 used = copy(list_used[depth])
bnagaev@116	136 if not candidates: # ???????? candidates ???? ??????????
bnagaev@116	137 depth -= 1
bnagaev@116	138 if compsub:
bnagaev@116	139 compsub.pop()
bnagaev@116	140 continue
bnagaev@116	141
bnagaev@116	142 # ?? used ???? ???????????????? ??????????????, ?????????????????????? ???? ?????????? ?????????????????? ???? candidates
bnagaev@116	143 # (?????? ???? used ???? ?????????????????? ???????? ???? ?? 1 ???? candidates)
bnagaev@116	144 used_candidates = False
bnagaev@116	145
bnagaev@116	146 for used1 in used:
bnagaev@116	147 for candidates1 in candidates:
bnagaev@116	148 if not self.bounded(used1, candidates1):
bnagaev@116	149 break
bnagaev@116	150 else:
bnagaev@116	151 used_candidates = True
bnagaev@116	152
bnagaev@116	153 if used_candidates:
bnagaev@116	154 depth -= 1
bnagaev@116	155
bnagaev@116	156 if compsub:
bnagaev@116	157 compsub.pop()
bnagaev@116	158 continue
bnagaev@116	159
bnagaev@116	160 # ???????????????? ?????????????? v ???? candidates ?? ?????????????????? ???? ?? compsub
bnagaev@116	161 v = candidates.pop()
bnagaev@116	162 candidates.add(v)
bnagaev@116	163 compsub.append(v)
bnagaev@116	164 # ?????????????????? new_candidates ?? new_used, ???????????? ???? candidates ?? used ??????????????, ???? ?????????????????????? ?? v
bnagaev@116	165 # (???? ????????, ???????????????? ???????????? ?????????????????????? ?? v)
bnagaev@116	166 new_candidates = set()
bnagaev@116	167 for candidates1 in candidates:
bnagaev@116	168 if self.bounded(candidates1, v) and candidates1 != v:
bnagaev@116	169 new_candidates.add(candidates1)
bnagaev@116	170
bnagaev@116	171 new_used = set()
bnagaev@116	172 for used1 in used:
bnagaev@116	173 if self.bounded(used1, v) and used1 != v:
bnagaev@116	174 new_used.add(used1)
bnagaev@116	175
bnagaev@116	176 # ?????????????? v ???? candidates ?? ???????????????? ?? used
bnagaev@116	177 list_candidates[depth].remove(v)
bnagaev@116	178 list_used[depth].add(v)
bnagaev@116	179 # ???????? new_candidates ?? new_used ??????????
bnagaev@116	180 if not new_candidates and not new_used:
bnagaev@116	181 # compsub ??? ??????????
bnagaev@116	182 if len(compsub) >= minsize:
bnagaev@116	183 cliques.append(frozenset(compsub))
bnagaev@116	184 else:
bnagaev@116	185 # ?????????? ???????????????????? ???????????????? bron_kerbosh(new_candidates, new_used)
bnagaev@116	186 depth += 1
bnagaev@116	187
bnagaev@116	188 # TIMEOUT check start
bnagaev@116	189 if timeout != -1:
bnagaev@121	190 if datetime.now() - start_time > timeout_timedelta:
bnagaev@116	191 raise TimeoutError
bnagaev@116	192 # TIMEOUT check end
bnagaev@116	193
bnagaev@116	194 if depth >= len(list_candidates):
bnagaev@116	195 list_candidates.append(set())
bnagaev@116	196 list_used.append(set())
bnagaev@116	197
bnagaev@116	198 list_candidates[depth] = copy(new_candidates)
bnagaev@116	199 list_used[depth] = copy(new_used)
bnagaev@116	200
bnagaev@116	201 continue
bnagaev@116	202
bnagaev@116	203 # ?????????????? v ???? compsub
bnagaev@116	204 if compsub:
bnagaev@116	205 compsub.pop()
bnagaev@116	206
bnagaev@116	207 return cliques
bnagaev@116	208
bnagaev@116	209
bnagaev@116	210 def fast_cliques(self, minsize=1):
bnagaev@147	211 """ returns list of cliques
bnagaev@147	212
bnagaev@116	213 clique is frozenset
bnagaev@116	214 """
bnagaev@116	215 print 'Fast algorithm started'
bnagaev@116	216 cliques = []
bnagaev@116	217
bnagaev@116	218 while True:
bnagaev@117	219 graph = Graph(self.nodes, self.lines)
bnagaev@116	220 for clique in cliques:
bnagaev@116	221 graph.drop_nodes(clique)
bnagaev@119	222 if not graph.nodes:
bnagaev@116	223 break
bnagaev@116	224
bnagaev@116	225 while True:
bnagaev@116	226 # drop nodes, while its is possible
bnagaev@119	227 if len(graph.nodes) == 1:
bnagaev@119	228 break
bnagaev@116	229 c = graph.count_all()
bnagaev@116	230 min_count = min(c.values())
bnagaev@116	231 bad_nodes = [node for (node, count) in c.items() if count == min_count]
bnagaev@119	232 if len(bad_nodes) == len(graph.nodes) and min_count != 0:
bnagaev@116	233 break
bnagaev@116	234
bnagaev@116	235 costs = dict([(node, graph.cost_one(node)) for node in bad_nodes])
bnagaev@116	236 min_cost = min(costs.values())
bnagaev@116	237 for node, cost in costs.items():
bnagaev@116	238 if cost == min_cost:
bnagaev@116	239 graph.drop_node(node)
bnagaev@119	240 break
bnagaev@116	241
bnagaev@116	242 while True:
bnagaev@116	243 # add nodes, while its is possible
bnagaev@116	244 candidats = {}
bnagaev@116	245 for node in self.nodes:
bnagaev@117	246 c = len([i for i in graph.nodes if self.bounded(node, i)])
bnagaev@117	247 if c == len(self.nodes):
bnagaev@117	248 graph1 = Graph(graph.nodes, graph.lines)
bnagaev@116	249 graph1.add_node(node, self)
bnagaev@116	250 candidats[node] = graph1.cost_one(node)
bnagaev@116	251 if not candidats:
bnagaev@116	252 break
bnagaev@116	253
bnagaev@116	254 max_cost = max(candidats.values())
bnagaev@116	255 node = [node for (node, cost) in candidats.items() if cost == max_cost][0]
bnagaev@116	256 graph.add_node(node, self)
bnagaev@116	257
bnagaev@116	258 cliques.append(frozenset(graph.nodes))
bnagaev@116	259
bnagaev@116	260 return cliques
bnagaev@116	261
bnagaev@116	262
bnagaev@116	263 def cliques(self, timeout=-1, minsize=1):
bnagaev@147	264 """ returns length-sorted list of cliques
bnagaev@147	265
bnagaev@116	266 clique is frozenset
bnagaev@116	267
bnagaev@116	268 can change self!
bnagaev@116	269
bnagaev@116	270 try to execute bron_kerbosh
bnagaev@116	271 if it raises TimeoutError, executes fast_cliques
bnagaev@116	272 """
bnagaev@116	273
bnagaev@117	274 self.drop_if_count(minsize)
bnagaev@116	275
bnagaev@116	276 try:
bnagaev@117	277 cliques = self.bron_kerbosh(timeout, minsize)
bnagaev@117	278 cliques.sort(key=lambda clique: len(clique), reverse=True)
bnagaev@116	279 except TimeoutError:
bnagaev@117	280 cliques = self.fast_cliques(minsize)
bnagaev@117	281 return cliques
bnagaev@116	282
bnagaev@116	283 if __name__ == "__main__":
bnagaev@116	284 import doctest
bnagaev@116	285 doctest.testmod()