# Manber's graph-partitioning algorithm implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File.

Generally speaking he wants to divide vertices of a weighted, directed graph G=(V,E) into two sets V1 and V2 in such a way, that the sum of the weights of the edges that go from V1 to V2 is maximized.

He states that since this is a NP-complete problem he chose to first partition the graph randomly and then examine each vertex to see if switching this vertex to the opposite set would improve the total. This whole process is repeated several times for several random initial partitions to see which one of them yields the best results.

The following pseudocode is provided:

Best_Non_Overlapping_Pairs(G: weighted graph)
repeat k times { k is a constant; we used 100 }
randomly assign each vertex to either V1 or V2 with equal probability;
for each vertex v in V do
put v on the queue;
loop until the queue is empty
pop v from the queue;
if switching v to the opposite set improves the sum of weights then
switch v;
-------->   if switching v caused other vertices, not already on the queue, to prefer to switch then put them on the queue;
store the best solution to date;


I'm not sure what I'm supposed to code for part marked with an arrow. How do I check for the "preference" of non queued vertices? Is it even needed? I've implemented the algorithm without this part and it seems to work as intended. Or perhaps someone is familiar with a library that provides this implementation?

## migrated from stackoverflow.comOct 5 '18 at 18:20

This question came from our site for professional and enthusiast programmers.