Layout Algorithm

[moklick]

It would be nice to have an automatic layout like breadth first tree or something like that we could use to order the graph

[shaabanban]

Was writing something similar... found this library to be an excellent resource https://github.com/dagrejs/dagre

[codie3611]

Also worth noting is https://github.com/erikbrinkman/d3-dag

[antoinne85]

Cytoscape has several extensions for managing layout as well, if you'd like mor options and examples.

https://js.cytoscape.org/#extensions/layout-extensions

[moklick]

Thanks for the links. Dagre looks really nice but I think it would be an overhead for this project. I don't want to add another dependency here. Maybe we should create a plugin like react-flow-layouter that is not part of the core module.

[bartvanremortele]

I suggest to also take a look at WebCola which is a constraint based layout.

[Tallyb]

EXCELLENT LIBRARY! thank you so much.

Here is an example of how to use dagre. It assumes you get an array of elements that contains a links field. The names on elements and on links are unique and can be used as keys. (Adjust this as per your data).

import dagre from 'dagre';

const NODE_WIDTH = 200;
const NODE_HEIGHT = 50;

const generateFlow = (elements: Array<element>) => {

  const g = new dagre.graphlib.Graph();
  g.setGraph({});
  g.setDefaultEdgeLabel(function() { return {}; });

  elements.forEach ((e:any) =>  {
    g.setNode(e.name, {
      label: e.name,
      width: NODE_WIDTH,
      height: NODE_HEIGHT
    });
    e.links.forEach((i: any) => {
      g.setEdge(e.name, i.name);
    });
  });

  dagre.layout(g);

  const nodes = g.nodes().map((i: any) => {
    let n = g.node(i);
    return {
      id: i,
      data: {
        label: i
      },
      width: n.width, 
      height: n.height,
      position: { 
        x: n.x - n.width /2,
        y: n.y - n.height / 2
      },
    };
  });

  const edges = g.edges().map((e:any) => ({
    id: `__${e.v}__${e.w}`,
    points: g.edge(e).points,
    source: e.w,
    target: e.v,
    animated: true 

  }));

  return [...nodes, ...edges];
};

[moklick]

Hey @Tallyb

thanks :) this looks good.

[mymywang]

Thanks for the sample code! I'm also trying to integrate with dagre, but I need to get the node's DOM size instead of hardcoding the NODE_WIDTH and NODE_HEIGHT for layout. It's because the node size is dynamic depending on the content inside the node.

I'm trying to set ref to my custom node elements, and grab the node DOM size after the initial rendering, and then use dagre to do auto-layout. However, because the rendering of the custom node is controlled inside react-flow, I can't find a way to set the ref.

Do you have any suggestions? Is there a way I can access the node DOM elements? @moklick @Tallyb Thanks in advance!

Edit: Apparently I could do it by document.getElementById() but I'd like to see if there's a better way.

[moklick]

Hey @mymywang

we are tracking the current dimension of each node under node.__rf.width and node.__rf.height. You can get the nodes from the store as seen in the provider example. We are updating the dimensions when the size changes. Does it help?

[mymywang]

@moklick Yes that's exactly what I was looking for. Appreciate your fast reply!

[lisandro-jofre]

@moklick Yes that's exactly what I was looking for. Appreciate your fast reply!

Could you paste a code sample of how you implemented dynamic dimensions?

[charithreddyv]

EXCELLENT LIBRARY! thank you so much.

Here is an example of how to use dagre. It assumes you get an array of elements that contains a links field. The names on elements and on links are unique and can be used as keys. (Adjust this as per your data).

import dagre from 'dagre';

const NODE_WIDTH = 200;
const NODE_HEIGHT = 50;

const generateFlow = (elements: Array<element>) => {

  const g = new dagre.graphlib.Graph();
  g.setGraph({});
  g.setDefaultEdgeLabel(function() { return {}; });

  elements.forEach ((e:any) =>  {
    g.setNode(e.name, {
      label: e.name,
      width: NODE_WIDTH,
      height: NODE_HEIGHT
    });
    e.links.forEach((i: any) => {
      g.setEdge(e.name, i.name);
    });
  });

  dagre.layout(g);

  const nodes = g.nodes().map((i: any) => {
    let n = g.node(i);
    return {
      id: i,
      data: {
        label: i
      },
      width: n.width, 
      height: n.height,
      position: { 
        x: n.x - n.width /2,
        y: n.y - n.height / 2
      },
    };
  });

  const edges = g.edges().map((e:any) => ({
    id: `__${e.v}__${e.w}`,
    points: g.edge(e).points,
    source: e.w,
    target: e.v,
    animated: true 

  }));

  return [...nodes, ...edges];
};

