Multi-page Layout

This section presents the multi-page layout concept.

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.

Figure 10.79. Multi-page layout sample

Multi-page layout sample
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 10.80. Replacing an edge and introducing connector nodes and connector edges

Replacing an edge and introducing connector nodes and connector edges
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 10.81. Splitting up a node and introducing a proxy node, proxy edges, a proxy reference node, and a proxy reference edge

Splitting up a node and introducing a proxy node, proxy edges, a proxy reference node, and a proxy reference edge
Splitting up a node and introducing a proxy node, proxy edges, a proxy reference node, and a proxy reference edge
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 10.64. 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.
IElementFactory 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

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:

  • The preferred way to start a multi-page layout is to use the CalcLayout method of class MultiPageLayouter.
  • The result of the layout is a set of graphs, the page graphs.
  • The original graph that is given to MultiPageLayouter is not modified in any way.
  • The page graphs contain graph elements from the original graph plus additional nodes and edges.

A multi-page layout is started using:

Layout Invocation
API
MultiPageLayout CalcLayout(LayoutGraph graph)
Description Method to start multi-page layout.

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.

Important

The result of a multi-page layout calculation cannot be returned through MultiPageLayouter's DoLayout method.

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

ILayoutCallback LayoutCallback { get; set; }
Description Sets the ILayoutCallback implementation. After a multi-page layout has completed, the implementation gets called and receives the MultiPageLayout container object holding the resulting page graphs.

A simple ILayoutCallback implementation:

Example 10.32. ILayoutCallback implementation

static class SimpleLayoutCallback : ILayoutCallback {
  MultiPageLayout result;

  public void LayoutDone(MultiPageLayout result) {
    this.result = result;
  }

