Alexis Eidelman Sidewalk Patch for LIAM2

sidewalk.patch

### Eclipse Workspace Patch 1.0
#P liam2
Index: src/alignment.py
===================================================================
--- src/alignment.py	(revision 960)
+++ src/alignment.py	(working copy)
@@ -2,6 +2,7 @@
 
 from itertools import izip
 import os
+from random import random
 
 import numpy as np
 
@@ -46,12 +47,19 @@
     return expressions, possible_values, need
 
 
+#TODO: change to ctx_length, groups, score, need, filter_value to match align() signature a bit more
 def align_get_indices_nd(ctx_length, groups, need, filter_value, score,
-                         take_filter=None, leave_filter=None):
+                         take_filter=None, leave_filter=None,
+                         method="default"):
     assert isinstance(need, np.ndarray) and \
            issubclass(need.dtype.type, np.integer)
     assert score is None or isinstance(score, (bool, int, float, np.ndarray))
+    assert method in ("default", "sidewalk")
 
+    if method == "sidewalk" and (np.max(score) > 1 or np.min(score) < 0):
+        raise Exception("Sidewalk method can only be used with a score "
+                        "between 0 and 1. You may want to use a logistic "
+                        "function.")
     if filter_value is not None:
         bool_filter_value = filter_value.copy()
     else:
@@ -114,10 +122,21 @@
                 else:
                     group_maybe_indices = members_indices
                 if isinstance(score, np.ndarray):
-                    maybe_members_rank_value = score[group_maybe_indices]
-                    sorted_local_indices = np.argsort(maybe_members_rank_value)
-                    sorted_global_indices = \
-                        group_maybe_indices[sorted_local_indices]
+                    if method == 'default':
+                        maybe_members_rank_value = score[group_maybe_indices]
+                        sorted_local_indices = \
+                            np.argsort(maybe_members_rank_value)
+                        sorted_global_indices = \
+                            group_maybe_indices[sorted_local_indices]
+                    elif method == 'sidewalk':
+#                        group_score = score[group_maybe_indices]
+#                        # np.arange
+#                        local_indices = range(len(group_maybe_indices))
+#                        sorted_local_indices = np.random.permutation(local_indices)
+#                        sorted_global_indices = \
+#                            group_maybe_indices[sorted_local_indices
+                        sorted_global_indices = \
+                            np.random.permutation(group_maybe_indices)
                 else:
                     # if the score expression is a constant, we don't need to
                     # sort indices. In that case, the alignment will first take
@@ -126,8 +145,19 @@
 
                 # maybe_to_take is always > 0
                 maybe_to_take = affected - num_always
-                # take the last X individuals (ie those with the highest score)
-                indices_to_take = sorted_global_indices[-maybe_to_take:]
+                if method == 'default':
+                    # take the last X individuals (ie those with the highest
+                    # score)
+                    indices_to_take = sorted_global_indices[-maybe_to_take:]
+                elif method == 'sidewalk':
+                    # use random() so that the first individual is not always
+                    # taken regardless of his score/probability
+                    thresholds = random() + np.arange(maybe_to_take)
+                    group_score = score[sorted_global_indices]
+                    cum_scores = np.cumsum(group_score)
+                    # extract indices where scores exceed each threshold
+                    local_ind_to_take = np.searchsorted(cum_scores, thresholds)
+                    indices_to_take = sorted_global_indices[local_ind_to_take]
 
                 underflow = maybe_to_take - len(indices_to_take)
                 if underflow > 0:
@@ -158,7 +188,8 @@
                  filter=None, take=None, leave=None,
                  expressions=None, possible_values=None,
                  errors='default', frac_need='uniform',
-                 link=None, secondary_axis=None):
+                 link=None, secondary_axis=None,
+                 method='default'):
         super(AlignmentAbsoluteValues, self).__init__(score, filter)
 
         if isinstance(need, basestring):
@@ -206,6 +237,11 @@
                             "an axis name")
         self.secondary_axis = secondary_axis
 
+        if method not in ("default", "sidewalk"):
+            raise Exception("Method for alignment should be either 'default' "
+                            "either 'sidewalk'")
+        self.method = method
+
     def traverse(self, context):
         for node in FilteredExpression.traverse(self, context):
             yield node