src/galeshapley.cpp

   1 #include "galeshapley.h"
   2 #include <map>
   3 #include <deque>
   4 #include <string>
   5 #include <cassert>
   6 #include <iostream>
   7 #include <algorithm>
   8
   9 GaleShapley::
  10 GaleShapley(size_type capacidad):
  11         Susanita(capacidad)
  12 {
  13 }
  14
  15 void
  16 GaleShapley::
  17 primera_ronda() // O(N^2)
  18 {
  19         cant_comprometidos = 0;
  20         for (personas_type::iterator ih = hombres.begin(); // O(N)
  21                         ih != hombres.end(); ++ih)
  22         {
  23                 (*ih)->declarar_a(*((*ih)->prefs.front())); // O(1)
  24         }
  25
  26         // En total es O(N)*(O(N) + O(log(N))) = O(N^2)
  27         for (personas_type::iterator im = mujeres.begin(); // O(N)
  28                         im != mujeres.end(); ++im)
  29         {
  30                 Persona& m = **im;
  31                 if (m.ofertas.empty()) // O(1)
  32                         continue;
  33                 Persona* prometido = m.pop_oferta(); // O(log(N))
  34                 m.comprometer_con(*prometido); // O(N)
  35                 cant_comprometidos++;
  36         }
  37 }
  38
  39 void
  40 GaleShapley::
  41 nesima_ronda() // O(N^2)
  42 {
  43         // Todo el for es O(N^2)
  44         for (personas_type::iterator ih = hombres.begin(); // O(N)
  45                         ih != hombres.end(); ++ih)
  46         {
  47                 Persona& h = **ih;
  48                 if (h.estado == Persona::COMPROMETIDO)
  49                         continue;
  50
  51                 Persona* pm = 0;
  52                 for (personas_type::iterator im = h.prefs.begin(); // O(N)
  53                                 im != h.prefs.end(); ++im)
  54                 {
  55                         pm = *im;
  56
  57                         if (h.rechazos[pm->nombre] != NULL) // O(1)
  58                                 // Si está
  59                                 continue;
  60                         break;
  61                 }
  62                 assert(h.rechazos[pm->nombre] == NULL);
  63                 h.declarar_a(*pm); // O(1)
  64         }
  65
  66         // Todo el for es O(N^2)
  67         for (personas_type::iterator im = mujeres.begin(); // O(N)
  68                         im != mujeres.end(); ++im)
  69         {
  70                 Persona& m = **im;
  71                 if (m.ofertas.empty()) // O(1)
  72                         continue;
  73
  74                 Persona* ph = m.pop_oferta(); // O(log(N))
  75                 if (m.estado == Persona::COMPROMETIDO)
  76                 {
  77                         if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
  78                         {
  79                                 // la oferta es mejor, rompemos el compromiso
  80                                 // No cambiamos la cantidad de comprometidos
  81                                 // porque estamos cambiando uno por otro
  82                                 m.comprometer_con(*ph); // O(N)
  83                         }
  84                         else
  85                         {
  86                                 // estamos mejor con nuestra pareja actual, asi
  87                                 // que no hacemos mas que rechazar a todos
  88                                 // (incluyendo el mejor candidato)
  89                                 for (Persona::ofertas_type::iterator i // O(N)
  90                                                 = m.ofertas.begin();
  91                                                 i != m.ofertas.end(); ++i)
  92                                         (*i)->rechazos[(&m)->nombre] = &m;//O(1)
  93
  94                                 ph->rechazos[(&m)->nombre] = &m;
  95                                 m.ofertas.clear(); // O(N)
  96                         }
  97                 }
  98                 else
  99                 {
 100                         m.comprometer_con(*ph); // O(N)
 101                         cant_comprometidos++;
 102                 }
 103         }
 104 }
 105
 106 bool
 107 GaleShapley::
 108 todos_h_comprometidos() const // O(1)
 109 {
 110         if (cant_comprometidos == capacidad) {
 111                 return true;
 112         }
 113         return false;
 114 }
 115
 116
 117 void
 118 GaleShapley::
 119 casamentear() // O(N^4)
 120 {
 121         primera_ronda(); // O(N^2)
 122
 123         // El bucle podría correrse (haciendo una estimación bruta y
 124         // poco realista) N*N veces, así que sería en total O(N^4)
 125         while (!todos_h_comprometidos()) // O(1)
 126                 nesima_ronda(); // O(N^2)
 127 }
 128