  public MultiPageLayout Pop() {
    MultiPageLayout result = 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 MultiPageWindow helper class MultiPageIGraphBuilder is used to build a folded graph view that contains the page graphs from a multi-page layout calculation.

Setup for Layout

To calculate a multi-page layout, class MultiPageLayouter needs

  • a core layout algorithm to actually compute the layouts of the page graphs
  • data providers registered with the original graph that provide unique IDs for all nodes, edges, node labels, and edge labels of the model graph
  • an ILayoutCallback implementation, if the layout is invoked using the DoLayout method of class MultiPageLayouter

The core layout algorithm can be set using the CoreLayouter property (originally defined in interface ILayoutStage):

Example 10.33. Setting the core layouter

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

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

MultiPageLayouter 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 MultiPageLayout container.

Unique IDs for nodes and edges can be specified using the data provider look-up keys NodeIdDpKey and EdgeIdDpKey, respectively, unique IDs for node labels and edge labels using the look-up keys NodeLabelIdDpKey and EdgeLabelIdDpKey, respectively.

The following code shows the canonical approach to provide unique IDs for graph elements. This scheme is also used in tutorial demo application MultiPageWindow.

Example 10.34. Canonical setup of mandatory unique IDs for graph elements

void SetupCanonicalUniqueIDs(IGraph modelGraph) {
  // An IMapper implementation that simply returns the given object itself as 
  // its unique ID.
  IMapper<object, object> idMapper = 
      Mappers.CreateMapper<object, object>(key => key);
  IMapperRegistry registry = modelGraph.MapperRegistry;

  // Use this IMapper implementation for all kinds of graph elements that need 
  // unique IDs.
  registry.AddMapper(MultiPageLayouter.NodeIdDpKey, idMapper);
  registry.AddMapper(MultiPageLayouter.EdgeIdDpKey, idMapper);
  registry.AddMapper(MultiPageLayouter.NodeLabelIdDpKey, idMapper);
  registry.AddMapper(MultiPageLayouter.EdgeLabelIdDpKey, idMapper);
}

In summary, the setup of MultiPageLayouter looks like this:

Example 10.35. Setup of MultiPageLayouter

// 'modelGraph' is of type yWorks.yFiles.UI.Model.IGraph.

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

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

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

// Calculate multi-page layout.
// Afterwards, 'multiPageLayout' contains a list with the single page graphs.
CopiedLayoutIGraph copiedModel = new CopiedLayoutIGraph(modelGraph);
MultiPageLayout multiPageLayout = mpl.CalcLayout(copiedModel);
  
// Now, do something with 'multiPageLayout'...

// Remove the data providers registered by SetupCanonicalUniqueIDs.
modelGraph.MapperRegistry.RemoveMapper(MultiPageLayouter.EdgeLabelIdDpKey);
modelGraph.MapperRegistry.RemoveMapper(MultiPageLayouter.NodeLabelIdDpKey);
modelGraph.MapperRegistry.RemoveMapper(MultiPageLayouter.EdgeIdDpKey);
modelGraph.MapperRegistry.RemoveMapper(MultiPageLayouter.NodeIdDpKey);

Layout Options

Page Size
API
YDimension MaxPageSize { get; set; }
Description Specifies the page dimensions, i.e., the width and height into which the layout of a page graph needs to fit.

By default, MultiPageLayouter distributes the nodes from the original graph to the page graphs automatically. By means of a data provider that is bound to the graph using the look-up key NodeClusterIdDpKey, nodes of the original graph that should end up in the same page graph can be assigned an object that serves as an ID. MultiPageLayouter then tries to distribute nodes with the same ID to the same page graph.

Algorithm Execution Options

Maximal Duration
API
long PreferredMaximalDuration { get; set; }
Description

Sets the preferred maximal 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 less connectors and proxy elements in the page graphs.

Related Classes and Interfaces

Class MultiPageLayout

Class MultiPageLayout is the container to hold the results of the multi-page layout. It is returned by the CalcLayout method of class MultiPageLayouter.

MultiPageLayout 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.

The following code shows how to use NodeInfo objects to find all indexes of page graphs that are connected to the first page graph from a multi-page layout result:

Example 10.36. Querying the MultiPageLayout

// 'result' is of type yWorks.yFiles.Layout.Multipage.MultiPageLayout.

// Get the first from the resulting page graphs.
LayoutGraph firstGraph = result.GetPage(0);

foreach (Node node in firstGraph.Nodes) {
  // Get the NodeInfo object for the current node.
  NodeInfo ni = result.GetNodeInfo(node);

  // Is the current node a connector node?
  if (ni.Type == NodeInfo.TypeConnected) {
    // Get its opposite connector node.
    Node oppositeConnectorNode = ni.ReferencingNode();
    // Get the opposite's node NodeInfo object.
    NodeInfo ni2 = result.GetNodeInfo(oppositeConnectorNode);

    // Find out the index of the page graph the opposite node is in.
    int otherPage = ni2.PageNo();
    Console.WriteLine("Connector node (" + node +
                      ") connects to page graph at index: " + otherPage);
  }
}

Interface IElementFactory

During the sub-division process, class MultiPageLayouter uses an implementation of interface IElementFactory as a factory to create the

  • connector nodes and edges,
  • proxy nodes and edges, and
  • proxy reference nodes and edges

that replace elements of the original graph and augment the page graphs. Class DefaultElementFactory is the predefined default implementation, which provides convenient implementations of all callback methods.

Tutorial Demo Code

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

Supplemental Layout Data

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 10.65, “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 10.65. Data provider look-up keys

Key Element Type Value Type Description
NodeIdDpKey node object For each node an object that is used as a unique ID.
EdgeIdDpKey edge object For each edge an object that is used as a unique ID.
NodeLabelIdDpKey NodeLabelLayout object For each NodeLabelLayout instance an object that is used as a unique ID.
EdgeLabelIdDpKey EdgeLabelLayout object For each EdgeLabelLayout instance an object that is used as a unique ID.
NodeClusterIdDpKey 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.
EdgeTypeDpKey edge object For each edge an arbitrary object indicating its (application-specific) type.