The LayoutGraph API - Part 1: Structure

The yFiles graph structure implementation follows the principle that the graph instance is solely responsible for all structural changes. Structural changes primarily involve creating and removing nodes and edges. This principle has important implications:

• A valid graph instance must exist before you can create any graph elements (“inside” this graph instance) at all.
• You cannot create a node or an edge “outside” a graph.
• All created graph elements immediately belong to a specific graph.

Additionally, there is a clear hierarchy of responsibilities for accessing graph element information:

• A graph provides access to its nodes and edges.
• A node provides access to its edges: this can be all edges, or all incoming and outgoing edges.
• An edge provides access to its source and target node.
• A node provides access to its labels via property LayoutNode.labels.
• An edge provides access to its labels via property LayoutEdge.labels.

A graph can have any number of nodes and edges. However, each node and edge belongs to exactly one graph. A node can have any number of edges, but an edge always has two nodes: its source node and its target node.

Each instance of type LayoutNode and type LayoutEdge holds a reference to the graph instance to which it belongs. This reference is cleared when the graph element has been removed or hidden from its graph. Furthermore, each graph element knows its position within the respective set of elements in its graph.

The properties nodes and edges provide access to the layout graph’s nodes and edges.

const graph = getMyGraph()

// Iterating the nodes and their labels
for (const node of graph.nodes) {
  // Do something with each node...
  for (const nodeLabel of node.labels) {
    // Do something with each label...
  }
}

// Iterating the edges of the graph
for (const edge of graph.edges) {
  // Do something with each edge...
}

// Get the first and last node of the node set from the graph.
const firstNode = graph.nodes.first
const lastNode = graph.nodes.last

Creating and Removing Graph Elements

When populating an existing graph with graph elements, it is important to observe certain preconditions:

• Only class LayoutGraph provides methods to create nodes and edges.
• To create an edge in a graph G, both its source node and its target node must already exist in G.

const graph = new LayoutGraph()

// create 2 nodes
const n1 = graph.createNode()
const n2 = graph.createNode()
// create an edge between the 2 nodes
const e = graph.createEdge(n1, n2)

In addition to the most frequently used simple edge creation, it is also possible to specify the exact place where a newly created edge should be inserted into both the sequence of outgoing edges at its source node and the sequence of incoming edges at its target node. Furthermore, an existing edge can be completely remodeled. This means both its end nodes and the insertion places at either end node can be changed via method changeEdge. Reversing an edge, as another way of changing an edge, is also supported, see method reverseEdge.

Exact edge insertion shows the line of code for specifying the exact place of edge insertion.

const graph = getMyGraph()
const source = getMySourceNode()
const target = getMyTargetNode()

// Create a new edge at the second position of all incoming edges at the target
// node.
graph.createEdge(
  source,
  target,
  source.outEdges.first(),
  RelativePosition.AFTER,
  target.inEdges.first(),
  RelativePosition.AFTER
)
const graph: LayoutGraph = getMyGraph()
const source = getMySourceNode()
const target = getMyTargetNode()

// Create a new edge at the second position of all incoming edges at the target
// node.
graph.createEdge(
  source,
  target,
  source.outEdges.first()!,
  RelativePosition.AFTER,
  target.inEdges.first()!,
  RelativePosition.AFTER
)

The opposite of graph element creation is their removal. The LayoutGraph offers remove methods (overloads) for all item types, e.g., to remove nodes method remove. When removing a node or an edge, their reference to the containing graph is cleared. To remove all elements at once, use method clear.

When removing a single node from a graph, all its connecting edges are also removed. Technically, they are removed before the node is removed, since an edge requires both its source node and target node to reside in the same graph.

An alternative to removing graph elements is to temporarily hide them, as described in Hiding Graph Elements.

The LayoutGraph class also provides ways to check whether a graph item belongs to it or if there is an edge connecting two nodes. The latter feature is especially useful if there is no direct reference to an edge, for instance. A hidden graph element does not belong to any graph until it is unhidden again.

// Check if some given node belongs to this graph.
const containsNode = graph.contains(node)

// Check if there is an edge between first and last node of the graph.
const containsEdge = graph
  .getEdgesBetween(graph.nodes.first(), graph.nodes.last())
  .some()

// Check if some given node belongs to this graph.
const containsNode = graph.contains(node)

