How to adjust spacing and avoid overlaps for 4-directional mindmaps

[Brain]

Hi everyone,
I’m working on a GoJS diagram with a double tree layout, where nodes can expand in four directions (top, right, bottom, left). I’m dividing all my nodes based on their direction in 4 go.Set and then applying a treeLayout on every single set. However, I’m facing an issue where nodes overlap because these layouts operate independently.
I’d like to find a way to space them as they overlap dynamically.
What I’ve tried so far is changing the treeVertex “layerSpacing” property on relayout, computing bounds of overlapping node and adjusting the spacing accordingly. With this approch, however, I have a problem: when the layout regains space (by deleting or removing nodes) my algorithm does not detect that more space is available and thus does not “shrink” the layerSpacing.

         (v: go.TreeVertex) => {
            console.log("vertex initial spacing: ", v.layerSpacing, this._oldSpacing)
            if (v.parent !== null) {
                return; // Only affect root nodes
            }
            const diagram = this.diagram
            console.log("assign vertexess")

            if (diagram === null) {
                return
            }
            console.log("vertex diagram:", diagram)
            const root = v.node
            if (root == null) {
                return
            }
            console.log("vertex node:", root)

            const children = [...diagram.nodes]


            let maxSpacing = 0
            // Compare bounding boxes to detect overlaps
            for (let i = 0; i < children.length; i++) {
                for (let j = i + 1; j < children.length; j++) {
                    const child1 = children[i];
                    const child2 = children[j];

                    const bounds1 = child1.actualBounds;
                    const bounds2 = child2.actualBounds;

                    if (bounds1.intersectsRect(bounds2)) {
                        console.log(`Overlap detected between ${child1.key} and ${child2.key}`);

                        // Adjust spacing dynamically (increase the layer spacing)
                        const newSpacing = Math.abs(bounds1.bottom - bounds2.top) + 50;
                        if (newSpacing > maxSpacing) {
                            maxSpacing = newSpacing
                        }

                    }
                }
            }
            this._oldSpacing = Math.max(this._oldSpacing, maxSpacing)

            console.log("vertex spacing: ", this._oldSpacing)
            v.layerSpacing = this._oldSpacing
        }

This is my code. I don’t mind changing approach if there is a better one.
I’ll attach also a screenshot of the issue.

As you can see, on the left the node do overlap and this is what I’d like to avoid.
Thank you!

[walter]

I assume you meant “on the right”.

How would you want the conflict to be avoided?

• Move the two nodes on the right further right (extra space in the layer, but what if the downward subtree becomes really broad – i.e. wide)?
• Move the two nodes on the right upward (not centered relative to the parent, but such a skew might look bad)?
• Or move the four nodes on the bottom further down?
• Or to the left (but what if the subtree to the left grows in breadth – i.e. height)?
• Or more controversially, move the “…8d76368a” node down without moving the other three nodes down?
• Or even more controversially, make those overlapping nodes smaller so that they don’t overlap?

[Brain]

My idea was to evenly space (in all four directions, so that it doesn’t look bad) the first layer of children (push them on the “outside”) the correct amount to avoid such overlapping

[walter]

What should happen when the second or third layer is very broad, resulting in overlaps?

[Brain]

Ideally, it should continue the trend of pushing them away? Do you have any other suitable idea?

[walter]

I’ll work on a sample for you later today.

[walter]

Here’s the TypeScript definition of QuadrupleTreeLayout, which is just like DoubleTreeLayout but goes in four directions. You may want to customize the behavior of the QuadrupleTreeLayout.arrangeTrees method.

/*
 *  Copyright 1998-2025 by Northwoods Software Corporation. All Rights Reserved.
 */

/*
 * This is an extension and not part of the main GoJS library.
 * The source code for this is at extensionsJSM/QuadrupleTreeLayout.ts.
 * Note that the API for this class may change with any version, even point releases.
 * If you intend to use an extension in production, you should copy the code to your own source directory.
 * Extensions can be found in the GoJS kit under the extensions or extensionsJSM folders.
 * See the Extensions intro page (https://gojs.net/latest/intro/extensions.html) for more information.
 */

