qpUpdateCliquesRemoving(qpgraph)
qpUpdateCliquesRemoving()所属R语言包：qpgraph
Update clique list when removing one edge
取出一条边时，更新集团名单
译者：生物统计家园网 机器人LoveR
描述----------Description----------
Updates the set of (maximal) cliques of a given undirected graph when removing one edge.
更新集取出一条边时，一个给定的无向图（最大）拉帮结派。
用法----------Usage----------
qpUpdateCliquesRemoving(g, clqlst, v, w, verbose=TRUE)
参数----------Arguments----------
参数：g
either a graphNEL object or an adjacency matrix of the given undirected graph.
无论是graphNEL对象或给定的无向图的邻接矩阵。
参数：clqlst
list of cliques of the graph encoded in g. this list should start on element n+1 (for n vertices) while between elements 1 to n there should be references to the cliques to which each of the 1 to n vertices belong to (i.e., the output of qpGetCliques) with parameter clqspervtx=TRUE.
在G编码的图形拉帮结派的名单。而1到n元素之间应该有拉帮结派，每1到n个顶点属于此列表元素n +1（n个顶点）开始（即，qpGetCliques的输出）参数clqspervtx=TRUE。
参数：v
vertex of the edge being removed.
顶点的边缘被删除。
参数：w
vertex of the edge being removed.
顶点的边缘被删除。
参数：verbose
show progress on calculations.
显示在计算方面取得的进展。
Details
详情----------Details----------
To find the list of all (maximal) cliques in an undirected graph is an NP-hard problem which means that its computational cost is bounded by an exponential running time (Garey and Johnson, 1979). For this reason, this is an extremely time and memory consuming computation for large dense graphs. If we spend the time to obtain one such list of cliques and we remove one edge of the graph with this function we may be able to update the set of maximal cliques instead of having to generate it again entirely with qpGetCliques but it requires that in the first call to qpGetCliques we set clqspervtx=TRUE. It calls a C implementation of the algorithm from Stix (2004).
要找到一个无向图中所有派系（最大）是一个NP-难的问题，这意味着指数的运行时间解读彼得凯和约翰逊（1979年）的范围内，其计算成本。出于这个原因，这是一个非常时间和内存的大型稠密图的消费计算。如果我们花时间去获得一个这样的列表，拉帮结派，我们删除一个与此功能的图形的边缘，我们也许能够更新的最大派系，而不是再次生成它完全以qpGetCliques但它需要在第一次调用qpGetCliques设置clqspervtx=TRUE。它要求从STIX（2004）算法的C实现。
值----------Value----------
The updated list of maximal cliques after removing one edge from the input graph. Note that because the corresponding input clique list had to be generated with the argument clqspervtx=TRUE in the call to qpGetCliques, the resulting updated list of cliques also includes in its first p entries (p=number of variables) the indices of the cliques where that particular vertex belongs to. Notice also that although this strategy might be in general more efficient than generating again the entire list of cliques, when removing one edge from the graph, the clique enumeration problem remains NP-hard (see Garey and Johnson, 1979) and therefore depending on the input graph its computation may become unfeasible.
取出后输入图从一个边缘的最大派系的更新列表。请注意，因为相应的输入集团名单参数clqspervtx=TRUE在调用qpGetCliques，由此产生的更新的派系名单中还包括在其第一个p项（P =变量数）拉帮结派的地方，特别是顶点属于指数。还要注意，虽然这一战略可能在一般情况下，较有效地再次生成的整个派系名单，从图中取出一条边时，集团枚举问题仍然是NP-难（见解读彼得凯和约翰逊，1979年），因此根据上输入图它的计算可能成为不可行的。
作者（S）----------Author(s)----------
R. Castelo
参考文献----------References----------
theory of NP-completeness. W.H. Freeman, San Francisco, 1979.
Comput. Optimization and Appl., 27:173-186, 2004.
参见----------See Also----------
qpCliqueNumber qpGetCliques qpIPF
qpCliqueNumberqpGetCliquesqpIPF
举例----------Examples----------
require(graph)
set.seed(123)
nVar <- 1000
g1 <- randomEGraph(V=as.character(1:nVar), p=0.1)
g1
clqs1 <- qpGetCliques(g1, clqspervtx=TRUE, verbose=FALSE)
length(clqs1)
g2 <- removeEdge(from="1", to=edges(g1)[["1"]][1], g1)
g2
system.time(clqs2a <- qpGetCliques(g2, verbose=FALSE))
system.time(clqs2b <- qpUpdateCliquesRemoving(g1, clqs1, "1", edges(g1)[["1"]][1], verbose=FALSE))
length(clqs2a)
length(clqs2b)-nVar
转载请注明:出自 生物统计家园网(http://www.biostatistic.net)。
注：
注1：为了方便大家学习，本文档为生物统计家园网机器人LoveR翻译而成，仅供个人R语言学习参考使用，生物统计家园保留版权。
注2：由于是机器人自动翻译，难免有不准确之处，使用时仔细对照中、英文内容进行反复理解，可以帮助R语言的学习。
注3：如遇到不准确之处，请在本贴的后面进行回帖，我们会逐渐进行修订。
|
发表于 2012-2-26 11:41:52
