compute_cut_weight {gor}

Compute cut weight and size

Description

Compute cut weight and size from its associated vertex set. It can also return the edges in the cut.

Usage

compute_cut_weight(S, n, eG, w = NA, return.cut = FALSE)

Arguments

S

Subset of the vertex set of the graph.

n

Size of the graph.

eG

Edgelist of the graph as returned by as_edgelist, that is, a matrix with q rows and 2 columns. Note that this is the graph format used by the routine.

w

Weight matrix or NA if all edge weights are 1. It should be zero for those edges not in G

return.cut

Boolean. Should the routine return the edges in the cut? It defaults to FALSE. When TRUE, the routine also returns the input subset S, for easier cut plotting with plot_cut.

Details

In a graph, a cut K is defined by means of a vertex subset S as the edges joining vertices inside S with vertices outside S. This routine computes these edges and their associated weight.

Value

A list with two components: $size is the number of edges in the cut, $weight is the weight of the cut, that is, the sum of the weights of the edges in the cut. If w=NA these two numbers coincide. When return.cut is TRUE, there are two additional components of the list: $cut, which contains the edges in the cut as rows of a two-column matrix, and $set, which contains the input set, as a convenience for plotting with plot_cut.

Author(s)

Cesar Asensio

See Also

build_cut_random builds a random cut, build_cut_greedy builds a cut using a greedy algorithm, improve_cut_flip uses local search to improve a cut obtained by other methods, plot_cut plots a cut.

Examples

K10 <- make_full_graph(10)
S <- c(1,4,7)
compute_cut_weight(S, gorder(K10), as_edgelist(K10))
cS <- compute_cut_weight(S, gorder(K10), as_edgelist(K10),
    return.cut = TRUE)
plot_cut(cS, K10)