import * as go from 'gojs';

/**
 * Perform four TreeLayouts, each going different directions from a root node.
 * The choice of direction is determined by the mandatory predicate {@link directionFunction},
 * which is called on each child Node of the root Node.
 *
 * Normally there should be a single root node.  Hoewver if there are multiple root nodes
 * found in the nodes and links that this layout is responsible for, this will pretend that
 * there is a real root node and make all of the apparent root nodes children of that pretend root.
 *
 * If there is no root node, all nodes are involved in cycles, so the first given node is chosen.
 *
 * If you want to experiment with this extension, try the <a href="../../samples/quadrupleTree.html">Quadruple Tree</a> sample.
 * @category Layout Extension
 */
export class QuadrupleTreeLayout extends go.Layout {
  private _directionFunction: (node: go.Node) => number;
  private _topOptions: Partial<go.TreeLayout> | null;
  private _leftOptions: Partial<go.TreeLayout> | null;
  private _rightOptions: Partial<go.TreeLayout> | null;
  private _bottomOptions: Partial<go.TreeLayout> | null;

  constructor(init?: Partial<QuadrupleTreeLayout>) {
    super();
    this._directionFunction = (node) => 0;
    this._topOptions = null;
    this._leftOptions = null;
    this._rightOptions = null;
    this._bottomOptions = null;
    if (init) Object.assign(this, init);
  }

  /**
   * This function is called on each child node of the root node
   * in order to determine which angle the subtree starting from that child node will grow.
   * The value must be a function and must not be null.
   */
  get directionFunction(): (node: go.Node) => number {
    return this._directionFunction;
  }
  set directionFunction(value: (node: go.Node) => number) {
    if (this._directionFunction !== value) {
      if (typeof value !== 'function') {
        throw new Error('new value for QuadrupleTreeLayout.directionFunction must be a function taking a node data object and returning an angle >= zero and < 360.');
      }
      this._directionFunction = value;
      this.invalidateLayout();
    }
  }

  /**
   * Gets or sets the options to be applied to a {@link go.TreeLayout}.
   * By default this is null -- no properties are set on the TreeLayout
   * except by {@link createTreeLayout}, depending on
   * the result of calling {@link directionFunction} on a child of the root.
   */
  get topOptions(): Partial<go.TreeLayout> | null {
    return this._topOptions;
  }
  set topOptions(value: Partial<go.TreeLayout> | null) {
    if (this._topOptions !== value) {
      this._topOptions = value;
      this.invalidateLayout();
    }
  }

  /**
   * Gets or sets the options to be applied to a {@link go.TreeLayout}.
   * By default this is null -- no properties are set on the TreeLayout
   * except by {@link createTreeLayout}, depending on
   * the result of calling {@link directionFunction} on a child of the root.
   */
  get leftOptions(): Partial<go.TreeLayout> | null {
    return this._leftOptions;
  }
  set leftOptions(value: Partial<go.TreeLayout> | null) {
    if (this._leftOptions !== value) {
      this._leftOptions = value;
      this.invalidateLayout();
    }
  }

  /**
   * Gets or sets the options to be applied to a {@link go.TreeLayout}.
   * By default this is null -- no properties are set on the TreeLayout
   * except by {@link createTreeLayout}, depending on
   * the result of calling {@link directionFunction} on a child of the root.
   */
  get rightOptions(): Partial<go.TreeLayout> | null {
    return this._rightOptions;
  }
  set rightOptions(value: Partial<go.TreeLayout> | null) {
    if (this._rightOptions !== value) {
      this._rightOptions = value;
      this.invalidateLayout();
    }
  }