// Check if there is an edge between first and last node of the graph.
const containsEdge = graph
  .getEdgesBetween(graph.nodes.first()!, graph.nodes.last()!)
  .some()

Class LayoutNode

Class LayoutNode manages the edges connected to a node.

More specifically, a node knows the overall number of connecting edges (the degree of the node) and the number of incoming edges (in-degree) and outgoing edges (out-degree).

const node = getMyNode()

// get the number of edges at a node.
const degree = node.degree

// get the number of incoming edges at a node.
const inDegree = node.inDegree

// get the number of outgoing edges at a node.
const outDegree = node.outDegree

Furthermore, it can give enumerators to iterate over all connecting edges, iterate over all incoming edges, and iterate over all outgoing edges.

const node = getMyNode()

// get an enumerator to iterate over all edges at a node.
const edges = node.edges
// enumerate all edges using es-5 syntax
edges.forEach(console.log, console)

// get an enumerator to iterate over all incoming edges at a node.
const inEdges = node.inEdges
// enumerate all edges using es-6 for-of
for (const inEdge of inEdges) {
  console.log(inEdge)
}

// get an enumerator to iterate over all outgoing edges at a node.
const outEdges = node.outEdges

const node: LayoutNode = getMyNode()

// get an enumerator to iterate over all edges at a node.
const edges = node.edges
// enumerate all edges using es-5 syntax
edges.forEach(console.log, console)

// get an enumerator to iterate over all incoming edges at a node.
const inEdges = node.inEdges
// enumerate all edges using es-6 for-of
for (const inEdge of inEdges) {
  console.log(inEdge)
}

// get an enumerator to iterate over all outgoing edges at a node.
const outEdges = node.outEdges

Since a self-loop is both an incoming and an outgoing edge at its node, it appears twice when iterating over all edges of the node. Also, a self-loop counts twice when asking for the degree of a node.

Class LayoutEdge

The most important information an instance of class LayoutEdge provides is its source and its target node. Closely related is the method to get the opposite when holding one of the edge’s end nodes.

const edge = getMyEdge()

// get the two end nodes of an edge.
const source = edge.source
const target = edge.target

// getting the opposite when holding one of either source or target node.
const opposite = edge.opposite(source)
const edge: LayoutEdge = getMyEdge()

// get the two end nodes of an edge.
const source = edge.source
const target = edge.target

// getting the opposite when holding one of either source or target node.
const opposite = edge.opposite(source)

Although a removed or hidden edge holds no reference to a graph, it can still provide access to its source and target node, independent of their status.

As a convenience, class LayoutEdge's property selfLoop also offers information about whether the edge is a self-loop.

Group Nodes

As described in The Graph Model, yFiles for HTML provides an enhanced graph model that supports group nodes. In this model, a node can be contained within another node, referred to as its parent group, and each group can contain any number of nodes, referred to as its children.

A layout style suitable for group nodes typically positions the children of the same group close together and encloses them within their parent node.

If an IGraph contains groups, applying a layout to it automatically creates a corresponding LayoutGraph model with grouping information. Group node insets and minimum size constraints are also configured automatically.

You can access and modify group information on the LayoutGraph in a manner very similar to IGraph.

• isGroupNode
• getParent
• getChildren

You can also implement basic changes to the grouping using the graph and the following methods:

• createGroupNode
• setIsGroupNode
• setParent

If you need advanced operations such as the (temporary) removal of the grouping structure, you can use the LayoutGraphGrouping class.

Hiding Graph Elements

This section describes features of the graph model used by the layout part of yFiles. You only need to understand this model if you are implementing your own ILayoutAlgorithm, ILayoutStage, or another type from the layout part. The section Applying an Automatic Layout describes how to apply an automatic layout to an IGraph or GraphComponent.

Hiding is a technique to temporarily remove graph elements. This involves taking them out of the graph structure to perform a task on the remaining graph, and then putting them back in, un-hiding them.

The LayoutGraphHider class provides support for hiding graph elements. It offers methods to hide collections of graph elements, or even all elements from the graph at once. It also automatically keeps track of all elements hidden by these method calls.

To unhide graph elements, the LayoutGraphHider class provides a small set of methods that unhide all previously hidden elements at once.

