/usr/share/pyshared/ferari/combined.py is in python-ferari 1.0.0-1.
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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | # Copyright (C) 2006 Robert C. Kirby
#
# This file is part of FErari.
#
# FErari is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# FErari is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with FErari. If not, see <http://www.gnu.org/licenses/>.
#
# First added: 2005-04-01
# Last changed: 2006-04-01
import binary, pg, build_tensors, graph
from xpermutations import xuniqueCombinations
def process_prime( vecs ):
n = len( vecs )
d = len( vecs.iteritems().next() )
# get graph of CRR weights
G = binary.get_graph( vecs , binary.rho )
# do partial geometric processing up to colinearity
p = pg.process( vecs , 1 )
# "reverse arrows" in the dependency graph
# to get a mapping from remaining vectors to their children
# this will let us enumerate
children = dict( [ (v,[]) for v in vecs ] )
for (v,parent) in p.iteritems():
if parent:
pcur = parent.iterkeys().next()
children[pcur].append( v )
# grab the things that didn't have a linear dependency
remaining = dict( [ a for a in vecs.iteritems() if not p[a[0]] ] )
# search for second order linear dependencies
Ls = pg.rp_line_finder( remaining , 2 )
vecs_to_lines = dict( [ (v,set()) for v in vecs ] )
for L in Ls:
for v in L:
vecs_to_lines[v].add( L )
def process( vecs ):
n = len( vecs )
d = len( vecs.iteritems().next() )
# get graph of CRR weights
G = binary.get_graph( vecs , binary.rho )
# do partial geometric processing up to colinearity
p = pg.process( vecs , 1 )
# "reverse arrows" in the dependency graph
# to get a mapping from remaining vectors to their children
# this will let us enumerate
children = dict( [ (v,[]) for v in vecs ] )
for (v,parent) in p.iteritems():
if parent:
pcur = parent.iterkeys().next()
children[pcur].append( v )
# grab the things that didn't have a linear dependency
remaining = dict( [ a for a in vecs.iteritems() if not p[a[0]] ])
# search for second order linear dependencies
Ls = pg.rp_line_finder( remaining , 2 )
vecs_to_triples = dict([ (v,set()) for v in vecs ])
for L in Ls:
for trip in xuniqueCombinations( list(L) , 3 ):
for c1 in [trip[0]]+ children[trip[0]]:
for c2 in [trip[1]] + children[trip[1]]:
for c3 in [trip[2]] + children[trip[2]]:
newtrip = (c1,c2,c3)
for c in newtrip:
vecs_to_triples[c].add(newtrip)
# modified Prim's algorithm
start = G.iterkeys().next()
weights = { start: 0 }
parents = { start: None }
done = set()
while weights:
u = graph.argmin( weights )
weights.pop( u )
done.add( u )
for v in G[u]:
if v not in done:
if v not in weights \
or G[u][v][0] < weights[v]:
weights[v] = G[u][v][0]
parents[v] = (u,G[u][v][0],G[u][v][1])
for trip in vecs_to_triples[u]:
undone_in_trip = set(trip).difference( done )
if len( undone_in_trip ) == 1:
vnew = undone_in_trip.pop()
if vnew not in weights or 2 < weights[vnew]:
weights[vnew] = 2
newparent = tuple(set(trip).difference((vnew,)))
parents[vnew] = (newparent,2,"lc")
return parents
def graph_cost( p , A0dict ):
s = 0
for u in p:
if p[u]:
s += p[u][1]
else:
s += binary.nnz(A0dict[u])
return s
def main():
data = []
for shape in ("tetrahedron",):
for degree in range(2,4):
A0dict = build_tensors.laplacian( shape , degree )
p = process( A0dict )
data.append( (len(A0dict),len(A0dict.itervalues().next()),\
graph_cost( p , A0dict ) ) )
print data
if __name__ == "__main__":
main()
|