component.dist | R Documentation |
component.dist
returns a list containing a vector of length n
such that the i
th element contains the number of components of graph G having size i
, and a vector of length n
giving component membership (where n
is the graph order). Component strength is determined by the connected
parameter; see below for details.
component.largest
identifies the component(s) of maximum order within graph G
. It returns either a logical
vector indicating membership in a maximum component or the adjacency matrix of the subgraph of G induced by the maximum component(s), as determined by result
. Component strength is determined as per component.dist
.
component.dist(dat, connected=c("strong","weak","unilateral", "recursive")) component.largest(dat, connected=c("strong","weak","unilateral", "recursive"), result = c("membership", "graph"), return.as.edgelist = FALSE)
dat |
one or more input graphs. |
connected |
a string selecting strong, weak, unilateral or recursively connected components; by default, |
result |
a string indicating whether a vector of membership indicators or the induced subgraph of the component should be returned. |
return.as.edgelist |
logical; if |
Components are maximal sets of mutually connected vertices; depending on the definition of “connected” one employs, one can arrive at several types of components. Those supported here are as follows (in increasing order of restrictiveness):
weak
: v_1 is connected to v_2 iff there exists a semi-path from v_1 to v_2 (i.e., a path in the weakly symmetrized graph)
unilateral
: v_1 is connected to v_2 iff there exists a directed path from v_1 to v_2 or a directed path from v_2 to v_1
strong
: v_1 is connected to v_2 iff there exists a directed path from v_1 to v_2 and a directed path from v_2 to v_1
recursive
: v_1 is connected to v_2 iff there exists a vertex sequence v_a,...,v_z such that v_1,v_a,...,v_z,v_2 and v_2,v_z,...,v_a,v_1 are directed paths
Note that the above definitions are distinct for directed graphs only; if dat
is symmetric, then the connected
parameter has no effect.
For component.dist
, a list containing:
membership |
A vector of component memberships, by vertex |
csize |
A vector of component sizes, by component |
cdist |
A vector of length |V(G)| with the (unnormalized) empirical distribution function of component sizes |
If multiple input graphs are given, the return value is a list of lists.
For component.largest
, either a logical
vector of component membership indicators or the adjacency matrix/edgelist of the subgraph induced by the largest component(s) is returned. If multiple graphs were given as input, a list of results is returned.
Unilaterally connected component partitions may not be well-defined, since it is possible for a given vertex to be unilaterally connected to two vertices that are not unilaterally connected with one another. Consider, for instance, the graph a->b<-c<-d. In this case, the maximal unilateral components are ab and bcd, with vertex b properly belonging to both components. For such graphs, a unique partition of vertices by component does not exist, and we “solve” the problem by allocating each “problem vertex” to one of its components on an essentially arbitrary basis. (component.dist
generates a warning when this occurs.) It is recommended that the unilateral
option be avoided where possible.
Do not make the mistake of assuming that the subgraphs returned by component.largest
are necessarily connected. This is usually the case, but depends upon the uniqueness of the largest component.
Carter T. Butts buttsc@uci.edu
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
components
, symmetrize
, reachability
geodist
g<-rgraph(20,tprob=0.06) #Generate a sparse random graph #Find weak components cd<-component.dist(g,connected="weak") cd$membership #Who's in what component? cd$csize #What are the component sizes? #Plot the size distribution plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h") lgc<-component.largest(g,connected="weak") #Get largest component gplot(g,vertex.col=2+lgc) #Plot g, with component membership #Plot largest component itself gplot(component.largest(g,connected="weak",result="graph")) #Find strong components cd<-component.dist(g,connected="strong") cd$membership #Who's in what component? cd$csize #What are the component sizes? #Plot the size distribution plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h") lgc<-component.largest(g,connected="strong") #Get largest component gplot(g,vertex.col=2+lgc) #Plot g, with component membership #Plot largest component itself gplot(component.largest(g,connected="strong",result="graph"))
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.