can you please share a code sandbox would help us out , thanks in advance

[mymywang]

@lisandro-jofre This is the code I implemented. I created a util function to generate layout with dagre. The input is the node states from react flow, which contains node dimension node.__rf.width.

import dagre, { GraphLabel } from 'dagre';
import { Node } from 'react-flow-renderer';

const createGraphLayout = (flowNodeStates: Node[]): Node[] => {
  const g = new dagre.graphlib.Graph({ directed });
  g.setGraph({ ranker: 'tight-tree' });

  // Default to assigning a new object as a label for each new edge.
  g.setDefaultEdgeLabel(() => ({}));

  flowNodeStates.forEach((node) => {
    g.setNode(node.id, {
      label: node.id,
      width: node.__rf.width,
      height: node.__rf.height,
    });
    // My node data contains out bound edges. You can set edge based on your data structure of the graph.
    node.data.outBoundEdges &&
      node.data.outBoundEdges.forEach((edge) => {
        g.setEdge(node.id, edge.targetNodeId);
      });
  });

  dagre.layout(g);

  return flowNodeStates.map((nodeState) => {
    const node = g.node(nodeState.id);
    return {
      ...nodeState,
      position: {
        // The position from dagre layout is the center of the node.
        // Calculating the position of the top left corner for rendering.
        x: node.x - node.width / 2,
        y: node.y - node.height / 2,
      },
    };
  });
};

Then I invoke this function from my react flow component when shouldLayout is true. It's true by default so it will be invoked in the initial render. After layout is generated, fit the graph in the view.

const MyGraph: React.FC = () => {
  // Get node states for dimensions from react flow
  const nodeStates = useStoreState((store) => store.nodes);
  const fitViewAction = useStoreActions((actions) => actions.fitView);
  const [shouldLayout, setShouldLayout] = useState<boolean>(true);
  const [shouldFitView, setShouldFitView] = useState<boolean>(false);

  useEffect(() => {
    if (shouldLayout && arrayHasLength(nodeStates) && nodeStates.every(nodeHasDimension)) {
      // Invoke the util function
      const elementsWithLayout: Elements = createGraphLayout(nodeStates);
      setFlowElements(elementsWithLayout);
      setShouldLayout(false);
      setShouldFitView(true);
    }
  }, [shouldLayout, nodeStates]);

  useEffect(() => {
    if (shouldFitView && fitViewAction) {
      fitViewAction({ padding: 0.5 });
      setShouldFitView(false);
    }
  }, [shouldFitView]);

  return (
    <ReactFlow ... />
  )
}

[moklick]

I added an example based on dagre to the website: https://reactflow.dev/examples/layouting/

[OrhanTozan]

@mymywang @moklick this example doesn't work for me, React Flow doesn't seem to rerender. Even after performing fitView(). (All nodes get rendered on top of each other). This is despite the nodes state returned by useStoreState actually contains nodes with different x and y positions.

[moklick]

Hey @OrhanTozan

is the example not working in your browser? Or did you re-implement it?

[OrhanTozan]

Nvm I had to strip away the _rf properties from the nodes

[el3ctrician]

This is very nice but open a very big issue : https://github.com/dagrejs/dagre/pull/271 without support for manual ranking the layout is very unusable ...

[moklick]

Hey @el3ctrician

dagre is just one option. It's simple to setup and easy to use.

We used elkjs for more complex layouts.

[moklick]

I will close this issue since it's clear that we will not add layouting to the react flow core.

For simple layouts we recommend dagre and for more complex ones elkjs.

We have an example of how to do layouting with react-flow in the layout example.

[baughmann]

Is there a decent way to deal with overlapping edges? For example, many nodes in my implementation have several different edges that may connect the same two nodes back and fourth. What might be a good way to deal with this?

This implementation of laying out will overlap the connections and make them appear as one, and it does not seem possible to set a position on an edge because it just connects two nodes together.

[gigiskarlett]

Hey @el3ctrician

dagre is just one option. It's simple to setup and easy to use.

We used elkjs for more complex layouts.

Is there an example of React FLow using elks? @moklick

[moklick]

Not that I know..

[litewarp]

In case anyone is curious, here is an Elk example of the createGraphLayout function. Only tricky part is that you need to load/return your elements as a promise since the elk.layout call is asynchronous.

