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 🦋

ok so libpack is the bestie that handles connected components while you're out here laying out graphs with the other graphviz libraries. it does two main-character jobs:

• it can grab one single graph and break it apart into its connected components 🔨
• and it can take a whole collection of graphs (not even necessarily components of the same graph, no cap) that have already been laid out separately, and pack them all together 🎀

and because this library is meant to hang out with libcommon, it lowkey relies on the Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t used over there. the exact dependency tea is spilled below in each function's description, iykyk 💅

---

🌱 Creating components 🌱

Agraph_t** ccomps (Agraph_t* g, int* cnt, char* pfx)

ccomps takes a graph g and hands you back an array of pointers to subgraphs of g which are its connected components. cnt gets set to the number of components. if pfx is non-NULL, it's used as a prefix for the names of the subgraphs; otherwise the string "_cc_" is used. ⚠️ heads up bestie: those subgraphs only contain the relevant nodes, not any corresponding edges. depending on what you're doing, that actually lets the caller go pull edge info from the root graph. slay.

the array returned is obtained from malloc and must be freed by the caller 🫶. this function relies on the mark field in Agnodeinfo_t.

Agraph_t** pccomps (Agraph_t* g, int* cnt, char* pfx, boolean* pinned)

literally identical to ccomps, except it puts all pinned nodes in the first component returned. also, if pinned is non-NULL, it gets set to true if pinned nodes are found and false otherwise. 💖

int nodeInduce (Agraph_t* g)

takes a subgraph g and finds all the edges in its root graph where both endpoints are in g. it returns the number of such edges, and if an edge isn't already in the subgraph, it gets added. periodt. ✨

int isConnected (Agraph_t* g)

returns non-zero if the graph g is connected. that's it, that's the function. 🌈

---

🎀 Packing components 🎀

point* putGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info ip)

putGraphs packs a collection of already-laid-out graphs into a single layout that avoids any overlap. it takes as input ng graphs gs. for each graph, it's 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's 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, where a convex part of one graph might get inserted into the concave part of another. the granularity of the polyominoes used depends on the value of ip->mode:

• if it's l_node, a polyomino is constructed to approximate the nodes and edges.
• if it's 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)

takes ng subgraphs gs of a root graph root and calls putGraphs with the given arguments to generate a packing of the subgraphs. if that works out, it then invokes shifts the subgraphs to their new positions. returns 0 on success. ✨

int packSubgraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)

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 a collection of rectangles into a single layout that 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 that's successful, it translates the rectangles in bbs appropriately. 🫶

---

🧚 Utility functions 🧚

the library provides several functions you can use to tailor the packing based on graph attributes. cute, right?

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. here's the vibe check on the return values:

• 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)

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)

returns a pack_mode associated with g. simple as that. 💖

int getPack (Agraph_t* g, int not_def, int dflt)

queries the graph attribute "pack". if it's defined as a non-negative integer, the integer is returned; if it's 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)

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), cgraph(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. bestie... it just doesn't. no cap. 😭

---

👑 AUTHORS 👑

Emden Gansner (erg@research.att.com). thank you emden, we love you fr fr 🫶

---

and that's the whole page babes!! this one's from the Library Functions Manual, LIBPACK(3), dated 04 APRIL 2009 — go forth and pack those components, you absolute icon 💅✨