Multi-page Layout
This section presents the multi-page layout concept.
- About the Concept: What it is about, the main traits of this concept.
- Introduction of MultiPageLayout, the main class that enables multi-page layout.
About the Concept
Multi-page layout enables the presentation of large graphs in an easily navigable and clear manner. It means breaking apart a given graph into a set of smaller graphs so that each layout of a small graph fits into a given width and height.
A multi-page layout with its set of small graphs avoids common presentation problems of large graphs with many nodes and edges. Problems, like, e.g., graph elements that are hardly discernible because of a small zoom level when viewing/printing the entire graph, or long edge paths that are hard to follow over numerous poster pages in a poster print-out of a graph.
The algorithm aims to find small graphs whose layout utilizes the specified width and height to the best extent. It puts as many as possible elements from the original graph into each small graph, thus minimizing the number of resulting small graphs.
Breaking apart the original graph is done by sub-dividing it and, for each connection between two nodes that is cut, introducing additional nodes and edges as proxy elements in both involved smaller graphs.
The proxy elements in either small graph stand in for the original edge and can be used as a means to get to the corresponding other small graph.
Sub-division can furthermore also take place at the node level, where nodes with many connections are split up into multiple “parts” that are distributed to different small graphs. This also introduces additional nodes and edges as proxy elements in the involved smaller graphs.
Carefully observe that, in contrast to the major layout algorithms of the yFiles library, multi-page layout produces not a single graph as its result, but instead a set of graphs.
Terminology
The original graph that is given to the algorithm is also called the model graph The smaller graphs that result from sub-dividing and augmenting the model graph are referred to as the page graphs.
The additional nodes and edges that are introduced to represent an edge from the original graph between two nodes which are in different page graphs after sub-division, are called connector nodes and connector edges, respectively, or also often simply connectors.
Further nodes and edges are added when a node with many connections needs to be split up into multiple parts in order to be able to assign these parts to different page graphs. Each of the parts gets an equal share of the original neighbor nodes (roughly).
The additional new parts of the original node are called proxy nodes, all edges incident to them are called proxy edges. They represent the connections between the original node and its neighbors.
For each of the proxy nodes in other page graphs, the original node gets a so-called proxy reference node as a new neighbor. The connecting edge to this new neighbor is called proxy reference edge.
Relevant Classes
The following table lists the relevant classes and interfaces for multi-page layout:
| Classname | Description |
|---|---|
Running a Multi-Page Layout
The MultiPageLayout class is the main class for calculating multi-page layouts. It generates a set of so-called page graphs whose layouts each fit into a given width and height.
To calculate the actual layouts of the page graphs, it relies on a core layout algorithm.
MultiPageLayout uses a scheme that is different from that of the yFiles major layout algorithms in several ways:
- The result of the layout is a set of graphs, the page graphs, bundled in MultiPageLayoutResult.
- The original graph that is given to MultiPageLayout is not modified in any way.
- The page graphs contain graph elements from the original graph plus additional nodes and edges.
- The result has to be retrieved in callback which has to be set to layoutCallback before running the layout.
The result of the algorithm is returned in a Querying the MultiPageLayoutResult container object. The original graph that is given to MultiPageLayout is not modified in any way.
Although the MultiPageLayout is applied as described in Applying an Automatic Layout just like every other layout algorithm, the result of the layout calculation is not accessible without further setup.
MultiPageLayout’s applyLayout method does not modify the original graph.
Instead, the MultiPageLayoutResult container object needs to be retrieved through an implementation of interface ILayoutCallback. Its callback method layoutDone is called at the end of applyLayout. The implementation needs to be registered with MultiPageLayout using property
- layoutCallback
- Sets the ILayoutCallback implementation. After a multi-page layout has completed, the implementation gets called and receives the MultiPageLayoutResult container object holding the resulting page graphs.
class LayoutCallback extends BaseClass(ILayoutCallback) {
$graphs = null
/**
* @param {!MultiPageLayoutResult} result
*/
layoutDone(result) {
// delegate to a factory to create IGraph implementations from the results
const builder = new MultiPageIGraphBuilder(result)
this.$graphs = builder.createGraphs()
}
/**
* @type {?Array.<IGraph>}
*/
get graphs() {
return this.$graphs
}
}class LayoutCallback extends BaseClass(ILayoutCallback) implements ILayoutCallback {
private $graphs: IGraph[] | null = null
layoutDone(result: MultiPageLayoutResult): void {
// delegate to a factory to create IGraph implementations from the results
const builder = new MultiPageIGraphBuilder(result)
this.$graphs = builder.createGraphs()
}
get graphs(): IGraph[] | null {
return this.$graphs
}
}Note that the resulting page graphs in the MultiPageLayoutResult container object are
all of type LayoutGraph.
The helper class MultiPageIGraphBuilder in the example is custom code. The Obtaining the Result from a Multi-Page Layout section
shows how to implement such a class. Also, a more comprehensive example is shown in the tutorial sample application
Multi-Page Layout demo.
Setup for Layout
To calculate a multi-page layout, a MultiPageLayout instance needs
- a core layout algorithm to actually compute the layouts of the page graphs
- a configured instance of MultiPageLayoutData to provide unique IDs for all nodes, edges, node labels, and edge labels of the model graph
- an ILayoutCallback implementation
The core layout algorithm has to be passed to the constructor.
MultiPageLayout uses unique IDs for the elements from the original graph to relate page graph elements to their originals from the model graph. In particular, the IDs are necessary to collect the information that is returned for connectors and proxy elements as part of the MultiPageLayoutResult container. For most use cases it is sufficient if the IDs are simply the references to the original elements themselves.
Unique IDs for nodes and edges can be specified using the MultiPageLayoutData's properties nodeIds and edgeIds, respectively, unique IDs for node labels and edge labels using the properties nodeLabelIds and edgeLabelIds, respectively.
The following code shows the canonical approach to provide unique IDs for graph elements. This scheme is also used in tutorial demo application Multi-Page Layout demo.
/**
* @returns {!MultiPageLayoutData}
*/
function setupCanonicalUniqueIDs() {
return new MultiPageLayoutData({
nodeIds: (node) => node,
edgeIds: (edge) => edge,
nodeLabelIds: (label) => label,
edgeLabelIds: (label) => label
})
}function setupCanonicalUniqueIDs(): MultiPageLayoutData {
return new MultiPageLayoutData({
nodeIds: (node: INode) => node,
edgeIds: (edge: IEdge) => edge,
nodeLabelIds: (label: ILabel) => label,
edgeLabelIds: (label: ILabel) => label
})
}In summary, the setup of MultiPageLayout looks like this:
// Create the core layout algorithm.
const hierarchicLayout = new HierarchicLayout()
// Create multi-page layout algorithm with the core layout
const multiPageLayout = new MultiPageLayout({
coreLayout: hierarchicLayout,
layoutCallback: new LayoutCallback()
})
// Set up unique IDs for graph elements.
const data = setupCanonicalUniqueIDs()
// Calculate multi-page layout.
// Afterwards, the LayoutCallback's LayoutDone method
// will be called with the result
graph.applyLayout(multiPageLayout, data)
Options
- Page Size
- maximumPageSize
- Specifies the page dimensions, i.e., the width and height into which the layout of a page graph needs to fit.
- Maximum Duration
- maximumDuration
- Sets the preferred maximum duration of the layout process in milliseconds. By default, the algorithm runs without time restriction.Higher values enable the algorithm to find a smaller set of page graphs, where each makes better use of the available page size. Also, there are fewer connectors and proxy elements in the page graphs.
By default, MultiPageLayout distributes the nodes from the original graph to the page graphs automatically. MultiPageLayoutData allows for assigning an object that serves as ID to each node using property nodeClusterIds. MultiPageLayout then tries to distribute nodes with the same ID to the same page graph.
Obtaining the Result from a Multi-Page Layout
MultiPageLayoutResult is the container to hold the results of the multi-page layout. It is passed to the layoutDone method of the layoutCallback.
MultiPageLayoutResult provides access to all page graphs from the layout result and enables identification of original graph elements, connectors, and proxy elements. This information is encapsulated in INodeInfo and IEdgeInfo objects, respectively INodeLabelInfo and IEdgeLabelInfo objects.
Note that the page graphs in MultiPageLayoutResult are LayoutGraph instances. Therefore they have to be copied into IGraph instances to be used with a view.
The example Building page graphs from the MultiPageLayoutResult shows a basic class which gets a result and provides a method to create IGraph instances for the pages.
class MultiPageGraphBuilder {
result
// remember which pageNode corresponds to which created INode
pageNodeToINode = new HashMap()
// remember which port in the original graph corresponds to which port in the page graph
modelPortToIPort = new HashMap()
/**
* The created instance handles the given result
* @param {!MultiPageLayoutResult} result
*/
constructor(result) {
this.result = result
}
/**
* Create a page graph from a page of the result
* @param {!MultiPageLayoutResult} result
* @param {number} pageIndex
* @returns {!DefaultGraph}
*/
createPageGraph(result, pageIndex) {
if (pageIndex < 0 || pageIndex >= result.pageCount()) {
throw new Error('index out of bounds')
}
// get the resulting page graph
const page = result.getPage(pageIndex)
// create the IGraph instance to copy the result to
const graph = new DefaultGraph()
// copy all nodes
page.nodes.forEach((pageNode) => {
// get the NodeInfo object for the current node.
const nodeInfo = result.getNodeInfo(pageNode)
// create an INode instance for it
const node = this.createNode(graph, page, pageNode, nodeInfo)
this.pageNodeToINode.set(pageNode, node)
})
// copy all edges
page.edges.forEach((pageEdge) => {
const edgeInfo = result.getEdgeInfo(pageEdge)
this.createEdge(page, graph, pageEdge, edgeInfo)
})
return graph
}
/**
* Create an INode for the given page node
* @param {!IGraph} graph
* @param {!LayoutGraph} page
* @param {!YNode} pageNode
* @param {?INodeInfo} nodeInfo
* @returns {!INode}
*/
createNode(graph, page, pageNode, nodeInfo) {
/* ... */
}
/**
* Create an IEdge for the given edge info
* @param {!LayoutGraph} page
* @param {!IGraph} graph
* @param {!Edge} pageEdge
* @param {?IEdgeInfo} edgeInfo
* @returns {!IEdge}
*/
createEdge(page, graph, pageEdge, edgeInfo) {
/* ... */
}
/**
* Get a default node style for the given node type
* @param {!NodeType} nodeInfoType
* @returns {!INodeStyle}
*/
getDefaultNodeStyle(nodeInfoType) {
/* ... */
}
/**
* Get a default edge style for the given edge type
* @param {!EdgeType} edgeInfoType
* @returns {!IEdgeStyle}
*/
getDefaultEdgeStyle(edgeInfoType) {
/* ... */
}
/**
* Create a port on the given node which is a copy of the given port
* @param {!INode} node
* @param {!IPort} port
* @returns {!IPort}
*/
copyPort(node, port) {
/* ... */
}
/**
* Create a label on the given node which is a copy of the given label
* @param {!INode} node
* @param {!ILabel} label
* @returns {!ILabel}
*/
copyLabel(node, label) {
/* ... */
}
}class MultiPageGraphBuilder {
result: MultiPageLayoutResult
// remember which pageNode corresponds to which created INode
pageNodeToINode: HashMap<YNode, INode> = new HashMap()
// remember which port in the original graph corresponds to which port in the page graph
modelPortToIPort: HashMap<IPort, IPort> = new HashMap()
/**
* The created instance handles the given result
*/
constructor(result: MultiPageLayoutResult) {
this.result = result
}
/**
* Create a page graph from a page of the result
*/
createPageGraph(result: MultiPageLayoutResult, pageIndex: number): DefaultGraph {
if (pageIndex < 0 || pageIndex >= result.pageCount()) {
throw new Error('index out of bounds')
}
// get the resulting page graph
const page = result.getPage(pageIndex)
// create the IGraph instance to copy the result to
const graph = new DefaultGraph()
// copy all nodes
page.nodes.forEach((pageNode) => {
// get the NodeInfo object for the current node.
const nodeInfo = result.getNodeInfo(pageNode)
// create an INode instance for it
const node = this.createNode(graph, page, pageNode, nodeInfo)
this.pageNodeToINode.set(pageNode, node)
})
// copy all edges
page.edges.forEach((pageEdge) => {
const edgeInfo = result.getEdgeInfo(pageEdge)
this.createEdge(page, graph, pageEdge, edgeInfo)
})
return graph
}
/**
* Create an INode for the given page node
*/
// @ts-ignore ... because the return type doesn't match
createNode(graph: IGraph, page: LayoutGraph, pageNode: YNode, nodeInfo: INodeInfo | null): INode {
/* ... */
}
/**
* Create an IEdge for the given edge info
*/
// @ts-ignore ... because the return type doesn't match
createEdge(page: LayoutGraph, graph: IGraph, pageEdge: Edge, edgeInfo: IEdgeInfo | null): IEdge {
/* ... */
}
/**
* Get a default node style for the given node type
*/
// @ts-ignore ... because the return type doesn't match
getDefaultNodeStyle(nodeInfoType: NodeType): INodeStyle {
/* ... */
}
/**
* Get a default edge style for the given edge type
*/
// @ts-ignore ... because the return type doesn't match
getDefaultEdgeStyle(edgeInfoType: EdgeType): IEdgeStyle {
/* ... */
}
/**
* Create a port on the given node which is a copy of the given port
*/
// @ts-ignore ... because the return type doesn't match
copyPort(node: INode, port: IPort): IPort {
/* ... */
}
/**
* Create a label on the given node which is a copy of the given label
*/
// @ts-ignore ... because the return type doesn't match
copyLabel(node: INode, label: ILabel): ILabel {
/* ... */
}
}The example Creating nodes for a page graph shows how to create a node based on a node in the page (layout) graph. Some of the nodes might be a representation of a node in the original graph. Such nodes get the original node’s style, tag, but also labels and ports. Other nodes might get a style based on its type or a custom label, which, e.g., might show to which node that node is linked to.
/**
* Create an INode for the given page node
* @param {!IGraph} graph
* @param {!LayoutGraph} page
* @param {!YNode} pageNode
* @param {!INodeInfo} nodeInfo
* @returns {!INode}
*/
createNode(graph, page, pageNode, nodeInfo) {
// representedNode is the node in the original graph which is represented by pageNode
// it might be null if the pageNode is a dummy or proxy
const originalLayoutGraph = nodeInfo.representedNode.graph
const representedNode = originalLayoutGraph.getOriginalNode(nodeInfo.representedNode)
const style = representedNode !== null ? representedNode.style.clone() : this.getDefaultNodeStyle(nodeInfo.type)
// create the copied node with the layout assigned by MultiPageLayout
const nodeLayout = page.getLayout(pageNode)
const node = graph.createNode(
new Rect(nodeLayout.x, nodeLayout.y, nodeLayout.width, nodeLayout.height),
style,
representedNode !== null ? representedNode.tag : null
)
switch (nodeInfo.type) {
// ... type specific modifications
case NodeType.NORMAL:
// ...
break
}
// copy the appearance of the represented node
if (representedNode !== null) {
for (const label of representedNode.labels) {
this.copyLabel(node, label)
}
for (const port of representedNode.ports) {
const copiedPort = this.copyPort(node, port)
this.modelPortToIPort.set(port, copiedPort)
}
}
return node
}
/**
* Create an INode for the given page node
*/
createNode(graph: IGraph, page: LayoutGraph, pageNode: YNode, nodeInfo: INodeInfo): INode {
// representedNode is the node in the original graph which is represented by pageNode
// it might be null if the pageNode is a dummy or proxy
const originalLayoutGraph = nodeInfo.representedNode!.graph as CopiedLayoutGraph
const representedNode = originalLayoutGraph.getOriginalNode(nodeInfo.representedNode!)
const style =
representedNode !== null ? (representedNode as INode).style.clone() : this.getDefaultNodeStyle(nodeInfo.type)
// create the copied node with the layout assigned by MultiPageLayout
const nodeLayout = page.getLayout(pageNode)
const node = graph.createNode(
new Rect(nodeLayout.x, nodeLayout.y, nodeLayout.width, nodeLayout.height),
style,
representedNode !== null ? (representedNode as INode).tag : null
)
switch (nodeInfo.type) {
// ... type specific modifications
case NodeType.NORMAL:
// ...
break
}
// copy the appearance of the represented node
if (representedNode !== null) {
for (const label of (representedNode as INode).labels) {
this.copyLabel(node, label)
}
for (const port of (representedNode as INode).ports) {
const copiedPort = this.copyPort(node, port)
this.modelPortToIPort.set(port, copiedPort)
}
}
return node
}
Creating edges is quite similar, as shown in the example Creating edges for a page graph.
/**
* Create an IEdge for the given edge info
* @param {!LayoutGraph} page
* @param {!IGraph} graph
* @param {!Edge} pageEdge
* @param {!IEdgeInfo} edgeInfo
* @returns {!IEdge}
*/
createEdge(page, graph, pageEdge, edgeInfo) {
// representedEdge is the edge in the original graph which is represented by pageEdge
// it might be null if the pageNode is a dummy or proxy
const originalLayoutGraph = edgeInfo.representedEdge.graph
const representedEdge = originalLayoutGraph.getOriginalEdge(edgeInfo.representedEdge)
const style = representedEdge !== null ? representedEdge.style.clone() : this.getDefaultEdgeStyle(edgeInfo.type)
let edge
if (representedEdge !== null) {
// if the edge has a model edge: create the copied edge between
// the copies of its source and target ports
const viewSourcePort = this.modelPortToIPort.get(representedEdge.sourcePort)
const viewTargetPort = this.modelPortToIPort.get(representedEdge.targetPort)
edge = graph.createEdge(viewSourcePort, viewTargetPort, style, representedEdge.tag)
} else {
// otherwise create it between the copies of its source and target nodes
const viewSource = this.pageNodeToINode.get(pageEdge.source)
const viewTarget = this.pageNodeToINode.get(pageEdge.target)
edge = graph.createEdge(viewSource, viewTarget)
}
// adjust the port location
const newSourcePortLocation = page.getSourcePointAbs(pageEdge)
const newTargetPortLocation = page.getTargetPointAbs(pageEdge)
graph.setPortLocation(edge.sourcePort, newSourcePortLocation.toPoint())
graph.setPortLocation(edge.targetPort, newTargetPortLocation.toPoint())
// and copy the bends
const edgeLayout = page.getLayout(pageEdge)
for (let i = 0; i < edgeLayout.pointCount(); i++) {
const bendLocation = edgeLayout.getPoint(i)
graph.addBend(edge, new Point(bendLocation.x, bendLocation.y), i)
}
// also copy the labels (not shown here)
switch (edgeInfo.type) {
// ... type specific modifications
case EdgeType.NORMAL:
// ...
break
}
return edge
}
/**
* Create an IEdge for the given edge info
*/
createEdge(page: LayoutGraph, graph: IGraph, pageEdge: Edge, edgeInfo: IEdgeInfo): IEdge {
// representedEdge is the edge in the original graph which is represented by pageEdge
// it might be null if the pageNode is a dummy or proxy
const originalLayoutGraph = edgeInfo.representedEdge!.graph as CopiedLayoutGraph
const representedEdge = originalLayoutGraph.getOriginalEdge(edgeInfo.representedEdge!)
const style =
representedEdge !== null ? (representedEdge as IEdge).style.clone() : this.getDefaultEdgeStyle(edgeInfo.type)
let edge: IEdge
if (representedEdge !== null) {
// if the edge has a model edge: create the copied edge between
// the copies of its source and target ports
const viewSourcePort = this.modelPortToIPort.get((representedEdge as IEdge).sourcePort)!
const viewTargetPort = this.modelPortToIPort.get((representedEdge as IEdge).targetPort)!
edge = graph.createEdge(viewSourcePort, viewTargetPort, style, (representedEdge as IEdge).tag)
} else {
// otherwise create it between the copies of its source and target nodes
const viewSource = this.pageNodeToINode.get(pageEdge.source)!
const viewTarget = this.pageNodeToINode.get(pageEdge.target)!
edge = graph.createEdge(viewSource, viewTarget)
}
// adjust the port location
const newSourcePortLocation = page.getSourcePointAbs(pageEdge)
const newTargetPortLocation = page.getTargetPointAbs(pageEdge)
graph.setPortLocation(edge.sourcePort!, newSourcePortLocation.toPoint())
graph.setPortLocation(edge.targetPort!, newTargetPortLocation.toPoint())
// and copy the bends
const edgeLayout = page.getLayout(pageEdge)
for (let i = 0; i < edgeLayout.pointCount(); i++) {
const bendLocation = edgeLayout.getPoint(i)
graph.addBend(edge, new Point(bendLocation.x, bendLocation.y), i)
}
// also copy the labels (not shown here)
switch (edgeInfo.type) {
// ... type specific modifications
case EdgeType.NORMAL:
// ...
break
}
return edge
}
Note that the layout, i.e. the node’s bounds and the edge’s source and target port locations as well as the bends
are copied from the page (layout) graph. The sample application Multi-Page Layout demo
shows a much more elaborate version of the example MultiPageGraphBuilder.
Tutorial Demo Code
The tutorial demo application Multi-Page Layout demo shows how to use class MultiPageLayout to sub-divide large graphs into smaller bits of navigable information.
Supplemental Layout Data
When using MultiPageLayout, supplemental layout data for a graph’s elements can be specified either by using class MultiPageLayoutData or by registering data providers with the graph using given look-up keys. The table Supplemental Layout Data lists all properties of MultiPageLayoutData and the corresponding look-up keys that MultiPageLayout tests during the layout process in order to query supplemental data.
Providing supplemental layout data is described in detail in Layout Data.