Copyright: Copyright © 1992 - 1996 Tom Sawyer Software
Citation: Copyright © 1992 - 1996 Tom Sawyer Software


Basic Constant Spacing Popup
Selecting this check box specifies that spacing around objects is based on a constant spacing model rather than a magnified spacing model.


Basic Directed Popup
These radio buttons allow you to set the graph to be directed or undirected.


Basic Edge Clipping Popup
Enables the edge clipping facility to clip each edge against the borders of the two nodes to which it connects. Edge clipping minimizes unnecessary edge segment drawing.


Basic Frame Spacing Popup
These edit fields allow you to set the graph frame spacing values. These values dictate the spacing from the edges of the graph's frame to the corresponding edge of the graph.


Basic Incremental Layout Popup
Activates Incremental Layout.


Basic Minimize Edge Crossings Popup
Specifies that the algorithm attempt to reduce edge crossings during incremental layout. Reduce Crossings is disabled if the Active check box is not checked.


Basic Position To Grid Popup
Selecting this check box specifies that a layout of disconnected nodes will follow a grid tiled placement style rather than a bin packed style.


Basic Sort by Name Popup
If names are loaded into each node, selecting this check box indicates that disconnected nodes will be sorted by node name.


Circular Applications
Applications for circular layout

The Circular Layout Library is designed for the network management market, but has applications in others as well. The library currently has support for IP networking. Future releases will add specific support for additional networking protocols based on customer demand. It is a relatively straightforward process to add support for additional networking protocols.


Circular Biconnectivity Popup
Selecting this check box specifies that the clustering algorithm tries to group nodes in the same biconnected components together.


Circular Cluster Size Popup
If checked, the values in the minimum and maximum edit fields will be used as recommended limits on the size of clusters. The cluster algorithm will try to ensure that cluster sizes are within this range.


Circular Edge Degree Popup
Allows you to set the minimum degree that a node must have before it causes the creation of a new cluster during default clustering. If a node has a degree greater than or equal to this value, these nodes will be the seeds to form initial clusters. This value is only used if Cluster By Biconnectivity is not set.


Circular Group Id Popup
Selecting this check box specifies that the family of clustering routines should first consider the Group IDs that may or may not be set within each node. If enabled, all nodes that share the same Group ID will be placed in the same cluster.


Circular Grouping Button
Node grouping dialog

This dialog allows you to set options specific to grouping elements.

For more specific information click on the appropriate section of the dialog's image.


Circular IP Address Popup
Selecting this check box specifies that the clustering algorithm group nodes by their IP addresses. To set items specific to this type of clustering, use the Net Mask dialog.


Circular layout

Circular layout produces graph layouts that emphasize natural group structures inherent in a graph’s topology.

The circular layout is designed to lay out undirected graphs and has a number of features inherent in its design. These include:

Support for node grouping using Internet Protocol (IP) networking standards.

Support for administrative node grouping features.

Radial placement of those groups.

Highlighting the relationship between prominent backbone main clusters in your graph and peripheral sub-sites in your graph.

Emphasis on the "points of failure" in your system with clustering techniques that reveal graph structure.

The generic options of this layout may be set using the Generic Layout Style Options dialog.

The options specific to Circular Layout can be set with the Layout Style Options dialog.

See Also

Applications for circular layout

Why node grouping?


Circular Minimum Slope Popup
Allows you to specify the minimum desired absolute slope percentage for all the edges between clusters.


Circular Net Mask Button
IP netmask dialog

This dialog allows you to set the options specific to grouping elements.

For more specific information click on the appropriate section of the dialog's image.


Circular Node Spacing Popup
Allows you to set the constant node spacing multiplication factor used to calculate the constant node spacing around nodes in each cluster.


Circular Radial Frame Popup
Allows you to specify the frame percent around each cluster for clusters on the same level.


Circular Style Dialog
Circular layout style options dialog

This dialog allows you to set the options specific to Circular Layout.

Select Options|Style... to open the Layout Style Options dialog, then select Circular in the Layout Styles drop-down list to view the options specific to Circular Layout.

For more specific information click on the appropriate section of the dialog's image.


Circular Tangential Frame Popup
Allows you to specify the frame percent for the levels of the hierarchical graphs that clusters are placed in.


Circular Why Node Grouping
Why node grouping?

Node grouping is an effective way to reduce the amount of information that needs to be mentally processed when looking at a graph. Such grouping allows a user to create a mental structure of a graph that is less complex than it might be otherwise. This structure highlights groups and their logical interconnection.

Network administrators often want to impart their knowledge of a network into a visual representation that can emphasize that knowledge. An administrator might like to group all "device nodes" located in the same building onto a single circle, and later display a graph that shows how each of the buildings on a campus are connected together logically.

Furthermore, an administrator might like to use grouping information defined by a specific networking protocol to display that information visually. If the information is presented clearly and the mental map fits the visual map, the network will be easier to manage. The Graph Layout Toolkit's Circular Library has incorporated these ideas in its design.


Color dialog

For more specific information click on the appropriate section of the dialog's image.


Color Dialog Basic Colors Option Popup
Left-click on a color square to select one of the colors.


Contents

Introduction

The Graph Layout Toolkit

Getting Started

Layout styles

Circular

Hierarchical

Orthogonal

Symmetric

Commands

File

Edit

Options

View

Tools

Layout

Navigation

Window

Help

Reference

Glossary


Context Sensitive Pop-up Menu
Context sensitive popup menu

Clicking the right mouse button opens the context sensitive popup menu. There are a variety of different popup menus. For example, clicking the right mouse button on a node brings up a menu that has options pertaining to nodes, clicking on an edge displays options for edges and clicking in the main window displays options for the view.


Define Custom Colors Dialog
Opens an addition to the Color dialog which allows you to define and save your own custom colors.


