1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
.TH LIBPACK 3 "01 MAY 2002"
.SH NAME
\fBlibpack\fR \- support for connected components
.SH SYNOPSIS
.ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i
.PP
.nf
\f5
#include <graphviz/pack.h>
typedef enum { l_clust, l_node, l_graph} pack_mode;
typedef struct {
unsigned int margin;
boolean doSplines;
pack_mode mode;
boolean* fixed;
} pack_info;
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*);
\fP
.fi
.SH DESCRIPTION
\fIlibpack\fP supports the use of connected components in the
context of laying out graphs using other \fIgraphviz\fP 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 moderately tightly. The packing is done using the polyomino
algorithm of K. Freivalds et al.
As this library is meant to be used with \fIlibcommon\fP, it relies
on the \fIAgraphinfo_t\fP, \fIAgnodeinfo_t\fP and \fIAgedgeinfo_t\fP used
in that
library. The specific dependencies are given below in the function
descriptions.
.SS "Creating components"
.PP
.SS " Agraph_t** ccomps (Agraph_t* g, int* cnt, char* pfx)"
The function \fIccomps\fP takes a graph \fIg\fP and returns an array
of pointers to subgraphs of \fIg\fP which are its connected components.
\fIcnt\fP is set to the number of components. If \fIpfx\fP 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.
.PP
The array returned is obtained from \fImalloc\fP and must be freed by
the caller. The function relies on the \fImark\fP field in
\fIAgnodeinfo_t\fP.
.PP
.SS " Agraph_t** pccomps (Agraph_t* g, int* cnt, char* pfx, boolean* pinned)"
This is identical to \fIccomps\fP except that is puts all pinned nodes
in the first component returned. In addition, if \fIpinned\fP is non-NULL,
it is set to true if pinned nodes are found and false otherwise.
.PP
.SS " int nodeInduce (Agraph_t* g)"
This function takes a subgraph \fIg\fP and finds all edges in its root
graph both of whose endpoints are in \fIg\fP. It returns the number of
such edges and, if this edge is not already
in the subgraph, it is added.
.PP
.SS " int isConnected (Agraph_t* g)"
This function returns non-zero if the graph \fIg\fP is connected.
.SS "Packing components"
.PP
.SS " point* putGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info ip)"
\fIputGraphs\fP packs together a collection of laid out graphs into a
single layout which avoids any overlap. It takes as input \fIng\fP
graphs \fIgs\fP. For each graph, it is assumed that all the nodes have
been positioned using \fIpos\fP, and that the \fIxsize\fP and \fIysize\fP
fields have been set.
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.
.PP
If \fIroot\fP is non-NULL, it is taken as the root
graph of the subgraphs \fIgs\fP and is used to find the edges. Otherwise,
\fIputGraphs\fP uses the edges found in each graph \fIgs[i]\fP.
.PP
The granularity of the polyominoes used depends on the value of
\fIip->mode\fP. If this is \fIl_node\fP, a polyomino is constructed
to approximate the nodes and edges. If this is \fIl_clust\fP, the
polyomino treats top-level clusters as single rectangles, unioned
with the polyominoes for the remaining nodes and edges. If the value
is \fIl_graph\fP, the polyomino for a graph is a single rectangle
corresponding to the bounding box of the graph.
.PP
If \fIip->doSplines\fP is true, the function uses the spline information
in the \fIspl\fP field of an edge, if it exists.
Otherwise, the algorithm represents an edge as a
straight line segment connecting node centers.
.PP
The parameter \fIip->margin\fP specifies a boundary of \fImargin\fP points
to be allowed around each node. It must be non-negative.
.PP
The parameter \fIip->fixed\fP, if non-null, should point to an array
of \fIng\fP booleans. If \fIip->fixed[i]\fP is true, graph \fIgs[i]\fP
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.
.PP
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 \fImalloc\fP and must be freed by
the caller. If any problem occurs, \fIputGraphs\fP returns NULL.
As a side-effect, at its start, \fIputGraphs\fP sets the \fIbb\fP
of each graph to reflect its initial layout. Note that \fIputGraphs\fP
does not do any translation or change the input graphs in any other way
than setting the \fIbb\fP.
.PP
This function uses the \fIbb\fP field in \fIAgraphinfo_t\fP,
the \fIpos\fP, \fIxsize\fP and \fIysize\fP fields in \fInodehinfo_t\fP and
the \fIspl\fP field in \fIAedgeinfo_t\fP.
.PP
.SS " int packGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)"
This function takes \fIng\fP subgraphs \fIgs\fP of a root graph \fIroot\fP
and calls \fIputGraphs\fP with the given arguments to generate
a packing of the subgraphs. If successful, it then invokes
\fIshiftGraphs\fP to apply the new positions. It returns 0 on success.
.PP
.SS " int packSubgraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* ip)"
This function simply calls \fIpackGraphs\fP with the given arguments, and
then recomputes the bounding box of the \fIroot\fP graph.
.SS "Utility functions"
The library provides several functions which can be used to tailor the
packing based on graph attributes.
.SS " pack_mode getPackMode (Agraph_t* g, pack_mode dflt)"
This function returns a \fIpack_mode\fP associated with \fIg\fP.
If the graph attribute \fI"packmode"\fP is "cluster", it returns
\fIl_clust\fP; for "graph", it returns \fIl_graph\fP;
for "node", it returns \fIl_node\fP;
otherwise, it returns \fIdflt\fP.
.SS " int getPack (Agraph_t* g, int not_def, int dflt)"
This function queries the graph attribute \fI"pack"\fP. If this is
defined as a non-negative integer, the integer is returned; if it
is defined as "true", the value \fIdflt\fP is returned; otherwise,
the value \fInot_def\fP is returned.
.SH SEE ALSO
.BR dot (1),
.BR neato (1),
.BR twopi (1),
.BR libgraph (3)
.br
K. Freivalds et al., "Disconnected Graph Layout and the Polyomino
Packing Approach", GD0'01, LNCS 2265, pp. 378-391.
.SH "BUGS"
The packing does not take into account edge or graph labels.
.SH AUTHORS
Emden Gansner (erg@research.att.com).
|
