Skip to content

An open-source, privacy-first, self-hosted knowledge workspace where humans and AI agents work together 开源、隐私优先、自托管的知识工作空间,让人与智能体在此协作

19.4 KB
Raw Blame
import {
    IGraphCamera,
    IGraphData,
    IGraphLink,
    IGraphNode,
    IGraphSourceLink,
    IGraphSourceNode,
} from "./types";

const GOLDEN_ANGLE = Math.PI * (3 - Math.sqrt(5));
const HIGHLIGHT_EDGE_OPACITY_FACTOR = 2.5;
const MIN_AUTO_FIT_SCALE = 0.02;
const MAX_AUTO_FIT_SCALE = 1;
export const MIN_GRAPH_EDGE_WIDTH = 1;

export const getGraphEdgeOpacity = (lineOpacity: number, highlighted: boolean) =>
    Math.max(0, Math.min(1, lineOpacity * (highlighted ? HIGHLIGHT_EDGE_OPACITY_FACTOR : 1)));

export const getGraphArrowLength = (linkWidth: number, scale: number) =>
    Math.max(7, linkWidth * scale * 2.2);

export const getGraphArrowGeometry = (
    sourceX: number,
    sourceY: number,
    targetX: number,
    targetY: number,
    targetRadius: number,
    arrowLength: number,
    lineWidth = 0,
) => {
    const deltaX = targetX - sourceX;
    const deltaY = targetY - sourceY;
    const distance = Math.max(0.001, Math.hypot(deltaX, deltaY));
    const directionX = deltaX / distance;
    const directionY = deltaY / distance;
    const tipX = targetX - directionX * targetRadius;
    const tipY = targetY - directionY * targetRadius;
    return {
        baseX: tipX - directionX * arrowLength,
        baseY: tipY - directionY * arrowLength,
        directionX,
        directionY,
        lineEndX: tipX - directionX * (arrowLength + lineWidth / 2),
        lineEndY: tipY - directionY * (arrowLength + lineWidth / 2),
        tipX,
        tipY,
    };
};

export const getGraphNodeSize = (baseSize: number, definitions: number) => {
    if (definitions < 1) {
        return baseSize;
    }
    return (Math.log2(definitions) + 1) * baseSize;
};

export const normalizeGraphData = (
    sourceNodes: IGraphSourceNode[],
    sourceLinks: IGraphSourceLink[],
    nodeSize: number,
): IGraphData => {
    const nodes: IGraphNode[] = [];
    const indexById = new Map<string, number>();
    for (const sourceNode of sourceNodes) {
        if (!sourceNode.id || indexById.has(sourceNode.id)) {
            continue;
        }
        nodes.push({
            ...sourceNode,
            degree: 0,
            index: 0,
        });
        indexById.set(sourceNode.id, 0);
    }
    nodes.sort((left, right) => left.id < right.id ? -1 : left.id > right.id ? 1 : 0);
    indexById.clear();
    nodes.forEach((node, index) => {
        node.index = index;
        indexById.set(node.id, index);
    });

    const links: IGraphLink[] = [];
    for (const sourceLink of sourceLinks) {
        const source = indexById.get(sourceLink.from);
        const target = indexById.get(sourceLink.to);
        if (source === undefined || target === undefined) {
            continue;
        }
        links.push({
            source,
            target,
            ref: sourceLink.ref,
        });
        nodes[source].degree++;
        nodes[target].degree++;
    }
    links.sort((left, right) => left.source - right.source || left.target - right.target ||
        Number(left.ref) - Number(right.ref));
    const parents = new Uint32Array(nodes.length);
    const ranks = new Uint8Array(nodes.length);
    nodes.forEach((_node, index) => {
        parents[index] = index;
    });
    const findRoot = (index: number) => {
        let root = index;
        while (parents[root] !== root) {
            root = parents[root];
        }
        while (parents[index] !== index) {
            const parent = parents[index];
            parents[index] = root;
            index = parent;
        }
        return root;
    };
    links.forEach((link) => {
        let sourceRoot = findRoot(link.source);
        let targetRoot = findRoot(link.target);
        if (sourceRoot === targetRoot) {
            return;
        }
        if (ranks[sourceRoot] < ranks[targetRoot]) {
            [sourceRoot, targetRoot] = [targetRoot, sourceRoot];
        }
        parents[targetRoot] = sourceRoot;
        if (ranks[sourceRoot] === ranks[targetRoot]) {
            ranks[sourceRoot]++;
        }
    });
    const nodesByRoot = new Map<number, number[]>();
    nodes.forEach((_node, index) => {
        const root = findRoot(index);
        const nodeIndices = nodesByRoot.get(root) || [];
        nodeIndices.push(index);
        nodesByRoot.set(root, nodeIndices);
    });
    const components = Array.from(nodesByRoot.values()).map((nodeIndices) => ({
        key: nodes[nodeIndices[0]].id,
        nodeIndices,
    })).sort((left, right) => left.key < right.key ? -1 : left.key > right.key ? 1 : 0);

    const sources = new Uint32Array(links.length);
    const targets = new Uint32Array(links.length);
    const references = new Uint8Array(links.length);
    const degrees = new Uint32Array(nodes.length);
    const sizes = new Float32Array(nodes.length);
    links.forEach((link, index) => {
        sources[index] = link.source;
        targets[index] = link.target;
        references[index] = link.ref ? 1 : 0;
    });
    nodes.forEach((node, index) => {
        degrees[index] = node.degree;
        sizes[index] = getGraphNodeSize(nodeSize, node.defs || 0);
    });

    return {
        nodes,
        links,
        components,
        indexById,
        sources,
        targets,
        references,
        degrees,
        sizes,
    };
};