Definition Acyclic
Acyclic

A graph is acyclic if it does not contain any cycles.


Definition Biconnected Component
Biconnected Component

A subgraph such that for any two nodes in the subgraph, there is at least two distinct undirected paths between them. (i.e; the paths have no nodes or edges in common besides the end nodes).


Definition Column Spacing
Column spacing

The distance between any two consecutive columns in the grid.


Definition Connected Component
Connected Component

A subgraph in which every pair of nodes has an undirected path between them.


Definition Constant Spacing Model
Constant Spacing Model

With this model, a constant space is allocated between like objects in a layout. There is a fixed distance between each adjacent node in a layout, regardless of the width and height of each node.


Definition Cycle
Cycle

A path that starts and ends at the same node.


Definition Cyclic
Cyclic

A graph is cyclic if it contains a cycle.


Definition Degree
Degree

The degree of a node is equal to the number of connections the node has to other nodes.


Definition Directed
Directed graph (Digraph)

A graph in which the direction of each edge is important. For example, a directed graph, or digraph, could be used to represent a "likes" relationship. The relationship "John likes Sally" would be represented with a directed edge labeled likes from John to Sally.


Definition Edge
Edge

A connection between two nodes. An edge may be directed or undirected.


Definition Frame
Frame

Controls the spacing around physical objects. For example, in hierarchical layout, graphs, levels, and nodes have frames.


Definition Frame Level Bounding Rectangle
Frame Level Bounding Rectangle

A rectangle that is slightly larger than the level bounding rectangle.


Definition Frame Node Bounding Rectangle
Frame Node Bounding Rectangle

A rectangle that is slightly larger than the node bounding rectangle.


Definition Graph
Graph

A general mathematical abstraction that is used to model information. Graphs may be used to represent any data that can be modeled as objects and connections between those objects.


Definition Graph Reduction
Graph Reduction

The process of reducing certain subgraphs within the main graph, so that they can be treated as a single entity. Extensive processing can be performed on this modified graph which can later be transformed back into the original graph.


Definition Incident
Incident

An edge is incident to a node if the node is an end point of the edge; that is, if the edge connects the node to another node.


Definition Incremental Layout
Incremental Layout

The previous layout of the graph influences the next layout. This can be useful in preserving the mental map as it tends to reduce changes through consecutive layouts.


Definition Isomorphic Graphs
Isomorphic Subgraphs

Two graphs are isomorphic if they have the same topology.


Definition Layout
Layout

Graph layout algorithms decide where an application program draws these graphs on a graphics output device. Most real-world uses for graphs are complex or change so quickly that layout software is needed to organize them.


Definition Level Bounding Rectangle
Level Bounding Rectangle

The smallest rectangle that encloses an entire level.


Definition Magnified Spacing Model
Magnified Spacing Model

With this model, each object requires an amount of white space around its perimeter that is proportional to the area of the object. If a node's width and height increase, the white space between the node and an adjacent node will also increase. If they decrease, so will the white space.


Definition Multigraph
Multigraph

A graph where two or more edges connect to the same pair of nodes. A multi-directed graph is a directed graph with two or more directed edges connecting the same pair of nodes in the same direction.


Definition Navigation
Navigation

This facility provides consistent mechanisms to manage many graphs and their interrelationships. This allows relationships from nodes or edges to other graphs.


Definition Node
Node

An element of a graph that can be used to represent objects.


Definition Node Bounding Rectangle
Node Bounding Rectangle

The smallest rectangle that encloses an entire node.


Definition Path
Path

A sequence of nodes and edges. For example, a path from node A to node B by way of node C includes the edges AC and CB and the nodes A, B and C. In the Graph Layout Toolkit paths are used to describe the visual representation of an edge with bends.


Definition Proper Hierarchy
Proper Hierarchy

In a proper hierarchical layout, the nodes of a directed graph are partitioned into groups called levels. All the nodes on a given level are positioned within the bounds of the level. For example, if the levels are oriented horizontally, all of the nodes in a level will have similar vertical positioning. Each edge in the layout spans only between adjacent levels. If the hierarchy is not proper, edges may span more than a single level.


Definition Reflexive Edge
Reflexive Edge

An edge that begins and ends at the same node.


Definition Row Spacing
Row spacing

The distance between any two consecutive rows in the grid.


Definition Subgraph
Subgraph

A graph whose set of nodes and edges is a subset of another graph.


Definition Symmetric Graph
Symmetric Graph

A graph which has a geometric embedding that has symmetries.


Definition Topology
Topology

The set of nodes and how they are connected, independent of any geometric representation.


Definition Undirected
Undirected graph

A graph in which the direction of each edge is unimportant. For example, the relationship "John and Sally are siblings" would be represented with an undirected edge labeled "sibling" drawn between Sally and John.


Dialog Custom Zoom
Custom zoom dialog

For more specific information click on the appropriate section of the dialog's image.


Dialog Custom Zoom Percent Popup
Allows you to customize the zoom percentage.


Edge settings options

The Edge submenu allows you to edit edge settings.

Menu Item	Description
Edge|Pen Size...	Open the Line Thickness dialog to select a new pen size for the selected edge(s).
Edge|Pen Color...	Open the Color dialog to select a new pen color for the selected edge(s).
Edge|Pen Style	Select a new pen style for the selected edge(s). The following choices are available: Solid, Dash, Dot, Dash Dot and Dash Dot Dot.


Edge Style Settings Line Thickness Dialog
Line thickness dialog

For more specific information click on the appropriate section of the dialog's image.


Generic Apply Button Popup
Applies these values to the current graph leaving the dialog open.


Generic Cancel Button Popup
Closes the current dialog and does not change any settings.


Generic Close Button Popup
Closes the current dialog and uses the specified value(s).


