Exact new-generation NRS solver

nrs-revamp.js

import { lusolve } from "npm:mathjs";

const path = "/home/torani/dev/nrs-impl/output/bulk.json";
const data = JSON.parse(await Deno.readTextFile(path));
const ids = Object.keys(data.entries);

const factors = [
  "AU",
  "AP",
  "MU",
  "MP",
  "CU",
  "CP",
  "AL",
  "AV",
  "AM",
  "B",
  "A",
];

const weights = [
  0.3,
  0.4,
  0.35,
  0.35,
  0.4,
  0.5,
  0.4,
  0.1,
  0.3,
  0.05,
  1.0,
];

const embed = (vector) => {
  return vector.map((score, i) => Math.pow(score, 1 / weights[i]));
};

const unembed = (vector) => {
  return vector.map((score, i) => Math.pow(score, weights[i]));
};

const vecsum = (vectors) => {
  return vectors.reduce(
    (a, b) => a.map((value, i) => value + b[i]),
    factors.map(() => 0.0),
  );
};

const vecmul = (a, b) => {
  return a.map((av, i) => av * b[i]);
};

const vec = (a) => {
  if (typeof a === "number") {
    return factors.map(() => a);
  }
  return [...a];
};

const overall = (vector) => {
  // lp norm of vector[:6] with p = 1/0.6
  let emotion = 0.0;
  for (let i = 0; i < 6; ++i) {
    if (vector[i] > 1e-4) {
      emotion += Math.pow(vector[i], 1 / 0.6);
    }
  }
  if (emotion > 1e-4) emotion = Math.pow(emotion, 0.6);

  // p = 0.7 for the next 3 elems
  let art = 0.0;
  for (let i = 6; i < 9; ++i) {
    if (vector[i] > 1e-4) {
      art += Math.pow(vector[i], 1 / 0.7);
    }
  }
  if (art > 1e-4) {
    art = Math.pow(art, 0.7);
  }

  return emotion + art + vector[9] + vector[10];
};

