Task: gapbs_triangle_orderedcount
Category: Graph algorithms
Difficulty: 3
Tags: gapbs,triangle_count,orderedcount,graph,csr,sorted_neighborhoods
Source: GAPBS: https://github.com/sbeamer/gapbs
Description: Triangle counting by ordered neighborhood intersection, counting each undirected triangle once.

Prompt template (YAML):
task: gapbs_triangle_orderedcount
summary: >
  Implement a GPU solution for the GAP Benchmark Suite triangle counting kernel
  using the OrderedCount strategy on an undirected graph with sorted CSR
  neighborhoods. Count each triangle exactly once using the orientation rule
  u > v > w.

inputs:
  - row_ptr: int32[n+1]
  - col_idx: int32[m]
  - params: n, m

output:
  - triangle_count: uint64 scalar

notes:
  - The graph is undirected, has no duplicate edges, and every CSR row is
    sorted in ascending vertex order.
  - Match the CPU reference semantics exactly.
  - Count a triangle only when u > v > w, matching GAPBS OrderedCount.
  - A two-pointer intersection on sorted neighborhoods is the intended core
    primitive.

interface: |
  ```c
  // Single end-to-end call. Do H2D + kernel + D2H and synchronize before returning.
  // Called multiple times (warmup + timed); must be idempotent.
  extern "C" void solution_compute(
      int n,
      const int * row_ptr,
      const int * col_idx,
      unsigned long long * triangle_count_out
  );
  ```


CPU reference implementation (C):
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static int g_n = 0;
static const int *g_row_ptr = NULL;
static const int *g_col_idx = NULL;

static void _orbench_old_init(int n, const int *row_ptr, const int *col_idx) {
    g_n = n;
    g_row_ptr = row_ptr;
    g_col_idx = col_idx;
}

static void _orbench_old_compute(unsigned long long *triangle_count_out) {
    uint64_t total = 0;
    if (!triangle_count_out || g_n <= 0 || !g_row_ptr || !g_col_idx) {
        return;
    }

    for (int u = 0; u < g_n; ++u) {
        const int u_begin = g_row_ptr[u];
        const int u_end = g_row_ptr[u + 1];
        for (int e_uv = u_begin; e_uv < u_end; ++e_uv) {
            const int v = g_col_idx[e_uv];
            if (v > u) {
                break;
            }
            int it = g_row_ptr[v];
            const int v_end = g_row_ptr[v + 1];
            for (int e_uw = u_begin; e_uw < u_end; ++e_uw) {
                const int w = g_col_idx[e_uw];
                if (w > v) {
                    break;
                }
                while (it < v_end && g_col_idx[it] < w) {
                    ++it;
                }
                if (it < v_end && g_col_idx[it] == w) {
                    ++total;
                }
            }
        }
    }

    *triangle_count_out = (unsigned long long)total;
}

// ── Unified compute_only wrapper (auto-migrated) ──
void solution_compute(int n, const int * row_ptr, const int * col_idx, unsigned long long * triangle_count_out) {
    _orbench_old_init(n, row_ptr, col_idx);
    _orbench_old_compute(triangle_count_out);
}