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.

Figure 5.94. Multi-page layout sample

Original diagram.	Four (out of eight) small graphs that result from running multi-page layout. Blue nodes are directly from the original diagram, yellow nodes are additional proxy elements (see text).

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.

Figure 5.95. Replacing an edge and introducing connector nodes and connector edges

Connected nodes A and B with their neighbors in the original graph.	A and B in different page graphs. Both nodes have an additional connector node (emphasized, smaller) and an additional connector edge (emphasized) that stand in for the connecting edge of the original graph.

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.

Figure 5.96. Splitting up a node and introducing a proxy node, proxy edges, a proxy reference node, and a proxy reference edge

Original node with its neighbors.	The node (conceptually) before the split.	The node split up into two "parts," A and A', in different page graphs, each having (roughly) one half of the original neighbors. A' (emphasized, normal size) is a proxy node of the original node A. It is connected to the original node's neighbors by means of proxy edges (emphasized) that stand in for the connecting edges of the original graph. A has an additional proxy reference node (emphasized, smaller) that references proxy node A'. The connecting edge is a proxy reference edge (emphasized).

Relevant Classes

The following table lists the relevant classes and interfaces for multi-page layout:

Table 5.66. Relevant classes for this algorithm

Classname	Description
MultiPageLayouter	Main algorithm. See the description below.
MultiPageLayout	The container to hold the results of a multi-page layout, i.e., the page graphs. See Related Classes and Interfaces.
ElementFactory	Interface that defines element creation callbacks for customization of the additional nodes and edges that augment the page graphs. See Related Classes and Interfaces.

Class MultiPageLayouter 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.

Class MultiPageLayouter uses a scheme that is different from that of the yFiles major layout algorithms in several ways:

A multi-page layout is started using:

calcLayout(graph:LayoutGraph):MultiPageLayout

The result of the algorithm is returned in a MultiPageLayout container object. The original graph that is given to MultiPageLayouter is not modified in any way.

Note that invoking a multi-page layout using the applyLayout convenience method of adapter class CopiedLayoutIGraph implicitly calls MultiPageLayouter's doLayout method (originally defined in interface Layouter). This method, however, does not return a MultiPageLayout object, i.e., the result of the layout calculation is not accessible without further setup.

Instead, the MultiPageLayout container object needs to be retrieved through an implementation of interface LayoutCallback, which needs to be registered with MultiPageLayouter using:

layoutCallback:LayoutCallback

A simple LayoutCallback implementation:

public class SimpleLayoutCallback implements LayoutCallback {
  var result:MultiPageLayout;

  function layoutDone(result:MultiPageLayout):void {
    this.result = result;
  }

  function pop():MultiPageLayout {
    var result:MultiPageLayout = this.result;
    this.result = null;
    return result;
  }
}

Note that the resulting page graphs in the MultiPageLayout container object are all of type LayoutGraph. In tutorial demo application MultiPageLayouterDemo.mxml helper class MultiPageIGraphBuilder is used to build a folded graph view that contains the page graphs from a multi-page layout calculation.

// Create multi-page layout algorithm.
var mpl:MultiPageLayouter = new MultiPageLayouter();

// Create and set core layout algorithm.
mpl.coreLayouter = new IncrementalHierarchicLayouter();

// An IMapper implementation that simply returns the given object itself as its 
// unique ID.
public class MyIMapper implements IMapper {  
  public function lookupValue(key:Object):Object { return key; }
  
  public function mapValue(key:Object, value:Object):void {}
  public function unMapValue(key:Object):void {}
}  

function setupCanonicalUniqueIDs(modelGraph:IGraph):void {
  var idProvider:IMapper = new MyIMapper();
  var registry:IMapperRegistry = modelGraph.mapperRegistry;
  
  // Use this IMapper implementation for all kinds of graph elements that need 
  // unique IDs.
  registry.addMapper(MultiPageLayouter.NODE_ID_DPKEY, idProvider);
  registry.addMapper(MultiPageLayouter.EDGE_ID_DPKEY, idProvider);
  registry.addMapper(MultiPageLayouter.NODE_LABEL_ID_DPKEY, idProvider);
  registry.addMapper(MultiPageLayouter.EDGE_LABEL_ID_DPKEY, idProvider);
}

// 'modelGraph' is of com.yworks.graph.model.IGraph.

// Create multi-page layout algorithm.
var mpl:MultiPageLayouter = new MultiPageLayouter();

// Create and set core layout algorithm.
var ihl:IncrementalHierarchicLayouter = new IncrementalHierarchicLayouter();
mpl.coreLayouter = ihl;

// Set up unique IDs for graph elements.
setupCanonicalUniqueIDs(modelGraph);

var callback:SimpleLayoutCallback = new SimpleLayoutCallback();
mpl.layoutCallback = callback;

// Calculate multi-page layout.
CopiedLayoutIGraph.applyLayout(modelGraph, mpl);

// Get the resulting page graphs.
var result:MultiPageLayout = callback.pop();

// Now, do something with 'result'...

// Remove the data providers registered by setupCanonicalUniqueIDs.
modelGraph.mapperRegistry.removeMapper(MultiPageLayouter.EDGE_LABEL_ID_DPKEY);
modelGraph.mapperRegistry.removeMapper(MultiPageLayouter.NODE_LABEL_ID_DPKEY);
modelGraph.mapperRegistry.removeMapper(MultiPageLayouter.EDGE_ID_DPKEY);
modelGraph.mapperRegistry.removeMapper(MultiPageLayouter.NODE_ID_DPKEY);

maxPageSize:YDimension

preferredMaximalDuration:uint

Tutorial demo application MultiPageLayouterDemo.mxml shows how to use class MultiPageLayouter to sub-divide large graphs into smaller bits of navigable information.

Class MultiPageLayouter knows a number of data provider keys which are used to retrieve supplemental layout data for a graph's elements. The data is bound to the graph by means of a data provider which is registered using a given look-up key. Table 5.67, “Data provider look-up keys” lists all look-up keys that MultiPageLayouter tests during the layout process in order to query supplemental data.

Binding supplemental layout data to a graph is described in the section called “Providing Supplemental Layout Data”.

Table 5.67. Data provider look-up keys

Key	Element Type	Value Type	Description
NODE_ID_DPKEY	node	Object	For each node an Object that is used as a unique ID.
EDGE_ID_DPKEY	edge	Object	For each edge an Object that is used as a unique ID.
NODE_LABEL_ID_DPKEY	NodeLabelLayout	Object	For each NodeLabelLayout instance an Object that is used as a unique ID.
EDGE_LABEL_ID_DPKEY	EdgeLabelLayout	Object	For each EdgeLabelLayout instance an Object that is used as a unique ID.
NODE_CLUSTER_ID_DPKEY	node	Object	For each node an arbitrary Object indicating its cluster ID. This ID is used to find nodes that preferably should be in the same page graph.
EDGE_TYPE_DPKEY	edge	Object	For each edge an arbitrary Object indicating its (application-specific) type.