cutpoints  R Documentation 
cutpoints
identifies the cutpoints of an input graph. Depending on mode
, either a directed or undirected notion of “cutpoint” can be used.
cutpoints(dat, mode = "digraph", connected = c("strong","weak","recursive"), return.indicator = FALSE)
dat 
one or more input graphs. 
mode 

connected 
string indicating the type of connectedness rule to apply (only relevant where 
return.indicator 
logical; should the results be returned as a logical ( 
A cutpoint (also known as an articulation point or cutvertex) of an undirected graph, G is a vertex whose removal increases the number of components of G. Several generalizations to the directed case exist. Here, we define a strong cutpoint of directed graph G to be a vertex whose removal increases the number of strongly connected components of G (see component.dist
). Likewise, weak and recursive cutpoints of G are those vertices whose removal increases the number of weak or recursive cutpoints (respectively). By default, strong cutpoints are used; alternatives may be selected via the connected
argument.
Cutpoints are of particular interest when seeking to identify critical positions in flow networks, since their removal by definition alters the connectivity properties of the graph. In this context, cutpoint status can be thought of as a primitive form of centrality (with some similarities to betweenness
).
Cutpoint computation is significantly faster for the undirected case (and for the weak/recursive cases) than for the strong directed case. While calling cutpoints
with mode="digraph"
on an undirected graph will give the same answer as mode="graph"
, it is thus to one's advantage to use the latter form. Do not, however, employ mode="graph"
with directed data, unless you enjoy unpredictable behavior.
A vector of cutpoints (if return.indicator==FALSE
), or else a logical vector indicating cutpoint status for each vertex.
Carter T. Butts buttsc@uci.edu
Berge, Claude. (1966). The Theory of Graphs. New York: John Wiley and Sons.
component.dist
, bicomponent.dist
, betweenness
#Generate some sparse random graph gd<rgraph(25,tp=1.5/24) #Directed gu<rgraph(25,tp=1.5/24,mode="graph") #Undirected #Calculate the cutpoints (as an indicator vector) cpu<cutpoints(gu,mode="graph",return.indicator=TRUE) cpd<cutpoints(gd,return.indicator=TRUE) #Plot the result gplot(gu,gmode="graph",vertex.col=2+cpu) gplot(gd,vertex.col=2+cpd) #Repeat with alternate connectivity modes cpdw<cutpoints(gd,connected="weak",return.indicator=TRUE) cpdr<cutpoints(gd,connected="recursive",return.indicator=TRUE) #Visualize the difference gplot(gd,vertex.col=2+cpdw) gplot(gd,vertex.col=2+cpdr)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.