Generic Default Button Popup
Sets the values of the current dialog to their default settings.


Generic Graphs Popup
Allows you to select which graph of the active views the current dialog applies to.


Generic Help Button Popup
Displays help on the current dialog.


Generic Layout Style Dialog
Generic layout style options dialog

For more specific information click on the appropriate section of the dialog's image.


Generic Layout Style Popup
Allows you to select which layout style the current dialog applies to.


Generic Layout on Apply Popup
If checked, specifies that the current graph be laid out when apply is selected.


Generic Node Palette Popup
Node palette popup

Allows you to choose from a variety of node styles including nodes representing buses, routers, monitors, etc.


Generic Okay Button Popup
Applies the current settings and closes the dialog.


Generic Reset Button Popup
Resets the values in the current dialog to their previous values.


Generic View Document
Allows you to select which view of the graph the current dialog applies to.


Getting Started Creating a New Document/Graph
Creating a new document

1	Select File|New or click [image] in the toolbar. A window will appear entitled "Document1."
2	Repeating step 1 will result in a second window opening, entitled "Document2," and so on.


Getting Started Editing
Editing

Several editing options are available for more flexible graph drawing and editing capabilities. These options include Undo, Cut, Copy, Duplicate, and Delete.

To access the editing options:

1	Select the desired object(s). See Selecting object(s) for more information.
2	Choose an option from the Edit menu or click one of the [image] [image] [image] tools in the toolbar to manipulate the object(s).


Getting Started Inserting Nodes into a Graph
Inserting nodes into a graph

1	Select Tools|Create Node or click [image] in the toolbar.
2	Select a node style from the Options|Node Palette.
3	Set the attributes for each individual node such as its color, and font by choosing Options|Node.
4	Press the left mouse button in the window client area where you would like to create the node.


Getting Started Navigation
Navigation

You can combine a selected set of nodes and their incident edges into a so-called meta-node by creating a frame around them. This, in a way, corresponds to a node-to-graph navigation relationship, where the node is the newly created meta-node and the graph is the newly created graph of selected nodes and edges framed.

Once a navigation relationship is established, you can go back and forth between Parent and Child windows (node and the graph it navigates to, respectively).

To expand the child view "in place" of the parent node:

1	Right mouse click within the child view window
2	Select Expand from the context sensitive popup menu, or Navigation|Expand.

To collapse the Child window back into its own window/document:

1	Right mouse click within the child view window.
2	Select Collapse from the context sensitive popup menu, or Navigation|Collapse.


Getting Started Opening a Document/Graph
Opening a document

Graph files are saved in an ASCII "model" file. The extension for a model file is either .mdl or .get.

To open a document:

1	Choose File|Open or click [image] in the toolbar to load a graph.


Getting Started Opening many Documents with the File Manager
Opening many documents with the file manager

The Graph Layout Toolkit Demonstration can act as a "drop target" for .mdl  and .get files.

If you are running Microsoft Windows 3.1 or Microsoft Windows NT:

1	Open the File Manager application and navigate to a particular file's subdirectory.
2	Select all of the .mdl or .get files in any one of the particular subdirectories.
3	"Drag and drop" that set of files onto the open Graph Layout Toolkit Demonstration client area. Each of these "dropped" files will be opened.

If you are running Microsoft Windows 95:

1	Open files by dragging and dropping the icons of the desired files into the open Graph Layout Toolkit Demonstration client area. Each of these "dropped" files will be opened.


Getting Started Running Layout
Running layout

1	Set the desired layout style by selecting one of the following: Layout|Circular, Layout|Hierarchical, Layout|Orthogonal or Layout|Symmetric
2	Set the general and layout style specific options, such as spacing in between the nodes of a graph, by choosing Options|Basic and/or Options|Style.
3	Perform the layout by choosing Layout|Apply from the menu or clicking [image] in the toolbar.


Getting Started Saving a Document/Graph
Saving a document

Graphs are saved in ACSII "model" files which can be reopened when needed. The extension for a model file is either .mdl or .get.

To save a document:

1	Choose File|Save, File|Save As... or click [image] in the toolbar to save a graph.


Getting Started Selecting
Selecting object(s)

Objects within the current window can be selected and manipulated in various ways. For example, color and font information can be tailored. For more information on manipulating graph objects, see the Option menu.

There are several ways to select objects.

To select a single object:

1	Choose Tools|Select or click [image] in the toolbar.
2	Left click on the object of interest to highlight it for further manipulation.

To select many objects either:

1	Choose Tools|Select or click [image] in the toolbar.
2	Press and hold the Ctrl key while clicking on the objects of interest. This highlights the objects for further manipulation.
or:

1	Choose Tools|Select or click [image] in the toolbar.
2	Left click and hold in an area of the current window that is above and to the right of the top-most object in the group of the objects of interest.
3	Drag the cursor diagonally over the objects of interest, creating a dark rectangular area that encompasses the objects.
4	Release the mouse button. This highlights the objects for further manipulation.

To select one type of object:

1	Choose Edit|Select All Nodes or Edit|Select All Edges to select all objects of that type.

To select all objects in the current window:

1	Choose Edit|Select All.


Getting Started Zooming
Zooming

The zooming capability allows you to view the contents of the active graph window in a variety of ways. You can "zoom into" a particular area of the graph for a closer look or view all objects at once.

You can zoom in and out of the active window in several ways:

1	Select Tools|Zoom or click [image] in the toolbar.
2	Hold the left mouse button and drag the mouse to frame the objects you would like to zoom into. When the left mouse button is released, the framed objects will fill the current window.
or,

1	Select one of the View|Menu options.
or,

1	Choose the + (plus) key from the number pad to zoom in 10 percent.
2	Choose the - (minus) key from the number pad to zoom out 10 percent.


