גרפים ורשתות

function incidence(nodeCount, edges) {
  return edges.map(([tail, head]) => {
    const row = Array(nodeCount).fill(0);
    row[tail] = -1;
    row[head] = 1;
    return row;
  });
}

function componentLabels(nodeCount, edges) {
  const adjacency = Array.from({ length: nodeCount }, () => []);
  edges.forEach(([u, v]) => {
    adjacency[u].push(v);
    adjacency[v].push(u);
  });
  const labels = Array(nodeCount).fill(-1);
  let count = 0;
  for (let start = 0; start < nodeCount; start += 1) {
    if (labels[start] !== -1) continue;
    const stack = [start];
    labels[start] = count;
    while (stack.length) {
      const node = stack.pop();
      adjacency[node].forEach((neighbor) => {
        if (labels[neighbor] === -1) {
          labels[neighbor] = count;
          stack.push(neighbor);
        }
      });
    }
    count += 1;
  }
  return { labels, count };
}

const transpose = (A) =>
  A[0].map((_, j) => A.map((row) => row[j]));

const matVec = (A, x) =>
  A.map((row) =>
    row.reduce((sum, value, j) => sum + value*x[j], 0),
  );

const multiply = (A, B) => {
  const columns = transpose(B);
  return A.map((row) =>
    columns.map((column) =>
      row.reduce((sum, value, j) => sum + value*column[j], 0),
    ),
  );
};

const dot = (x, y) =>
  x.reduce((sum, value, i) => sum + value*y[i], 0);

const edges = [[0, 1], [1, 2], [2, 0], [2, 3]];
const A = incidence(4, edges);
const At = transpose(A);
const L = multiply(At, A);
const potential = [1, -1, 0, 2];
const differences = matVec(A, potential);
const balances = matVec(At, differences);
const cycleFlow = [1, 1, 1, 0];
const components = componentLabels(4, edges);

console.table(A);
console.table(L);
console.log({
  differences,
  balances,
  totalBalance: balances.reduce((sum, value) => sum + value, 0),
  constantNullVector: matVec(A, [1, 1, 1, 1]),
  cycleBalance: matVec(At, cycleFlow),
  energy: dot(differences, differences),
  sameEnergy: dot(potential, balances),
  components,
  expectedRank: 4 - components.count,
  cycleDimension: edges.length - 4 + components.count,
});

def incidence(node_count, edges):
    matrix = []
    for tail, head in edges:
        row = [0]*node_count
        row[tail], row[head] = -1, 1
        matrix.append(row)
    return matrix

def component_labels(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    for u, v in edges:
        adjacency[u].append(v)
        adjacency[v].append(u)
    labels = [-1]*node_count
    count = 0
    for start in range(node_count):
        if labels[start] != -1:
            continue
        stack = [start]
        labels[start] = count
        while stack:
            node = stack.pop()
            for neighbor in adjacency[node]:
                if labels[neighbor] == -1:
                    labels[neighbor] = count
                    stack.append(neighbor)
        count += 1
    return {"labels": labels, "count": count}

def transpose(A):
    return [list(column) for column in zip(*A)]

def mat_vec(A, x):
    return [
        sum(value*x[j] for j, value in enumerate(row))
        for row in A
    ]

def multiply(A, B):
    columns = transpose(B)
    return [
        [
            sum(a*b for a, b in zip(row, column))
            for column in columns
        ]
        for row in A
    ]

def dot(x, y):
    return sum(a*b for a, b in zip(x, y))

edges = [(0, 1), (1, 2), (2, 0), (2, 3)]
A = incidence(4, edges)
A_t = transpose(A)
L = multiply(A_t, A)
potential = [1, -1, 0, 2]
differences = mat_vec(A, potential)
balances = mat_vec(A_t, differences)
cycle_flow = [1, 1, 1, 0]
components = component_labels(4, edges)

print("A =", A)
print("L =", L)
print("differences =", differences)
print("balances =", balances, "sum =", sum(balances))
print("A*1 =", mat_vec(A, [1, 1, 1, 1]))
print("A^T*cycle =", mat_vec(A_t, cycle_flow))
print("energies =", dot(differences, differences), dot(potential, balances))
print("components =", components)
print("expected rank =", 4-components["count"])
print("cycle dimension =", len(edges)-4+components["count"])