const DEFAULT_WIDTH = 75
const DEFAULT_HEIGHT = 75

const elk = new Elk({
  defaultLayoutOptions: {
    'elk.algorithm': 'layered',
    'elk.direction': 'RIGHT',
    'elk.spacing.nodeNode': '75',
    'elk.layered.spacing.nodeNodeBetweenLayers': '75'
  }
})

const createGraphLayout = async (elements: Elements): Promise<Elements> => {
  const nodes: ElkNode[] = []
  const edges: ElkPrimitiveEdge[] = []

  elements.forEach((el) => {
    if (isNode(el)) {
      nodes.push({
        id: el.id,
        width: el.__rf?.width ?? DEFAULT_WIDTH,
        height: el.__rf?.height ?? DEFAULT_HEIGHT
      })
    } else {
      edges.push({
        id: el.id,
        target: el.target,
        source: el.source
      })
    }
  })

  const newGraph = await elk.layout({
    id: 'root',
    children: nodes,
    edges: edges
  })
  return elements.map((el) => {
    if (isNode(el)) {
      const node = newGraph?.children?.find((n) => n.id === el.id)
      if (node?.x && node?.y && node?.width && node?.height) {
        el.position = {
          x: node.x - node.width / 2 + Math.random() / 1000,
          y: node.y - node.height / 2
        }
      }
    }
    return el
  })
}

[federicoodorizzi]

In case anyone is curious, here is an Elk example of the createGraphLayout function. Only tricky part is that you need to load/return your elements as a promise since the elk.layout call is asynchronous.

const DEFAULT_WIDTH = 75
const DEFAULT_HEIGHT = 75

const elk = new Elk({
  defaultLayoutOptions: {
    'elk.algorithm': 'layered',
    'elk.direction': 'RIGHT',
    'elk.spacing.nodeNode': '75',
    'elk.layered.spacing.nodeNodeBetweenLayers': '75'
  }
})

const createGraphLayout = async (elements: Elements): Promise<Elements> => {
  const nodes: ElkNode[] = []
  const edges: ElkPrimitiveEdge[] = []

  elements.forEach((el) => {
    if (isNode(el)) {
      nodes.push({
        id: el.id,
        width: el.__rf?.width ?? DEFAULT_WIDTH,
        height: el.__rf?.height ?? DEFAULT_HEIGHT
      })
    } else {
      edges.push({
        id: el.id,
        target: el.target,
        source: el.source
      })
    }
  })

  const newGraph = await elk.layout({
    id: 'root',
    children: nodes,
    edges: edges
  })
  return elements.map((el) => {
    if (isNode(el)) {
      const node = newGraph?.children?.find((n) => n.id === el.id)
      if (node?.x && node?.y && node?.width && node?.height) {
        el.position = {
          x: node.x - node.width / 2 + Math.random() / 1000,
          y: node.y - node.height / 2
        }
      }
    }
    return el
  })
}

Hey, would you be able to provide a full example? I'm not sure how to use promises and I'd like to try an alternative to Dagre. Thanks!

[litewarp]

You just need to delay rendering of the layout until the elements have been loaded. So, something like this should work:

import { createGraphLayout } from './layout'
import { initialElements } from './elements'

const FlowComponent: React.FC = () => {
  const [elements, setElements] = useState<Elements>()

  useEffect(() => {
    createGraphLayout(initialElements)
      .then(els => setElements(els))
      .catch(err => console.error(err))
  }, [])

  return (
    <>{!elements ? (
         <p>Loading ...</p> 
       ) : (
         <ReactFlow elements={elements} {...otherProps} />
       )
    }</>
  )
}

[federicoodorizzi]

Does anyone know if there's a way to prevent edges to overlap with nodes?

[chandrasekhar1996]

Also worth noting is https://github.com/erikbrinkman/d3-dag

@codie3611 do you have any examples of using d3-dag with react-flow?

[chandrasekhar1996]

I suggest to also take a look at WebCola which is a constraint based layout.

@bartvanremortele do you have any examples that I can refer to of using react-flow-renderer with WebCola? I am interested in using this library but couldn't find any examples of using it with this library.

[FelipeDecome]

Does anyone know if there's a way to prevent edges to overlap with nodes?

@federicoodorizzi you should take a look into this lib https://github.com/MrBlenny/react-flow-chart

