1
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Oct 5 '18 at 18:20

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

1
$\begingroup$

Every time you switched a vertex, you go through all vertices already not on the queue (popped) and for every of them do the following:

  1. Check if switching it to another part of the partition improves the objective function.
  2. If yes, push it onto the queue.
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.