Identify the Cutpoints of a Graph or Digraph
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 cut-vertex) 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.
#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)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.