  /**
   * Gets or sets the options to be applied to a {@link go.TreeLayout}.
   * By default this is null -- no properties are set on the TreeLayout
   * except by {@link createTreeLayout}, depending on
   * the result of calling {@link directionFunction} on a child of the root.
   */
  get bottomOptions(): Partial<go.TreeLayout> | null {
    return this._bottomOptions;
  }
  set bottomOptions(value: Partial<go.TreeLayout> | null) {
    if (this._bottomOptions !== value) {
      this._bottomOptions = value;
      this.invalidateLayout();
    }
  }

  /**
   * @hidden @internal
   * Copies properties to a cloned Layout.
   */
  override cloneProtected(copy: this): void {
    super.cloneProtected(copy);
    copy._directionFunction = this._directionFunction;
    copy._topOptions = this._topOptions;
    copy._leftOptions = this._leftOptions;
    copy._rightOptions = this._rightOptions;
    copy._bottomOptions = this._bottomOptions;
  }

  /**
   * Perform two {@link go.TreeLayout}s by splitting the collection of Parts
   * into two separate subsets but sharing only a single root Node.
   * @param coll
   */
  override doLayout(coll: go.Diagram | go.Group | go.Iterable<go.Part>): void {
    const coll2: go.Set<go.Part> = this.collectParts(coll);
    if (coll2.count === 0) return;
    const diagram = this.diagram;
    if (diagram !== null) diagram.startTransaction('Quadruple Tree Layout');

    // split the nodes and links into two Sets, depending on direction
    let parts0 = new go.Set<go.Part>();
    let parts90 = new go.Set<go.Part>();
    let parts180 = new go.Set<go.Part>();
    let parts270 = new go.Set<go.Part>();
    const root = this.separatePartsForLayout(coll2, parts0, parts90, parts180, parts270);
    if (root === null) {
      console.log("no ROOT node found for QuadrupleTreeLayout")
      return;
    }
    // but the ROOT node will be in both collections

    // create and perform four TreeLayouts, one in each direction,
    // without moving the ROOT node, on the different subsets of nodes and links
    const layout0 = this.createTreeLayout(0);
    const layout90 = this.createTreeLayout(90);
    const layout180 = this.createTreeLayout(180);
    const layout270 = this.createTreeLayout(270);

    layout0.doLayout(parts0);
    layout90.doLayout(parts90);
    layout180.doLayout(parts180);
    layout270.doLayout(parts270);

    parts0.remove(root); parts0 = parts0.filter(p => p instanceof go.Link ? (p.fromNode !== root && p.toNode !== root) : true);
    parts90.remove(root); parts90 = parts90.filter(p => p instanceof go.Link ? (p.fromNode !== root && p.toNode !== root) : true);
    parts180.remove(root); parts180 = parts180.filter(p => p instanceof go.Link ? (p.fromNode !== root && p.toNode !== root) : true);
    parts270.remove(root); parts270 = parts270.filter(p => p instanceof go.Link ? (p.fromNode !== root && p.toNode !== root) : true);
    this.arrangeSubtrees(parts0, parts90, parts180, parts270, layout0, layout90, layout180, layout270);

    if (diagram !== null) diagram.commitTransaction('Quadruple Tree Layout');
  }

  /**
   * This just returns an instance of {@link go.TreeLayout} with the given angle,
   * with arrangement FixedRoots,
   * and initialized with the appropriate options.
   * @param angle - true for growth downward or rightward
   */
  protected createTreeLayout(angle: number): go.TreeLayout {
    const lay = new go.TreeLayout();
    let opts = null;
    switch (angle) {
      case 270: opts = this.topOptions; break;
      case 180: opts = this.leftOptions; break;
      case 0: opts = this.rightOptions; break;
      case 90: opts = this.bottomOptions; break;
      default: break;
    }
    if (opts !== null) Object.assign(lay, opts);
    lay.diagram = this.diagram;
    lay.angle = angle;
    lay.arrangement = go.TreeArrangement.FixedRoots;
    return lay;
  }

