Organic Edge Routing

OrganicEdgeRouter routes edges organically to ensure that they do not overlap nodes and that they keep a specifiable minimal distance to the nodes. It is especially well suited for non-orthogonal, organic or cyclic layout styles.

The algorithm is based on a force directed layout paradigm. Nodes act as repulsive forces on edges in order to guarantee a certain minimal distance between nodes and edges. Edges tend to contract themselves. Using simulated annealing, this finally leads to edge layouts that are calculated for each edge separately.

This algorithm will only work correctly if there is enough room between each pair of nodes in the graph. In particular, there should be a distance of at least twice the minimal distance (see below) between any two nodes.In order to ensure that these preconditions are met, the technique described below can be used.

Basic Options

By default, OrganicEdgeRouter reroutes all edges of a given graph. When only a subset of the edges should be routed, you can specify this subset by means of layout data.

Minimal Distance

minimumDistance

This specifies the minimal allowed distance between nodes and edges.

Use Existing Bends

keepExistingBends

This option specifies whether existing bends should be used as an initial solution for the new routing.

Route Only Necessary

routeAllEdges

If this option is enabled, all edges are routed. By default, this option is disabled and only edges that violate the minimal distance criterion are rerouted.

Allow Edge Overlaps

edgeNodeOverlapAllowed

This option specifies whether edges are allowed to overlap with nodes. Enabling this option often improves the routing when nodes are not allowed to move (i.e., when using the node enlargement layout stage is not an option), and some distances between nodes do not comply with the algorithm’s preconditions. Note that the minimal distance cannot always be maintained when using this option.

Enhancing the Routing Process

In order to ensure that the preconditions of OrganicEdgeRouter are met for arbitrary graphs, the routing process can be enhanced using specialized layout stages. In particular, the createNodeEnlargementStage method returns a layout stage that perfectly lends itself for usage in conjunction with logic that creates more space between the nodes of a graph. The code in Ensuring OrganicEdgeRouter's preconditions presents this technique.

const oer = new OrganicEdgeRouter()
const nodeEnlarger = oer.createNodeEnlargementStage()

const cls = new CompositeLayoutStage()
cls.appendStage(nodeEnlarger)
cls.appendStage(new BendConverter())
cls.appendStage(new RemoveOverlapsStage(0.0))

oer.coreLayout = cls
graph.applyLayout(oer)

Layout Data

When using class OrganicEdgeRouter, supplemental layout data for a graph’s elements can be specified either by using class OrganicEdgeRouterData or by registering data providers with the graph using given look-up keys. Supplemental layout data lists all properties of OrganicEdgeRouterData and the corresponding look-up keys that OrganicEdgeRouter tests during the layout process in order to query supplemental data.

Providing supplemental layout data is described in detail in Layout Data.

Supplemental layout data

affectedEdges

For each edge a boolean value indicating whether the edge shall be considered for rerouting or not.

Data Provider Key: AFFECTED_EDGES_DP_KEY

Maps from edge to boolean

abortHandler

An AbortHandler instance that will be queried by the layout algorithm to determine whether layout calculation shall be terminated.

Data Provider Key: ABORT_HANDLER_DP_KEY

Maps from graph to AbortHandler