1LIBPACK(3) Library Functions Manual LIBPACK(3)
2
6 libpack - support for connected components
7
9 #include <graphviz/pack.h>
10 typedef enum { l_clust, l_node, l_graph, l_array} pack_mode;
12 typedef struct {
14 float aspect; /* desired aspect ratio */
15 int sz; /* row/column size size */
16 unsigned int margin; /* margin left around objects, in points */
17 int doSplines; /* use splines in constructing graph shape */
18 pack_mode mode; /* granularity and method */
19 boolean *fixed; /* fixed[i] == true implies g[i] should not be moved */
20 packval_t* vals; /* for arrays, sort numbers */
21 int flags;
22 } pack_info;
23 point* putRects(int ng, boxf* bbs, pack_info* pinfo);
25 int packRects(int ng, boxf* bbs, pack_info* pinfo);
26 point* putGraphs (int, Agraph_t**, Agraph_t*, pack_info*);
28 int packGraphs (int, Agraph_t**, Agraph_t*, pack_info*);
29 int packSubgraphs (int, Agraph_t**, Agraph_t*, pack_info*);
30 pack_mode getPackMode (Agraph_t*, pack_mode dflt);
32 int getPack (Agraph_t*, int, int);
33 int isConnected (Agraph_t*);
35 Agraph_t** ccomps (Agraph_t*, int*, char*);
36 Agraph_t** pccomps (Agraph_t*, int*, char*, boolean*);
37 int nodeInduce (Agraph_t*);
38
41 libpack supports the use of connected components in the context of lay‐
42 ing out graphs using other graphviz libraries. One set of functions
43 can be used to take a single graph and break it apart into connected
44 components. A complementary set of functions takes a collection of
45 graphs (not necessarily components of a single graph) which have been
46 laid out separately, and packs them together.
47 As this library is meant to be used with libcommon, it relies on the
49 Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t used in that library. The
50 specific dependencies are given below in the function descriptions.
51 Creating components
54 Agraph_t** ccomps (Agraph_t* g, int* cnt, char* pfx)
55 The function ccomps takes a graph g and returns an array of pointers to
56 subgraphs of g which are its connected components. cnt is set to the
57 number of components. If pfx is non-NULL, it is used as a prefix for
58 the names of the subgraphs; otherwise, the string ``_cc_'' is used.
59 Note that the subgraphs only contain the relevant nodes, not any corre‐
60 sponding edges. Depending on the use, this allows the caller to
61 retrieve edge information from the root graph.
62 The array returned is obtained from malloc and must be freed by the
64 caller. The function relies on the mark field in Agnodeinfo_t.
65 Agraph_t** pccomps (Agraph_t* g, int* cnt, char* pfx, boolean* pinned)
67 This is identical to ccomps except that is puts all pinned nodes in the
68 first component returned. In addition, if pinned is non-NULL, it is set
69 to true if pinned nodes are found and false otherwise.
70 int nodeInduce (Agraph_t* g)
72 This function takes a subgraph g and finds all edges in its root graph
73 both of whose endpoints are in g. It returns the number of such edges
74 and, if this edge is not already in the subgraph, it is added.
75 int isConnected (Agraph_t* g)
77 This function returns non-zero if the graph g is connected.
78 Packing components
81 point* putGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info ip)
82 putGraphs packs together a collection of laid out graphs into a single
83 layout which avoids any overlap. It takes as input ng graphs gs. For
84 each graph, it is assumed that all the nodes have been positioned using
85 pos, and that the xsize and ysize fields have been set.
86 If root is non-NULL, it is taken as the root graph of the subgraphs gs
88 and is used to find the edges. Otherwise, putGraphs uses the edges
89 found in each graph gs[i].
90 For the modes l_node, l_clust, and l_graph, the packing is done using
92 the polyomino-based algorithm of Freivalds et al. This allows for a
93 fairly tight packing, in which a convex part of one graph might be
94 inserted into the concave part of another. The granularity of the
95 polyominoes used depends on the value of ip->mode. If this is l_node, a
96 polyomino is constructed to approximate the nodes and edges. If this is
97 l_clust, the polyomino treats top-level clusters as single rectangles,
98 unioned with the polyominoes for the remaining nodes and edges. If the
99 value is l_graph, the polyomino for a graph is a single rectangle cor‐
100 responding to the bounding box of the graph.
101 The mode l_node specifies that the graphs should be packed as an array.
103 If ip->doSplines is true, the function uses the spline information in
105 the spl field of an edge, if it exists. Otherwise, the algorithm rep‐
106 resents an edge as a straight line segment connecting node centers.
107 The parameter ip->margin specifies a boundary of margin points to be
109 allowed around each node. It must be non-negative.
110 The parameter ip->fixed, if non-null, should point to an array of ng
112 booleans. If ip->fixed[i] is true, graph gs[i] should be left at its
113 original position. The packing will first first place all of the fixed
114 graphs, then fill in the with the remaining graphs.
115 The function returns an array of points which can be used as the origin
117 of the bounding box of each graph. If the graphs are translated to
118 these positions, none of the graph components will overlap. The array
119 returned is obtained from malloc and must be freed by the caller. If
120 any problem occurs, putGraphs returns NULL. As a side-effect, at its
121 start, putGraphs sets the bb of each graph to reflect its initial lay‐
122 out. Note that putGraphs does not do any translation or change the
123 input graphs in any other way than setting the bb.
124 This function uses the bb field in Agraphinfo_t, the pos, xsize and
126 ysize fields in nodehinfo_t and the spl field in Aedgeinfo_t.
127 int packGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)
129 This function takes ng subgraphs gs of a root graph root and calls put‐
130 Graphs with the given arguments to generate a packing of the subgraphs.
131 If successful, it then invokes shifts the subgraphs to their new posi‐
132 tions. It returns 0 on success.
133 int packSubgraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)
135 This function simply calls packGraphs with the given arguments, and
136 then recomputes the bounding box of the root graph.
137 int pack_graph(int ng, Agraph_t** gs, Agraph_t* root, boolean* fixed)
139 uses packSubgraphs to place the individual subgraphs into a single lay‐
140 out with the parameters obtained from getPackInfo. If successful, dot‐
141 neato_postprocess is called on the root graph.
142 point* putRects (int ng, boxf* bbs, pack_info* ip)
144 putRects packs together a collection of rectangles into a single layout
145 which avoids any overlap. It takes as input ng rectangles bbs.
146 Its behavior and return value are analogous to those of putGraphs.
148 However, the modes l_node and l_clust are illegal. The fields fixed
149 and doSplines of ip are unused.
150 int packRects (int ng, boxf* bbs, pack_info* ip)
152 packRects is analogous to packGraphs: it calls putRects and, if this is
153 successful, it translates the rectangles in bbs appropriately.
154 Utility functions
156 The library provides several functions which can be used to tailor the
157 packing based on graph attributes.
158 pack_mode parsePackModeInfo(char* p, pack_mode dflt, pack_info* pinfo)
160 analyzes p as a string representation of pack mode, storing the infor‐
161 mation in pinfo. If p is "cluster", it returns l_clust; for "graph",
162 it returns l_graph; for "node", it returns l_node; for "array", it
163 returns l_array; for "aspect", it returns l_aspect; otherwise, it
164 returns dflt. Related data is also stored in pinfo.
165 pack_mode getPackModeInfo(Agraph_t * g, pack_mode dflt, pack_info* pinfo)
167 This function processes the graph's "packmode" attribute, storing the
168 information in pinfo. It returns pinfo->mode. The attribute is pro‐
169 cessed using parsePackModeInfo with dflt passed as the default argu‐
170 ment.
171 pack_mode getPackMode (Agraph_t* g, pack_mode dflt)
173 This function returns a pack_mode associated with g.
174 int getPack (Agraph_t* g, int not_def, int dflt)
176 This function queries the graph attribute "pack". If this is defined as
177 a non-negative integer, the integer is returned; if it is defined as
178 "true", the value dflt is returned; otherwise, the value not_def is
179 returned.
180 pack_mode getPackInfo(Agraph_t * g, pack_mode dflt, int dfltMargin,
182 pack_info* pinfo)
183 This function calls both getPackModeInfo and getPack, storing the
184 information in pinfo. dfltMargin is used for both integer arguments of
185 getPack, with the result saved as pinfo->margin. It returns
186 pinfo->mode.
187
189 dot(1), neato(1), twopi(1), libgraph(3)
190 K. Freivalds et al., "Disconnected Graph Layout and the Polyomino Pack‐
191 ing Approach", GD0'01, LNCS 2265, pp. 378-391.
192
195 The packing does not take into account edge or graph labels.
196
198 Emden Gansner (erg@research.att.com).
199 04 APRIL 2009 LIBPACK(3)