It implements a path finding algorithm in this file. https://github.com/MrBlenny/react-flow-chart/blob/c27628b6a082f533ab0cea7e86415b0a48ed8ab1/src/components/Link/utils/generateCurvePath.ts#L80

Here is the example of this algorithm working https://mrblenny.github.io/react-flow-chart/index.html?path=/story/other-config--smart-link-routing

Besides this one, you could try https://ialab.it.monash.edu/webcola/examples/unix.html This example example show how to use webcola to calculate the curve needed to prevent nodes and edges overlaping

[thadk]

It might not properly account for subgraphs or edges fully yet but here is a basic port of the elk example above to react-flow v10 #1555 (currently in beta!)

import Elk, { ElkNode, ElkPrimitiveEdge } from "elkjs";
import { Node, Edge } from "react-flow-renderer";

/* From https://github.com/wbkd/react-flow/issues/5#issuecomment-954001434 */
/* 
Get a sense of the parameters at:
https://rtsys.informatik.uni-kiel.de/elklive/examples.html?e=general%2Fspacing%2FnodesEdges 
*/

const DEFAULT_WIDTH = 330;
const DEFAULT_HEIGHT = 75;
const DEFAULT_WIDTH_FOR_ROOT = 170;

const elk = new Elk({
  defaultLayoutOptions: {
    'elk.algorithm': 'layered',
    'elk.direction': 'RIGHT',
    'elk.spacing.nodeNode': '75',
    'elk.layered.spacing.nodeNodeBetweenLayers': '75'
  }
})

const createGraphLayout = async (nodes: Array<Node>, edges: Array<Edge>): Promise<Array<Node>> => {
    const elkNodes: ElkNode[] = [];
    const elkEdges: ElkPrimitiveEdge[] = [];

    nodes.forEach((flowNode) => {
        elkNodes.push({
            id: flowNode.id,
            width: flowNode.id === "0" ? DEFAULT_WIDTH_FOR_ROOT : flowNode.width ?? DEFAULT_WIDTH,
            height: flowNode.height ?? DEFAULT_HEIGHT,
        });
    });
    edges.forEach((flowEdge) => {
        elkEdges.push({
            id: flowEdge.id,
            target: flowEdge.target,
            source: flowEdge.source,
        });
    });

    const newGraph = await elk.layout({
        id: "root",
        children: elkNodes,
        edges: elkEdges,
    });
    return nodes.map((flowNode) => {
        const node = newGraph?.children?.find((n) => n.id === flowNode.id);
        if (node?.x && node?.y && node?.width && node?.height) {
            flowNode.position = {
                x: node.x - node.width / 2 + Math.random() / 1000,
                y: node.y - node.height / 2,
            };
        }
        return flowNode;
    });
};

export default createGraphLayout;

Then in your main <ReactFlow>, here's an example of the onInit prop:

  const onInit = (reactFlowInstance: ReactFlowInstance) => {
    console.log('flow loaded:', reactFlowInstance);
    createGraphLayoutElk(reactFlowInstance.getNodes(), reactFlowInstance.getEdges())
    .then((els) => setNodes(els))
    .catch((err) => console.error(err));
    reactFlowInstance.fitView();

  };

[AlyonaGN]

@thadk hi! Could you please let me know what you mean by onPaneReady? Seems that in order to get .__rf[width/height] nodes need to 'go through' ReactFlow at least once and if we use useEffect with nodes from react-flow store in a dependency array to call the layout function when nodes get their width and height and then set the result into a state variable that comes as 'elements' into ReactFlow we get endless re-renders (which is reasonable, but was wondering if there are ways to avoid this). Probably, onPaneReady is the solution, but haven’t found this in the docs. I understand that you might mean onLoad, but I noticed that when onLoad is invoked nodes' height and width are still null. @moklick if you have thoughts on this re-render issue, could you please share? Many thanks in advance!

[moklick]

Hey @AlyonaGN

I understand that it's a bit confusing here :D The onPaneReady handler was part of our next version which is currently in beta (you can find all information in this PR #1555). We renamed it to onInit. In your case I would store the information if you layouted the graph in a ref and only do it once:

const layouted = useRef(false);

useEffect(() => {
  if (!layouted.current) {
    const allNodesInitialized = elements.filter(isNode).every(n => n.width);

   if (allNodesInitialized) {
     layouted.current = true;
     setElements(layoutElements(elements))
   }   
  }
}, [elements])

[AlyonaGN]

@moklick thanks a lot! The flag ref works perfectly for this.

[skvark]

