/usr/lib/python2.7/dist-packages/brial/cluster.py is in python-brial 1.2.0-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | # -*- python -*-
# encoding: utf-8
"""
cluster.py
Created by Michael Brickenstein on 2011-08-05.
Copyright 2011 The PolyBoRi Team. See LICENSE file.
"""
import sys
import os
from .statistics import used_vars, used_vars_set
from .PyPolyBoRi import Variable
def main():
pass
class ClusterAlgorithmFailed(Exception):
pass
class ClusterAlgorithm(object):
def __init__(self, ideal, determination_modifier=1):
if len(ideal) == 0:
raise ValueError('ideal generators list should be non empty')
self.ideal = ideal
self.determination_modifier = determination_modifier
self.used_variables_ideal = used_vars_set(ideal)
self.number_of_used_variables_in_ideal = len(self.used_variables_ideal)
self.used_variables_of_polynomial = dict(
[(p, set(p.vars_as_monomial().variables())) for p in ideal])
self.variables_introduction_mapping = dict()
self.cluster = set()
self.used_variables_cluster = set()
self.build_variables_usage()
self.initialize_variables_introduction_mapping()
def build_variables_usage(self):
self.variables_usage = dict()
for (p, variables) in self.used_variables_of_polynomial.items():
for v in variables:
self.variables_usage.setdefault(v, []).append(p)
def initialize_variables_introduction_mapping(self):
self._build_variables_introduction_mapping()
def _build_variables_introduction_mapping(self):
def var_set_to_tuple(s):
return tuple(sorted(s, key=Variable.index))
self.variables_introduction_mapping.clear()
for (p, var_set) in self.used_variables_of_polynomial.items():
if p in self.cluster:
continue
as_tuple = var_set_to_tuple(var_set.difference(self.
used_variables_cluster))
self.variables_introduction_mapping.setdefault(
as_tuple, []).append(p)
def adjust_variables_introduction_mapping(self, introduced_variables):
self._build_variables_introduction_mapping()
def determined_enough(self):
return (self.number_of_used_variables_in_cluster + self.
determination_modifier <= len(self.cluster))
def find_cluster(self):
p = self.initial_choice()
self.cluster = set()
self.add_polynomial_to_cluster(p)
while not self.determined_enough():
self.increase_cluster()
return list(self.cluster)
def add_polynomial_to_cluster(self, p):
self.cluster.add(p)
self.used_variables_cluster = set(used_vars_set(self.cluster).
variables())
self.number_of_used_variables_in_cluster = len(self.
used_variables_cluster)
self.adjust_variables_introduction_mapping(self.
used_variables_of_polynomial[p])
def initial_choice(self):
def max_key(entry):
(entry_variable, entry_polynomials) = entry
return len(entry_polynomials)
(variable, polynomials) = max(self.variables_usage.items(),
key=max_key)
def min_key(p):
return len(self.used_variables_of_polynomial[p])
return min(polynomials, key=min_key)
def increase_cluster(self):
introduced_variables_possibilities = (list(self.
variables_introduction_mapping.keys()))
introduced_variables = min(introduced_variables_possibilities, key=len)
polynomials = self.variables_introduction_mapping[introduced_variables]
assert len(polynomials) > 0
for p in polynomials:
self.add_polynomial_to_cluster(p)
if len(self.cluster) == len(self.ideal):
raise ClusterAlgorithmFailed
self.adjust_variables_introduction_mapping(introduced_variables)
def find_cluster(ideal):
algorithm = ClusterAlgorithm(ideal)
return algorithm.find_cluster()
if __name__ == '__main__':
main()
|