Manber's graph-partitioning implementation

Question

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 $V_1$ and $V_2$ in such a way, that the sum of the weights of the edges that go from $V_1$ to $V_2$ is maximized.

He states that since this is a NP-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 the bolded part. How do I check for the "preference" of non queues vertices? Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

Answer 1

How do I check for the "preference" of non queues vertices?

The previous step was

          if switching v to the opposite set improves the sum of weights then
             switch v;

so clearly you already know how to check for the preference of a vertex. Whether or not it is in the queue is immaterial.

To do it efficiently requires some additional data storage and pre-calculation which is not explicitly described in the pseudocode. In more detail,

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times
       randomly assign each vertex to either V1 or V2 with equal probability;

       initialise two arrays of edge weight sums, internalSums and externalSums
       for each edge e = (s, t) in E do
          if s and t are in the same partition
             increment internalSums[s] and internalSums[t] by weight(e)
          else
             increment externalSums[s] and externalSums[t] by weight(e)

       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if internalSums[v] > externalSums[v]
             switch v;
             swap internalSums[v] and externalSums[v]
             for each edge e = (v, u) in E do
                update internalSums[u] and externalSums[u] appropriately
                if u is not in the queue and internalSums[u] > externalSums[u]
                   enqueue u
       store the best solution to date;

---

Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

I must confess that I would be unable to distinguish easily between the algorithm working as intended and the algorithm selecting a purely random partition and skipping the rest of the process.