If someone is interested in using https://github.com/erikbrinkman/d3-dag for layout, I created a simple example. I also tried Elk, but it doubled my bundle size.

A type error is ignored since I didn't have the time to figure the correct type out yet.

import { Node, Edge } from 'react-flow-renderer';
import { dagConnect, sugiyama, decrossOpt } from 'd3-dag';

const nodeRadius = 80;

const createGraphLayout = (nodes: Array<Node>, edges: Array<Edge>): Array<Node> => {
  const create = dagConnect();
  const dag = create(edges.map((e) => [e.source, e.target]));
  const layout = sugiyama()
    .decross(decrossOpt())
    .nodeSize((node) => [(node ? 3.6 : 0.25) * nodeRadius, 3 * nodeRadius]);

  // @ts-ignore
  layout(dag);

  const newNodes: Array<Node> = [];

  for (const node of dag) {
    const n = nodes.find((n) => n.id === node.data.id);
    const newNode = { ...n, position: { x: node.x, y: node.y } } as Node;
    newNodes.push(newNode);
  }

  return newNodes;
};

[moklick]

@skvark Thanks for sharing! This is super helpful :)

[benlongo]

It looks like with v11, that this hook would be useful https://reactflow.dev/docs/api/hooks/use-nodes-initialized/

[giorgosera]

@benlongo thanks for sharing I really needed this. But I am not sure it works as expected.

I created a sandbox here that demonstrates the unexpected behavior.

In that sandbox I do the following to pretend I am updating the initial list of nodes.

  // I am pretending I update the nodes list
  useEffect(() => {
    const updatedNode = {
      id: "my node",
      type: "input",
      data: { label: "input" },
      position: { x: 0, y: 0 }
    };
    setNodes((currNodes) => [updatedNode]);
  }, []);

and then in another useEffect I do the following

  useEffect(() => {
    if (nodesInitialized) {
      // The node printed here won't have a width or height in some cases
      console.log(nodesInitialized, nodes);
    }
  }, [nodes, nodesInitialized]);

If you look at the logs you'll see that in some cases nodesInitialized is true but the nodes list printed is lacking the width and height properties.

Maybe I misunderstood when and how this hook will work but I'd expect it to be true only when width/height are available. That's what I get according to the docs. Am I getting it wrong?

[benlongo]

I also had a tough time getting this working, probably due to my lack of foundational understanding in the way useEffect works. I ended up with the following approach which seems to do the trick.

function SomeGraphComponent(props: SomeGraphComponentProps) {
    const { nodes, edges } = useMemo(() => computeGraphStructure(...), [...]);
    const [layoutedNodes, setLayoutedNodes] = useState<Node[] | null>(null);
    const nodesInitialized = useNodesInitialized();
    const reactFlowInstances = useReactFlow();

    const runLayout =  () => {
        if (nodesInitialized) {
            // somehow calculate your graph layout
            // In my case this requires async work so it's inside this function
            // If this was sync work, then I think you could do useMemo. Perhaps there is a thing like useAsyncMemo?
            computeNodeLayout(...)
                .then(setLayoutedNodes)
                .catch(...);
        }
    }

    // Run the layout. If your nodes are changing this will re-run when required
    useEffect(() => {
        runLayout();
    }, [nodesInitialized, nodes]);

    return <ReactFlow nodes={layoutedNodes ?? []} edges={edges} />
}

I think this answer covers some relevant topics: https://stackoverflow.com/a/66071205/3570474 I'm not sure if this approach is better, but it seems better to have useState than a ref to my novice eyes.

[moklick]

@giorgosera @benlongo layouting isn't an easy thing to do and our API design is not 100% perfect.. I think a "How to layout nodes" guide would be helpful for everyone. I will put it on our list!

@giorgosera in order to avoid race conditions, I would take the nodes from the internal React Flow store directly in the useEffects that depends on the nodesInitialized flag: https://codesandbox.io/s/reverent-rui-iq13ks?file=/App.js:2091-2201

[giorgosera]

@giorgosera @benlongo layouting isn't an easy thing to do and our API design is not 100% perfect.. I think a "How to layout nodes" guide would be helpful for everyone. I will put it on our list!

Sounds like a great idea!

@giorgosera in order to avoid race conditions, I would take the nodes from the internal React Flow store directly in the useEffects that depends on the nodesInitialized flag: https://codesandbox.io/s/reverent-rui-iq13ks?file=/App.js:2091-2201

Got it. Thanks for the tip.