graph-layout

Arguments: &key nodes links selected-node (selected-node-steps 8) fixed-nodes links-reader node1-reader node2-reader center-x-reader center-y-reader width-reader height-reader center-writer linear-links-reader redisplay-function cancel-function animate redisplay-at-end pause canvas (canvas-left 0) (canvas-top 0) (canvas-right 1000) (canvas-bottom 1000) extended-canvas-left extended-canvas-top extended-canvas-right extended-canvas-bottom (canvas-center-x (floor (+ canvas-left canvas-right) 2)) (canvas-center-y (floor (+ canvas-top canvas-bottom) 2)) (min-node-to-node-spacing 12) (min-link-to-node-spacing 12) (max-iterations 200) (work-from-current-layout t) (spacing-increment-for-many-links 15) (long-path-spacing-increment 15) (long-path-max-spacing 60) (num-links-before-extra-spacing 2) (iterations-for-extra-spacing 12) (limit-outward-stretching t) (protect-tail-node-positions t) (consider-alternate-spots-by-linked-nodes :after-crossed-links) (number-of-alternate-positions 3) consider-additional-leaf-positions ignore-crossed-tails exclude-tail-nodes-from-home-positions compress-layout-at-end center-the-graph

This function performs a graph layout by determining the positions to which a set of arbitrary user nodes (or vertices) should be moved to make the graph relatively readable when drawn in some way. It does not draw anything, but simply specifies where to move nodes. The drawing (rendering) aspect could be done with the Common Graphics nodes-and-links facility (see node-pane-mixin) or with some other rendering tool, either in Common Graphics or not.

The layout algorithm specializes in cyclic graphs, where it is non-trivial to arrange the nodes. It attempts to arrange the nodes so that nodes are near their neighbor nodes, but without any link lines (edges) passing through nodes to which they aren't connected. (Straight link lines between the centers of nodes are assumed.) It arrives at a solution incrementally by repeatedly moving individual nodes to better niches.

The algorithm will also lay out simple trees, though for trees it would usually be better to use a different layout algorithm that arranges things in a more regular directional pattern. This function would likely fit more of a tree into a given area, though in a less regular arrangement than a dedicated tree grapher.

This function can work with any sort of user data, as long as there is an object for each node (or vertex) and each link (or edge). This works by passing in accessor functions that return the current position and size of an arbitrary node object, or the list of links for a node or the two nodes for a link. One other access function that you pass in will be called repeatedly by this function to store a new position for a node. When this function returns, the calling application can then read the node positions that this access function stored somewhere, and then draw the graph in some way.

Three values are returned: (1) t or nil indicating whether the layout succeeded (see just below), (2) the number of iterations that were done, and (3) t or nil indicating whether the user canceled.

The term succeeded means reached a state where no further improvement could be made by moving a single node.

There is an example in the Navigator Dialog that illustrates using this function along with the nodes-and-links facility for rendering. The example is called Custom Graphical Objects: A Nodes and Links Editor.

See also the utility functions graph-boundaries (which calculates a rectangle holding all nodes), center-all-nodes (which repositions nodes), and other-node which returns the node connected to a specified node by a link.

Arguments

The many arguments to this function are grouped into four categories: Main, Accessor Function, Miscellaneous, and Option.

Main Arguments

• nodes is a list of some sort of node objects. It can be nil if a list of links is provided, in which case the accessor functions that you provide will find the list of all nodes from the links. Otherwise it should be a list to which the accessor functions can be applied to return information about the nodes, and to which the center-writer function can be applied to update a node's current position.
• links is a list of some sort of link objects. It can be nil if a list of nodes is provided, in which case the accessor functions that you provide will find the list of all links from the nodes. Otherwise it should be a list to which the accessor functions can be applied to return information about the links.
• selected-node may be nil if no node is to be treated as the special selected node. Otherwise it should be one of the nodes in the graph. This node will have a fixed position during the layout if selected-node-steps is nil, or else will be moved gradually during the layout to the center of the primary canvas.
• selected-node-steps is the number of iterations that will be used to move the selected-node (if any) to the center of the canvas; if nil, then the selected-node (if any) will stay fixed at its current position.
• fixed-nodes is a list of some subset of the nodes list. These nodes will not be moved at all during the layout. The other nodes will arrange themselves around the fixed nodes. This can be useful when changing the set of nodes that are displayed, to keep some or all of the existing nodes in the same place and arranging newer nodes around them, to retain context.

Accessor Function Arguments

