improve_cut_flip: Improving a cut with local search

In gor: Algorithms for the Subject Graphs and Network Optimization

Improving a cut with local search

Description

Local search to improve a cut by using "neighboring" vertex subsets differing in just one element from the initial subset.

Usage

improve_cut_flip(G, K, w = NA, return.cut = TRUE)

Arguments

G	A graph
K	A cut list with components $set, $size, $weight and $cut as returned by routines build_cut_greedy, build_cut_random or compute_cut_weight. Only the $set and $weight components are used. K represents the cut to be improved
w	Weight matrix (defaults to NA). It should be zero for those edges not in G
return.cut	Boolean. Should the routine return the cut? It is passed on to compute_cut_weight on return. It defaults to TRUE

Details

Given some cut specified by a vertex subset S in a graph, this routine scans the neighboring subsets obtained from S by adding/removing a vertex from S looking for a larger cut. If such a cut is found, it replaces the starting cut and the search starts again. This iterative procedure continues until no larger cut can be found. Of course, the resulting cut is only a local maximum.

Value

A list with four components: $set contains the subset of V(g) representing the cut, $size contains the number of edges of the cut, $weight contains the weight of the cut (which coincides with $size if w is NA) and $cut contains the edges of the cut, joining vertices inside $set with vertices outside $set. When return.cut is FALSE, components $set and $cut are omitted.

Author(s)

Cesar Asensio

See Also

build_cut_random builds a random cut, build_cut_greedy builds a cut using a greedy algorithm, compute_cut_weight computes cut size, weight and edges, plot_cut plots a cut.

Examples

set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)  # Random graph

c1 <- build_cut_random(g)
c1$size    # 44
plot_cut(c1, g)

c2 <- build_cut_greedy(g)
c2$size    # 59
plot_cut(c2, g)

c3 <- improve_cut_flip(g, c1)
c3$size    # 65
plot_cut(c3,g)

c4 <- improve_cut_flip(g, c2)
c4$size    # 60
plot_cut(c4,g)

gor documentation built on May 4, 2023, 1:06 a.m.