allpy
view allpy/graph.py @ 191:73f9779491ef
Renamed lib to allpy
Previously, every import looked like "from allpy.lib import ...", which
was ridiculous.
Consequences:
1. Uses of the package look like "from allpy import"
2. When testing the package locally, you have to add `pwd` to PYTHONPATH,
not `pwd`/.. (this is a good thing (tm))
3. It is now possible to make a proper Debian package
The change renames directory & fixes all imports referencing allpy.lib
The results are untested since there were no working tests before the
change.
author | Daniil Alexeyevsky <me.dendik@gmail.com> |
---|---|
date | Thu, 18 Nov 2010 19:38:05 +0300 |
parents | lib/graph.py@f7dead025719 |
children | 4e6e85851133 |
line source
1 # -*- coding: utf-8 -*-
7 pass
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 """
52 @staticmethod
54 """ Construct object, representing line of graph """
58 """ Return if these two nodes of the graph are bounded with line """
62 """ Returns number of connections of this node """
66 """ Returns sum of costs of all connections of this node """
71 """ Returns {node: number of connections of this node} """
80 """ Remove node and all involved lines """
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 """
98 """ Run drop_node for each of given nodes
100 Returns if nodes was not empty (ugly beauty)
101 """
107 """ Run drop_node for each node, that has less than minsize lines """
111 break
114 """ Bron and Kerboch algorithm implementation
116 returns list of cliques
117 clique is frozenset
118 if timeout=-1, it means infinity
119 if timeout has happened, raises TimeoutError
121 lava flow
122 """
143 continue
145 # ?? used ???? ???????????????? ??????????????, ?????????????????????? ???? ?????????? ?????????????????? ???? candidates
146 # (?????? ???? used ???? ?????????????????? ???????? ???? ?? 1 ???? candidates)
152 break
161 continue
163 # ???????????????? ?????????????? v ???? candidates ?? ?????????????????? ???? ?? compsub
167 # ?????????????????? new_candidates ?? new_used, ???????????? ???? candidates ?? used ??????????????, ???? ?????????????????????? ?? v
168 # (???? ????????, ???????????????? ???????????? ?????????????????????? ?? v)
179 # ?????????????? v ???? candidates ?? ???????????????? ?? used
182 # ???????? new_candidates ?? new_used ??????????
184 # compsub ??? ??????????
188 # ?????????? ???????????????????? ???????????????? bron_kerbosh(new_candidates, new_used)
191 # TIMEOUT check start
195 # TIMEOUT check end
204 continue
206 # ?????????????? v ???? compsub
214 """ returns list of cliques
216 clique is frozenset
217 """
226 break
229 # drop nodes, while its is possible
231 break
236 break
243 break
246 # add nodes, while its is possible
255 break
267 """ returns length-sorted list of cliques
269 clique is frozenset
271 can change self!
273 try to execute bron_kerbosh
274 if it raises TimeoutError, executes fast_cliques
275 """