allpy: lib/graph.py annotate

allpy

annotate lib/graph.py @ 116:0ef1a722b738

lib: graph.py -- class Graph with clique builbing functions

author	boris <bnagaev@gmail.com>
date	Sat, 23 Oct 2010 20:29:40 +0400
parents
children	fd7371f14c6d

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