allpy
view allpy/graph.py @ 933:f3358da68bcd
Fixed two bugs in one place: base Alignment/Block
- realign used to cut sequence tails if the new alignment was wider than the
existing one
- any block modification that added new columns used to forget to add the
columns to the alignment
AFAIR, currently the only such modifications are IO, append_*, and realign()
To fix it I've:
- changed realign to use _pad_to_width() same as IO used,
- and changed _pad_to_width() to behave in a blocks-safe manner: it now calls
self._append_columns(), which in case of blocks calls itself recursively to
add columns to parent too.
author | Daniil Alexeyevsky <dendik@kodomo.fbb.msu.ru> |
---|---|
date | Tue, 22 Nov 2011 00:13:40 +0300 |
parents | f9feb1d40968 |
children | 3cc7ef543da5 |
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 """