|
wolffd@0
|
1 .TH CCOMPS 1 "27 August 2008"
|
|
wolffd@0
|
2 .SH NAME
|
|
wolffd@0
|
3 ccomps \- connected components filter for graphs
|
|
wolffd@0
|
4 .SH SYNOPSIS
|
|
wolffd@0
|
5 .B ccomps
|
|
wolffd@0
|
6 [
|
|
wolffd@0
|
7 .B \-sxvnzC?
|
|
wolffd@0
|
8 ]
|
|
wolffd@0
|
9 [
|
|
wolffd@0
|
10 .BI -X [#]v
|
|
wolffd@0
|
11 ]
|
|
wolffd@0
|
12 [
|
|
wolffd@0
|
13 .BI -o outfile
|
|
wolffd@0
|
14 ]
|
|
wolffd@0
|
15 [
|
|
wolffd@0
|
16 .I files
|
|
wolffd@0
|
17 ]
|
|
wolffd@0
|
18 .SH DESCRIPTION
|
|
wolffd@0
|
19 .B ccomps
|
|
wolffd@0
|
20 decomposes graphs into their connected components,
|
|
wolffd@0
|
21 printing the components to standard output.
|
|
wolffd@0
|
22 .SH OPTIONS
|
|
wolffd@0
|
23 The following options are supported:
|
|
wolffd@0
|
24 .TP
|
|
wolffd@0
|
25 .B \-s
|
|
wolffd@0
|
26 No output graph is printed. The return value can be used to
|
|
wolffd@0
|
27 check if the graph is connected or not.
|
|
wolffd@0
|
28 .TP
|
|
wolffd@0
|
29 .B \-x
|
|
wolffd@0
|
30 Only the connected components are printed, as separate graphs.
|
|
wolffd@0
|
31 .TP
|
|
wolffd@0
|
32 .B \-v
|
|
wolffd@0
|
33 Counts of nodes, edges and connected components are printed.
|
|
wolffd@0
|
34 .TP
|
|
wolffd@0
|
35 .B \-z
|
|
wolffd@0
|
36 Sort components by size, with the largest first. This is only
|
|
wolffd@0
|
37 effective if either \fB-x\fP or \fB-X#v\fP is present.
|
|
wolffd@0
|
38 Thus, \fB-zX#0\fP will cause the largest component to be printed.
|
|
wolffd@0
|
39 .TP
|
|
wolffd@0
|
40 .B \-C
|
|
wolffd@0
|
41 Use clusters in computing components in addition to normal edge
|
|
wolffd@0
|
42 connectivity. In essence, this gives the connected components of the
|
|
wolffd@0
|
43 derived graph in which nodes top-level clusters and nodes in the
|
|
wolffd@0
|
44 original graph. This maintains all subgraph structure within a
|
|
wolffd@0
|
45 component, even if a subgraph does not contain any nodes.
|
|
wolffd@0
|
46 .TP
|
|
wolffd@0
|
47 .B \-n
|
|
wolffd@0
|
48 Do not project subgraph structure. Normally, if
|
|
wolffd@0
|
49 .B ccomps
|
|
wolffd@0
|
50 produces components as graphs distinct from the input graph, it will
|
|
wolffd@0
|
51 define subgraphs which are projections of subgraphs of the input graph
|
|
wolffd@0
|
52 onto the component. (If the projection is empty, no subgraph is produced.)
|
|
wolffd@0
|
53 If this flag is set, the component contains only the relevant nodes and
|
|
wolffd@0
|
54 edges.
|
|
wolffd@0
|
55 .TP
|
|
wolffd@0
|
56 .BI \-X " node_name"
|
|
wolffd@0
|
57 Prints only the component containing the node \fInode_name\fP,
|
|
wolffd@0
|
58 if any.
|
|
wolffd@0
|
59 .TP
|
|
wolffd@0
|
60 .BI \-X# " index"
|
|
wolffd@0
|
61 Prints only component number \fIindex\fP, if any, starting at 0.
|
|
wolffd@0
|
62 .TP
|
|
wolffd@0
|
63 .BI \-o " outfile"
|
|
wolffd@0
|
64 If specified, each graph will be written to a different file
|
|
wolffd@0
|
65 with the names derived from \fIoutfile\fP. In particular,
|
|
wolffd@0
|
66 if both \fB-o\fP and \fB-x\fP flags are used, then each connected
|
|
wolffd@0
|
67 component is written to a different file. If \fIoutfile\fP does
|
|
wolffd@0
|
68 not have a suffix, the first file will have the name \fIoutfile\fP;
|
|
wolffd@0
|
69 then next \fIoutfile_1\fP, then next \fIoutfile_2\fP, and so on.
|
|
wolffd@0
|
70 If \fIoutfile\fP has a suffix, i.e., has the form \fIbase.sfx\fP,
|
|
wolffd@0
|
71 then the files will be named \fIbase.sfx\fP, \fIbase_1.sfx\fP,
|
|
wolffd@0
|
72 \fIbase_2.sfx\fP, etc.
|
|
wolffd@0
|
73 .LP
|
|
wolffd@0
|
74 By default, each input graph is printed, with each connected
|
|
wolffd@0
|
75 component given as a subgraph whose name is a concatenation of
|
|
wolffd@0
|
76 the name of the input graph, the string "_component_" and the
|
|
wolffd@0
|
77 number of the component.
|
|
wolffd@0
|
78 .SH OPERANDS
|
|
wolffd@0
|
79 The following operand is supported:
|
|
wolffd@0
|
80 .TP 8
|
|
wolffd@0
|
81 .I files
|
|
wolffd@0
|
82 Names of files containing 1 or more graphs in dot format.
|
|
wolffd@0
|
83 If no
|
|
wolffd@0
|
84 .I files
|
|
wolffd@0
|
85 operand is specified,
|
|
wolffd@0
|
86 the standard input will be used.
|
|
wolffd@0
|
87 .SH RETURN CODES
|
|
wolffd@0
|
88 Unless used to extract a single connected component,
|
|
wolffd@0
|
89 .B ccomps
|
|
wolffd@0
|
90 returns
|
|
wolffd@0
|
91 .B 0
|
|
wolffd@0
|
92 if all the input graphs are connected; and
|
|
wolffd@0
|
93 non-zero if any graph has multiple components, or any error occurred.
|
|
wolffd@0
|
94 If just extracting a single component,
|
|
wolffd@0
|
95 .B ccomps
|
|
wolffd@0
|
96 returns
|
|
wolffd@0
|
97 .B 0
|
|
wolffd@0
|
98 on success and non-zero if an error occurred.
|
|
wolffd@0
|
99 .SH "BUGS"
|
|
wolffd@0
|
100 It is possible, though unlikely, that the names used for connected
|
|
wolffd@0
|
101 components and their subgraphs may conflict with existing subgraph names.
|
|
wolffd@0
|
102 .SH AUTHORS
|
|
wolffd@0
|
103 Stephen C. North <north@research.att.com>
|
|
wolffd@0
|
104 .br
|
|
wolffd@0
|
105 Emden R. Gansner <erg@research.att.com>
|
|
wolffd@0
|
106 .SH "SEE ALSO"
|
|
wolffd@0
|
107 gc(1), dot(1), gvpr(1), gvcolor(1), acyclic(1), sccmap(1), tred(1), libgraph(3)
|
