DragonFly On-Line Manual Pages
LIBPACK(3) DragonFly Library Functions Manual LIBPACK(3)
NAME
libpack - support for connected components
SYNOPSIS
#include <graphviz/pack.h>
typedef enum { l_clust, l_node, l_graph, l_array} pack_mode;
typedef struct {
float aspect; /* desired aspect ratio */
int sz; /* row/column size size */
unsigned int margin; /* margin left around objects, in points */
int doSplines; /* use splines in constructing graph shape */
pack_mode mode; /* granularity and method */
boolean *fixed; /* fixed[i] == true implies g[i] should not be moved */
packval_t* vals; /* for arrays, sort numbers */
int flags;
} pack_info;
point* putRects(int ng, boxf* bbs, pack_info* pinfo);
int packRects(int ng, boxf* bbs, pack_info* pinfo);
point* putGraphs (int, Agraph_t**, Agraph_t*, pack_info*);
int packGraphs (int, Agraph_t**, Agraph_t*, pack_info*);
int packSubgraphs (int, Agraph_t**, Agraph_t*, pack_info*);
pack_mode getPackMode (Agraph_t*, pack_mode dflt);
int getPack (Agraph_t*, int, int);
int isConnected (Agraph_t*);
Agraph_t** ccomps (Agraph_t*, int*, char*);
Agraph_t** pccomps (Agraph_t*, int*, char*, boolean*);
int nodeInduce (Agraph_t*);
DESCRIPTION
libpack supports the use of connected components in the context of
laying out graphs using other graphviz libraries. One set of functions
can be used to take a single graph and break it apart into connected
components. A complementary set of functions takes a collection of
graphs (not necessarily components of a single graph) which have been
laid out separately, and packs them together.
As this library is meant to be used with libcommon, it relies on the
Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t used in that library. The
specific dependencies are given below in the function descriptions.
Creating components
Agraph_t** ccomps (Agraph_t* g, int* cnt, char* pfx)
The function ccomps takes a graph g and returns an array of pointers to
subgraphs of g which are its connected components. cnt is set to the
number of components. If pfx is non-NULL, it is used as a prefix for
the names of the subgraphs; otherwise, the string ``_cc_'' is used.
Note that the subgraphs only contain the relevant nodes, not any
corresponding edges. Depending on the use, this allows the caller to
retrieve edge information from the root graph.
The array returned is obtained from malloc and must be freed by the
caller. The function relies on the mark field in Agnodeinfo_t.
Agraph_t** pccomps (Agraph_t* g, int* cnt, char* pfx, boolean* pinned)
This is identical to ccomps except that is puts all pinned nodes in the
first component returned. In addition, if pinned is non-NULL, it is set
to true if pinned nodes are found and false otherwise.
int nodeInduce (Agraph_t* g)
This function takes a subgraph g and finds all edges in its root graph
both of whose endpoints are in g. It returns the number of such edges
and, if this edge is not already in the subgraph, it is added.
int isConnected (Agraph_t* g)
This function returns non-zero if the graph g is connected.
Packing components
point* putGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info ip)
putGraphs packs together a collection of laid out graphs into a single
layout which avoids any overlap. It takes as input ng graphs gs. For
each graph, it is assumed that all the nodes have been positioned using
pos, and that the xsize and ysize fields have been set.
If root is non-NULL, it is taken as the root graph of the subgraphs gs
and is used to find the edges. Otherwise, putGraphs uses the edges
found in each graph gs[i].
For the modes l_node, l_clust, and l_graph, the packing is done using
the polyomino-based algorithm of Freivalds et al. This allows for a
fairly tight packing, in which a convex part of one graph might be
inserted into the concave part of another. The granularity of the
polyominoes used depends on the value of ip->mode. If this is l_node, a
polyomino is constructed to approximate the nodes and edges. If this is
l_clust, the polyomino treats top-level clusters as single rectangles,
unioned with the polyominoes for the remaining nodes and edges. If the
value is l_graph, the polyomino for a graph is a single rectangle
corresponding to the bounding box of the graph.
The mode l_node specifies that the graphs should be packed as an array.
If ip->doSplines is true, the function uses the spline information in
the spl field of an edge, if it exists. Otherwise, the algorithm
represents an edge as a straight line segment connecting node centers.
The parameter ip->margin specifies a boundary of margin points to be
allowed around each node. It must be non-negative.
The parameter ip->fixed, if non-null, should point to an array of ng
booleans. If ip->fixed[i] is true, graph gs[i] should be left at its
original position. The packing will first first place all of the fixed
graphs, then fill in the with the remaining graphs.
The function returns an array of points which can be used as the origin
of the bounding box of each graph. If the graphs are translated to
these positions, none of the graph components will overlap. The array
returned is obtained from malloc and must be freed by the caller. If
any problem occurs, putGraphs returns NULL. As a side-effect, at its
start, putGraphs sets the bb of each graph to reflect its initial
layout. Note that putGraphs does not do any translation or change the
input graphs in any other way than setting the bb.
This function uses the bb field in Agraphinfo_t, the pos, xsize and
ysize fields in nodehinfo_t and the spl field in Aedgeinfo_t.
int packGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)
This function takes ng subgraphs gs of a root graph root and calls
putGraphs with the given arguments to generate a packing of the
subgraphs. If successful, it then invokes shifts the subgraphs to their
new positions. It returns 0 on success.
int packSubgraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)
This function simply calls packGraphs with the given arguments, and
then recomputes the bounding box of the root graph.
int pack_graph(int ng, Agraph_t** gs, Agraph_t* root, boolean* fixed)
uses packSubgraphs to place the individual subgraphs into a single
layout with the parameters obtained from getPackInfo. If successful,
dotneato_postprocess is called on the root graph.
point* putRects (int ng, boxf* bbs, pack_info* ip)
putRects packs together a collection of rectangles into a single layout
which avoids any overlap. It takes as input ng rectangles bbs.
Its behavior and return value are analogous to those of putGraphs.
However, the modes l_node and l_clust are illegal. The fields fixed
and doSplines of ip are unused.
int packRects (int ng, boxf* bbs, pack_info* ip)
packRects is analogous to packGraphs: it calls putRects and, if this is
successful, it translates the rectangles in bbs appropriately.
Utility functions
The library provides several functions which can be used to tailor the
packing based on graph attributes.
pack_mode parsePackModeInfo(char* p, pack_mode dflt, pack_info* pinfo)
analyzes p as a string representation of pack mode, storing the
information in pinfo. If p is "cluster", it returns l_clust; for
"graph", it returns l_graph; for "node", it returns l_node; for
"array", it returns l_array; for "aspect", it returns l_aspect;
otherwise, it returns dflt. Related data is also stored in pinfo.
pack_mode getPackModeInfo(Agraph_t * g, pack_mode dflt, pack_info* pinfo)
This function processes the graph's "packmode" attribute, storing the
information in pinfo. It returns pinfo->mode. The attribute is
processed using parsePackModeInfo with dflt passed as the default
argument.
pack_mode getPackMode (Agraph_t* g, pack_mode dflt)
This function returns a pack_mode associated with g.
int getPack (Agraph_t* g, int not_def, int dflt)
This function queries the graph attribute "pack". If this is defined as
a non-negative integer, the integer is returned; if it is defined as
"true", the value dflt is returned; otherwise, the value not_def is
returned.
pack_mode getPackInfo(Agraph_t * g, pack_mode dflt, int dfltMargin,
pack_info* pinfo)
This function calls both getPackModeInfo and getPack, storing the
information in pinfo. dfltMargin is used for both integer arguments of
getPack, with the result saved as pinfo->margin. It returns
pinfo->mode.
SEE ALSO
dot(1), neato(1), twopi(1), libgraph(3)
K. Freivalds et al., "Disconnected Graph Layout and the Polyomino
Packing Approach", GD0'01, LNCS 2265, pp. 378-391.
BUGS
The packing does not take into account edge or graph labels.
AUTHORS
Emden Gansner (erg@research.att.com).
04 APRIL 2009 LIBPACK(3)
pack-old(n) Tk Built-In Commands pack-old(n)
______________________________________________________________________________
NAME
pack-old - Obsolete syntax for packer geometry manager
SYNOPSIS
pack after sibling window options ?window options ...?
pack append parent window options ?window options ...?
pack before sibling window options ?window options ...?
pack unpack window
______________________________________________________________________________
DESCRIPTION
Note: this manual entry describes the syntax for the pack command as it
existed before Tk version 3.3. Although this syntax continues to be
supported for backward compatibility, it is obsolete and should not be
used anymore. At some point in the future it may cease to be
supported.
The packer is a geometry manager that arranges the children of a parent
by packing them in order around the edges of the parent. The first
child is placed against one side of the window, occupying the entire
span of the window along that side. This reduces the space remaining
for other children as if the side had been moved in by the size of the
first child. Then the next child is placed against one side of the
remaining cavity, and so on until all children have been placed or
there is no space left in the cavity.
The before, after, and append forms of the pack command are used to
insert one or more children into the packing order for their parent.
The before form inserts the children before window sibling in the
order; all of the other windows must be siblings of sibling. The
after form inserts the windows after sibling, and the append form
appends one or more windows to the end of the packing order for parent.
If a window named in any of these commands is already packed in its
parent, it is removed from its current position in the packing order
and repositioned as indicated by the command. All of these commands
return an empty string as result.
The unpack form of the pack command removes window from the packing
order of its parent and unmaps it. After the execution of this command
the packer will no longer manage window's geometry.
The placement of each child is actually a four-step process; the
options argument following each window consists of a list of one or
more fields that govern the placement of that window. In the
discussion below, the term cavity refers to the space left in a parent
when a particular child is placed (i.e. all the space that was not
claimed by earlier children in the packing order). The term parcel
refers to the space allocated to a particular child; this is not
necessarily the same as the child window's final geometry.
The first step in placing a child is to determine which side of the
cavity it will lie against. Any one of the following options may be
used to specify a side:
top Position the child's parcel against the top of the cavity,
occupying the full width of the cavity.
bottom Position the child's parcel against the bottom of the cavity,
occupying the full width of the cavity.
left Position the child's parcel against the left side of the cavity,
occupying the full height of the cavity.
right Position the child's parcel against the right side of the
cavity, occupying the full height of the cavity.
At most one of these options should be specified for any given window.
If no side is specified, then the default is top.
The second step is to decide on a parcel for the child. For top and
bottom windows, the desired parcel width is normally the cavity width
and the desired parcel height is the window's requested height, as
passed to Tk_GeometryRequest. For left and right windows, the desired
parcel height is normally the cavity height and the desired width is
the window's requested width. However, extra space may be requested
for the window using any of the following options:
padx num Add num pixels to the window's requested width before
computing the parcel size as described above.
pady num Add num pixels to the window's requested height before
computing the parcel size as described above.
expand This option requests that the window's parcel absorb any
extra space left over in the parent's cavity after packing
all the children. The amount of space left over depends on
the sizes requested by the other children, and may be zero.
If several windows have all specified expand then the extra
width will be divided equally among all the left and right
windows that specified expand and the extra height will be
divided equally among all the top and bottom windows that
specified expand.
If the desired width or height for a parcel is larger than the
corresponding dimension of the cavity, then the cavity's dimension is
used instead.
The third step in placing the window is to decide on the window's width
and height. The default is for the window to receive either its
requested width and height or the those of the parcel, whichever is
smaller. If the parcel is larger than the window's requested size,
then the following options may be used to expand the window to
partially or completely fill the parcel:
fill Set the window's size to equal the parcel size.
fillx Increase the window's width to equal the parcel's width, but
retain the window's requested height.
filly Increase the window's height to equal the parcel's height, but
retain the window's requested width.
The last step is to decide the window's location within its parcel. If
the window's size equals the parcel's size, then the window simply
fills the entire parcel. If the parcel is larger than the window, then
one of the following options may be used to specify where the window
should be positioned within its parcel:
frame center Center the window in its parcel. This is the default if
no framing option is specified.
frame n Position the window with its top edge centered on the
top edge of the parcel.
frame ne Position the window with its upper-right corner at the
upper-right corner of the parcel.
frame e Position the window with its right edge centered on the
right edge of the parcel.
frame se Position the window with its lower-right corner at the
lower-right corner of the parcel.
frame s Position the window with its bottom edge centered on the
bottom edge of the parcel.
frame sw Position the window with its lower-left corner at the
lower-left corner of the parcel.
frame w Position the window with its left edge centered on the
left edge of the parcel.
frame nw Position the window with its upper-left corner at the
upper-left corner of the parcel.
The packer manages the mapped/unmapped state of all the packed children
windows. It automatically maps the windows when it packs them, and it
unmaps any windows for which there was no space left in the cavity.
The packer makes geometry requests on behalf of the parent windows it
manages. For each parent window it requests a size large enough to
accommodate all the options specified by all the packed children, such
that zero space would be leftover for expand options.
KEYWORDS
geometry manager, location, packer, parcel, size
Tk 4.0 pack-old(n)