const hashString = (value: string) => {
    let hash = 2166136261;
    for (let index = 0; index < value.length; index++) {
        hash ^= value.charCodeAt(index);
        hash = Math.imul(hash, 16777619);
    }
    return hash >>> 0;
};

const pseudoRandom = (value: number) => {
    let hash = value + 0x6d2b79f5;
    hash = Math.imul(hash ^ hash >>> 15, hash | 1);
    hash ^= hash + Math.imul(hash ^ hash >>> 7, hash | 61);
    return ((hash ^ hash >>> 14) >>> 0) / 4294967296;
};

interface IGraphBounds {
    minX: number;
    minY: number;
    maxX: number;
    maxY: number;
}

interface IGraphComponentPlacement extends IGraphBounds {
    fixed: boolean;
    key: string;
    nodeIndices: number[];
    packingMaxX: number;
    packingMaxY: number;
    packingMinX: number;
    packingMinY: number;
}

interface IGraphPackingIndex {
    bounds: IGraphBounds[];
    cells: Map<string, number[]>;
    cellSize: number;
}

const getGraphBounds = (nodeIndices: number[], positions: Float32Array, sizes: Float32Array): IGraphBounds => {
    let minX = Number.POSITIVE_INFINITY;
    let minY = Number.POSITIVE_INFINITY;
    let maxX = Number.NEGATIVE_INFINITY;
    let maxY = Number.NEGATIVE_INFINITY;
    nodeIndices.forEach((nodeIndex) => {
        const offset = nodeIndex * 2;
        const radius = sizes[nodeIndex];
        minX = Math.min(minX, positions[offset] - radius);
        minY = Math.min(minY, positions[offset + 1] - radius);
        maxX = Math.max(maxX, positions[offset] + radius);
        maxY = Math.max(maxY, positions[offset + 1] + radius);
    });
    return {minX, minY, maxX, maxY};
};

const translateGraphNodes = (
    nodeIndices: number[],
    positions: Float32Array,
    deltaX: number,
    deltaY: number,
) => {
    nodeIndices.forEach((nodeIndex) => {
        const offset = nodeIndex * 2;
        positions[offset] += deltaX;
        positions[offset + 1] += deltaY;
    });
};

const getPackingCellKey = (x: number, y: number) => `${x}:${y}`;