Getting_Started Linking Nodes through Edges
Linking nodes with edges

1	Select Tools|Create Edges or click [image] in the toolbar.
2	Left-click and hold the left mouse button on the source node.
3	Move the cursor to the target node.
4	Release the left mouse button when the cursor is inside the boundaries of the target node.
5	Set the attributes for each individual edge such as its thickness, color, and style by choosing Options|Edge.
Note: Reflexive edges can be created in a similar manner.


Glossary

A

Acyclic

B

Biconnected Component

C

Column Spacing

Connected Component

Constant Spacing Model

Cycle

Cyclic

D

Degree

Directed Graph

E

Edge

F

Frame

Frame Level Bounding Rectangle

Frame Node Bounding Rectangle

G

Graph

Graph Reduction

I

Incident

Incremental Layout

Isomorphic Subgraphs

L

Layout

Level Bounding Rectangle

M

Multigraph

Magnified Spacing Model

N

Navigation

Node

Node Bounding Rectangle

P

Path

Proper Hierarchy

R

Reflexive Edge

Row Spacing

S

Subgraph

Symmetric Graph

T

Topology

U

Undirected Graph


Grouping Dialog

This dialog allows you to set the group id of nodes. The group id is used in circular layout to identify which nodes should be in which clusters. Nodes with the same group identifier are laid out in the same cluster.

Clicking on Grouping... in the Circular Layout Style Options dialog opens the Node Grouping dialog.

From more specific information click on the appropriate section of the dialog's image.


Grouping Group Filter Popup
Allows you to select which nodes are going to be filtered. The options include All, Selected, Grouped Ungrouped.


Grouping Group Id Popup
Allows you to set the Group ID of the selected node(s).


Grouping Sort By Popup
Allows you to set how the nodes are sorted. The options include sorting by Name or Group ID.


Grouping Ungroup All
Ungroups all of the current groups.


Grouping Update
Updates the grouping information to the current group setting information.


Grouping Update Button Popup
Updates the dialog with the current information.


Grouping Window Popup
Displays the name of nodes and their corresponding Group ID.


Hierarchical Applications
Applications for hierarchical layout

The Hierarchical Layout Library is useful in a number of application domains, which include:

Project management software.

Compiler and software development tools.

Data inspection tools.

Work-flow software.

Information management software.

Reverse engineering applications.

Networking software.

Database schema viewers.


Hierarchical Edge Clipping Popup
This radio box specifies how edge clipping will occur.

If Node Centers is selected, the edge will be drawn to the center of each node. If Node Sides is selected, the edge will be clipped at the center of each node's side.


Hierarchical layout

The Hierarchical Layout Library produces graph layouts that emphasize hierarchical structures inherent in the topology of a graph.

It can render both directed and undirected graphs, although its design makes it particularly suitable for directed graphs.

It has a number of positive characteristics inherent in its design. These include:

Hierarchical organization of nodes in a graph.

Support for cyclic and acyclic directed graphs.

A relatively small number of edge crossings.

Performance that scales well as graph size increases.

Extensions to lay out undirected graphs.

The generic options of this layout may be set using the Generic Layout Style Options dialog.

The options specific to hierarchical layout can be set with the Layout Style Options dialog.

See Also

Applications for hierarchical layout

Proper hierarchical layout

Hierarchical layout processing

Hierarchical performance issues


Hierarchical layout processing

Multiedge processing

The Hierarchical Library detects and aggregates the multiedges present in the input graph. This phase processes the list of known multiedges and performs a path shifting operation to produce the multiedge slotted path effect The slotted effect can also produce groups of parallel paths. The Hierarchical Library provides full support for an arbitrary number of edges between pairs of nodes.

Reflexive edge processing

This phase detects and processes the set of reflexive edges in the input graph. For hierarchical layout, a path structure is built to visually represent a reflexive edge. The reflexive edge layout maintains a proper hierarchical layout.

Level assignment

Level assignment is a phase specific to hierarchical layout. It partitions nodes into groups called levels. Each node in a level shares a common y (x) coordinate if the levels are oriented horizontally (vertically). Each edge in the graph connects to two nodes that belong to different levels, and edges that span more than one level are decomposed into a series of edge segments, each spanning a single level. Dummy (invisible) nodes are used to connect the series of edge segments. This grouping of edge segments and dummy nodes is maintained as a path in the Hierarchical Library.

Graph reduction and position balancing

This facility detects certain subgraphs within the main graph, so it can treat each subgraph as a single entity. When processing of this reduced graph is finished, subgraphs are expanded back into the original graph (they are position-balanced to make effective use of the display area), crossing minimization is performed and the total path length is minimized.


Hierarchical Level Justification Popup
These radio buttons set the justification for the nodes in each level of the hierarchical layout.

For example, with different sized nodes, if the orientation is Left To Right and the justification is set to left, the left side of all nodes in a given level will be aligned.


Hierarchical Level Spacing Popup
This edit field allows you to set the spacing between each level in the graph. The constant level spacing describes how much larger the frame level bounding rectangle is than the level bounding rectangle.


Hierarchical Minimum Slope Popup
Allows you to set the minimum absolute slope percentage for all of the edges in the graph. If this minimum is not satisfied for an edge, the levels are arranged to adjust the slope by the required amount.


Hierarchical Node Spacing Popup
This edit field allows you to set the spacing between each node in each level of the graph. The constant node spacing describes how much larger the frame node bounding rectangle is than the node bounding rectangle.


Hierarchical Orientation Popup
These radio buttons allow you to set the orientation of a hierarchical graph.

For example, if the orientation is set to Left To Right, the "roots" of the graph are positioned closest to the left and the levels of the graph will be positioned vertically. If the orientation is set to Top To Bottom, the "roots" of the graph will be positioned closest to the top of the graph and the levels of the graph will be positioned horizontally.


