Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | 8x 8x 8x 8x 8x 8x 16x 8x 8x 8x 65x 8x 8x 65x 8x 317x 252x 8x 8x 8x 317x 317x 67x 67x 317x 8x 8x 8x | 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;",
];
}
|