// Hide all edges that are part of some set/collection
const graphHider = new LayoutGraphHider(graph)

graphHider.hideEdges(getEdgesToHide(graph))

// now do something with the graph
layoutAlgorithm.applyLayout(graph)

// cleanup
graphHider.unhideAll()

Binding Data to Graph Elements

This section describes features of the graph model used by the layout algorithms in yFiles. You only need to understand this model if you are implementing your own ILayoutAlgorithm, ILayoutStage, or another type from the layout part. The section Applying an Automatic Layout describes how to apply an automatic layout to an IGraph or GraphComponent.

All supplementary data of the graph and its elements, which can be used by layout algorithms during computation, is managed by the class LayoutGraphContext. The data is stored and accessed using implementations of the generic IMapper<K,V> interface.

Layout Graph Context

Maps to associate custom data with graph elements can be created in different ways. The most common way to specify data to be used by layout algorithms is to use a LayoutData<TNode,TEdge,TNodeLabel,TEdgeLabel> which offers convenient properties to specify the data and automatically registers that data with the graph at the start of a layout run. This concept is described in more detail in Layout Data.

Another option is to simply create an instance of a mapper implementation such as Mapper<K,V>. The IMapper<K,V> class offers methods to create a read-only mapper based on a constant value (fromConstant<K,V>) or a dynamic mapper based on delegate functions (fromHandler<K,V>). Finally, the LayoutGraph offers performance-optimized data mappers createNodeDataMap<TValue> and createEdgeDataMap<TValue> specifically for associating data with nodes and edges. However, these maps have the disadvantage that they must be manually disposed of using methods like disposeNodeDataMap<TValue>.

// instantiate and fill a mapper
const mapper = new Map()
mapper.set(yesNode, true)
mapper.set(noNode, false)

// let the LayoutGraph instantiate a mapper and fill it
const nodeMapper = graph.createNodeDataMap()
nodeMapper.set(yesNode, true)
nodeMapper.set(noNode, false)

// ... use the mapper

// dispose of the mapper after use
graph.disposeNodeDataMap(nodeMapper)

// create a mapper that returns a constant value for any Node
const noMapper = IMapper.fromConstant(false)

// create a mapper that delegates to a property of the node
const delegatingMapper = IMapper.fromHandler(
  (node) => node.tag.flagSet, // delegating getter implementation
  (node, flag) => (node.tag.flagSet = flag) // delegating setter implementation
)

// instantiate and fill a mapper
const mapper = new Map<LayoutNode, boolean>()
mapper.set(yesNode, true)
mapper.set(noNode, false)

// let the LayoutGraph instantiate a mapper and fill it
const nodeMapper = graph.createNodeDataMap<boolean>()
nodeMapper.set(yesNode, true)
nodeMapper.set(noNode, false)

// ... use the mapper

// dispose of the mapper after use
graph.disposeNodeDataMap(nodeMapper)

// create a mapper that returns a constant value for any Node
const noMapper = IMapper.fromConstant<LayoutNode, boolean>(false)

// create a mapper that delegates to a property of the node
const delegatingMapper = IMapper.fromHandler<LayoutNode, boolean>(
  (node) => (node.tag as MyTag).flagSet, // delegating getter implementation
  (node, flag) => ((node.tag as MyTag).flagSet = flag!) // delegating setter implementation
)

Regardless of how the mapping is created, it is always registered with the LayoutGraphContext using a DataKey<TValue>, which is usually provided by the layout algorithm requiring the data. Data keys are generic and allow the graph context to assert type safety whenever data is registered. In addition, there is one data key implementation for each type of layout graph element, ensuring that the data is always associated with the correct elements. For example, the HierarchicalLayout.EDGE_THICKNESS_DATA_KEY asserts that the values must have a numerical value, and as it is an EdgeDataKey<TValue> the data can only be assigned to edges.

// register the data (mapper) with the context
graph.context.addItemData(
  HierarchicalLayout.EDGE_THICKNESS_DATA_KEY,
  myMapper
)

// ... somewhere else: retrieve the data from the context
const thicknessEdgeMapper = graph.context.getItemData(
  HierarchicalLayout.EDGE_THICKNESS_DATA_KEY
)

for (const edge of graph.edges) {
  // query value for a single edge (thickness)
  const thickness = thicknessEdgeMapper.get(edge)
  // use thickness as needed
}