Hierarchical performance issues

High Performance

The Hierarchical Library's performance is very good and can lay out graphs with hundreds of nodes in a few seconds. The performance also scales well to much larger graphs.


Hierarchical Proper Hierarchy Popup
If checked, sets the graph to be laid out as a proper hierarchy.


Hierarchical Proper Layout
Proper hierarchical layout

The Hierarchical Layout Library works by partitioning a graph into a set of levels. Each edge is represented by a path, a series of invisible nodes and visible edges, with each edge in the path spanning a single level.

What is a level?

A level is a grouping of nodes placed along a line. Usually a horizontal or vertical line can be drawn through the nodes that belong to a particular level. When a graph has a horizontal (vertical) level orientation, each level occupies a row (column) in the graph.

What is a proper hierarchy?

The Hierarchical Library outputs a proper hierarchical layout of your graph by default. In a proper hierarchical layout, the nodes of a directed graph are partitioned into groups called levels, such that:

All nodes on a given level are positioned within the bounds of the level. For example, if the levels are oriented horizontally, all of the nodes in a level will have similar vertical positioning.

Each edge in the layout spans only between adjacent levels (i.e., from level i to level i + 1, or from level i + 1 to level i). As a convention, the levels of a directed graph are numbered from 0 (the roots of the hierarchy) to n (the leaves furthest from the roots).


Hierarchical Style Dialog
Hierarchical layout style options dialog

This dialog allows you to set the options specific to Hierarchical Layout.

Select Options|Style... to open the Layout Style Options dialog, then select Hierarchical in the Layout Styles drop-down list to view the options specific to Hierarchical Layout.

For more specific information click on the appropriate section of the dialog's image.


Intro Getting Started
Getting Started

Creating a new document

Inserting nodes into a graph

Linking nodes with edges

Running layout

Selecting object(s)

Zooming

Editing

Opening a document

Opening many documents with the file manager

Saving a document

Navigation


Intro What is the Graph Layout Toolkit
Introduction to the Graph Layout Toolkit

 What are graphs?

A graph is a general mathematical abstraction that is used to model information. Graphs may be used to represent almost any structure that can be modeled as a set of discrete objects (nodes of a graph) and relationships among those objects (edges of a graph).

Almost every domain of computer science - and therefore most segments of the software industry - use graphs in some form to represent information. Software applications use graphs to represent object hierarchies, project schedules, network maps, database schema and data-flow diagrams.

What is "graph layout"?

Graph layout algorithms decide where an application program draws the nodes and edges on a graphics output device. Most real-world uses for graphs are complex or change so quickly that layout software is needed to organize them.

If an application represents information with graphs, visualizing them becomes an important human understanding tool.

What is the Graph Layout Toolkit?

The Graph Layout Toolkit is a family of portable, automated, object positioning libraries designed for integration into Graphical User Interface (GUI) application programs. Its purpose is to make graphs more readable by choosing logical (x,y) positions for nodes and suitable routing for edges.

With Graph Layout Toolkit services, an application program can create meaningful visual representations of graphs so that end users have an important visual tool for better understanding their modeled information.

The Graph Layout Toolkit functions as a software component. Since it does not include any graphics code, you are free to use it with any GUI toolkit or windowing system.

What are its features and benefits?

The Graph Layout Toolkit adheres to modern object-oriented programming (OOP) standards and C++ standards-based development.

It is composed of a base system and a virtual function-driven layout engine. In addition, the Graph Layout Toolkit provides a family of layout libraries that inherit from the layout engine. Features of the Graph Layout Toolkit include:

Graph manipulation.

A portable geometric model for working with graph drawings.

Interactive editing support.

Navigation facilities.

Layering and nesting capabilities.

System considerations

The Graph Layout Toolkit is portable to any environment with a C++ compiler supporting the ANSI C++ specification.

An ANSI C API is also provided for C application programs. The ANSI C API parallels the capabilities of the public interface provided as part of the C++ API. The Graph Layout Toolkit is not dependent on any particular hardware platform. Since most compilers for other languages provide mechanisms to make calls to the C language, the ANSI C API allows programmers to install the Graph Layout Toolkit with most application programs.

While the Graph Layout Toolkit object code is available now for the most commonly-used compilers, it is Tom Sawyer Software’s intention to continue to add support for more compilers. Since support is influenced by customer demand as well as machine and compiler availability, feel free to inquire about ports to machines and compilers not mentioned in the Graph Layout Toolkit supported platform list.

Memory requirements

There are no software limitations imposed on the topology of graphs; they may contain any number of nodes or edges. Each node currently requires about 400 bytes of memory; each edge requires about 200 bytes (based on four-byte integers). The layout call produces a path to visually describe each edge. Each path currently requires about 100 bytes.

In addition, each installed layout library adds some fields to each of the basic objects to store data specific to that particular library. Nearly all memory needed in the Graph Layout Toolkit is allocated only on demand to greatly reduce overall memory usage.

Disk space requirements

A distribution that includes header files and libraries requires approximately two megabytes of disk space. The space required will vary somewhat depending on the system architecture and compiler used.

Floating point variables

Different libraries have different requirements regarding the use of floating point variables. The Hierarchical and Orthogonal Libraries make minimal use of floating point variables, which improves performance. The Circular and Symmetric Libraries use floating point variables more heavily.

Code reentrance

The Graph Layout Toolkit is designed to be code reentrant. It works with operating systems that support multiple threads of execution within a single process such as Microsoft Windows 95, Microsoft Windows NT, OS/2, Mach and SunSoft’s Solaris 2.x. It does not make use of any global variables.

Data reentrance