• links-reader should be a function that accepts a node as a single argument and returns a list of that node's links.
• node1-reader should be a function that accepts a link as a single argument and returns the first of the link's two nodes. This is generally the "subject" of a relation or the "from" node of some sort.
• node2-reader should be a function that accepts a link as a single argument and returns the second of the link's two nodes.
• center-x-reader should be a function that accepts a node as a single argument and returns an integer that indicates the current horizontal position of the center of the node.
• center-y-reader should be a function that accepts a node as a single argument and returns an integer that indicates the current vertical position of the center of the node.
• width-reader should be a function that accepts a node as a single argument and returns an integer that indicates the current width of the node.
• height-reader should be a function that accepts a node as a single argument and returns an integer that indicates the current height of the node.
• center-writer should be a function that accepts three arguments, namely a node, a center-x integer, and a center-y integer. It should update the current position of the node so that the center-x-reader and center-y-reader functions will return the x and y values when they are subsequently called on the node.
• linear-links-reader should be nil if all link lines are allowed to point in any direction. Otherwise it should be a function that accepts a single argument, which will be one of the link objects that are passed in the list for the links argument. The function should return nil for a particular link if that link is allowed to point in any direction. Otherwise it should return one of the keyword symbols :upward, :downward, :leftward, or :rightward to indicate the direction that the link should point. The value :upward, for example, will force the node2 of the link to be at least somewhat higher than the node1 of the link in the layout. So :upward really means "more upward than downward" and the link line could, for example, point East by Northeast.
• redisplay-function should be a function that accepts a single argument for some sort of canvas on which the layout will be drawn. Typically the argument is a window, and the function will simply invalidate the window so that it will redraw itself. It is then up to the window's usual redisplay function to examine the set of nodes and links and to redraw everything according to the node positions that have been established through calls to the center-writer function.

Miscellaneous Arguments

• animate indicates whether the redisplay-function function is called multiple times to draw the layout as it is incrementally updated. If nil, the redisplay-function function is called only once at the end of the layout. If :node, then the redisplay-function function is called each time a node has moved. If any other true value, then the redisplay-function function is called once each time the entire set of nodes have had their positions updated. This last option is generally the better style of animation.
• redisplay-at-end indicates whether the redisplay-function is called after the layout has finished. This is probably useful only when animate is nil, in which case it could be used when another call to graph-layout is about to be made (typically with different options), to suppress all redisplay until the final call to graph-layout.
• pause indicates whether to pause each time the redisplay-function function is called. It may be nil for no pause, or a positive number indicating the number of seconds to pause. This simply calls sleep.
• canvas should be some sort of object on which the layout will be drawn, such as a window. This object will simply be passed to the redisplay-function function and cancel-function whenever they are called.
• canvas-left, canvas-top, canvas-right, and canvas-bottom should be integers that indicate the extent of the primary canvas into which graph-layout will attempt to fit everything. The units should be the same as those used by the accessor functions such as the center-x-reader and the center-writer. These are typically the extents of the currently visible part of a window, measured in pixels.
• extended-canvas-left, extended-canvas-top, extended-canvas-right, and extended-canvas-bottom may either be nil to force everthing to fit onto the primary canvas, or else integers to indicate the extent of a larger canvas into which nodes will be moved when they cannot be fit acceptably on the primary canvas. The values should encompass the primary canvas extents. These are typically the extents of the entire canvas that can be scrolled into a window, measured in pixels. This appears to be useful when the extended canvas is somewhat larger than the primary canvas, but not when it is a lot larger. Therefore, if the needed canvas size is a lot larger than the available visible area of a window, it's probably best to pass ONLY a primary canvas range and make it be the size that's needed for the entire graph that can scrolled into a window.
• canvas-center-x and canvas-center-y are integers that indicate the position that will be regarded as the logical center of the primary canvas, for such operations as moving the selected node to the center. When unspecified, they default to the actual center of the primary canvas.
• min-node-to-node-spacing is an integer indicating the minimum distance that will be maintained (when feasible) between nodes. When upspecified, it defaults to 12.
• min-link-to-node-spacing is an integer indicating the minimum distance that will be maintained between any link and any node to which it is not connected. When unspecified, it defaults to 12.
• max-iterations is the maximum number of times that all nodes will be potentially moved to better locations. Typically graph-layout will reach a stable state and return within a couple of dozen iterations. If max-iterations is reached before a stable state is reached, then graph-layout will stop iterating prematurely, though the current state that it leaves might still be usable. If explicitly passed as nil, it will default to 50.

Option Arguments