const addPackingBounds = (index: IGraphPackingIndex, bounds: IGraphBounds) => {
    const boundsIndex = index.bounds.length;
    index.bounds.push(bounds);
    const minCellX = Math.floor(bounds.minX / index.cellSize);
    const minCellY = Math.floor(bounds.minY / index.cellSize);
    const maxCellX = Math.floor(bounds.maxX / index.cellSize);
    const maxCellY = Math.floor(bounds.maxY / index.cellSize);
    for (let cellX = minCellX; cellX <= maxCellX; cellX++) {
        for (let cellY = minCellY; cellY <= maxCellY; cellY++) {
            const key = getPackingCellKey(cellX, cellY);
            const cell = index.cells.get(key) || [];
            cell.push(boundsIndex);
            index.cells.set(key, cell);
        }
    }
};

const hasPackingOverlap = (index: IGraphPackingIndex, bounds: IGraphBounds) => {
    const minCellX = Math.floor(bounds.minX / index.cellSize);
    const minCellY = Math.floor(bounds.minY / index.cellSize);
    const maxCellX = Math.floor(bounds.maxX / index.cellSize);
    const maxCellY = Math.floor(bounds.maxY / index.cellSize);
    const checked = new Set<number>();
    for (let cellX = minCellX; cellX <= maxCellX; cellX++) {
        for (let cellY = minCellY; cellY <= maxCellY; cellY++) {
            const cell = index.cells.get(getPackingCellKey(cellX, cellY));
            if (!cell) {
                continue;
            }
            for (const boundsIndex of cell) {
                if (checked.has(boundsIndex)) {
                    continue;
                }
                checked.add(boundsIndex);
                const placed = index.bounds[boundsIndex];
                if (bounds.minX < placed.maxX && bounds.maxX > placed.minX &&
                    bounds.minY < placed.maxY && bounds.maxY > placed.minY) {
                    return true;
                }
            }
        }
    }
    return false;
};