Data reentrance requires the locking of certain data structures during the operation of particular API functions and methods. Data reentrance can be an issue with multi-threaded operating systems. If different threads of execution are operating on the same graph object, API calls may cause side effects on the graph that is currently being laid out. The Graph Layout Toolkit does not provide its own locking mechanism. Your application should take advantage of system-specific locking services.

Exception handling

The Graph Layout Toolkit supports C++ exception handling for those C++ compilers that implement the feature. Exception handling is useful in that it helps your application gracefully recover from troublesome conditions such as low memory or low disk space.


Layout style options

To edit the options for a particular layout style use the Layout Style drop-down list box. The possible choices are:

Circular

Hierarchical

Orthogonal

Symmetric


Line Thickness Popup
Allows you to specify a line thickness from 1 to 9, 1 being the thinnest.


Menu Edit
Edit menu

The Edit menu includes commands for editing and access to the Clipboard.

To select an option from the Edit menu, left-click on Edit then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Edit|Undo	Ctrl+Z	Cancel the previous operation.
Edit|Cut	Ctrl+X	Cut the selected object(s) and save them in the clipboard.
Edit|Copy	Ctrl+C	Copy the selected object(s) and save them in the clipboard.
Edit|Paste	Ctrl+V	Paste the saved object(s) from the clipboard into the active graph window.
Edit|Duplicate	Ctrl+D	Duplicate the selected object(s) from the graph window.
Edit|Clear All	Ctrl+Del	Remove all objects from the graph window.
Edit|Delete	Del	Delete the selected object(s) from the graph window.
Edit|Select All	Ctrl+A	Select all objects in the active graph window.
Edit|Select All Nodes	Ctrl+N	Select all nodes in the active graph window.
Edit|Select All Edges	Ctrl+E	Select all edges in the active graph window.


Menu File
File menu

The File Menu includes commands that allow you to create, open, save and print a document.

To select an option from the File menu, left-click on File then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
File|New		Open a new document.
File|Open...		Open an existing document.
File|Close		Close the current document.
File|Save		Save the current document.
File|Save As...		Save the current document with the specified file name.
File|PostScript Setup...		Open the PostScript Setup dialog to set options specific to PostScript output.
File|Print		Open the Print dialog to set options specific to printing.
File|Print Setup...		Open the Print Setup dialog to set options specific to page layout.
File|Print Preview		Open a preview of the active window.
File|Exit	Alt+F4	Exit the Graph Layout Toolkit Demonstration.


Menu Help
Help menu

The Help menu includes commands for viewing on-line help.

To select an option from the Help menu, left-click on Help then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Help|Contents	F1	Open the contents page of the Graph Layout Toolkit Demonstration's on-line help.
Help|Using Help		Display information on how to use help.
Help|About...		Display the copyright and software version information for the Graph Layout Toolkit Demonstration as well as how to contact Tom Sawyer Software.


Menu Layout
Layout menu

The Layout menu includes options for setting a layout style and performing a layout.

To select an option from the Layout menu, left-click on Layout then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Layout|Circular		Set the current layout style to Circular.
Layout|Hierarchical		Set the current layout style to Hierarchical.
Layout|Orthogonal		Set the current layout style to Orthogonal
Layout|Symmetric		Set the current layout style to Symmetric.
Layout|Randomize		Produce random output coordinates.
Layout|Apply	Ctrl+L	Apply the chosen layout style to the graph.


Menu Navigation
Navigation menu

The Navigation menu includes options that perform navigation operations.

To select an option from the Navigation menu, left-click on Navigation then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Navigation|Expand		Expand selected node(s) to show linked information.
Navigation|Collapse		Collapse selected node(s) to hide linked information.
Navigation|Expand All	Ctrl+S	Expand node(s) to show all linked information.
Navigation|Collapse All	Ctrl+H	Collapse node(s) to hide all linked information.


Menu Options
Options menu

The Options menu includes commands for viewing or changing the current document settings.

To select an option from the Options menu, left-click on Options then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Options|Basic...		Open the Generic Layout Style Options dialog to set options common to all layout styles.
Options|Style...		Open the Layout Style Options dialog to set options specific to a particular layout style.
Options|Node Palette		Open the Node Palette popup to choose from a variety of node styles.
Options|Node		Open the Node submenu to set options specific to node settings.
Options|Edge		Open the Edge submenu to set options specific to edge settings.


Menu Tool
Tools menu

The Tools menu options allow you to select and manipulate graph objects.

To select an option from the Tools menu, left-click on Tools then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Tools|Select		Select object(s).
Tools|Zoom		Zoom into or out of the active graph window.
Tools|Frame		Select a group of objects for further manipulation.
Tools|Create Nodes		Insert nodes into the graph.
Tools|Create Edges		Insert edges into the graph.


Menu View
View menu

The View menu includes options to customize the active window.

To select an option from the View menu, left-click on View then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
View|Fit in Window	Alt+F	Display the whole graph within the window.
View|25%		Display the graph at 25% its actual size.
View|50%		Display the graph at 50% its actual size.
View|Actual Size	Alt+Z	Display the graph at its actual size.
View|200%		Display the graph at 200% its actual size.
View|400%		Display the graph at 400% its actual size.
View|Custom...	Alt+C	Open the Custom Zoom dialog to customize the view of the current graph.

See Also

Zooming


Menu Window
Window menu

The Window menu includes options to arrange open windows.

To select an option from the Window menu, left-click on Window then left-click on the highlighted option of your choice or use the specified keyboard shortcut, if any.

Menu Item	Keyboard Shortcut	Description
Window|Cascade	Shift+F5	Cascade open windows.
Window|Tile Horizontally		Tile open windows horizontally on the desktop.
Window|Tile Vertically	Shift+F4	Tile open windows vertically on the desktop.
Window|Arrange Icons		Arrange iconic windows along the bottom.
Window|Close All		Close all open windows.
Window|Refresh	F5	Refresh the graph in the current window.
Window|Hide Inspectors		Hide all open inspector dialogs.
Window|Show Inspectors		Restore all open inspector dialogs.
All open documents are listed at the end of this drop-down list. You can change active windows by selecting another document in the list; the active window is check marked.


