allpy
view allpy/graph.py @ 653:2125782780c6
50% speed up for blocks_finder due to local application of remove_contained_preblocks.
For every preblock that is going to be extended by all the groups,
I first check that the resulting preblocks don't overlap. Due to
this local check we get slight advantage in speed.
author | Boris Burkov <BurkovBA@gmail.com> |
---|---|
date | Sun, 12 Jun 2011 15:36:07 +0400 |
parents | 1fb830d7517e |
children | bb91fbc0f69f |
line source
5 pass
8 """ Undirected weighted graph
10 graph[vertex1][vertex2] = weight
11 * vertex1 != vertex2 (no such edges)
12 * weight is float in (0, 1] or 1 (if all edges are equal)
13 * symmetrical
15 Features:
16 * this graph cannot contain vertices without any edges
18 >>> g = Graph()
19 >>> g.set_edge(1, 2)
20 >>> g.fast_cliques()
21 Fast algorithm started
22 [frozenset([1, 2])]
23 >>> g.set_edge(2, 3)
24 >>> g.set_edge(1, 3)
25 >>> g.fast_cliques()
26 Fast algorithm started
27 [frozenset([1, 2, 3])]
28 >>> g.bron_kerbosh()
29 Bron and Kerbosh algorithm started
30 [frozenset([1, 2, 3])]
31 >>> g.cliques()
32 Bron and Kerbosh algorithm started
33 [frozenset([1, 2, 3])]
35 """
53 """ Remove vertex and all involved edges """
61 """ Returns sum of weights of all connections of this vertex """
68 """ Add vertex and corresponding edges from parent_graph
70 Added edges should be contained in self graph
71 (takes care of hanging edges)
72 """
78 """ Bron and Kerboch algorithm implementation
80 returns list of cliques
81 clique is frozenset
82 if timeout=-1, it means infinity
83 if timeout has happened, raises TimeoutError
84 """
97 """ return some v from candidates """
101 """ if v from used connected with all from candidates """
105 break
111 """ process call and return list of recursive calls """
143 """ drop vertices untill self becomes a clique """
157 """ add vertices untill self becomes a nonextendible clique """
169 break
179 """ returns list of cliques
181 clique is frozenset
182 """
192 break
199 break
203 """ return list of connected components, remove single vertices """
223 """ returns length-sorted list of cliques
225 clique is frozenset
227 try to execute bron_kerbosh
228 if it raises TimeoutError, executes fast_cliques
229 """