• work-from-current-layout indicates whether to begin moving nodes incrementally from their current positions, rather than beginning with all nodes in the center of the canvas. True is useful for moving from one state to another interactively in such a way that user may be able to follow nodes of interest to their new locations. nil typically creates a cleaner layout, though, by removing any bias in the nodes' current positions before beginning.
• spacing-increment-for-many-links is an integer indicating how much space to reserve from the center of a node for each link that it has beyond four links. Other nodes and links will avoid overlapping this extra space. This prevents another node from sitting close to a highly-linked node and blocking a large arc of angles from which other link lines could emanate.
• long-path-spacing-increment indicates how much additional space should be required between nodes when the shortest path between the two nodes is relatively long. This helps to keep separate branches farther apart so that it's easier to tell that they are distinct groups of nodes. It may also decrease the amount of tangling of unrelated branches of nodes. This feature may slow down the layout a little and makes it use up somewhat more space, but usually results in a cleaner layout. If long-path-spacing-increment is nil or zero, then nothing is done. Otherwise the specified value will be added to the required distance between a node and another node or link for each link in the shortest path between the two objects beyond the first num-links-before-extra-spacing links. For example, if num-links-before-extra-spacing is 4, long-path-spacing-increment is 15, and the shortest path between two nodes is 7 links long, then graph-layout will add (* 15 (- 7 4)) = 45 pixels to the usual min-node-to-node-spacing value to determine how far apart it will try to keep those two nodes.
• num-links-before-extra-spacing is the number of links in the shortest path between two nodes (or a node and a link) before the long-path-spacing-increment will be added for each additionl link, when long-path-spacing-increment is a positive number.
• long-path-max-spacing is the maximum additional pixel distance that will be required between two nodes whose connecting path is long. This is used only when long-path-spacing-increment is a positive integer. If long-path-max-spacing is nil, then no maximum is used.
• iterations-for-extra-spacing is the number of iterations at the beginning of a full layout (when work-from-current-layout is nil) during which long-path-max-spacing will be set to a higher number than the argument that was passed. The first iteration will set that parameter to a much larger value, and the increase will be reduced on successive iterations until it is the argument value after iterations-for-extra-spacing iterations. If this argument is nil or zero then long-path-max-spacing is not increased. A positive value here may get the layout off to a better start by initially keeping distantly-linked nodes farther from each other than they would otherwise be. This can result in fewer crossed branches of nodes.
• limit-outward-stretching, when true, will avoid moving nodes toward the edges of the canvas as much, to prevent stretching out the graph a lot more than necessary.
• consider-alternate-spots-by-linked-nodes indicates whether to consider alternate positions than the usual ones that extend from the linked nodes of a node that is being moved, on some iterations. When true, this may result in a better final layout, but may take longer or be less smooth for an interactive update. The special value :after-crossed-links, which considers alternate positions for a node only after an iteration where no spot was found for the node without crossed links, might be a good general compromise. It is the default.
• number-of-alternate-positions is the number of extra positions to each side of a linked node to consider, when consider-alternate-spots-by-linked-nodes is true.
• consider-additional-leaf-positions will look for places to move leaf nodes that extend orthoganally from each of the nodes that are linked with the single node to which the leaf node is linked; this takes longer but may result in a better graph.
• protect-tail-node-positions indicates whether nodes in a tail are allowed to maintain their current positions like any other node, rather than being moved to make room for more highly-connected nodes. True is better for interactive layouts, to reach a final state sooner, though nil may result in a better final graph.
• ignore-crossed-tails indicates whether to do nothing special about tail nodes whose links cross other links, perhaps needlessly, rather than making a special effort to uncross them. True is faster for interactive graphs, but it does not appear to take much time, so perhaps nil is always best for this argument.
• exclude-tail-nodes-from-home-positions might make a difference in the layout by not considering linked nodes that are in tails when calculating the ideal position to which to move a node.
• compress-layout-at-end indicates whether to pull some nodes in closer to the center of the graph after the layout has reached its otherwise final state. The layout tends to spread nodes throughout the available space on the primary canvas, as part of the algorithm for a good layout, and doesn't know when it is about to reach a stable state. Passing this argument as true executes an unrelated algorithm at the end to compress the nodes somewhat, though some arrangements of nodes toward the outside will not be pulled in at all. This option is purely a matter of preference.
• center-the-graph, if true, causes the entire graph (the block that encompasses all nodes) to be moved to the center of the canvas at the end of the layout. If the value is :after-each-iteration, then it is also centered after each iteration; this may improve the layout by maximizing the minimum amount of margin that's available on any side of the graph during the layout, but may make an animated layout jerk back and forth.

Copyright (c) 1998-2022, Franz Inc. Lafayette, CA., USA. All rights reserved.
This page was not revised from the 10.0 page.
Created 2019.8.20.