export const createInitialPositions = (
    data: IGraphData,
    linkDistance: number,
    previous?: Map<string, [number, number]>,
) => {
    const positions = new Float32Array(data.nodes.length * 2);
    const spacing = Math.max(24, linkDistance * 0.35);
    const placements: IGraphComponentPlacement[] = data.components.map((component) => {
        const savedNodes: number[] = [];
        let centerX = 0;
        let centerY = 0;
        component.nodeIndices.forEach((nodeIndex) => {
            const saved = previous?.get(data.nodes[nodeIndex].id);
            if (!saved || !Number.isFinite(saved[0]) || !Number.isFinite(saved[1])) {
                return;
            }
            const offset = nodeIndex * 2;
            positions[offset] = saved[0];
            positions[offset + 1] = saved[1];
            centerX += saved[0];
            centerY += saved[1];
            savedNodes.push(nodeIndex);
        });
        const fixed = savedNodes.length > 0;
        const savedSet = new Set(savedNodes);
        if (fixed) {
            centerX /= savedNodes.length;
            centerY /= savedNodes.length;
            let savedRadius = spacing;
            savedNodes.forEach((nodeIndex) => {
                const offset = nodeIndex * 2;
                savedRadius = Math.max(savedRadius, Math.hypot(
                    positions[offset] - centerX,
                    positions[offset + 1] - centerY,
                ) + data.sizes[nodeIndex]);
            });
            let added = 0;
            component.nodeIndices.forEach((nodeIndex) => {
                if (savedSet.has(nodeIndex)) {
                    return;
                }
                const hash = hashString(data.nodes[nodeIndex].id);
                const angle = added * GOLDEN_ANGLE + (hash % 1024) / 1024;
                const radius = savedRadius + Math.sqrt(++added) * spacing;
                positions[nodeIndex * 2] = centerX + Math.cos(angle) * radius;
                positions[nodeIndex * 2 + 1] = centerY + Math.sin(angle) * radius;
            });
        } else {
            const orderedNodes = component.nodeIndices.slice().sort((left, right) =>
                data.degrees[right] - data.degrees[left] || left - right);
            orderedNodes.forEach((nodeIndex, localIndex) => {
                if (localIndex === 0) {
                    return;
                }
                const hash = hashString(data.nodes[nodeIndex].id);
                const angle = (localIndex - 1) * GOLDEN_ANGLE + (hash % 1024) / 1024;
                const radius = Math.sqrt(localIndex) * spacing;
                positions[nodeIndex * 2] = Math.cos(angle) * radius;
                positions[nodeIndex * 2 + 1] = Math.sin(angle) * radius;
            });
            const bounds = getGraphBounds(component.nodeIndices, positions, data.sizes);
            const centerX = (bounds.minX + bounds.maxX) / 2;
            const centerY = (bounds.minY + bounds.maxY) / 2;
            translateGraphNodes(component.nodeIndices, positions, -centerX, -centerY);
        }
        const bounds = getGraphBounds(component.nodeIndices, positions, data.sizes);
        const padding = component.nodeIndices.length > 1 ? Math.max(48, linkDistance * 0.75) :
            Math.max(12, data.sizes[component.nodeIndices[0]] * 1.5);
        return {
            ...bounds,
            fixed,
            key: component.key,
            nodeIndices: component.nodeIndices,
            packingMaxX: bounds.maxX + padding,
            packingMaxY: bounds.maxY + padding,
            packingMinX: bounds.minX - padding,
            packingMinY: bounds.minY - padding,
        };
    });

    const fixedPlacements = placements.filter((placement) => placement.fixed);
    const movablePlacements = placements.filter((placement) => !placement.fixed).sort((left, right) => {
        const leftArea = (left.packingMaxX - left.packingMinX) * (left.packingMaxY - left.packingMinY);
        const rightArea = (right.packingMaxX - right.packingMinX) * (right.packingMaxY - right.packingMinY);
        return rightArea - leftArea || (left.key < right.key ? -1 : left.key > right.key ? 1 : 0);
    });
    const fixedBounds = fixedPlacements.length > 0 ? getGraphBounds(
        fixedPlacements.flatMap((placement) => placement.nodeIndices), positions, data.sizes,
    ) : undefined;
    const packingCenterX = fixedBounds ? (fixedBounds.minX + fixedBounds.maxX) / 2 : 0;
    const packingCenterY = fixedBounds ? (fixedBounds.minY + fixedBounds.maxY) / 2 : 0;
    const packingIndex: IGraphPackingIndex = {
        bounds: [],
        cells: new Map(),
        cellSize: Math.max(64, linkDistance * 0.5),
    };
    fixedPlacements.forEach((placement) => {
        addPackingBounds(packingIndex, {
            minX: placement.packingMinX,
            minY: placement.packingMinY,
            maxX: placement.packingMaxX,
            maxY: placement.packingMaxY,
        });
    });
    let packingSequence = 0;
    movablePlacements.forEach((placement) => {
        const width = placement.packingMaxX - placement.packingMinX;
        const height = placement.packingMaxY - placement.packingMinY;
        let packedBounds: IGraphBounds;
        while (true) {
            const sequence = packingSequence++;
            const angle = pseudoRandom(sequence * 2) * Math.PI * 2;
            const radius = sequence === 0 ? 0 : spacing * Math.sqrt(sequence + pseudoRandom(sequence * 2 + 1));
            const centerX = packingCenterX + Math.cos(angle) * radius;
            const centerY = packingCenterY + Math.sin(angle) * radius;
            packedBounds = {
                minX: centerX - width / 2,
                minY: centerY - height / 2,
                maxX: centerX + width / 2,
                maxY: centerY + height / 2,
            };
            if (!hasPackingOverlap(packingIndex, packedBounds)) {
                break;
            }
        }
        const deltaX = packedBounds.minX - placement.packingMinX;
        const deltaY = packedBounds.minY - placement.packingMinY;
        translateGraphNodes(placement.nodeIndices, positions, deltaX, deltaY);
        addPackingBounds(packingIndex, packedBounds);
    });
    if (fixedPlacements.length === 0 && data.nodes.length > 0) {
        const nodeIndices = data.nodes.map((_node, index) => index);
        const bounds = getGraphBounds(nodeIndices, positions, data.sizes);
        const deltaX = -(bounds.minX + bounds.maxX) / 2;
        const deltaY = -(bounds.minY + bounds.maxY) / 2;
        translateGraphNodes(nodeIndices, positions, deltaX, deltaY);
    }
    return positions;
};

export const screenToGraph = (x: number, y: number, camera: IGraphCamera) => ({
    x: (x - camera.x) / camera.scale,
    y: (y - camera.y) / camera.scale,
});