  /**
   * This is called by {@link doLayout} to split the collection of Nodes and Links into four Sets,
   * one for each angle subtree.
   * This should determine the ROOT node for the whole layout, and return it.
   * If no root can be determined, this may return null.
   * The Parts collections should be modified to include the root node and all of the descendent Nodes and Links
   * growing in its direction.
   */
  protected separatePartsForLayout(
        coll: go.Set<go.Part>,
        parts0: go.Set<go.Part>,
        parts90: go.Set<go.Part>,
        parts180: go.Set<go.Part>,
        parts270: go.Set<go.Part>
      ): go.Node | null {
    let root: go.Node | null = null; // the one root
    const roots = new go.Set<go.Node>(); // in case there are multiple roots
    coll.each((node: go.Part) => {
      if (node instanceof go.Node && node.findTreeParentNode() === null) roots.add(node);
    });
    if (roots.count === 0) {
      // just choose the first node as the root
      const it = coll.iterator;
      while (it.next()) {
        if (it.value instanceof go.Node) {
          root = it.value;
          break;
        }
      }
    } else if (roots.count === 1) {
      // normal case: just one root node
      root = roots.first();
    } else {
      // multiple root nodes -- create a dummy node to be the one real root
      root = new go.Node(); // the new root node
      root.location = new go.Point(0, 0);
      const forwards = this.diagram ? this.diagram.isTreePathToChildren : true;
      // now make dummy links from the one root node to each node
      roots.each((child) => {
        const link = new go.Link();
        if (forwards) {
          link.fromNode = root;
          link.toNode = child;
        } else {
          link.fromNode = child;
          link.toNode = root;
        }
      });
    }
    if (root === null) return null;

    // the ROOT node is shared by both subtrees
    parts0.add(root);
    parts90.add(root);
    parts180.add(root);
    parts270.add(root);
    const lay = this;
    // look at all of the immediate children of the ROOT node
    root.findTreeChildrenNodes().each((child) => {
      // in what direction is this child growing?
      const a = lay.computeAngle(child);
      const parts = a === 0 ? parts0 : (a === 90 ? parts90 : (a === 180 ? parts180 : parts270));
      // add the whole subtree starting with this child node
      parts.addAll(child.findTreeParts());
      // and also add the link from the ROOT node to this child node
      const plink = child.findTreeParentLink();
      if (plink !== null) parts.add(plink);
    });
    return root;
  }

  /**
   * This predicate is called on each child node of the root node,
   * and only on immediate children of the root.
   * It should return true if this child node is the root of a subtree that should grow
   * rightwards or downwards, or false otherwise.
   * By default it just calls the {@link directionFunction}.
   * @param child
   * @returns {number} the angle at which the subtree should grow
   */
  protected computeAngle(child: go.Node): number {
    const f = this.directionFunction;
    if (!f) throw new Error('No QuadrupleTreeLayout.directionFunction supplied on the layout');
    return f(child);
  }

  /**
   * This is called to potentially move subtrees after each subtree has been laid out on its own.
   * The Parts collections no longer include the root node nor links connecting with the root node.
   * @param parts0 
   * @param parts90 
   * @param parts180 
   * @param parts270 
   * @param layout0 
   * @param layout90 
   * @param layout180 
   * @param layout270 
   */
  protected arrangeSubtrees(
        parts0: go.Set<go.Part>,
        parts90: go.Set<go.Part>,
        parts180: go.Set<go.Part>,
        parts270: go.Set<go.Part>,
        layout0: go.TreeLayout,
        layout90: go.TreeLayout,
        layout180: go.TreeLayout,
        layout270: go.TreeLayout
      ): void {
    if (this.diagram === null) return;
    const b0 = this.diagram.computePartsBounds(parts0);
    const b90 = this.diagram.computePartsBounds(parts90);
    const b180 = this.diagram.computePartsBounds(parts180);
    const b270 = this.diagram.computePartsBounds(parts270);
    let downward = 0;
    if (b0.left < b90.right && b0.bottom > b90.top) downward = b0.bottom - b90.top + layout90.nodeSpacing;
    if (b180.right > b90.left && b180.bottom > b90.top) downward = Math.max(downward, b180.bottom - b90.top + layout90.nodeSpacing)
    this.diagram.moveParts(parts90, new go.Point(0, downward));
    let upward = 0;
    if (b0.left < b270.right && b0.top < b270.bottom) upward = b270.bottom - b0.top + layout270.nodeSpacing;
    if (b180.right > b270.left && b180.top < b270.bottom) upward = Math.max(upward, b270.bottom - b180.top + layout270.nodeSpacing)
    this.diagram.moveParts(parts270, new go.Point(0, -upward));
  }
}