Net Mask Class Popup
Displays the current group class.


Net Mask IP Network Popup
Displays the current IP Network.


Net Mask Subnet Mask Popup
Displays the current Subnet Mask.


Net Mask Ungroup All Button Popup
Removes all Group IDs that are currently associated with the nodes.


Net Mask Window Popup
Displays the current IP information.


Node Font Color Popup
Allows you to select a color for the node text.


Node Font Dialog
Font dialog

For more specific information click on the appropriate section of the dialog's image.


Node Font Popup
Allows you to select the font of the node text.


Node Font Sample Popup
Displays a text sample of the items currently selected.


Node Font Script Popup
Displays the script style currently selected.


Node Font Size Popup
Allows you to select the font size of the node text.


Node Font Strikeout Popup
If checked, strikes through the node text.


Node Font Style Popup
Allows you to select the font style of the node text.


Node Font Underline Popup
If checked, underlines the node text.


Node settings options

The Node submenu allows you to edit node settings.

Menu Item	Description
Node|Frame Color...	Open the Color dialog to select a new color for the selected object's frame node background.
Node|Background Color...	Open the Color dialog to select a new color for the selected object's background.
Node|Foreground Color...	Open the Color dialog to select a new color for the selected object's foreground.
Node|Font...	Open the Font dialog to select a new font for the selected object's text.


Orthogonal Applications
Applications for orthogonal layout

The Orthogonal Layout Library is most useful in applications which require high clarity in graph presentation but do not require that drawings show inherent hierarchical structures. The following applications are often well suited to the use of the Orthogonal Library:

Physical and logical database design applications.

Software reengineering applications.

CAD diagrams.

OOA/OOD diagrams.

Data warehousing

CASE diagrams.


Orthogonal Column Spacing Popup
Allows you to specify the spacing between the columns of the grid that the nodes are laid out on.


Orthogonal Details
Orthogonal layout processing

The Orthogonal Layout Library works by drawing a graph onto a grid of rows and columns.

The grid

A grid consists of columns which are parallel to the y-axis and rows which are parallel to the x-axis. Two spacing parameters govern the grid: column spacing and row spacing.

Node positioning

Nodes are placed at different positions in rows and columns. A node may occupy several rows and columns depending on the relative sizes of the node height and width and the grid spacing parameters. In addition, a node is forced to span over more than one row or column if it has more than one incident edge on any one side.

Edge routing

Edges are represented by paths. Each edge in a path is drawn along a segment of a row or a column so that a path traverses a series of intersecting rows and columns in the grid.

Drawing quality

In orthogonal drawings, the edges must be routed along the grid. The layout algorithm ensures high quality in layouts by keeping the number of bends along edges relatively low. The Orthogonal Library also includes procedures for compressing the drawing so that the area is small. High clarity in drawings may be obtained by stretching nodes. However, this may not be acceptable in certain applications, so that (although the stretching that takes place is kept as low as possible) the algorithm can be tailored to control stretching in the whole graph or on a per node basis.


Orthogonal Fixed Node Size Popup
If unchecked, specifies that Orthogonal Layout resize nodes if needed.


Orthogonal Layout

Orthogonal layout produces graph layouts in which edges run parallel to the x- and y- axes.

The Orthogonal Library can draw both directed and undirected graphs. It has a number of positive characteristics inherent in its design. These include:

A small number of bends per edge and a relatively small number of edge crossings.

Minimal stretching of nodes which have a high number of edges.

Performance that scales well as graph size increases.

No overlap between nodes, or between nodes and non-incident edges.

When crossings do occur, the orthogonal drawing style ensures that the edges involved can still be read with clarity.

The generic options of this layout may be set using the Generic Layout Style Options dialog.

The options specific to Orthogonal Layout can be set with the Layout Style Options dialog.

See Also

Applications for orthogonal layout

Orthogonal layout processing

Orthogonal performance issues


Orthogonal Layout Quality Popup
This radio box allows you to set the layout quality, draft being the lowest quality. The higher the quality, the longer the layout will take to run.


Orthogonal performance issues

High Performance

The Orthogonal Library can lay out graphs with hundreds of nodes in a few seconds. The performance also scales well to much larger graphs.


Orthogonal Row Margin Popup
Allows you to specify the margin that a node can overlap a grid. This is expressed as a percentage of the row and column spacing and ensures that edges are not too close to the corner of nodes.


Orthogonal Row Spacing Popup
Allows you to specify the spacing between the rows of the grid that the nodes are laid out on.


Orthogonal Style Dialog
Orthogonal layout style options dialog

This dialog allows you to set the options specific to Orthogonal Layout.

Select Options|Style... to open the Layout Style Options dialog, then select Orthogonal in the Layout Styles drop-down list to view the options specific to Orthogonal Layout.

For more specific information click on the appropriate section of the dialog's image.


Post Script Scale By
Allows you to set whether the output is scaled by page row and column information or percentage value.

When the Pages radio button is selected, only the Page Columns and Page Rows edit fields are active.

When the Percent radio button is selected, only the Scale Factor edit field is active.


PostScript Monochrome Printer
Specifies that the printer in use is a monochrome printer.


PostScript Orientation
These radio buttons specify whether the output is in portrait or landscape format.


PostScript Show Crop Marks
Shows crop marks on the output.


PostScript Show Page Border
Shows the page borders on the output.


PostScript Show Page Label
Shows page labels on the output using the specified font and font size.


PostScript Show Page Numbers
Shows page numbers on the output using the specified font and font size.