// remove the data from the context
graph.context.remove(HierarchicalLayout.EDGE_THICKNESS_DATA_KEY)

// register the data (mapper) with the context
graph.context.addItemData(
  HierarchicalLayout.EDGE_THICKNESS_DATA_KEY,
  myMapper
)

// ... somewhere else: retrieve the data from the context
const thicknessEdgeMapper = graph.context.getItemData<number>(
  HierarchicalLayout.EDGE_THICKNESS_DATA_KEY
)

for (const edge of graph.edges) {
  // query value for a single edge (thickness)
  const thickness = thicknessEdgeMapper!.get(edge)
  // use thickness as needed
}

// remove the data from the context
graph.context.remove(HierarchicalLayout.EDGE_THICKNESS_DATA_KEY)

Layout Data

Most layout algorithms can be configured with additional data. Internally, they use the mappers associated with the LayoutGraphContext for this task. As described in Layout Graph Context, there are different ways to provide the data.

The most recommended way is to use the corresponding LayoutData. For instance, HierarchicalLayout can be configured using HierarchicalLayoutData<TNode,TEdge,TNodeEdge,TNodeLabel,TEdgeLabel>. The layout data often offers additional convenience for specifying the data, and it automatically registers the data at the start of the layout calculation. This registration process is especially useful when applying a layout to an IGraph, in which case the data transfer from the IGraph elements to the elements of the LayoutGraph, that the layout is calculated on, is performed automatically as well.

If one implements a custom layout stage (see: Writing a Custom Layout Stage), an instance of GenericLayoutData<TNode,TEdge,TNodeLabel,TEdgeLabel> can be used. It provides the possibility of registering ItemCollection<TItem>s and ItemMapping<TItem,TValue>s with arbitrary data keys. Like the predefined layout data types, the generic layout data leaves an original IGraph unaffected.

// an example data key for an ItemCollection:
// the corresponding mapper returns true for each node which is contained in the collection
const includedNodesDataKey = new NodeDataKey('IncludedNodesDataKey')

// an example data key for an ItemMapping:
// the corresponding mapper returns a number for each edge
const edgeWeightDataKey = new EdgeDataKey('EdgeWeightDataKey')

// generate generic data for IGraph elements
const genericData = new GenericLayoutData()

// add an ItemCollection for IncludedNodesDataKey
const includedNodes = genericData.addItemCollection(includedNodesDataKey)
includedNodes.predicate = (node) => 'IncludeMe' === node.tag

// add an ItemMapping for EdgeWeightDataKey
const edgeWeights = genericData.addItemMapping(edgeWeightDataKey)
edgeWeights.mapper.set(edge1, 10)
edgeWeights.mapper.set(edge2, 20)

await graphComponent.applyLayoutAnimated(layout, '0.5s', genericData)

// an example data key for an ItemCollection:
// the corresponding mapper returns true for each node which is contained in the collection
const includedNodesDataKey = new NodeDataKey<boolean>('IncludedNodesDataKey')

// an example data key for an ItemMapping:
// the corresponding mapper returns a number for each edge
const edgeWeightDataKey = new EdgeDataKey<number>('EdgeWeightDataKey')

// generate generic data for IGraph elements
const genericData = new GenericLayoutData<INode, IEdge, ILabel, ILabel>()

// add an ItemCollection for IncludedNodesDataKey
const includedNodes = genericData.addItemCollection(includedNodesDataKey)
includedNodes.predicate = (node: INode) => 'IncludeMe' === node.tag

// add an ItemMapping for EdgeWeightDataKey
const edgeWeights = genericData.addItemMapping(edgeWeightDataKey)
edgeWeights.mapper.set(edge1, 10)
edgeWeights.mapper.set(edge2, 20)

await graphComponent.applyLayoutAnimated(layout, '0.5s', genericData)

Time Complexity

Time complexities shows the time complexities for several frequent tasks when working with the yFiles LayoutGraph implementation.

Creating graph elements takes constant time, as does removing an edge. However, removing a node implies first removing all its connecting edges, so this task takes linear time—​that is, time proportional to the number of connecting edges. Iteration is also performed in linear time. Checking whether a given node or edge belongs to a graph is done in constant time, while testing if there is an edge connecting two nodes takes linear time.