1# IGraph R package 2# Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 3# 334 Harvard street, Cambridge, MA 02139 USA 4# 5# This program is free software; you can redistribute it and/or modify 6# it under the terms of the GNU General Public License as published by 7# the Free Software Foundation; either version 2 of the License, or 8# (at your option) any later version. 9# 10# This program is distributed in the hope that it will be useful, 11# but WITHOUT ANY WARRANTY; without even the implied warranty of 12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13# GNU General Public License for more details. 14# 15# You should have received a copy of the GNU General Public License 16# along with this program; if not, write to the Free Software 17# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 18# 02110-1301 USA 19# 20################################################################### 21 22#' Minimum cut in a graph 23#' 24#' \code{min_cut} calculates the minimum st-cut between two vertices in a graph 25#' (if the \code{source} and \code{target} arguments are given) or the minimum 26#' cut of the graph (if both \code{source} and \code{target} are \code{NULL}). 27#' 28#' The minimum st-cut between \code{source} and \code{target} is the minimum 29#' total weight of edges needed to remove to eliminate all paths from 30#' \code{source} to \code{target}. 31#' 32#' The minimum cut of a graph is the minimum total weight of the edges needed 33#' to remove to separate the graph into (at least) two components. (Which is to 34#' make the graph \emph{not} strongly connected in the directed case.) 35#' 36#' The maximum flow between two vertices in a graph is the same as the minimum 37#' st-cut, so \code{max_flow} and \code{min_cut} essentially calculate the same 38#' quantity, the only difference is that \code{min_cut} can be invoked without 39#' giving the \code{source} and \code{target} arguments and then minimum of all 40#' possible minimum cuts is calculated. 41#' 42#' For undirected graphs the Stoer-Wagner algorithm (see reference below) is 43#' used to calculate the minimum cut. 44#' 45#' @aliases graph.mincut 46#' @param graph The input graph. 47#' @param source The id of the source vertex. 48#' @param target The id of the target vertex (sometimes also called sink). 49#' @param capacity Vector giving the capacity of the edges. If this is 50#' \code{NULL} (the default) then the \code{capacity} edge attribute is used. 51#' @param value.only Logical scalar, if \code{TRUE} only the minimum cut value 52#' is returned, if \code{FALSE} the edges in the cut and a the two (or more) 53#' partitions are also returned. 54#' @return For \code{min_cut} a nuieric constant, the value of the minimum 55#' cut, except if \code{value.only = FALSE}. In this case a named list with 56#' components: 57#' \item{value}{Numeric scalar, the cut value.} 58#' \item{cut}{Numeric vector, the edges in the cut.} 59#' \item{partition1}{The vertices in the first partition after the cut 60#' edges are removed. Note that these vertices might be actually in 61#' different components (after the cut edges are removed), as the graph 62#' may fall apart into more than two components.} 63#' \item{partition2}{The vertices in the second partition 64#' after the cut edges are removed. Note that these vertices might be 65#' actually in different components (after the cut edges are removed), as 66#' the graph may fall apart into more than two components.} 67#' @seealso \code{\link{max_flow}} for the related maximum flow 68#' problem, \code{\link{distances}}, \code{\link{edge_connectivity}}, 69#' \code{\link{vertex_connectivity}} 70#' @references M. Stoer and F. Wagner: A simple min-cut algorithm, 71#' \emph{Journal of the ACM}, 44 585-591, 1997. 72#' @examples 73#' g <- make_ring(100) 74#' min_cut(g, capacity=rep(1,vcount(g))) 75#' min_cut(g, value.only=FALSE, capacity=rep(1,vcount(g))) 76#' 77#' g2 <- graph( c(1,2,2,3,3,4, 1,6,6,5,5,4, 4,1) ) 78#' E(g2)$capacity <- c(3,1,2, 10,1,3, 2) 79#' min_cut(g2, value.only=FALSE) 80#' @export 81#' @include auto.R 82 83min_cut <- function(graph, source=NULL, target=NULL, capacity=NULL, 84 value.only=TRUE) { 85 86 if (!is_igraph(graph)) { 87 stop("Not a graph object") 88 } 89 if (is.null(capacity)) { 90 if ("capacity" %in% edge_attr_names(graph)) { 91 capacity <- E(graph)$capacity 92 } 93 } 94 if (is.null(source) && !is.null(target) || 95 is.null(target) && !is.null(source)) { 96 stop("Please give both source and target or neither") 97 } 98 if (!is.null(capacity)) { 99 capacity <- as.numeric(capacity) 100 } 101 102 value.only <- as.logical(value.only) 103 on.exit( .Call(C_R_igraph_finalizer) ) 104 if (is.null(target) && is.null(source)) { 105 if (value.only) { 106 res <- .Call(C_R_igraph_mincut_value, graph, capacity) 107 } else { 108 res <- .Call(C_R_igraph_mincut, graph, capacity) 109 res$cut <- res$cut + 1 110 res$partition1 <- res$partition1 + 1 111 res$partition2 <- res$partition2 + 1 112 113 if (igraph_opt("return.vs.es")) { 114 res$cut <- create_es(graph, res$cut) 115 res$partition1 <- create_vs(graph, res$partition1) 116 res$partition2 <- create_vs(graph, res$partition2) 117 } 118 119 res 120 } 121 } else { 122 if (value.only) { 123 res <- .Call(C_R_igraph_st_mincut_value, graph, 124 as.igraph.vs(graph, source)-1, 125 as.igraph.vs(graph, target)-1, capacity) 126 } else { 127 stop("Calculating minimum s-t cuts is not implemented yet") 128 } 129 } 130 res 131} 132 133 134 135#' Vertex connectivity. 136#' 137#' The vertex connectivity of a graph or two vertices, this is recently also 138#' called group cohesion. 139#' 140#' The vertex connectivity of two vertices (\code{source} and \code{target}) in 141#' a directed graph is the minimum number of vertices needed to remove from the 142#' graph to eliminate all (directed) paths from \code{source} to \code{target}. 143#' \code{vertex_connectivity} calculates this quantity if both the 144#' \code{source} and \code{target} arguments are given and they're not 145#' \code{NULL}. 146#' 147#' The vertex connectivity of a graph is the minimum vertex connectivity of all 148#' (ordered) pairs of vertices in the graph. In other words this is the minimum 149#' number of vertices needed to remove to make the graph not strongly 150#' connected. (If the graph is not strongly connected then this is zero.) 151#' \code{vertex_connectivity} calculates this quantity if neither the 152#' \code{source} nor \code{target} arguments are given. (Ie. they are both 153#' \code{NULL}.) 154#' 155#' A set of vertex disjoint directed paths from \code{source} to \code{vertex} 156#' is a set of directed paths between them whose vertices do not contain common 157#' vertices (apart from \code{source} and \code{target}). The maximum number of 158#' vertex disjoint paths between two vertices is the same as their vertex 159#' connectivity in most cases (if the two vertices are not connected by an 160#' edge). 161#' 162#' The cohesion of a graph (as defined by White and Harary, see references), is 163#' the vertex connectivity of the graph. This is calculated by 164#' \code{cohesion}. 165#' 166#' These three functions essentially calculate the same measure(s), more 167#' precisely \code{vertex_connectivity} is the most general, the other two are 168#' included only for the ease of using more descriptive function names. 169#' 170#' @aliases vertex.connectivity vertex.disjoint.paths cohesion vertex_connectivity 171#' vertex_disjoint_paths graph.cohesion 172#' @param graph,x The input graph. 173#' @param source The id of the source vertex, for \code{vertex_connectivity} it 174#' can be \code{NULL}, see details below. 175#' @param target The id of the target vertex, for \code{vertex_connectivity} it 176#' can be \code{NULL}, see details below. 177#' @param checks Logical constant. Whether to check that the graph is connected 178#' and also the degree of the vertices. If the graph is not (strongly) 179#' connected then the connectivity is obviously zero. Otherwise if the minimum 180#' degree is one then the vertex connectivity is also one. It is a good idea to 181#' perform these checks, as they can be done quickly compared to the 182#' connectivity calculation itself. They were suggested by Peter McMahan, 183#' thanks Peter. 184#' @param ... Ignored. 185#' @return A scalar real value. 186#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 187#' @seealso \code{\link{max_flow}}, \code{\link{edge_connectivity}}, 188#' \code{\link{edge_disjoint_paths}}, \code{\link{adhesion}} 189#' @references White, Douglas R and Frank Harary 2001. The Cohesiveness of 190#' Blocks In Social Networks: Node Connectivity and Conditional Density. 191#' \emph{Sociological Methodology} 31 (1) : 305-359. 192#' @export 193#' @keywords graphs 194#' @examples 195#' 196#' g <- barabasi.game(100, m=1) 197#' g <- delete_edges(g, E(g)[ 100 %--% 1 ]) 198#' g2 <- barabasi.game(100, m=5) 199#' g2 <- delete_edges(g2, E(g2)[ 100 %--% 1]) 200#' vertex_connectivity(g, 100, 1) 201#' vertex_connectivity(g2, 100, 1) 202#' vertex_disjoint_paths(g2, 100, 1) 203#' 204#' g <- sample_gnp(50, 5/50) 205#' g <- as.directed(g) 206#' g <- induced_subgraph(g, subcomponent(g, 1)) 207#' cohesion(g) 208#' 209vertex_connectivity <- function(graph, source=NULL, target=NULL, checks=TRUE) { 210 211 if (!is_igraph(graph)) { 212 stop("Not a graph object") 213 } 214 215 if (is.null(source) && is.null(target)) { 216 on.exit( .Call(C_R_igraph_finalizer) ) 217 .Call(C_R_igraph_vertex_connectivity, graph, as.logical(checks)) 218 } else if (!is.null(source) && !is.null(target)) { 219 on.exit( .Call(C_R_igraph_finalizer) ) 220 .Call(C_R_igraph_st_vertex_connectivity, graph, as.igraph.vs(graph, source)-1, 221 as.igraph.vs(graph, target)-1) 222 } else { 223 stop("either give both source and target or neither") 224 } 225} 226 227 228 229#' Edge connectivity. 230#' 231#' The edge connectivity of a graph or two vertices, this is recently also 232#' called group adhesion. 233#' 234#' The edge connectivity of a pair of vertices (\code{source} and 235#' \code{target}) is the minimum number of edges needed to remove to eliminate 236#' all (directed) paths from \code{source} to \code{target}. 237#' \code{edge_connectivity} calculates this quantity if both the \code{source} 238#' and \code{target} arguments are given (and not \code{NULL}). 239#' 240#' The edge connectivity of a graph is the minimum of the edge connectivity of 241#' every (ordered) pair of vertices in the graph. \code{edge_connectivity} 242#' calculates this quantity if neither the \code{source} nor the \code{target} 243#' arguments are given (ie. they are both \code{NULL}). 244#' 245#' A set of edge disjoint paths between two vertices is a set of paths between 246#' them containing no common edges. The maximum number of edge disjoint paths 247#' between two vertices is the same as their edge connectivity. 248#' 249#' The adhesion of a graph is the minimum number of edges needed to remove to 250#' obtain a graph which is not strongly connected. This is the same as the edge 251#' connectivity of the graph. 252#' 253#' The three functions documented on this page calculate similar properties, 254#' more precisely the most general is \code{edge_connectivity}, the others are 255#' included only for having more descriptive function names. 256#' 257#' @aliases edge.connectivity edge_disjoint_paths graph.adhesion adhesion 258#' edge_connectivity edge.disjoint.paths 259#' @param graph The input graph. 260#' @param source The id of the source vertex, for \code{edge_connectivity} it 261#' can be \code{NULL}, see details below. 262#' @param target The id of the target vertex, for \code{edge_connectivity} it 263#' can be \code{NULL}, see details below. 264#' @param checks Logical constant. Whether to check that the graph is connected 265#' and also the degree of the vertices. If the graph is not (strongly) 266#' connected then the connectivity is obviously zero. Otherwise if the minimum 267#' degree is one then the edge connectivity is also one. It is a good idea to 268#' perform these checks, as they can be done quickly compared to the 269#' connectivity calculation itself. They were suggested by Peter McMahan, 270#' thanks Peter. 271#' @return A scalar real value. 272#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 273#' @seealso \code{\link{max_flow}}, \code{\link{vertex_connectivity}}, 274#' \code{\link{vertex_disjoint_paths}}, \code{\link{cohesion}} 275#' @references Douglas R. White and Frank Harary: The cohesiveness of blocks in 276#' social networks: node connectivity and conditional density, TODO: citation 277#' @export 278#' @keywords graphs 279#' @examples 280#' 281#' g <- barabasi.game(100, m=1) 282#' g2 <- barabasi.game(100, m=5) 283#' edge_connectivity(g, 100, 1) 284#' edge_connectivity(g2, 100, 1) 285#' edge_disjoint_paths(g2, 100, 1) 286#' 287#' g <- sample_gnp(50, 5/50) 288#' g <- as.directed(g) 289#' g <- induced_subgraph(g, subcomponent(g, 1)) 290#' adhesion(g) 291#' 292edge_connectivity <- function(graph, source=NULL, target=NULL, checks=TRUE) { 293 294 if (!is_igraph(graph)) { 295 stop("Not a graph object") 296 } 297 298 if (is.null(source) && is.null(target)) { 299 on.exit( .Call(C_R_igraph_finalizer) ) 300 .Call(C_R_igraph_edge_connectivity, graph, as.logical(checks)) 301 } else if (!is.null(source) && !is.null(target)) { 302 on.exit( .Call(C_R_igraph_finalizer) ) 303 .Call(C_R_igraph_st_edge_connectivity, graph, 304 as.igraph.vs(graph, source)-1, as.igraph.vs(graph, target)-1) 305 } else { 306 stop("either give both source and target or neither") 307 } 308} 309 310#' @export 311 312edge_disjoint_paths <- function(graph, source, target) { 313 314 if (!is_igraph(graph)) { 315 stop("Not a graph object") 316 } 317 318 on.exit( .Call(C_R_igraph_finalizer) ) 319 .Call(C_R_igraph_edge_disjoint_paths, graph, 320 as.igraph.vs(graph, source)-1, as.igraph.vs(graph, target)-1) 321} 322 323#' @export 324 325vertex_disjoint_paths <- function(graph, source=NULL, target=NULL) { 326 327 if (!is_igraph(graph)) { 328 stop("Not a graph object") 329 } 330 331 on.exit( .Call(C_R_igraph_finalizer) ) 332 .Call(C_R_igraph_vertex_disjoint_paths, graph, as.igraph.vs(graph, source)-1, 333 as.igraph.vs(graph, target)-1) 334} 335 336#' @export 337 338adhesion <- function(graph, checks=TRUE) { 339 340 if (!is_igraph(graph)) { 341 stop("Not a graph object") 342 } 343 344 on.exit( .Call(C_R_igraph_finalizer) ) 345 .Call(C_R_igraph_adhesion, graph, as.logical(checks)) 346} 347 348#' @rdname vertex_connectivity 349#' @method cohesion igraph 350#' @export 351 352cohesion.igraph <- function(x, checks=TRUE, ...) { 353 354 if (!is_igraph(x)) { 355 stop("Not a graph object") 356 } 357 358 on.exit( .Call(C_R_igraph_finalizer) ) 359 .Call(C_R_igraph_cohesion, x, as.logical(checks)) 360} 361 362#' List all (s,t)-cuts of a graph 363#' 364#' List all (s,t)-cuts in a directed graph. 365#' 366#' Given a \eqn{G} directed graph and two, different and non-ajacent vertices, 367#' \eqn{s} and \eqn{t}, an \eqn{(s,t)}-cut is a set of edges, such that after 368#' removing these edges from \eqn{G} there is no directed path from \eqn{s} to 369#' \eqn{t}. 370#' 371#' @aliases stCuts st_cuts 372#' @param graph The input graph. It must be directed. 373#' @param source The source vertex. 374#' @param target The target vertex. 375#' @return A list with entries: \item{cuts}{A list of numeric vectors 376#' containing edge ids. Each vector is an \eqn{(s,t)}-cut.} 377#' \item{partition1s}{A list of numeric vectors containing vertex ids, they 378#' correspond to the edge cuts. Each vertex set is a generator of the 379#' corresponding cut, i.e. in the graph \eqn{G=(V,E)}, the vertex set \eqn{X} 380#' and its complementer \eqn{V-X}, generates the cut that contains exactly the 381#' edges that go from \eqn{X} to \eqn{V-X}.} 382#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 383#' @seealso \code{\link{st_min_cuts}} to list all minimum cuts. 384#' @references JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in 385#' graphs, \emph{Algorithmica} 15, 351--372, 1996. 386#' @keywords graphs 387#' @examples 388#' 389#' # A very simple graph 390#' g <- graph_from_literal(a -+ b -+ c -+ d -+ e) 391#' st_cuts(g, source="a", target="e") 392#' 393#' # A somewhat more difficult graph 394#' g2 <- graph_from_literal(s --+ a:b, a:b --+ t, 395#' a --+ 1:2:3, 1:2:3 --+ b) 396#' st_cuts(g2, source="s", target="t") 397#' @export 398#' @include auto.R 399 400st_cuts <- st_cuts 401 402 403#' List all minimum \eqn{(s,t)}-cuts of a graph 404#' 405#' Listing all minimum \eqn{(s,t)}-cuts of a directed graph, for given \eqn{s} 406#' and \eqn{t}. 407#' 408#' Given a \eqn{G} directed graph and two, different and non-ajacent vertices, 409#' \eqn{s} and \eqn{t}, an \eqn{(s,t)}-cut is a set of edges, such that after 410#' removing these edges from \eqn{G} there is no directed path from \eqn{s} to 411#' \eqn{t}. 412#' 413#' The size of an \eqn{(s,t)}-cut is defined as the sum of the capacities (or 414#' weights) in the cut. For unweighted (=equally weighted) graphs, this is 415#' simply the number of edges. 416#' 417#' An \eqn{(s,t)}-cut is minimum if it is of the smallest possible size. 418#' 419#' @aliases st_min_cuts stMincuts 420#' @param graph The input graph. It must be directed. 421#' @param source The id of the source vertex. 422#' @param target The id of the target vertex. 423#' @param capacity Numeric vector giving the edge capacities. If this is 424#' \code{NULL} and the graph has a \code{weight} edge attribute, then this 425#' attribute defines the edge capacities. For forcing unit edge capacities, 426#' even for graphs that have a \code{weight} edge attribute, supply \code{NA} 427#' here. 428#' @return A list with entries: \item{value}{Numeric scalar, the size of the 429#' minimum cut(s).} \item{cuts}{A list of numeric vectors containing edge ids. 430#' Each vector is a minimum \eqn{(s,t)}-cut.} \item{partition1s}{A list of 431#' numeric vectors containing vertex ids, they correspond to the edge cuts. 432#' Each vertex set is a generator of the corresponding cut, i.e. in the graph 433#' \eqn{G=(V,E)}, the vertex set \eqn{X} and its complementer \eqn{V-X}, 434#' generates the cut that contains exactly the edges that go from \eqn{X} to 435#' \eqn{V-X}.} 436#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 437#' @seealso \code{\link{st_cuts}}, \code{\link{min_separators}} 438#' @references JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in 439#' graphs, \emph{Algorithmica} 15, 351--372, 1996. 440#' @keywords graphs 441#' @examples 442#' 443#' # A difficult graph, from the Provan-Shier paper 444#' g <- graph_from_literal(s --+ a:b, a:b --+ t, 445#' a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b) 446#' st_min_cuts(g, source="s", target="t") 447#' @export 448#' @include auto.R 449 450st_min_cuts <- st_min_cuts 451 452 453#' Dominator tree 454#' 455#' Dominator tree of a directed graph. 456#' 457#' A flowgraph is a directed graph with a distinguished start (or root) vertex 458#' \eqn{r}, such that for any vertex \eqn{v}, there is a path from \eqn{r} to 459#' \eqn{v}. A vertex \eqn{v} dominates another vertex \eqn{w} (not equal to 460#' \eqn{v}), if every path from \eqn{r} to \eqn{w} contains \eqn{v}. Vertex 461#' \eqn{v} is the immediate dominator or \eqn{w}, 462#' \eqn{v=\textrm{idom}(w)}{v=idom(w)}, if \eqn{v} dominates \eqn{w} and every 463#' other dominator of \eqn{w} dominates \eqn{v}. The edges 464#' \eqn{{(\textrm{idom}(w), w)| w \ne r}}{{(idom(w),w)| w is not r}} form a 465#' directed tree, rooted at \eqn{r}, called the dominator tree of the graph. 466#' Vertex \eqn{v} dominates vertex \eqn{w} if and only if \eqn{v} is an 467#' ancestor of \eqn{w} in the dominator tree. 468#' 469#' This function implements the Lengauer-Tarjan algorithm to construct the 470#' dominator tree of a directed graph. For details see the reference below. 471#' 472#' @aliases dominator.tree dominator_tree 473#' @param graph A directed graph. If it is not a flowgraph, and it contains 474#' some vertices not reachable from the root vertex, then these vertices will 475#' be collected and returned as part of the result. 476#' @param root The id of the root (or source) vertex, this will be the root of 477#' the tree. 478#' @param mode Constant, must be \sQuote{\code{in}} or \sQuote{\code{out}}. If 479#' it is \sQuote{\code{in}}, then all directions are considered as opposite to 480#' the original one in the input graph. 481#' @return A list with components: \item{dom}{ A numeric vector giving the 482#' immediate dominators for each vertex. For vertices that are unreachable from 483#' the root, it contains \code{NaN}. For the root vertex itself it contains 484#' minus one. } \item{domtree}{ A graph object, the dominator tree. Its vertex 485#' ids are the as the vertex ids of the input graph. Isolate vertices are the 486#' ones that are unreachable from the root. } \item{leftout}{ A numeric vector 487#' containing the vertex ids that are unreachable from the root. } 488#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 489#' @references Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for 490#' finding dominators in a flowgraph, \emph{ACM Transactions on Programming 491#' Languages and Systems (TOPLAS)} I/1, 121--141, 1979. 492#' @keywords graphs 493#' @examples 494#' 495#' ## The example from the paper 496#' g <- graph_from_literal(R-+A:B:C, A-+D, B-+A:D:E, C-+F:G, D-+L, 497#' E-+H, F-+I, G-+I:J, H-+E:K, I-+K, J-+I, 498#' K-+I:R, L-+H) 499#' dtree <- dominator_tree(g, root="R") 500#' layout <- layout_as_tree(dtree$domtree, root="R") 501#' layout[,2] <- -layout[,2] 502#' plot(dtree$domtree, layout=layout, vertex.label=V(dtree$domtree)$name) 503#' @export 504 505dominator_tree <- dominator_tree 506 507 508#' Minimum size vertex separators 509#' 510#' List all vertex sets that are minimal (s,t) separators for some s and t, in 511#' an undirected graph. 512#' 513#' A \eqn{(s,t)} vertex separator is a set of vertices, such that after their 514#' removal from the graph, there is no path between \eqn{s} and \eqn{t} in the 515#' graph. 516#' 517#' A \eqn{(s,t)} vertex separator is minimal if none of its subsets is an 518#' \eqn{(s,t)} vertex separator. 519#' 520#' @aliases minimal.st.separators min_st_separators 521#' @param graph The input graph. It may be directed, but edge directions are 522#' ignored. 523#' @return A list of numeric vectors. Each vector contains a vertex set 524#' (defined by vertex ids), each vector is an (s,t) separator of the input 525#' graph, for some \eqn{s} and \eqn{t}. 526#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 527#' @references Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All 528#' the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer and 529#' Stephan Eidenbenz (editors): \emph{Graph-theoretic concepts in computer 530#' science}, 1665, 167--172, 1999. Springer. 531#' @keywords graphs 532#' @examples 533#' 534#' ring <- make_ring(4) 535#' min_st_separators(ring) 536#' 537#' chvatal <- make_graph("chvatal") 538#' min_st_separators(chvatal) 539 540min_st_separators <- min_st_separators 541 542 543#' Maximum flow in a graph 544#' 545#' In a graph where each edge has a given flow capacity the maximal flow 546#' between two vertices is calculated. 547#' 548#' \code{max_flow} calculates the maximum flow between two vertices in a 549#' weighted (ie. valued) graph. A flow from \code{source} to \code{target} is 550#' an assignment of non-negative real numbers to the edges of the graph, 551#' satisfying two properties: (1) for each edge the flow (ie. the assigned 552#' number) is not more than the capacity of the edge (the \code{capacity} 553#' parameter or edge attribute), (2) for every vertex, except the source and 554#' the target the incoming flow is the same as the outgoing flow. The value of 555#' the flow is the incoming flow of the \code{target} vertex. The maximum flow 556#' is the flow of maximum value. 557#' 558#' @aliases graph.maxflow 559#' @param graph The input graph. 560#' @param source The id of the source vertex. 561#' @param target The id of the target vertex (sometimes also called sink). 562#' @param capacity Vector giving the capacity of the edges. If this is 563#' \code{NULL} (the default) then the \code{capacity} edge attribute is used. 564#' Note that the \code{weight} edge attribute is not used by this function. 565#' @return A named list with components: 566#' \item{value}{A numeric scalar, the value of the maximum flow.} 567#' \item{flow}{A numeric vector, the flow itself, one entry for each 568#' edge. For undirected graphs this entry is bit trickier, since for 569#' these the flow direction is not predetermined by the edge 570#' direction. For these graphs the elements of the this vector can be 571#' negative, this means that the flow goes from the bigger vertex id to 572#' the smaller one. Positive values mean that the flow goes from 573#' the smaller vertex id to the bigger one.} 574#' \item{cut}{A numeric vector of edge ids, the minimum cut corresponding 575#' to the maximum flow.} 576#' \item{partition1}{A numeric vector of vertex ids, the vertices in the 577#' first partition of the minimum cut corresponding to the maximum 578#' flow.} 579#' \item{partition2}{A numeric vector of vertex ids, the vertices in the 580#' second partition of the minimum cut corresponding to the maximum 581#' flow.} 582#' \item{stats}{A list with some statistics from the push-relabel 583#' algorithm. Five integer values currently: \code{nopush} is the 584#' number of push operations, \code{norelabel} the number of 585#' relabelings, \code{nogap} is the number of times the gap heuristics 586#' was used, \code{nogapnodes} is the total number of gap nodes omitted 587#' because of the gap heuristics and \code{nobfs} is the number of 588#' times a global breadth-first-search update was performed to assign 589#' better height (=distance) values to the vertices.} 590#' @seealso \code{\link{min_cut}} for minimum cut calculations, 591#' \code{\link{distances}}, \code{\link{edge_connectivity}}, 592#' \code{\link{vertex_connectivity}} 593#' @references A. V. Goldberg and R. E. Tarjan: A New Approach to the Maximum 594#' Flow Problem \emph{Journal of the ACM} 35:921-940, 1988. 595#' @examples 596#' 597#' E <- rbind( c(1,3,3), c(3,4,1), c(4,2,2), c(1,5,1), c(5,6,2), c(6,2,10)) 598#' colnames(E) <- c("from", "to", "capacity") 599#' g1 <- graph_from_data_frame(as.data.frame(E)) 600#' max_flow(g1, source=V(g1)["1"], target=V(g1)["2"]) 601#' @export 602#' @include auto.R 603 604max_flow <- max_flow 605 606 607#' Vertex separators 608#' 609#' Check whether a given set of vertices is a vertex separator. 610#' 611#' \code{is_separator} decides whether the supplied vertex set is a vertex 612#' separator. A vertex set is a vertex separator if its removal results a 613#' disconnected graph. 614#' 615#' In the special case of a fully connected graph with \eqn{n} vertices, each 616#' set of \eqn{n-1} vertices is considered to be a vertex separator. 617#' 618#' @aliases is.separator 619#' @param graph The input graph. It may be directed, but edge directions are 620#' ignored. 621#' @param candidate A numeric vector giving the vertex ids of the candidate 622#' separator. 623#' @return A logical scalar, whether the supplied vertex set is a (minimal) 624#' vertex separator or not. 625#' @seealso \code{\link{is_min_separator}}, \code{\link{min_separators}} 626#' lists all vertex separator of minimum size. 627#' @export 628 629is_separator <- is_separator 630 631 632#' Minimal vertex separators 633#' 634#' Check whether a given set of vertices is a minimal vertex separator. 635#' 636#' \code{is_min_separator} decides whether the supplied vertex set is a minimal 637#' vertex separator. A minimal vertex separator is a vertex separator, such 638#' that none of its subsets is a vertex separator. 639#' 640#' In the special case of a fully connected graph with \eqn{n} vertices, each 641#' set of \eqn{n-1} vertices is considered to be a vertex separator. 642#' 643#' @aliases is.minimal.separator 644#' @param graph The input graph. It may be directed, but edge directions are 645#' ignored. 646#' @param candidate A numeric vector giving the vertex ids of the candidate 647#' separator. 648#' @return A logical scalar, whether the supplied vertex set is a (minimal) 649#' vertex separator or not. 650#' @seealso \code{\link{min_separators}} lists all vertex separator of minimum 651#' size. 652#' @examples 653#' # The graph from the Moody-White paper 654#' mw <- graph_from_literal(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7, 655#' 5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10, 656#' 10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16, 657#' 17-18:19:20, 18-20:21, 19-20:22:23, 20-21, 658#' 21-22:23, 22-23) 659#' 660#' # Cohesive subgraphs 661#' mw1 <- induced_subgraph(mw, as.character(c(1:7, 17:23))) 662#' mw2 <- induced_subgraph(mw, as.character(7:16)) 663#' mw3 <- induced_subgraph(mw, as.character(17:23)) 664#' mw4 <- induced_subgraph(mw, as.character(c(7,8,11,14))) 665#' mw5 <- induced_subgraph(mw, as.character(1:7)) 666#' 667#' check.sep <- function(G) { 668#' sep <- min_separators(G) 669#' sapply(sep, is_min_separator, graph=G) 670#' } 671#' 672#' check.sep(mw) 673#' check.sep(mw1) 674#' check.sep(mw2) 675#' check.sep(mw3) 676#' check.sep(mw4) 677#' check.sep(mw5) 678#' 679#' @export 680 681is_min_separator <- is_min_separator 682 683 684#' Minimum size vertex separators 685#' 686#' Find all vertex sets of minimal size whose removal separates the graph into 687#' more components 688#' 689#' This function implements the Kanevsky algorithm for finding all minimal-size 690#' vertex separators in an undirected graph. See the reference below for the 691#' details. 692#' 693#' In the special case of a fully connected input graph with \eqn{n} vertices, 694#' all subsets of size \eqn{n-1} are listed as the result. 695#' 696#' @aliases minimum.size.separators 697#' @param graph The input graph. It may be directed, but edge directions are 698#' ignored. 699#' @return A list of numeric vectors. Each numeric vector is a vertex 700#' separator. 701#' @seealso \code{\link{is.separator}} 702#' @references Arkady Kanevsky: Finding all minimum-size separating vertex sets 703#' in a graph. \emph{Networks} 23 533--541, 1993. 704#' 705#' JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, 706#' \emph{Algorithmica} 15, 351--372, 1996. 707#' 708#' J. Moody and D. R. White. Structural cohesion and embeddedness: A 709#' hierarchical concept of social groups. \emph{American Sociological Review}, 710#' 68 103--127, Feb 2003. 711#' @export 712#' @examples 713#' # The graph from the Moody-White paper 714#' mw <- graph.formula(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7, 715#' 5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10, 716#' 10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16, 717#' 17-18:19:20, 18-20:21, 19-20:22:23, 20-21, 718#' 21-22:23, 22-23) 719#' 720#' # Cohesive subgraphs 721#' mw1 <- induced.subgraph(mw, as.character(c(1:7, 17:23))) 722#' mw2 <- induced.subgraph(mw, as.character(7:16)) 723#' mw3 <- induced.subgraph(mw, as.character(17:23)) 724#' mw4 <- induced.subgraph(mw, as.character(c(7,8,11,14))) 725#' mw5 <- induced.subgraph(mw, as.character(1:7)) 726#' 727#' min_separators(mw) 728#' min_separators(mw1) 729#' min_separators(mw2) 730#' min_separators(mw3) 731#' min_separators(mw4) 732#' min_separators(mw5) 733#' 734#' # Another example, the science camp network 735#' camp <- graph.formula(Harry:Steve:Don:Bert - Harry:Steve:Don:Bert, 736#' Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat, 737#' Holly - Carol:Pat:Pam:Jennie:Bill, 738#' Bill - Pauline:Michael:Lee:Holly, 739#' Pauline - Bill:Jennie:Ann, 740#' Jennie - Holly:Michael:Lee:Ann:Pauline, 741#' Michael - Bill:Jennie:Ann:Lee:John, 742#' Ann - Michael:Jennie:Pauline, 743#' Lee - Michael:Bill:Jennie, 744#' Gery - Pat:Steve:Russ:John, 745#' Russ - Steve:Bert:Gery:John, 746#' John - Gery:Russ:Michael) 747#' min_separators(camp) 748 749min_separators <- min_separators 750