PostScript Show Various
Shows element names on the output using the specified font and font size.


Postscript Setup Border
Allows you to set the border around the page in inches.


PostScript Setup dialog

For more specific information click on the appropriate section of the dialog's image.


Postscript Setup Format
Allows you to specify the output as either PostScipt or encapsulated PostScript format.


Postscript Setup Height
Allows you to set the height of the page in inches.


Postscript Setup Width
Allows you to set the width of the page in inches.


Print dialog

For more specific information click on the appropriate section of the dialog's image.


Print Dialog Collate Popup
If checked, specifies that the copies be collated.


Print Dialog Copies Popup
Allows you to specify the number of copies to be printed.


Print Dialog Print Quality Popup
Allows you to specify the dots per inch the printer will use.


Print Dialog Print to File Popup
If checked, prints the current graph to the specified file.


Print Dialog Printer Popup
Specifies the printer you are printing to.


Print Dialog Range Popup
Allows you to specify the page range to be printed.


Print Dialog Setup Popup
Allows you to set options specific to the printer.


Print Setup Borders Popup
If checked, specifies that page borders be printed.


Print Setup Caption Checkbox Popup
If checked, allows you to specify caption text in the Caption box.


Print Setup Caption Popup
If the Print Caption check box is checked, specify the caption text here.


Print Setup Crop Marks Popup
If checked, specifies that crop marks be printed.


Print Setup dialog

For more specific information click on the appropriate section of the dialog's image.


Print Setup Fit Popup
If checked, specifies that the graph be printed on one page.


Print Setup Margins Popup
Allows you to set the left, right, top and bottom margin widths.


Print Setup Numbers Popup
If checked, specifies that page numbers be printed.


Symmetric Applications
Applications for symmetric layout

The Symmetric Layout Library is useful in a number of application domains. Examples include layouts of:

Wide area networks.

Database schemata.

Semantic networks.


Symmetric Granularity Popup
Allows you to set the fineness of the grid on which the nodes are moved during layout. This value can be from 0 to 100 where a lower value represents a finer grid. Generally, a finer grid will produce a better final layout, though the computation time will be longer.


Symmetric Heuristic Solution
A heuristic solution

The Symmetric Library uses a heuristic for computing graph layouts.

The heuristic picks the node that is furthest out of place, and iteratively moves it closer to its ideal position. The node is moved until its error term (i.e., the distance it is out of place) falls below the threshold, epsilon. This process of picking and iteratively moving a node is itself iterated until no node is further than epsilon out of place.

Due to the nature of this hill-climbing method, the basic heuristic can loop forever. The Symmetric Library's layout method has been modified to detect and avoid infinitely looping configurations.


Symmetric Layout

The Graph Layout Toolkit's Symmetric Library produces graph layouts that emphasize the symmetries inherent in a graph's togology.

The Symmetric Library can render both directed and undirected graphs, though in the former case the direction of the edges is ignored. It has a number of useful characteristics inherent in its design. These include:

Symmetric layout of symmetric graphs

Almost congruent layout of isomorphic graphs

Uniform distribution of nodes

Relatively small number of edge crossings

The generic options of this layout may be set using the Generic Layout Style Options dialog.

The options specific to Symmetric Layout can be set with the Layout Style Options dialog.

See Also

Applications for symmetric layout

A heuristic solution

Symmetric layout processing

Symmetric performance issues


Symmetric layout processing

The layout process involves several phases, including multiedge and reflexive-edge processing. Additionally, the Graph Layout Toolkit detects connected subgraphs, calculates drawing order and occludes edges to nodes. An outline of each phase is provided below.

Multiedge processing

A multigraph is a graph with two or more edges connecting the same pair of nodes. The Symmetric Library treats all graphs as undirected, by ignoring the edge directions. Thus, given an input directed graph with edges AB and BA, the Symmetric Library will treat these as a pair of undirected multiedges connecting nodes A and B.

Multiedge preprocessing detects and aggregates the multiedges present in the input graph. This phase processes the multiedges and performs a path shifting operation to produce the multiedge slotted path effect.

Reflexive edge processing

This phase detects and processes the set of reflexive edges in the input graph. For symmetric layout, a reflexive edge is represented with a path containing two intermediate nodes and three edges.


Symmetric Node Spacing Popup
Allows you to set the space around each node in the final layout. It specifies the desired length of each edge as a function of the width and height of the nodes that the edge connects to. A value of 0 sets the node spacing so that nodes will be barely touching. The larger the value, the more white space between nodes.


Symmetric performance issues

Fast machine

The Symmetric Library's performance is proportional to the cube of the number of nodes present in a graph to be laid out. While the Symmetric Library usually runs well on PC class machines, we recommend using workstation class machines with this library if you have very large graphs to lay out.

Math coprocessor

If you are using a PC class machine, check whether your system has a math coprocessor installed. We strongly recommend that you install a math coprocessor if one is not already present on your machine since this library is highly dependent on numerical operations.


Symmetric Random Seed Popup
Allows you to set the seed for a sequence of numbers which are used to set initial coordinates for each node when the Symmetric Layout begins processing. Altering this may produce a different final layout.


Symmetric Style Dialog
Symmetric layout style options dialog

This dialog allows you to set the options specific to Symmetric Layout.

Select Options|Style... to open the Layout Style Options dialog, then select Symmetric in the Layout Styles drop-down list to view the options specific to Symmetric Layout.

For more specific information click on the appropriate section of the dialog's image.


Symmetric Tension Constant Popup
Allows you to set the tension constant value that is used for each edge in the graph. Higher tension constants generally cause edge lengths to be reduced.


Symmetric Termination Value Popup
Allows you to set how finely positions are tuned in resolving the energy in the graph. Smaller values produce higher quality layouts but run more slowly.