如何控制Dagre布局实现True分支左、False分支右的树形结构

问题描述 #

使用Dagre布局算法对代表分支逻辑的有向图节点进行定位，要求：

• True分支节点始终显示在其父节点左侧
• False分支节点始终显示在其父节点右侧
  仅分支的直接子节点带有hand属性（值为TRUE或FALSE），后续子节点无此属性，需保持自上而下布局的同时实现上述规则。

当前布局代码如下：

import type { LayoutAlgorithm } from '.';

const dagreLayout: LayoutAlgorithm = async (nodes, edges, options) => {
  const dagreGraph = new dagre.graphlib.Graph().setDefaultEdgeLabel(() => ({}));
  dagreGraph.setGraph({
    rankdir: options.direction, // Top-to-bottom layout
    nodesep: options.spacing[0],
    ranksep: options.spacing[1],
  });

  nodes.forEach((node) => {
    dagreGraph.setNode(node.id, {
      width: node.width ?? 0,
      height: node.height ?? 0,
    });
  });

  edges.forEach((edge) => {
    dagreGraph.setEdge(edge.source, edge.target);
  });

  dagre.layout(dagreGraph);

  const nextNodes = nodes.map((node) => {
    const { x, y } = dagreGraph.node(node.id);
    const position = {
      x: x - (node.width ?? 0) / 2,
      y: y - (node.height ?? 0) / 2,
    };

    return { ...node, position };
  });

  return { nodes: nextNodes, edges };
};

export default dagreLayout;

解决方案 #

要实现该规则，核心是通过Dagre的布局约束，强制带有hand: TRUE的直接子节点排在hand: FALSE的子节点左侧。我们可以通过添加不可见约束边的方式实现，具体步骤如下：

1. 构建父节点到子节点的映射，关联子节点的hand属性
2. 对每个有分支子节点的父节点，给TRUE和FALSE子节点之间添加一条不可见的边，强制Dagre将TRUE节点放在左侧
3. 保留原有边的正常添加逻辑，确保业务连接关系不变

修改后的完整代码：

import type { LayoutAlgorithm } from '.';

const dagreLayout: LayoutAlgorithm = async (nodes, edges, options) => {
  const dagreGraph = new dagre.graphlib.Graph().setDefaultEdgeLabel(() => ({}));
  dagreGraph.setGraph({
    rankdir: options.direction, // Top-to-bottom layout
    nodesep: options.spacing[0],
    ranksep: options.spacing[1],
  });

  // 构建父节点到子节点的映射，包含子节点的hand属性
  const parentChildrenMap = new Map<string, Array<{ nodeId: string; hand?: string }>>();
  edges.forEach(edge => {
    const childNode = nodes.find(n => n.id === edge.target);
    if (!childNode) return;
    
    if (!parentChildrenMap.has(edge.source)) {
      parentChildrenMap.set(edge.source, []);
    }
    parentChildrenMap.get(edge.source)!.push({
      nodeId: childNode.id,
      hand: childNode.hand // 仅直接子节点有该属性
    });
  });

  // 添加节点到Dagre图
  nodes.forEach((node) => {
    dagreGraph.setNode(node.id, {
      width: node.width ?? 0,
      height: node.height ?? 0,
    });
  });

  // 添加原有业务边
  edges.forEach((edge) => {
    dagreGraph.setEdge(edge.source, edge.target);
  });

  // 添加不可见约束边，强制TRUE子节点在FALSE子节点左侧
  parentChildrenMap.forEach(children => {
    const trueChild = children.find(c => c.hand === 'TRUE');
    const falseChild = children.find(c => c.hand === 'FALSE');
    
    if (trueChild && falseChild) {
      // 不可见边不会显示，但会影响布局顺序
      dagreGraph.setEdge(trueChild.nodeId, falseChild.nodeId, {
        invisible: true,
        weight: 100 // 提高权重确保该约束优先于其他默认布局规则
      });
    }
  });

  // 执行布局计算
  dagre.layout(dagreGraph);

  // 转换节点位置（保持原有逻辑）
  const nextNodes = nodes.map((node) => {
    const { x, y } = dagreGraph.node(node.id);
    const position = {
      x: x - (node.width ?? 0) / 2,
      y: y - (node.height ?? 0) / 2,
    };

    return { ...node, position };
  });

  return { nodes: nextNodes, edges };
};

export default dagreLayout;

原理说明 #

• Dagre在自上而下布局（rankdir: TB）时，同一层级（rank）的节点默认按布局算法排序，添加不可见的从TRUE到FALSE的边后，Dagre会认为这两个节点存在顺序依赖，从而强制TRUE节点排在左侧。
• 设置weight: 100是为了让该约束的优先级高于Dagre的默认布局规则，避免被其他因素干扰。
• 仅针对带有hand属性的直接子节点添加约束，后续无hand属性的子节点会由Dagre自动处理布局，不影响分支逻辑的整体结构。

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