const calc = (cb) => {
  console.log("Started");

  const processVector = (matrix) => {
    // if matrix is number then return matrix
    if (typeof matrix === "number") {
      return factors.map(() => matrix);
    }

    const diagonal = factors.map((factor) => matrix[factor] ?? 0.0);
    if (
      Object.keys(matrix).filter((key) => factors.indexOf(key) < 0).length > 0
    ) {
      console.debug(matrix);
      throw new Error("Dense matrices are not supported");
    }

    return diagonal;
  };

  const readjustImpact = (impact) => {
    impact.score = Object.fromEntries(
      Object.entries(impact.score).map((
        [key, value],
      ) => [key, cb(value)]),
    );
  };

  for (const id of ids) {
    const entry = data.entries[id];
    for (const [childId, weight] of Object.entries(entry.children)) {
      const diagWeight = processVector(weight);
    }
    if (Object.keys(entry.children).length > 0) {
      const relation = {
        contributors: { [id]: 1 },
        references: entry.children,
        DAH_meta: {},
      };
      data.relations.push(relation);
    }
  }

  const impacts = [];
  for (const impact of data.impacts) {
    readjustImpact(impact);

    const contributors = impact.contributors;
    const score = processVector(impact.score);

    const processedImpact = {
      contributors,
      score,
    };

    impacts.push(processedImpact);
  }

  const relations = [];
  for (const relation of data.relations) {
    const contributors = relation.contributors;
    const references = relation.references;

    const processedRelation = {
      contributors,
      references,
    };

    relations.push(processedRelation);
  }

  console.log("Done processing");

  function tarjansSCC(graph) {
    let index = 0;
    const stack = [];
    const indices = new Map();
    const lowlink = new Map();
    const onStack = new Set();
    const sccs = [];

    function dfs(v) {
      indices.set(v, index);
      lowlink.set(v, index);
      index++;
      stack.push(v);
      onStack.add(v);

      for (const w of graph[v] || []) {
        if (!indices.has(w)) {
          dfs(w);
          lowlink.set(v, Math.min(lowlink.get(v), lowlink.get(w)));
        } else if (onStack.has(w)) {
          lowlink.set(v, Math.min(lowlink.get(v), indices.get(w)));
        }
      }

      if (lowlink.get(v) === indices.get(v)) {
        const scc = [];
        let w;
        do {
          w = stack.pop();
          onStack.delete(w);
          scc.push(w);
        } while (w !== v);
        sccs.push(scc);
      }
    }

    for (const v in graph) {
      if (!indices.has(v)) {
        dfs(v);
      }
    }

    return sccs;
  }

  function topoSort(graph) {
    const visited = new Set();
    const temp = new Set(); // for cycle detection (optional)
    const result = [];

    function dfs(v) {
      if (visited.has(v)) return;
      if (temp.has(v)) throw new Error("Graph is not a DAG (contains cycle)");
      temp.add(v);

      for (const neighbor of graph[v] || []) {
        dfs(neighbor);
      }

      temp.delete(v);
      visited.add(v);
      result.push(v);
    }

    for (const v in graph) {
      if (!visited.has(v)) {
        dfs(v);
      }
    }

    result.reverse(); // reverse post-order
    return result;
  }

  const graph = {};

  for (const id of ids) {
    graph[id] = [];
  }

  for (const relation of relations) {
    for (const contributor of Object.keys(relation.contributors)) {
      for (const reference of Object.keys(relation.references)) {
        graph[reference]?.push(contributor);
      }
    }
  }

  for (const id of ids) {
    graph[id] = [...new Set(graph[id])];
  }

  let sccs = tarjansSCC(graph);

  console.debug(
    ids.length,
    sccs.length,
  );

  const idsSet = new Set(ids);
  for (let i = 0; i < sccs.length; i++) {
    sccs[i] = sccs[i].filter((id) => idsSet.has(id));
  }

  sccs = sccs.filter((scc) => scc.length > 0);

  const condensedGraph = {};

  for (let i = 0; i < sccs.length; i++) {
    condensedGraph[i.toString()] = [];
  }

  const idToScc = new Map();
  for (let i = 0; i < sccs.length; i++) {
    for (const id of sccs[i]) {
      idToScc.set(id, i.toString());
    }
  }

  for (const id of ids) {
    for (const neighbor of graph[id]) {
      const fromScc = idToScc.get(id);
      const toScc = idToScc.get(neighbor);
      if (fromScc !== toScc && toScc !== undefined) {
        condensedGraph[fromScc].push(toScc);
      }
    }
  }

  for (let i = 0; i < sccs.length; i++) {
    condensedGraph[i] = [...new Set(condensedGraph[i])];
  }

  const idxOrder = topoSort(condensedGraph);

  const order = idxOrder.map((i) => sccs[parseInt(i)]);

  const scored = new Map();
  for (const scc of order) {
    const sccConstantScores = [];

    // constant pass
    for (const id of scc) {
      const affectedImpacts = [];
      const affectedRelations = [];

      for (const impact of impacts) {
        if (impact.contributors[id] !== undefined) {
          affectedImpacts.push(impact);
        }
      }

      for (const relation of relations) {
        if (
          relation.contributors[id] !== undefined
        ) {
          affectedRelations.push(relation);

          for (const ref of Object.keys(relation.references)) {
            if (!scored.has(ref) && scc.indexOf(ref) < 0) {
              throw new Error("hello");
            }
          }
        }
      }

      // score
      const constantScores = [];
      for (const affectedImpact of affectedImpacts) {
        let score = vec(affectedImpact.score);
        let weight = vec(affectedImpact.contributors[id]);
        constantScores.push(vecmul(embed(score), weight));
      }

      for (const affectedRelation of affectedRelations) {
        for (
          const [ref, weight] of Object.entries(affectedRelation.references)
        ) {
          if (scored.has(ref)) {
            const refScore = scored.get(ref);
            const weightVec = vecmul(
              vec(processVector(weight)),
              vec(processVector(affectedRelation.contributors[id])),
            );
            constantScores.push(vecmul(refScore, weightVec));
          }
        }
      }

      const constantScore = vecsum(constantScores);
      sccConstantScores.push(constantScore);
    }

    const idToIdx = new Map();
    for (let i = 0; i < scc.length; i++) {
      idToIdx.set(scc[i], i);
    }

    const mat = [];
    const n = scc.length;
    for (let j = 0; j < factors.length; j++) {
      mat[j] = [];
      for (let i = 0; i < n; i++) {
        mat[j].push(new Array(n).fill(0));
      }
    }

    for (const id of scc) {
      const affectedRelations = [];

      for (const relation of relations) {
        if (
          relation.contributors[id] !== undefined
        ) {
          affectedRelations.push(relation);
        }
      }

      const i = idToIdx.get(id);
      for (let k = 0; k < factors.length; ++k) {
        mat[k][i][i] = 1;
      }
      if (n > 2) {
      }
      for (const affectedRelation of affectedRelations) {
        for (
          const [ref, weight] of Object.entries(affectedRelation.references)
        ) {
          if (!scored.has(ref)) {
            const weightVec = vecmul(
              vec(processVector(weight)),
              vec(processVector(affectedRelation.contributors[id])),
            );

            const j = idToIdx.get(ref);

            for (let k = 0; k < factors.length; ++k) {
              mat[k][i][j] = -weightVec[k];
            }
          }
        }
      }
    }

    const scores = [];
    for (const id of scc) {
      scores.push(factors.map(() => 0.0));
    }

    for (let k = 0; k < factors.length; ++k) {
      const c = sccConstantScores.map((cs) => cs[k]);
      const x = lusolve(mat[k], c).flatMap((r) => r);
      for (let i = 0; i < scc.length; ++i) {
        scores[i][k] = x[i];
      }
    }

    // console.debug(scores);

    for (const id of scc) {
      scored.set(id, scores[idToIdx.get(id)]);
    }
  }

  for (const id of ids) {
    scored.set(id, unembed(scored.get(id)));
  }

  return Object.fromEntries(scored);
};

const positive = calc((value) => Math.max(value, 0.0));
const negative = calc((value) => -Math.min(value, 0.0));

const total = {};

for (const id of ids) {
  total[id] = positive[id].map((value, i) => value - negative[id][i]);
}

console.debug(
  Object.entries(total).map(([a, b]) => [a, overall(b)]).toSorted((a, b) =>
    b[1] - a[1]
  ),
);

console.log("Done");

absolute cinema