|Allegro CL version 10.1|
Unrevised from 10.0 to 10.1.
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)
nil indicating whether the layout succeeded
(see just below), (2) the number of iterations that were done, and
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.
The many arguments to this function are grouped into four categories: Main, Accessor Function, Miscellaneous, and Option.
nilif 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.
nilif 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.
nilif 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.
nil, then the selected-node (if any) will stay fixed at its current position.
nilif 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
nilfor a particular link if that link is allowed to point in any direction. Otherwise it should return one of the keyword symbols
:rightwardto 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
:upwardreally means "more upward than downward" and the link line could, for example, point East by Northeast.
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.
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.
nilfor no pause, or a positive number indicating the number of seconds to pause. This simply calls sleep.
nilto 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.
nil, it will default to 50.
niltypically creates a cleaner layout, though, by removing any bias in the nodes' current positions before beginning.
nilor 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.
nil, then no maximum is used.
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
nilor 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.
: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.
nilmay result in a better final graph.
nilis always best for this argument.
: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-2017, Franz Inc. Oakland, CA., USA. All rights reserved.
This page was not revised from the 10.0 page.
|Allegro CL version 10.1|
Unrevised from 10.0 to 10.1.