如何在React项目中实现更完善的类GitHub提交网络图？

我计划在React项目中实现类似GitHub的提交网络图，核心思路是通过GitHub API获取仓库提交记录并生成网络图。目前已使用@antv/g6包实现了基础版本，编写了如下基础代码计算简单提交历史的坐标：

const x = 100, y = 100;
const dx = 150, dy = 170;

let coordinates = {};
coordinates[root] = [x, y];

let queue = [root];

while (queue.length > 0) {
    let current = queue.shift();
    let [x, y] = coordinates[current];

    if (graph[current].length === 0) {
        continue;
    } else if (graph[current].length === 1) {
        let child = graph[current][0];
        coordinates[child] = [x + dx, y];
        queue.push(child);
    } else if (graph[current].length === 2) {
        let [child1, child2] = graph[current];
        coordinates[child1] = [x + dx, y];
        coordinates[child2] = [x + dx, y + dy];
        queue.push(child1);
        queue.push(child2);
    }
}

但该方案仅适用于简单提交历史，对于存在多分支、多合并的仓库，需要更高级的实现逻辑，请问是否有更优的实现方案？

针对多分支、多合并的复杂提交历史，你可以从以下几个方向优化布局逻辑：

1. 基于拓扑排序的分层布局（核心逻辑） #

GitHub的提交图本质是有向无环图（DAG），分层布局是处理这类图的标准方案。核心思路是按提交时间从旧到新排序节点，再分层分配坐标，同时处理分支的分散与合并：

• 先对节点做拓扑排序，确保父节点始终在子节点左侧（对应时间更早）
• 为每个节点分配横向层级（layer），根节点layer=0，子节点layer=父节点layer+1
• 同一层级内的节点，根据分支数量均匀分配纵向坐标，避免重叠

示例代码片段：

// 生成拓扑排序后的节点列表（按提交时间从旧到新）
function topologicalSort(graph) {
    const inDegree = {};
    const queue = [];
    const result = [];

    // 初始化每个节点的入度
    Object.keys(graph).forEach(node => inDegree[node] = 0);
    Object.values(graph).forEach(children => {
        children.forEach(child => inDegree[child]++);
    });

    // 入度为0的根节点入队
    Object.keys(inDegree).forEach(node => {
        if (inDegree[node] === 0) queue.push(node);
    });

    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current);
        graph[current]?.forEach(child => {
            inDegree[child]--;
            if (inDegree[child] === 0) queue.push(child);
        });
    }
    return result;
}

// 计算节点坐标
function calculateCoordinates(graph, root) {
    const sortedNodes = topologicalSort(graph);
    const layerMap = {};
    const coordinates = {};
    const layerWidth = 150; // 横向层级间距
    const verticalGap = 170; // 纵向节点间距

    // 初始化根节点
    layerMap[root] = 0;
    coordinates[root] = [0, 0];

    // 遍历排序后的节点分配坐标
    sortedNodes.forEach(node => {
        const currentLayer = layerMap[node];
        const children = graph[node] || [];
        
        // 同一父节点的子节点向两侧分散，避免重叠
        children.forEach((child, index) => {
            layerMap[child] = currentLayer + 1;
            const verticalOffset = (index - (children.length - 1)/2) * verticalGap;
            coordinates[child] = [
                (currentLayer + 1) * layerWidth,
                coordinates[node][1] + verticalOffset
            ];
        });
    });

    // 处理合并节点：取所有父节点的纵向坐标平均值
    Object.keys(graph).forEach(node => {
        const parents = getParents(graph, node);
        if (parents.length > 1) {
            const avgY = parents.reduce((sum, p) => sum + coordinates[p][1], 0) / parents.length;
            coordinates[node][1] = avgY;
        }
    });

    return coordinates;
}

// 辅助函数：获取节点的所有父节点
function getParents(graph, node) {
    const parents = [];
    Object.keys(graph).forEach(parent => {
        if (graph[parent].includes(node)) parents.push(parent);
    });
    return parents;
}

2. 合并节点的特殊处理 #

合并提交节点存在多个父节点时，需让它的位置尽量靠近所有父节点的中间，同时减少连线交叉：

• 取所有父节点的纵向坐标平均值作为当前节点的纵向坐标
• 若父节点分布过宽，可适当微调父节点的纵向位置，优化连线视觉效果

3. 冲突检测与自动调整 #

针对密集分支场景，加入节点重叠检测逻辑：

• 同一层级内，检查节点纵向坐标是否重叠，若重叠则向上/向下偏移
• 使用贪心算法从左到右遍历层级，逐个调整节点位置，避免冲突

4. 结合G6内置DAG布局 #

@antv/g6内置的dagre布局专门适配有向无环图，可直接基于它扩展，减少重复造轮子：

import G6 from '@antv/g6';

const graph = new G6.Graph({
    container: 'container',
    layout: {
        type: 'dagre',
        rankdir: 'LR', // 从左到右布局（对应时间从旧到新）
        nodesep: 50, // 节点间距
        ranksep: 150, // 层级间距
    },
    // 其他配置...
});

// 加载提交图数据后渲染
graph.data(yourCommitGraphData);
graph.render();

你可以自定义dagre的节点排序规则，比如优先按提交时间排序，对合并节点做特殊位置处理。

5. 大提交量场景的性能优化 #

针对提交记录极多的仓库，需做性能优化：

• 分页加载提交记录，仅渲染当前视图内的节点
• 合并重复的分支连线，减少渲染压力
• 使用G6的虚拟渲染能力，避免内存泄漏

内容的提问来源于stack exchange，提问作者Samarthya Singh