src/model/constraints2.js

import { EDGES } from "./theory.js";
/**
 * Builds the MiniZinc COP for Step 2:
 * shortest path of fixed length over the chord graph.
 * MZN nodes are 1-indexed: solver path int i refers to graph.nodes[i-1].
 * @param {Object} parameters - Step-2 form params; see {@link Step2Chords#schema}.
 * @param {Object} graph - Chord graph from {@link chordGraph}.
 * @return {string} MiniZinc source.
 */
export function modelChords(parameters, graph) {
  const pathLength = parameters.bars;
  const creativity = parameters.creativity;
  const { nodes } = graph;
  const costMatrix = buildCostMatrix(graph, creativity);
  // Fallback to graph tonic when chord is opposite-mode or inactive in the graph.
  const oppositeTonic = graph.tonic === "I" ? "i" : "I";
  const resolve = (chord) =>
    graph.activeNodes.includes(chord) && chord !== oppositeTonic
      ? chord
      : graph.tonic;
  const startNode = nodes.indexOf(resolve(parameters.start_chord)) + 1;
  const endNode = nodes.indexOf(resolve(parameters.end_chord)) + 1;
  return [
    `int: n_nodes = ${nodes.length};`,
    `int: path_length = ${pathLength};`,
    `int: start_node = ${startNode};`,
    `int: end_node = ${endNode};`,
    "set of int: NODES = 1..n_nodes;",
    "set of int: PATH_INDICES = 1..path_length;",
    "array[NODES, NODES] of int: cost_matrix = [|",
    ...costMatrix.map(
      (row, r) => `  ${row.join(", ")}${r < costMatrix.length - 1 ? " |" : ""}`,
    ),
    "|];",
    "array[PATH_INDICES] of var NODES: path;",
    "var int: total_cost;",
    ...startEndChord(),
    ...minimizeCost(pathLength),
  ].join("\n");
}
/** @private Cost matrix with creativity-based (upsilon) randomization. */
function buildCostMatrix(graph, creativity) {
  const { nodes, edges, costs } = graph;
  const matrix = Array.from({ length: nodes.length }, () =>
    Array(nodes.length).fill(EDGES.MISSING),
  );
  const realCosts = edges
    .filter(([u, v]) => u !== v)
    .map(([u, v]) => costs.get(`${u}->${v}`));
  const minCost = Math.min(...realCosts);
  const maxCost = Math.max(...realCosts);
  for (const [u, v] of edges) {
    let cost = costs.get(`${u}->${v}`);
    if (creativity > 0) {
      const rand = minCost + Math.random() * (maxCost - minCost);
      cost = Math.max(
        1,
        Math.round((1 - creativity) * cost + creativity * rand),
      );
    }
    matrix[nodes.indexOf(u)][nodes.indexOf(v)] = cost;
  }
  return matrix;
}
/** @private F4: path starts at start_node (psi), ends at end_node (omega). */
function startEndChord() {
  return [
    "constraint path[1] = start_node;",
    "constraint path[path_length] = end_node;",
  ];
}
/**
 * @private H20: minimize total path (gamma_0,...,gamma_iota) cost.
 * For pathLength <= 2 the path is fully determined by start/end;
 * minimize on a determined model crashes MiniZinc-Wasm, so we fall back to satisfy.
 */
function minimizeCost(pathLength) {
  return [
    "constraint total_cost = sum(i in 1..(path_length - 1))(cost_matrix[path[i], path[i+1]]);",
    pathLength <= 2 ? "solve satisfy;" : "solve minimize total_cost;",
  ];
}