Demo:

<!DOCTYPE html>
<html>
<body>
  <script type="importmap">{"imports":{"gojs":"../latest/release/go-module.js"}}</script>
  <script id="code" type="module">
import * as go from "gojs";
import { QuadrupleTreeLayout } from "./QuadrupleTreeLayout.js";

const myDiagram =
  new go.Diagram('myDiagramDiv', {
    layout: new QuadrupleTreeLayout({
        // choose the direction in which the root child node's subtree will grow
        directionFunction: (n) => n.data?.dir || 0,
        // controlling the parameters of each TreeLayout:
        //topOptions: { alignment: go.TreeAlignment.Start },
        //bottomOptions: { nodeSpacing: 0, layerSpacing: 20 },
      }
    )
  });

myDiagram.nodeTemplate = new go.Node('Auto', { isShadowed: true })
  .add(
    // define the node's outer shape
    new go.Shape('RoundedRectangle', { fill: 'lightgray', stroke: '#D8D8D8' })
      .bind('fill', 'color'),
    // define the node's text
    new go.TextBlock({ margin: 5, font: 'bold 11px Helvetica, bold Arial, sans-serif' })
      .bind('text', 'key')
  );

myDiagram.linkTemplate = new go.Link({ selectable: false }) // the whole link panel
  .add(
    new go.Shape() // the link shape
  );

// create the model for the double tree; could be eiher TreeModel or GraphLinksModel
myDiagram.model = new go.TreeModel([
  { key: 'Root' },
  { key: 'Left1', parent: 'Root', dir: 180 },
  { key: 'leaf1', parent: 'Left1' },
  { key: 'leaf2', parent: 'Left1' },
  { key: 'Left2', parent: 'Left1' },
  { key: 'leaf3', parent: 'Left2' },
  { key: 'leaf4', parent: 'Left2' },
  { key: 'leaf5', parent: 'Left1' },
  { key: 'Right1', parent: 'Root', dir: 0 },
  { key: 'Right2', parent: 'Right1' },
  { key: 'leaf11', parent: 'Right2' },
  { key: 'leaf12', parent: 'Right2' },
  { key: 'leaf13', parent: 'Right2' },
  { key: 'leaf14', parent: 'Right1' },
  { key: 'leaf15', parent: 'Right1' },
  { key: 'Right3', parent: 'Root', dir: 0 },
  { key: 'leaf16', parent: 'Right3' },
  { key: 'leaf17', parent: 'Right3' },
  { key: 'Top1', parent: 'Root', dir: 270 },
  { key: 'Top2', parent: 'Root', dir: 270 },
  { key: 'Top3', parent: 'Root', dir: 270 },
  { key: 'Top4', parent: 'Root', dir: 270 },
  { key: 'Bottom1', parent: 'Root', dir: 90 },
  { key: 'Bottom2', parent: 'Root', dir: 90 },
  { key: 'Bottom3', parent: 'Root', dir: 90 },
  { key: 'Bottom4', parent: 'Root', dir: 90 },
]);
</script>

<div id="sample">
  <div id="myDiagramDiv" style="background-color: white; border: solid 1px black; width: 100%; height: 500px"></div>
</div>
</body>
</html>