export const getDraggedGraphPosition = (
    x: number,
    y: number,
    camera: IGraphCamera,
    offsetX: number,
    offsetY: number,
) => {
    const position = screenToGraph(x, y, camera);
    return {
        x: position.x + offsetX,
        y: position.y + offsetY,
    };
};

export const fitGraphCamera = (
    positions: Float32Array,
    sizes: Float32Array,
    width: number,
    height: number,
    padding = 32,
): IGraphCamera => {
    if (positions.length === 0 || width < 1 || height < 1) {
        return {scale: 1, x: width / 2, y: height / 2};
    }
    let minX = Number.POSITIVE_INFINITY;
    let minY = Number.POSITIVE_INFINITY;
    let maxX = Number.NEGATIVE_INFINITY;
    let maxY = Number.NEGATIVE_INFINITY;
    for (let index = 0; index < sizes.length; index++) {
        const radius = sizes[index];
        const x = positions[index * 2];
        const y = positions[index * 2 + 1];
        minX = Math.min(minX, x - radius);
        maxX = Math.max(maxX, x + radius);
        minY = Math.min(minY, y - radius);
        maxY = Math.max(maxY, y + radius);
    }
    const contentWidth = Math.max(1, maxX - minX);
    const contentHeight = Math.max(1, maxY - minY);
    const availableWidth = Math.max(1, width - padding * 2);
    const availableHeight = Math.max(1, height - padding * 2);
    const scale = Math.max(MIN_AUTO_FIT_SCALE, Math.min(MAX_AUTO_FIT_SCALE, availableWidth / contentWidth,
        availableHeight / contentHeight));
    return {
        scale,
        x: width / 2 - (minX + maxX) / 2 * scale,
        y: height / 2 - (minY + maxY) / 2 * scale,
    };
};

export const fitSingleNodeCamera = (
    x: number,
    y: number,
    radius: number,
    width: number,
    height: number,
    maxScale: number,
    measureLabel: (scale: number) => {height: number, width: number},
    padding = 8,
): IGraphCamera => {
    if (width < 1 || height < 1) {
        return {scale: 1, x: width / 2, y: height / 2};
    }
    const availableWidth = Math.max(1, width - padding * 2);
    const availableHeight = Math.max(1, height - padding * 2);
    const getBounds = (scale: number) => {
        const nodeRadius = Math.max(1, radius * scale);
        const labelOffset = Math.max(2, radius * scale) + 4;
        const label = measureLabel(scale);
        return {
            height: Math.max(nodeRadius * 2, label.height),
            left: -nodeRadius,
            right: labelOffset + label.width,
        };
    };
    const fits = (scale: number) => {
        const bounds = getBounds(scale);
        return bounds.right - bounds.left <= availableWidth && bounds.height <= availableHeight;
    };
    let scale = Math.max(MIN_AUTO_FIT_SCALE, Math.min(MAX_AUTO_FIT_SCALE, maxScale));
    if (!fits(scale)) {
        let minimum = MIN_AUTO_FIT_SCALE;
        let maximum = scale;
        if (fits(minimum)) {
            for (let index = 0; index < 24; index++) {
                const candidate = (minimum + maximum) / 2;
                if (fits(candidate)) {
                    minimum = candidate;
                } else {
                    maximum = candidate;
                }
            }
            scale = minimum;
        } else {
            scale = minimum;
        }
    }
    const bounds = getBounds(scale);
    const centerX = (bounds.left + bounds.right) / 2;
    return {
        scale,
        x: width / 2 - centerX - x * scale,
        y: height / 2 - y * scale,
    };
};

export const centerGraphCamera = (
    positions: Float32Array,
    sizes: Float32Array,
    width: number,
    height: number,
    scale: number,
): IGraphCamera => {
    const fitted = fitGraphCamera(positions, sizes, width, height);
    const graphCenterX = (width / 2 - fitted.x) / fitted.scale;
    const graphCenterY = (height / 2 - fitted.y) / fitted.scale;
    return {
        scale,
        x: width / 2 - graphCenterX * scale,
        y: height / 2 - graphCenterY * scale,
    };
};