From 7babf5828503c92107adafb3f0fdecb3a01f3b17 Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.home.verplant.org>
Date: Sat, 10 May 2008 11:01:54 +0200
Subject: [PATCH] src/sn_population.c: Implemented a brute force minimization
 for very good solutions.

---
 src/sn_population.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

diff --git a/src/sn_population.c b/src/sn_population.c
index 1e69092..1bfea20 100644
--- a/src/sn_population.c
+++ b/src/sn_population.c
@@ -41,6 +41,9 @@ struct sn_population_s
 {
   uint32_t size;
 
+  sn_network_t *best_network;
+  int best_rating;
+
   sn_network_t **networks;
   int *ratings;
   uint32_t networks_num;
@@ -63,6 +66,58 @@ static int rate_network (const sn_network_t *n)
   return (rate);
 } /* int rate_network */
 
+static int brute_force_minimize (sn_network_t *n_orig)
+{
+  int stage_index;
+  int comparator_index;
+
+  printf ("brute_force_minimize: Running full fledged brute force optimization.\n");
+
+  for (stage_index = 0;
+      stage_index < SN_NETWORK_STAGE_NUM (n_orig);
+      stage_index++)
+  {
+    sn_stage_t *s_orig;
+
+    s_orig = SN_NETWORK_STAGE_GET (n_orig, stage_index);
+
+    for (comparator_index = 0;
+	comparator_index < SN_STAGE_COMP_NUM (s_orig);
+	comparator_index++)
+    {
+      sn_network_t *n_copy;
+      sn_stage_t *s_copy;
+      int status;
+
+      n_copy = sn_network_clone (n_orig);
+      if (n_copy == NULL)
+	continue;
+
+      s_copy = SN_NETWORK_STAGE_GET (n_copy, stage_index);
+      sn_stage_comparator_remove (s_copy, comparator_index);
+
+      status = sn_network_brute_force_check (n_copy);
+      if (status == 0)
+      {
+	printf ("brute_force_minimize: Removed a comparator "
+	    "(stage %i, comparator %i).\n",
+	    stage_index, comparator_index);
+	sn_stage_comparator_remove (s_orig, comparator_index);
+
+	comparator_index--;
+      }
+
+      sn_network_destroy (n_copy);
+      n_copy = NULL;
+    } /* for (comparator_index) */
+  } /* for (stage_index) */
+
+  /* FIXME: Remove this check after debugging. */
+  assert (sn_network_brute_force_check (n_orig) == 0);
+  
+  return (0);
+} /* int brute_force_minimize */
+
 sn_population_t *sn_population_create (uint32_t size)
 {
   sn_population_t *p;
@@ -138,6 +193,31 @@ int sn_population_push (sn_population_t *p, sn_network_t *n)
 
   pthread_mutex_lock (&p->lock);
 
+  if (p->best_rating >= rating)
+  {
+    pthread_mutex_unlock (&p->lock);
+
+    brute_force_minimize (n_copy);
+    rating = rate_network (n_copy);
+
+    pthread_mutex_lock (&p->lock);
+  }
+
+  if ((p->best_rating >= rating)
+      || (p->best_network == NULL))
+  {
+    sn_network_t *n_copy_best;
+
+    n_copy_best = sn_network_clone (n);
+    if (n_copy_best != NULL)
+    {
+      if (p->best_network != NULL)
+	sn_network_destroy (p->best_network);
+      p->best_network = n_copy_best;
+      p->best_rating = rating;
+    }
+  }
+
   if (p->networks_num < p->size)
   {
     p->networks[p->networks_num] = n_copy;
-- 
2.11.0