8 files changed, 406 insertions, 8 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 3b0de87..1b00bfc 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -10,6 +10,7 @@ link_directories(~/.local/lib)
 file(GLOB SOURCES lib/*.c)
 add_executable(wolff_potts src/wolff_potts.c ${SOURCES})
 add_executable(wolff_vector src/wolff_vector.c ${SOURCES})
+add_executable(wolff_dgm src/wolff_dgm.c ${SOURCES})
 
 find_package(OpenMP)
 if (OPENMP_FOUND)
@@ -19,6 +20,7 @@ endif()
 
 target_link_libraries(wolff_potts gsl m cblas fftw3)
 target_link_libraries(wolff_vector gsl m cblas fftw3)
+target_link_libraries(wolff_dgm gsl m cblas fftw3)
 
-install(TARGETS wolff_potts wolff_vector DESTINATION bin)
+install(TARGETS wolff_potts wolff_vector wolff_dgm DESTINATION bin)
 
diff --git a/lib/cluster.c b/lib/cluster.c
index c800a0f..fa417fa 100644
--- a/lib/cluster.c
+++ b/lib/cluster.c
@@ -92,6 +92,93 @@ v_t flip_cluster(ising_state_t *s, v_t v0, q_t rot, gsl_rng *r) {
   return nv;
 }
 
+v_t flip_cluster_dgm(dgm_state_t *s, v_t v0, h_t rot, gsl_rng *r) {
+  v_t nv = 0;
+
+  ll_t *stack = NULL;     // create a new stack
+  stack_push(&stack, v0); // push the initial vertex to the stack
+
+  bool *marks = (bool *)calloc(s->g->nv, sizeof(bool));
+
+  while (stack != NULL) {
+    v_t v = stack_pop(&stack);
+
+    if (!marks[v]) {
+      h_t s_old, s_new;
+      dihinf_t *R_new; 
+      bool external_flipped;
+
+      marks[v] = true;
+
+      if (v == s->g->nv - 1) {
+        R_new = dihinf_compose(rot, s->R);
+        external_flipped = true;
+      } else {
+        s_old = s->spins[v];
+        s_new = dihinf_act(rot, s_old);
+        external_flipped = false;
+      }
+
+      v_t nn = s->g->v_i[v + 1] - s->g->v_i[v];
+
+      for (v_t i = 0; i < nn; i++) {
+        h_t sn;
+        double prob;
+        bool external_neighbor = false;
+
+        v_t vn = s->g->v_adj[s->g->v_i[v] + i];
+
+        if (vn == s->g->nv - 1) {
+          external_neighbor = true;
+        } else {
+          sn = s->spins[vn];
+        }
+
+        if (external_flipped || external_neighbor) {
+          h_t rot_s_old, rot_s_new;
+
+          if (external_neighbor) {
+            rot_s_old = dihinf_inverse_act(s->R, s_old);
+            rot_s_new = dihinf_inverse_act(s->R, s_new);
+          } else {
+            rot_s_old = dihinf_inverse_act(s->R, sn);
+            rot_s_new = dihinf_inverse_act(R_new, sn);
+          }
+
+          double dE = s->H(s->H_info, rot_s_old) - s->H(s->H_info, rot_s_new);
+          prob = 1.0 - exp(-dE / s->T);
+
+          s->M += rot_s_new - rot_s_old;
+          s->E += dE;
+        } else {
+          double dE = (s->J)(s_old - sn) - (s->J)(s_new - sn);
+          prob = 1.0 - exp(-dE / s->T);
+          s->E += dE;
+        }
+
+        if (gsl_rng_uniform(r) < prob) { // and with probability ps[e]...
+          stack_push(&stack, vn); // push the neighboring vertex to the stack
+        }
+      }
+
+      if (external_flipped) {
+        free(s->R);
+        s->R = R_new;
+      } else {
+        s->spins[v] = s_new;
+      }
+
+      if (v != s->g->nv - 1) { // count the number of non-external sites that flip
+        nv++;
+      }
+    }
+  }
+
+  free(marks);
+
+  return nv;
+}
+
 v_t flip_cluster_vector(vector_state_t *s, v_t v0, double *rot, gsl_rng *r) {
   v_t nv = 0;
 
diff --git a/lib/cluster.h b/lib/cluster.h
index 095ed61..2de17e5 100644
--- a/lib/cluster.h
+++ b/lib/cluster.h
@@ -21,6 +21,7 @@
 #include "measurement.h"
 #include "orthogonal.h"
 #include "dihedral.h"
+#include "dihinf.h"
 
 typedef struct {
   graph_t *g;
@@ -38,6 +39,18 @@ typedef struct {
 
 typedef struct {
   graph_t *g;
+  h_t *spins;
+  double T;
+  double (*J)(h_t);
+  double (*H)(double *, h_t);
+  double *H_info;
+  dihinf_t *R;
+  double E;
+  h_t M;
+} dgm_state_t;
+
+typedef struct {
+  graph_t *g;
   double *spins;
   double T;
   double (*J)(double);
@@ -53,5 +66,7 @@ v_t flip_cluster(ising_state_t *s, v_t v0, q_t s1, gsl_rng *r);
 
 v_t flip_cluster_vector(vector_state_t *s, v_t v0, double *rot, gsl_rng *r);
 
+v_t flip_cluster_dgm(dgm_state_t *s, v_t v0, h_t rot, gsl_rng *r);
+
 graph_t *graph_add_ext(const graph_t *g);
 
diff --git a/lib/dihinf.c b/lib/dihinf.c
new file mode 100644
index 0000000..4f88a7a
--- /dev/null
+++ b/lib/dihinf.c
@@ -0,0 +1,28 @@
+
+#include "dihinf.h"
+
+dihinf_t *dihinf_compose(h_t g1i, const dihinf_t *g2) {
+  // we only need to consider the action of reflections
+  dihinf_t *g3 = (dihinf_t *)malloc(1 * sizeof(dihinf_t));
+
+  g3->r = !g2->r;
+  g3->i = g1i - g2->i;
+
+  return g3;
+}
+
+h_t dihinf_act(h_t gi, h_t s) {
+  // we only need to consider the action of reflections
+
+  return gi - s;
+}
+
+h_t dihinf_inverse_act(const dihinf_t *g, h_t s) {
+  if (g->r) {
+    return g->i - s;
+  } else {
+    return s - g->i;
+  }
+}
+
+
diff --git a/lib/dihinf.h b/lib/dihinf.h
new file mode 100644
index 0000000..2bc7dc2
--- /dev/null
+++ b/lib/dihinf.h
@@ -0,0 +1,17 @@
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+#include "types.h"
+
+typedef struct {
+  h_t i;
+  bool r;
+} dihinf_t;
+
+dihinf_t *dihinf_compose(h_t gti, const dihinf_t *g2);
+
+h_t dihinf_act(h_t gi, h_t s);
+
+h_t dihinf_inverse_act(const dihinf_t *g, h_t s);
+
diff --git a/lib/types.h b/lib/types.h
index daac873..fcc2ce7 100644
--- a/lib/types.h
+++ b/lib/types.h
@@ -8,16 +8,18 @@ typedef uint_fast16_t L_t;
 typedef uint_fast64_t count_t;
 typedef int_fast64_t h_t;
 
-#define MAX_v INT_FAST32_MAX
-#define MAX_Q INT_FAST8_MAX
-#define MAX_D INT_FAST8_MAX
-#define MAX_L INT_FAST16_MAX
-#define MAX_COUNT INT_FAST64_MAX
+#define MAX_v UINT_FAST32_MAX
+#define MAX_Q UINT_FAST8_MAX
+#define MAX_D UINT_FAST8_MAX
+#define MAX_L UINT_FAST16_MAX
+#define MAX_COUNT UINT_FAST64_MAX
+#define MAX_H INT_FAST64_MAX
+#define MIN_H INT_FAST64_MIN
 
 #define PRIv PRIuFAST32
 #define PRIq PRIuFAST8
 #define PRID PRIuFAST8
 #define PRIL PRIuFAST16
 #define PRIcount PRIuFAST64
-#define PRIh PRIFAST64
+#define PRIh PRIdFAST64
 
diff --git a/src/wolff_dgm.c b/src/wolff_dgm.c
new file mode 100644
index 0000000..a9287f1
--- /dev/null
+++ b/src/wolff_dgm.c
@@ -0,0 +1,247 @@
+
+#include <getopt.h>
+
+#include <cluster.h>
+
+double identity(h_t x) {
+  return -pow(x, 2);
+}
+
+double basic_H(double *H, h_t x) {
+  return -H[0] * pow(x, 2);
+}
+
+int main(int argc, char *argv[]) {
+
+  L_t L = 128;
+  count_t N = (count_t)1e7;
+  count_t min_runs = 10;
+  count_t n = 3;
+  D_t D = 2;
+  double T = 2.26918531421;
+  double *H = (double *)calloc(MAX_Q, sizeof(double));
+  double eps = 0;
+  bool silent = false;
+  bool record_autocorrelation = false;
+  count_t ac_skip = 1;
+  count_t W = 10;
+
+  int opt;
+  q_t H_ind = 0;
+
+  while ((opt = getopt(argc, argv, "N:n:D:L:T:H:m:e:saS:W:")) != -1) {
+    switch (opt) {
+    case 'N':
+      N = (count_t)atof(optarg);
+      break;
+    case 'n':
+      n = (count_t)atof(optarg);
+      break;
+    case 'D':
+      D = atoi(optarg);
+      break;
+    case 'L':
+      L = atoi(optarg);
+      break;
+    case 'T':
+      T = atof(optarg);
+      break;
+    case 'H':
+      H[H_ind] = atof(optarg);
+      H_ind++;
+      break;
+    case 'm':
+      min_runs = atoi(optarg);
+      break;
+    case 'e':
+      eps = atof(optarg);
+      break;
+    case 's':
+      silent = true;
+      break;
+    case 'a':
+      record_autocorrelation = true;
+      break;
+    case 'S':
+      ac_skip = (count_t)atof(optarg);
+      break;
+    case 'W':
+      W = (count_t)atof(optarg);
+      break;
+    default:
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  gsl_rng *r = gsl_rng_alloc(gsl_rng_mt19937);
+  gsl_rng_set(r, rand_seed());
+
+  dgm_state_t *s = (dgm_state_t *)calloc(1, sizeof(dgm_state_t));
+
+  graph_t *h = graph_create_square(D, L);
+  s->g = graph_add_ext(h);
+
+  s->spins = (h_t *)calloc(h->nv, sizeof(h_t));
+
+  s->H_info = H;
+  s->T = T;
+  s->H = basic_H;
+  s->J = identity;
+
+  s->R = (dihinf_t *)calloc(1, sizeof(dihinf_t));
+
+  s->M = 0;
+  s->E = 0;
+
+  double diff = 1e31;
+  count_t n_runs = 0;
+  count_t n_steps = 0;
+
+  meas_t *E, *clust, *M, *dM;
+
+  M = (meas_t *)calloc(1, sizeof(meas_t ));
+  dM = (meas_t *)calloc(1, sizeof(meas_t ));
+
+  E = calloc(1, sizeof(meas_t));
+  clust = calloc(1, sizeof(meas_t));
+
+  autocorr_t *autocorr;
+  if (record_autocorrelation) {
+    autocorr = (autocorr_t *)calloc(1, sizeof(autocorr_t));
+    autocorr->W = 2 * W + 1;
+    autocorr->OO = (double *)calloc(2 * W + 1, sizeof(double));
+  }
+
+  if (!silent) printf("\n");
+  while (((diff > eps || diff != diff) && n_runs < N) || n_runs < min_runs) {
+    if (!silent) printf("\033[F\033[JWOLFF: sweep %" PRIu64
+           ", dH/H = %.4f, dM/M = %.4f, dC/C = %.4f, dX/X = %.4f, cps: %.1f\n",
+           n_runs, fabs(E->dx / E->x), M->dx / M->x, E->dc / E->c, M->dc / M->c, h->nv / clust->x);
+
+    count_t n_flips = 0;
+
+    while (n_flips / h->nv < n) {
+      v_t v0 = gsl_rng_uniform_int(r, h->nv);
+      h_t step = round((((double)s->M) / h->nv) + gsl_ran_gaussian(r, 5));
+
+      v_t tmp_flips = flip_cluster_dgm(s, v0, step, r);
+      n_flips += tmp_flips;
+
+      if (n_runs > 0) {
+        n_steps++;
+        update_meas(clust, tmp_flips);
+      }
+
+      if (record_autocorrelation && n_runs > 0) {
+        if (n_steps % ac_skip == 0) {
+          update_autocorr(autocorr, s->E);
+        }
+      }
+    }
+
+    update_meas(M, s->M);
+    h_t min_h, max_h;
+    min_h = MAX_H;
+    max_h = MIN_H;
+    for (v_t i = 0; i < h->nv; i++) {
+      if (s->spins[i] < min_h) {
+        min_h = s->spins[i];
+      } else if (s->spins[i] > max_h) {
+        max_h = s->spins[i];
+      }
+    }
+    update_meas(dM, max_h - min_h);
+    update_meas(E, s->E);
+
+    diff = fabs(E->dc / E->c);
+
+    n_runs++;
+  }
+  if (!silent) {
+    printf("\033[F\033[J");
+  }
+  printf("WOLFF: sweep %" PRIu64
+         ", dH/H = %.4f, dM/M = %.4f, dC/C = %.4f, dX/X = %.4f, cps: %.1f\n",
+         n_runs, fabs(E->dx / E->x), M->dx / M->x, E->dc / E->c, M->dc / M->c, h->nv / clust->x);
+
+  double tau = 0;
+  bool tau_failed = false;
+
+  if (record_autocorrelation) {
+    double *Gammas = (double *)malloc((W + 1) * sizeof(double));
+
+    Gammas[0] = 1 + rho(autocorr, 0);
+    for (uint64_t i = 0; i < W; i++) {
+      Gammas[1 + i] = rho(autocorr, 2 * i + 1) + rho(autocorr, 2 * i + 2);
+    } 
+
+    uint64_t n;
+    for (n = 0; n < W + 1; n++) {
+      if (Gammas[n] <= 0) {
+        break;
+      }
+    }
+
+    if (n == W + 1) {
+      printf("WARNING: correlation function never hit the noise floor.\n");
+      tau_failed = true;
+    }
+
+    if (n < 2) {
+      printf("WARNING: correlation function only has one nonnegative term.\n");
+      tau_failed = true;
+    }
+
+    double *conv_Gamma = get_convex_minorant(n, Gammas);
+
+    double ttau = - 0.5;
+
+    for (uint64_t i = 0; i < n + 1; i++) {
+      ttau += conv_Gamma[i];
+    }
+    
+    free(Gammas);
+    free(autocorr->OO);
+    while (autocorr->Op != NULL) {
+      stack_pop_d(&(autocorr->Op));
+    }
+    free(autocorr);
+    
+    tau = ttau * ac_skip * clust->x / h->nv;
+  }
+
+  if (tau_failed) {
+    tau = 0;
+  }
+
+  FILE *outfile = fopen("out.m", "a");
+
+  fprintf(outfile, "<|D->%" PRID ",L->%" PRIL ",T->%.15f", D, L, T);
+  fprintf(outfile, ",E->%.15f,\\[Delta]E->%.15f,C->%.15f,\\[Delta]C->%.15f,M->%.15f", E->x / h->nv, E->dx / h->nv, E->c / h->nv, E->dc / h->nv, M->x / h->nv);
+  fprintf(outfile, ",\\[Delta]M->%.15f", M->dx / h->nv);
+  fprintf(outfile, ",\\[Chi]->%.15f", M->c / h->nv);
+  fprintf(outfile, ",\\[Delta]\\[Chi]->%.15f", M->dc / h->nv);
+  fprintf(outfile, ",w->%.15f,\\[Delta]w->%.15f,wc->%.15f,\\[Delta]wc->%.15f,Subscript[n,\"clust\"]->%.15f,Subscript[\\[Delta]n,\"clust\"]->%.15f,Subscript[m,\"clust\"]->%.15f,Subscript[\\[Delta]m,\"clust\"]->%.15f,\\[Tau]->%.15f|>\n", dM->x, dM->dx, dM->c, dM->dc, clust->x / h->nv, clust->dx / h->nv, clust->c / h->nv, clust->dc / h->nv,tau);
+
+  fclose(outfile);
+
+  FILE *image = fopen("out.dat", "a");
+  for (v_t i = 0; i < h->nv; i++) {
+    fprintf(image, "%" PRIh " ", s->spins[i]);
+  }
+  fprintf(image, "\n");
+  fclose(image);
+
+  free(E);
+  free(clust);
+  free(H);
+  free(s->R);
+  free(s->spins);
+  graph_free(s->g);
+  free(s);
+  graph_free(h);
+  gsl_rng_free(r);
+
+  return 0;
+}
+
diff --git a/src/wolff_potts.c b/src/wolff_potts.c
index 845eeca..eea9ed7 100644
--- a/src/wolff_potts.c
+++ b/src/wolff_potts.c
@@ -424,7 +424,7 @@ int main(int argc, char *argv[]) {
   for (q_t i = 0; i < q; i++) {
     fprintf(outfile, ",Subscript[t,%" PRIq "]->%.15f,Subscript[\\[Delta]t,%" PRIq "]->%.15f", i, lifetimes[i]->x, i, lifetimes[i]->dx);
   }
-  fprintf(outfile, ",Subscript[n,\"clust\"]->%.15f,Subscript[\\[Delta]n,\"clust\"]->%.15f,Subscript[m,\"clust\"]->%.15f,Subscript[\\[Delta]m,\"clust\"]->%.15f,\\[tau]->%.15f|>\n", clust->x / h->nv, clust->dx / h->nv, clust->c / h->nv, clust->dc / h->nv,tau);
+  fprintf(outfile, ",Subscript[n,\"clust\"]->%.15f,Subscript[\\[Delta]n,\"clust\"]->%.15f,Subscript[m,\"clust\"]->%.15f,Subscript[\\[Delta]m,\"clust\"]->%.15f,\\[Tau]->%.15f|>\n", clust->x / h->nv, clust->dx / h->nv, clust->c / h->nv, clust->dc / h->nv,tau);
 
   fclose(outfile);