Description Usage Arguments Details Value Author(s) References See Also Examples
Updates the set of (maximal) cliques of a given undirected graph when removing one edge.
1  qpUpdateCliquesRemoving(g, clqlst, v, w, verbose=TRUE)

g 
either a 
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

v 
vertex of the edge being removed. 
w 
vertex of the edge being removed. 
verbose 
show progress on calculations. 
To find the list of all (maximal) cliques in an undirected graph is an NPhard
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).
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 NPhard (see Garey and Johnson, 1979)
and therefore depending on the input graph its computation may become unfeasible.
R. Castelo
Garey, M.R. and Johnson D.S. Computers and intractability: a guide to the theory of NPcompleteness. W.H. Freeman, San Francisco, 1979.
Stix, V. Finding all maximal cliques in dynamic graphs Comput. Optimization and Appl., 27:173186, 2004.
qpCliqueNumber
qpGetCliques
qpIPF
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  ## the example below takes about 30 seconds to execute and for that reason
## it is not executed by default
## Not run:
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
## End(Not run)

Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.