1 2# IGraph R package 3# Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 4# 334 Harvard street, Cambridge, MA 02139 USA 5# 6# This program is free software; you can redistribute it and/or modify 7# it under the terms of the GNU General Public License as published by 8# the Free Software Foundation; either version 2 of the License, or 9# (at your option) any later version. 10# 11# This program is distributed in the hope that it will be useful, 12# but WITHOUT ANY WARRANTY; without even the implied warranty of 13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14# GNU General Public License for more details. 15# 16# You should have received a copy of the GNU General Public License 17# along with this program; if not, write to the Free Software 18# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19# 02110-1301 USA 20# 21################################################################### 22 23#' @export 24 25graph.get.isomorphisms.vf2 <- function(graph1, graph2, vertex.color1, 26 vertex.color2, edge.color1, 27 edge.color2) { 28 # Argument checks 29 if (!is_igraph(graph1)) { stop("Not a graph object") } 30 if (!is_igraph(graph2)) { stop("Not a graph object") } 31 if (missing(vertex.color1)) { 32 if ("color" %in% vertex_attr_names(graph1)) { 33 vertex.color1 <- V(graph1)$color 34 } else { 35 vertex.color1 <- NULL 36 } 37 } 38 if (!is.null(vertex.color1)) { 39 vertex.color1 <- as.integer(vertex.color1)-1L 40 } 41 if (missing(vertex.color2)) { 42 if ("color" %in% vertex_attr_names(graph2)) { 43 vertex.color2 <- V(graph2)$color 44 } else { 45 vertex.color2 <- NULL 46 } 47 } 48 if (!is.null(vertex.color2)) { 49 vertex.color2 <- as.integer(vertex.color2)-1L 50 } 51 if (missing(edge.color1)) { 52 if ("color" %in% edge_attr_names(graph1)) { 53 edge.color1 <- E(graph1)$color 54 } else { 55 edge.color1 <- NULL 56 } 57 } 58 if (!is.null(edge.color1)) { 59 edge.color1 <- as.integer(edge.color1)-1L 60 } 61 if (missing(edge.color2)) { 62 if ("color" %in% edge_attr_names(graph2)) { 63 edge.color2 <- E(graph2)$color 64 } else { 65 edge.color2 <- NULL 66 } 67 } 68 if (!is.null(edge.color2)) { 69 edge.color2 <- as.integer(edge.color2)-1L 70 } 71 72 on.exit( .Call(C_R_igraph_finalizer) ) 73 # Function call 74 res <- .Call(C_R_igraph_get_isomorphisms_vf2, graph1, graph2, vertex.color1, 75 vertex.color2, edge.color1, edge.color2) 76 77 lapply(res, function(x) V(graph2)[x + 1]) 78} 79 80#' @export 81 82graph.get.subisomorphisms.vf2 <- function(graph1, graph2, vertex.color1, 83 vertex.color2, edge.color1, 84 edge.color2) { 85 # Argument checks 86 if (!is_igraph(graph1)) { stop("Not a graph object") } 87 if (!is_igraph(graph2)) { stop("Not a graph object") } 88 if (missing(vertex.color1)) { 89 if ("color" %in% vertex_attr_names(graph1)) { 90 vertex.color1 <- V(graph1)$color 91 } else { 92 vertex.color1 <- NULL 93 } 94 } 95 if (!is.null(vertex.color1)) { 96 vertex.color1 <- as.integer(vertex.color1)-1L 97 } 98 if (missing(vertex.color2)) { 99 if ("color" %in% vertex_attr_names(graph2)) { 100 vertex.color2 <- V(graph2)$color 101 } else { 102 vertex.color2 <- NULL 103 } 104 } 105 if (!is.null(vertex.color2)) { 106 vertex.color2 <- as.integer(vertex.color2)-1L 107 } 108 if (missing(edge.color1)) { 109 if ("color" %in% edge_attr_names(graph1)) { 110 edge.color1 <- E(graph1)$color 111 } else { 112 edge.color1 <- NULL 113 } 114 } 115 if (!is.null(edge.color1)) { 116 edge.color1 <- as.integer(edge.color1)-1L 117 } 118 if (missing(edge.color2)) { 119 if ("color" %in% edge_attr_names(graph2)) { 120 edge.color2 <- E(graph2)$color 121 } else { 122 edge.color2 <- NULL 123 } 124 } 125 if (!is.null(edge.color2)) { 126 edge.color2 <- as.integer(edge.color2)-1L 127 } 128 129 on.exit( .Call(C_R_igraph_finalizer) ) 130 # Function call 131 res <- .Call(C_R_igraph_get_subisomorphisms_vf2, graph1, graph2, 132 vertex.color1, vertex.color2, edge.color1, edge.color2) 133 134 lapply(res, function(x) V(graph1)[x + 1]) 135} 136 137#' @export 138 139graph.isoclass.subgraph <- function(graph, vids) { 140 # Argument checks 141 if (!is_igraph(graph)) { stop("Not a graph object") } 142 vids <- as.igraph.vs(graph, vids)-1 143 144 on.exit( .Call(C_R_igraph_finalizer) ) 145 # Function call 146 res <- .Call(C_R_igraph_isoclass_subgraph, graph, vids) 147 res 148} 149 150#' @export 151 152graph.subisomorphic.lad <- function(pattern, target, domains=NULL, 153 induced=FALSE, map=TRUE, all.maps=FALSE, 154 time.limit=Inf) { 155 # Argument checks 156 if (!is_igraph(pattern)) { stop("Not a graph object") } 157 if (!is_igraph(target)) { stop("Not a graph object") } 158 induced <- as.logical(induced) 159 if (time.limit==Inf) { 160 time.limit <- 0L 161 } else { 162 time.limit <- as.integer(time.limit) 163 } 164 map <- as.logical(map) 165 all.maps <- as.logical(all.maps) 166 if (!is.null(domains)) { 167 if (!is.list(domains)) { 168 stop("`domains' must be a list of vertex vectors from `target'") 169 } 170 if (length(domains) != vcount(pattern)) { 171 stop("`domains' length and `pattern' number of vertices must match") 172 } 173 domains <- lapply(domains, function(x) as.igraph.vs(target, x)-1) 174 } 175 176 on.exit( .Call(C_R_igraph_finalizer) ) 177 # Function call 178 res <- .Call(C_R_igraph_subisomorphic_lad, pattern, target, domains, 179 induced, time.limit, map, all.maps) 180 181 if (map) { 182 res$map <- res$map + 1 183 if (igraph_opt("add.vertex.names") && is_named(target)) { 184 names(res$map) <- V(target)$name[res$map] 185 } 186 } 187 if (all.maps) res$maps <- lapply(res$maps, function(x) V(target)[x+1]) 188 189 res 190} 191 192## ---------------------------------------------------------------------- 193## NEW API 194 195#' Decide if two graphs are isomorphic 196#' 197#' @section \sQuote{auto} method: 198#' It tries to select the appropriate method based on the two graphs. 199#' This is the algorithm it uses: 200#' \enumerate{ 201#' \item If the two graphs do not agree on their order and size 202#' (i.e. number of vertices and edges), then return \code{FALSE}. 203#' \item If the graphs have three or four vertices, then the 204#' \sQuote{direct} method is used. 205#' \item If the graphs are directed, then the \sQuote{vf2} method is 206#' used. 207#' \item Otherwise the \sQuote{bliss} method is used. 208#' } 209#' 210#' @section \sQuote{direct} method: 211#' This method only works on graphs with three or four vertices, 212#' and it is based on a pre-calculated and stored table. It does not 213#' have any extra arguments. 214#' 215#' @section \sQuote{vf2} method: 216#' This method uses the VF2 algorithm by Cordella, Foggia et al., see 217#' references below. It supports vertex and edge colors and have the 218#' following extra arguments: 219#' \describe{ 220#' \item{vertex.color1, vertex.color2}{Optional integer vectors giving the 221#' colors of the vertices for colored graph isomorphism. If they 222#' are not given, but the graph has a \dQuote{color} vertex attribute, 223#' then it will be used. If you want to ignore these attributes, then 224#' supply \code{NULL} for both of these arguments. See also examples 225#' below.} 226#' \item{edge.color1, edge.color2}{Optional integer vectors giving the 227#' colors of the edges for edge-colored (sub)graph isomorphism. If they 228#' are not given, but the graph has a \dQuote{color} edge attribute, 229#' then it will be used. If you want to ignore these attributes, then 230#' supply \code{NULL} for both of these arguments.} 231#' } 232#' 233#' @section \sQuote{bliss} method: 234#' Uses the BLISS algorithm by Junttila and Kaski, and it works for 235#' undirected graphs. For both graphs the 236#' \code{\link{canonical_permutation}} and then the \code{\link{permute}} 237#' function is called to transfer them into canonical form; finally the 238#' canonical forms are compared. 239#' Extra arguments: 240#' \describe{ 241#' \item{sh1}{Character constant, the heuristics to use in the BLISS 242#' algorithm, for \code{graph1}. See the \code{sh} argument of 243#' \code{\link{canonical_permutation}} for possible values.} 244#' \item{sh2}{Character constant, the heuristics to use in the BLISS 245#' algorithm, for \code{graph2}. See the \code{sh} argument of 246#' \code{\link{canonical_permutation}} for possible values.} 247#' } 248#' \code{sh1} and \code{sh2} default to \sQuote{fm}. 249#' 250#' @param graph1 The first graph. 251#' @param graph2 The second graph. 252#' @param method The method to use. Possible values: \sQuote{auto}, 253#' \sQuote{direct}, \sQuote{vf2}, \sQuote{bliss}. See their details 254#' below. 255#' @param ... Additional arguments, passed to the various methods. 256#' @return Logical scalar, \code{TRUE} if the graphs are isomorphic. 257#' 258#' @aliases graph.isomorphic graph.isomorphic.34 graph.isomorphic.vf2 259#' graph.isomorphic.bliss 260#' 261#' @references 262#' Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical 263#' Labeling Tool for Large and Sparse Graphs, \emph{Proceedings of the 264#' Ninth Workshop on Algorithm Engineering and Experiments and the Fourth 265#' Workshop on Analytic Algorithms and Combinatorics.} 2007. 266#' 267#' LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm 268#' for matching large graphs, \emph{Proc. of the 3rd IAPR TC-15 Workshop 269#' on Graphbased Representations in Pattern Recognition}, 149--159, 2001. 270#' 271#' @export 272#' @family graph isomorphism 273#' @examples 274#' # create some non-isomorphic graphs 275#' g1 <- graph_from_isomorphism_class(3, 10) 276#' g2 <- graph_from_isomorphism_class(3, 11) 277#' isomorphic(g1, g2) 278#' 279#' # create two isomorphic graphs, by permuting the vertices of the first 280#' g1 <- barabasi.game(30, m=2, directed=FALSE) 281#' g2 <- permute(g1, sample(vcount(g1))) 282#' # should be TRUE 283#' isomorphic(g1, g2) 284#' isomorphic(g1, g2, method = "bliss") 285#' isomorphic(g1, g2, method = "vf2") 286#' 287#' # colored graph isomorphism 288#' g1 <- make_ring(10) 289#' g2 <- make_ring(10) 290#' isomorphic(g1, g2) 291#' 292#' V(g1)$color <- rep(1:2, length = vcount(g1)) 293#' V(g2)$color <- rep(2:1, length = vcount(g2)) 294#' # consider colors by default 295#' count_isomorphisms(g1, g2) 296#' # ignore colors 297#' count_isomorphisms(g1, g2, vertex.color1 = NULL, 298#' vertex.color2 = NULL) 299 300isomorphic <- function(graph1, graph2, method = c("auto", "direct", 301 "vf2", "bliss"), ...) { 302 303 if (!is_igraph(graph1)) { stop("Not a graph object") } 304 if (!is_igraph(graph2)) { stop("Not a graph object") } 305 method <- igraph.match.arg(method) 306 307 if (method == "auto") { 308 on.exit( .Call(C_R_igraph_finalizer) ) 309 .Call(C_R_igraph_isomorphic, graph1, graph2) 310 311 } else if (method == "direct") { 312 on.exit(.Call(C_R_igraph_finalizer)) 313 .Call(C_R_igraph_isomorphic_34, graph1, graph2) 314 315 } else if (method == "vf2") { 316 graph.isomorphic.vf2(graph1, graph2, ...)$iso 317 318 } else if (method == "bliss") { 319 graph.isomorphic.bliss(graph1, graph2, ...)$iso 320 321 } 322} 323 324#' @export 325#' @rdname isomorphic 326 327is_isomorphic_to <- isomorphic 328 329 330#' Decide if a graph is subgraph isomorphic to another one 331#' 332#' @section \sQuote{auto} method: 333#' This method currently selects \sQuote{lad}, always, as it seems 334#' to be superior on most graphs. 335#' 336#' @section \sQuote{lad} method: 337#' This is the LAD algorithm by Solnon, see the reference below. It has 338#' the following extra arguments: 339#' \describe{ 340#' \item{domains}{If not \code{NULL}, then it specifies matching 341#' restrictions. It must be a list of \code{target} vertex sets, given 342#' as numeric vertex ids or symbolic vertex names. The length of the 343#' list must be \code{vcount(pattern)} and for each vertex in 344#' \code{pattern} it gives the allowed matching vertices in 345#' \code{target}. Defaults to \code{NULL}.} 346#' \item{induced}{Logical scalar, whether to search for an induced 347#' subgraph. It is \code{FALSE} by default.} 348#' \item{time.limit}{The processor time limit for the computation, in 349#' seconds. It defaults to \code{Inf}, which means no limit.} 350#' } 351#' 352#' @section \sQuote{vf2} method: 353#' This method uses the VF2 algorithm by Cordella, Foggia et al., see 354#' references below. It supports vertex and edge colors and have the 355#' following extra arguments: 356#' \describe{ 357#' \item{vertex.color1, vertex.color2}{Optional integer vectors giving the 358#' colors of the vertices for colored graph isomorphism. If they 359#' are not given, but the graph has a \dQuote{color} vertex attribute, 360#' then it will be used. If you want to ignore these attributes, then 361#' supply \code{NULL} for both of these arguments. See also examples 362#' below.} 363#' \item{edge.color1, edge.color2}{Optional integer vectors giving the 364#' colors of the edges for edge-colored (sub)graph isomorphism. If they 365#' are not given, but the graph has a \dQuote{color} edge attribute, 366#' then it will be used. If you want to ignore these attributes, then 367#' supply \code{NULL} for both of these arguments.} 368#' } 369#' 370#' @param pattern The smaller graph, it might be directed or 371#' undirected. Undirected graphs are treated as directed graphs with 372#' mutual edges. 373#' @param target The bigger graph, it might be directed or 374#' undirected. Undirected graphs are treated as directed graphs with 375#' mutual edges. 376#' @param method The method to use. Possible values: \sQuote{auto}, 377#' \sQuote{lad}, \sQuote{vf2}. See their details below. 378#' @param ... Additional arguments, passed to the various methods. 379#' @return Logical scalar, \code{TRUE} if the \code{pattern} is 380#' isomorphic to a (possibly induced) subgraph of \code{target}. 381#' 382#' @aliases graph.subisomorphic.vf2 graph.subisomorphic.lad 383#' 384#' @references 385#' LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm 386#' for matching large graphs, \emph{Proc. of the 3rd IAPR TC-15 Workshop 387#' on Graphbased Representations in Pattern Recognition}, 149--159, 2001. 388#' 389#' C. Solnon: AllDifferent-based Filtering for Subgraph Isomorphism, 390#' \emph{Artificial Intelligence} 174(12-13):850--864, 2010. 391#' 392#' @export 393#' @family graph isomorphism 394#' @examples 395#' # A LAD example 396#' pattern <- make_graph(~ 1:2:3:4:5, 397#' 1 - 2:5, 2 - 1:5:3, 3 - 2:4, 4 - 3:5, 5 - 4:2:1) 398#' target <- make_graph(~ 1:2:3:4:5:6:7:8:9, 399#' 1 - 2:5:7, 2 - 1:5:3, 3 - 2:4, 4 - 3:5:6:8:9, 400#' 5 - 1:2:4:6:7, 6 - 7:5:4:9, 7 - 1:5:6, 401#' 8 - 4:9, 9 - 6:4:8) 402#' domains <- list(`1` = c(1,3,9), `2` = c(5,6,7,8), `3` = c(2,4,6,7,8,9), 403#' `4` = c(1,3,9), `5` = c(2,4,8,9)) 404#' subgraph_isomorphisms(pattern, target) 405#' subgraph_isomorphisms(pattern, target, induced = TRUE) 406#' subgraph_isomorphisms(pattern, target, domains = domains) 407#' 408#' # Directed LAD example 409#' pattern <- make_graph(~ 1:2:3, 1 -+ 2:3) 410#' dring <- make_ring(10, directed = TRUE) 411#' subgraph_isomorphic(pattern, dring) 412 413subgraph_isomorphic <- function(pattern, target, 414 method = c("auto", "lad", "vf2"), ...) { 415 416 method <- igraph.match.arg(method) 417 418 if (method == "auto") method <- "lad" 419 420 if (method == "lad") { 421 graph.subisomorphic.lad(pattern, target, map = FALSE, all.maps = FALSE, 422 ...)$iso 423 424 } else if (method == "vf2") { 425 graph.subisomorphic.vf2(target, pattern, ...)$iso 426 427 } 428} 429 430 431#' @export 432#' @rdname subgraph_isomorphic 433 434is_subgraph_isomorphic_to <- subgraph_isomorphic 435 436 437#' Count the number of isomorphic mappings between two graphs 438#' 439#' @param graph1 The first graph. 440#' @param graph2 The second graph. 441#' @param method Currently only \sQuote{vf2} is supported, see 442#' \code{\link{isomorphic}} for details about it and extra arguments. 443#' @param ... Passed to the individual methods. 444#' @return Number of isomorphic mappings between the two graphs. 445#' 446#' @include auto.R 447#' @aliases graph.count.isomorphisms.vf2 448#' 449#' @references 450#' LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm 451#' for matching large graphs, \emph{Proc. of the 3rd IAPR TC-15 Workshop 452#' on Graphbased Representations in Pattern Recognition}, 149--159, 2001. 453#' 454#' @export 455#' @family graph isomorphism 456#' @examples 457#' # colored graph isomorphism 458#' g1 <- make_ring(10) 459#' g2 <- make_ring(10) 460#' isomorphic(g1, g2) 461#' 462#' V(g1)$color <- rep(1:2, length = vcount(g1)) 463#' V(g2)$color <- rep(2:1, length = vcount(g2)) 464#' # consider colors by default 465#' count_isomorphisms(g1, g2) 466#' # ignore colors 467#' count_isomorphisms(g1, g2, vertex.color1 = NULL, 468#' vertex.color2 = NULL) 469 470count_isomorphisms <- function(graph1, graph2, method = "vf2", ...) { 471 472 method <- igraph.match.arg(method) 473 474 if (method == "vf2") { 475 graph.count.isomorphisms.vf2(graph1, graph2, ...) 476 } 477 478} 479 480 481#' Count the isomorphic mappings between a graph and the subgraphs of 482#' another graph 483#' 484#' @section \sQuote{lad} method: 485#' This is the LAD algorithm by Solnon, see the reference below. It has 486#' the following extra arguments: 487#' \describe{ 488#' \item{domains}{If not \code{NULL}, then it specifies matching 489#' restrictions. It must be a list of \code{target} vertex sets, given 490#' as numeric vertex ids or symbolic vertex names. The length of the 491#' list must be \code{vcount(pattern)} and for each vertex in 492#' \code{pattern} it gives the allowed matching vertices in 493#' \code{target}. Defaults to \code{NULL}.} 494#' \item{induced}{Logical scalar, whether to search for an induced 495#' subgraph. It is \code{FALSE} by default.} 496#' \item{time.limit}{The processor time limit for the computation, in 497#' seconds. It defaults to \code{Inf}, which means no limit.} 498#' } 499#' 500#' @section \sQuote{vf2} method: 501#' This method uses the VF2 algorithm by Cordella, Foggia et al., see 502#' references below. It supports vertex and edge colors and have the 503#' following extra arguments: 504#' \describe{ 505#' \item{vertex.color1, vertex.color2}{Optional integer vectors giving the 506#' colors of the vertices for colored graph isomorphism. If they 507#' are not given, but the graph has a \dQuote{color} vertex attribute, 508#' then it will be used. If you want to ignore these attributes, then 509#' supply \code{NULL} for both of these arguments. See also examples 510#' below.} 511#' \item{edge.color1, edge.color2}{Optional integer vectors giving the 512#' colors of the edges for edge-colored (sub)graph isomorphism. If they 513#' are not given, but the graph has a \dQuote{color} edge attribute, 514#' then it will be used. If you want to ignore these attributes, then 515#' supply \code{NULL} for both of these arguments.} 516#' } 517#' 518#' @param pattern The smaller graph, it might be directed or 519#' undirected. Undirected graphs are treated as directed graphs with 520#' mutual edges. 521#' @param target The bigger graph, it might be directed or 522#' undirected. Undirected graphs are treated as directed graphs with 523#' mutual edges. 524#' @param method The method to use. Possible values: 525#' \sQuote{lad}, \sQuote{vf2}. See their details below. 526#' @param ... Additional arguments, passed to the various methods. 527#' @return Logical scalar, \code{TRUE} if the \code{pattern} is 528#' isomorphic to a (possibly induced) subgraph of \code{target}. 529#' 530#' @aliases graph.count.subisomorphisms.vf2 531#' 532#' @references 533#' LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm 534#' for matching large graphs, \emph{Proc. of the 3rd IAPR TC-15 Workshop 535#' on Graphbased Representations in Pattern Recognition}, 149--159, 2001. 536#' 537#' C. Solnon: AllDifferent-based Filtering for Subgraph Isomorphism, 538#' \emph{Artificial Intelligence} 174(12-13):850--864, 2010. 539#' 540#' @export 541#' @family graph isomorphism 542 543count_subgraph_isomorphisms <- function(pattern, target, 544 method = c("lad", "vf2"), ...) { 545 546 method <- igraph.match.arg(method) 547 548 if (method == "lad") { 549 length(graph.subisomorphic.lad(pattern, target, all.maps = TRUE, ...)$maps) 550 551 } else if (method == "vf2") { 552 graph.count.subisomorphisms.vf2(target, pattern, ...) 553 } 554 555} 556 557 558#' Calculate all isomorphic mappings between the vertices of two graphs 559#' 560#' @param graph1 The first graph. 561#' @param graph2 The second graph. 562#' @param method Currently only \sQuote{vf2} is supported, see 563#' \code{\link{isomorphic}} for details about it and extra arguments. 564#' @param ... Extra arguments, passed to the various methods. 565#' @return A list of vertex sequences, corresponding to all 566#' mappings from the first graph to the second. 567#' 568#' @aliases graph.get.isomorphisms.vf2 569#' 570#' @export 571#' @family graph isomorphism 572 573isomorphisms <- function(graph1, graph2, method = "vf2", ...) { 574 575 method <- igraph.match.arg(method) 576 577 if (method == "vf2") { 578 graph.get.isomorphisms.vf2(graph1, graph2, ...) 579 } 580 581} 582 583 584#' All isomorphic mappings between a graph and subgraphs of another graph 585#' 586#' @section \sQuote{lad} method: 587#' This is the LAD algorithm by Solnon, see the reference below. It has 588#' the following extra arguments: 589#' \describe{ 590#' \item{domains}{If not \code{NULL}, then it specifies matching 591#' restrictions. It must be a list of \code{target} vertex sets, given 592#' as numeric vertex ids or symbolic vertex names. The length of the 593#' list must be \code{vcount(pattern)} and for each vertex in 594#' \code{pattern} it gives the allowed matching vertices in 595#' \code{target}. Defaults to \code{NULL}.} 596#' \item{induced}{Logical scalar, whether to search for an induced 597#' subgraph. It is \code{FALSE} by default.} 598#' \item{time.limit}{The processor time limit for the computation, in 599#' seconds. It defaults to \code{Inf}, which means no limit.} 600#' } 601#' 602#' @section \sQuote{vf2} method: 603#' This method uses the VF2 algorithm by Cordella, Foggia et al., see 604#' references below. It supports vertex and edge colors and have the 605#' following extra arguments: 606#' \describe{ 607#' \item{vertex.color1, vertex.color2}{Optional integer vectors giving the 608#' colors of the vertices for colored graph isomorphism. If they 609#' are not given, but the graph has a \dQuote{color} vertex attribute, 610#' then it will be used. If you want to ignore these attributes, then 611#' supply \code{NULL} for both of these arguments. See also examples 612#' below.} 613#' \item{edge.color1, edge.color2}{Optional integer vectors giving the 614#' colors of the edges for edge-colored (sub)graph isomorphism. If they 615#' are not given, but the graph has a \dQuote{color} edge attribute, 616#' then it will be used. If you want to ignore these attributes, then 617#' supply \code{NULL} for both of these arguments.} 618#' } 619#' 620#' @param pattern The smaller graph, it might be directed or 621#' undirected. Undirected graphs are treated as directed graphs with 622#' mutual edges. 623#' @param target The bigger graph, it might be directed or 624#' undirected. Undirected graphs are treated as directed graphs with 625#' mutual edges. 626#' @param method The method to use. Possible values: \sQuote{auto}, 627#' \sQuote{lad}, \sQuote{vf2}. See their details below. 628#' @param ... Additional arguments, passed to the various methods. 629#' @return A list of vertex sequences, corresponding to all 630#' mappings from the first graph to the second. 631#' 632#' @aliases graph.get.subisomorphisms.vf2 633#' 634#' @export 635#' @family graph isomorphism 636 637subgraph_isomorphisms <- function(pattern, target, 638 method = c("lad", "vf2"), ...) { 639 640 method <- igraph.match.arg(method) 641 642 if (method == "lad") { 643 graph.subisomorphic.lad(pattern, target, all.maps = TRUE, ...)$maps 644 645 } else if (method == "vf2") { 646 graph.get.subisomorphisms.vf2(target, pattern, ...) 647 } 648 649} 650 651 652#' Isomorphism class of a graph 653#' 654#' The isomorphism class is a non-negative integer number. 655#' Graphs (with the same number of vertices) having the same isomorphism 656#' class are isomorphic and isomorphic graphs always have the same 657#' isomorphism class. Currently it can handle only graphs with 3 or 4 658#' vertices. 659#' 660#' @param graph The input graph. 661#' @param v Optionally a vertex sequence. If not missing, then an induced 662#' subgraph of the input graph, consisting of this vertices, is used. 663#' @return An integer number. 664#' 665#' @aliases graph.isoclass graph.isoclass.subgraph 666#' 667#' @export 668#' @family graph isomorphism 669#' @examples 670#' # create some non-isomorphic graphs 671#' g1 <- graph_from_isomorphism_class(3, 10) 672#' g2 <- graph_from_isomorphism_class(3, 11) 673#' isomorphism_class(g1) 674#' isomorphism_class(g2) 675#' isomorphic(g1, g2) 676 677isomorphism_class <- function(graph, v) { 678 679 if (missing(v)) { 680 graph.isoclass(graph) 681 682 } else { 683 graph.isoclass.subgraph(graph, v) 684 } 685 686} 687 688 689#' Create a graph from an isomorphism class 690#' 691#' The isomorphism class is a non-negative integer number. 692#' Graphs (with the same number of vertices) having the same isomorphism 693#' class are isomorphic and isomorphic graphs always have the same 694#' isomorphism class. Currently it can handle only graphs with 3 or 4 695#' vertices. 696#' 697#' @param size The number of vertices in the graph. 698#' @param number The isomorphism class. 699#' @param directed Whether to create a directed graph (the default). 700#' @return An igraph object, the graph of the given size, directedness 701#' and isomorphism class. 702#' 703#' @aliases graph.isocreate 704#' @include auto.R 705#' 706#' @family graph isomorphism 707 708graph_from_isomorphism_class <- graph_from_isomorphism_class 709 710 711#' Canonical permutation of a graph 712#' 713#' The canonical permutation brings every isomorphic graphs into the same 714#' (labeled) graph. 715#' 716#' \code{canonical_permutation} computes a permutation which brings the graph 717#' into canonical form, as defined by the BLISS algorithm. All isomorphic 718#' graphs have the same canonical form. 719#' 720#' See the paper below for the details about BLISS. This and more information 721#' is available at \url{http://www.tcs.hut.fi/Software/bliss/index.html}. 722#' 723#' The possible values for the \code{sh} argument are: \describe{ 724#' \item{"f"}{First non-singleton cell.} \item{"fl"}{First largest 725#' non-singleton cell.} \item{"fs"}{First smallest non-singleton cell.} 726#' \item{"fm"}{First maximally non-trivially connectec non-singleton 727#' cell.} \item{"flm"}{Largest maximally non-trivially connected 728#' non-singleton cell.} \item{"fsm"}{Smallest maximally non-trivially 729#' connected non-singleton cell.} } See the paper in references for details 730#' about these. 731#' 732#' @aliases canonical.permutation canonical_permutation 733#' @param graph The input graph, treated as undirected. 734#' @param sh Type of the heuristics to use for the BLISS algorithm. See details 735#' for possible values. 736#' @return A list with the following members: \item{labeling}{The canonical 737#' permutation which takes the input graph into canonical form. A numeric 738#' vector, the first element is the new label of vertex 0, the second element 739#' for vertex 1, etc. } \item{info}{Some information about the BLISS 740#' computation. A named list with the following members: \describe{ 741#' \item{"nof_nodes"}{The number of nodes in the search tree.} 742#' \item{"nof_leaf_nodes"}{The number of leaf nodes in the search tree.} 743#' \item{"nof_bad_nodes"}{Number of bad nodes.} 744#' \item{"nof_canupdates"}{Number of canrep updates.} 745#' \item{"max_level"}{Maximum level.} \item{"group_size"}{The size 746#' of the automorphism group of the input graph, as a string. This number is 747#' exact if igraph was compiled with the GMP library, and approximate 748#' otherwise.} } } 749#' @author Tommi Junttila for BLISS, Gabor Csardi 750#' \email{csardi.gabor@@gmail.com} for the igraph and R interfaces. 751#' @seealso \code{\link{permute}} to apply a permutation to a graph, 752#' \code{\link{graph.isomorphic}} for deciding graph isomorphism, possibly 753#' based on canonical labels. 754#' @references Tommi Junttila and Petteri Kaski: Engineering an Efficient 755#' Canonical Labeling Tool for Large and Sparse Graphs, \emph{Proceedings of 756#' the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth 757#' Workshop on Analytic Algorithms and Combinatorics.} 2007. 758#' @keywords graphs 759#' @examples 760#' 761#' ## Calculate the canonical form of a random graph 762#' g1 <- sample_gnm(10, 20) 763#' cp1 <- canonical_permutation(g1) 764#' cf1 <- permute(g1, cp1$labeling) 765#' 766#' ## Do the same with a random permutation of it 767#' g2 <- permute(g1, sample(vcount(g1))) 768#' cp2 <- canonical_permutation(g2) 769#' cf2 <- permute(g2, cp2$labeling) 770#' 771#' ## Check that they are the same 772#' el1 <- as_edgelist(cf1) 773#' el2 <- as_edgelist(cf2) 774#' el1 <- el1[ order(el1[,1], el1[,2]), ] 775#' el2 <- el2[ order(el2[,1], el2[,2]), ] 776#' all(el1 == el2) 777#' @export 778 779canonical_permutation <- canonical_permutation 780 781 782#' Permute the vertices of a graph 783#' 784#' Create a new graph, by permuting vertex ids. 785#' 786#' This function creates a new graph from the input graph by permuting its 787#' vertices according to the specified mapping. Call this function with the 788#' output of \code{\link{canonical_permutation}} to create the canonical form 789#' of a graph. 790#' 791#' \code{permute} keeps all graph, vertex and edge attributes of the graph. 792#' 793#' @aliases permute.vertices permute 794#' @param graph The input graph, it can directed or undirected. 795#' @param permutation A numeric vector giving the permutation to apply. The 796#' first element is the new id of vertex 1, etc. Every number between one and 797#' \code{vcount(graph)} must appear exactly once. 798#' @return A new graph object. 799#' @author Gabor Csardi \email{csardi.gabor@@gmail.com} 800#' @seealso \code{\link{canonical_permutation}} 801#' @keywords graphs 802#' @examples 803#' 804#' # Random permutation of a random graph 805#' g <- sample_gnm(20, 50) 806#' g2 <- permute(g, sample(vcount(g))) 807#' graph.isomorphic(g, g2) 808#' 809#' # Permutation keeps all attributes 810#' g$name <- "Random graph, Gnm, 20, 50" 811#' V(g)$name <- letters[1:vcount(g)] 812#' E(g)$weight <- sample(1:5, ecount(g), replace=TRUE) 813#' g2 <- permute(g, sample(vcount(g))) 814#' graph.isomorphic(g, g2) 815#' g2$name 816#' V(g2)$name 817#' E(g2)$weight 818#' all(sort(E(g2)$weight) == sort(E(g)$weight)) 819#' @export 820 821permute <- permute 822 823 824#' Number of automorphisms 825#' 826#' Calculate the number of automorphisms of a graph, i.e. the number of 827#' isomorphisms to itself. 828#' 829#' An automorphism of a graph is a permutation of its vertices which brings the 830#' graph into itself. 831#' 832#' This function calculates the number of automorphism of a graph using the 833#' BLISS algorithm. See also the BLISS homepage at 834#' \url{http://www.tcs.hut.fi/Software/bliss/index.html}. 835#' 836#' @aliases graph.automorphisms automorphisms 837#' @param graph The input graph, it is treated as undirected. 838#' @param sh The splitting heuristics for the BLISS algorithm. Possible values 839#' are: \sQuote{\code{f}}: first non-singleton cell, \sQuote{\code{fl}}: first 840#' largest non-singleton cell, \sQuote{\code{fs}}: first smallest non-singleton 841#' cell, \sQuote{\code{fm}}: first maximally non-trivially connected 842#' non-singleton cell, \sQuote{\code{flm}}: first largest maximally 843#' non-trivially connected non-singleton cell, \sQuote{\code{fsm}}: first 844#' smallest maximally non-trivially connected non-singleton cell. 845#' @return A named list with the following members: \item{group_size}{The size 846#' of the automorphism group of the input graph, as a string. This number is 847#' exact if igraph was compiled with the GMP library, and approximate 848#' otherwise.} \item{nof_nodes}{The number of nodes in the search tree.} 849#' \item{nof_leaf_nodes}{The number of leaf nodes in the search tree.} 850#' \item{nof_bad_nodes}{Number of bad nodes.} \item{nof_canupdates}{Number of 851#' canrep updates.} \item{max_level}{Maximum level.} 852#' @author Tommi Junttila (\url{http://users.ics.aalto.fi/tjunttil/}) for BLISS 853#' and Gabor Csardi \email{csardi.gabor@@gmail.com} for the igraph glue code 854#' and this manual page. 855#' @seealso \code{\link{canonical_permutation}}, \code{\link{permute}} 856#' @references Tommi Junttila and Petteri Kaski: Engineering an Efficient 857#' Canonical Labeling Tool for Large and Sparse Graphs, \emph{Proceedings of 858#' the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth 859#' Workshop on Analytic Algorithms and Combinatorics.} 2007. 860#' @keywords graphs 861#' @examples 862#' 863#' ## A ring has n*2 automorphisms, you can "turn" it by 0-9 vertices 864#' ## and each of these graphs can be "flipped" 865#' g <- make_ring(10) 866#' automorphisms(g) 867#' @export 868 869automorphisms <- automorphisms 870