| Allegro CL version 8.2 This page is new in 8.2. |
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.
The many arguments to this function are grouped into four categories: Main, Accessor Function, Miscellaneous, and Option.
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.
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.
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.
nil
, then
the selected-node (if any) will stay fixed at its
current position.
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.
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.
nil
for no pause, or a positive number
indicating the number of seconds to pause. This simply
calls sleep.
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.
nil
, it will default to
50.
nil
typically creates a
cleaner layout, though, by removing any bias in the nodes' current
positions before beginning.
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.
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 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.
: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.
nil
may result in a better final
graph.
nil
is 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-2016, Franz Inc. Oakland, CA., USA. All rights reserved.
This page is new in the 8.2 release.
Created 2016.6.21.
| Allegro CL version 8.2 This page is new in 8.2. |