(WIP) SB Graph partitioner algorithms

[francosansone]

To compute gain of exchange intervals

$\mathbf{compute\_ gain} (A_c, B_c, EC'_A, EC'_B, IC'_A, IC'_B)$

• $GAIN = \{ g_{ij} | \#(EC'_A(A_i) \uplus EC'_B(B_j)) - \#IC'_A(A_i) - \# IC'_B(B_j) \}$ Intervals length must be taken into account.
• $\mathbf{return} GAIN$

---

Update external cost, internal cost and gain values after each iteration.

To compute removed edges:

compute_removed_edges $(i, A, s, EC, G)$

• if $\#A_i == s$
  • $removed\_EC = EC_1(A_i) $
• else
  • $A'_i = compute\_EC([A_i:A_i + s])$
  • $removed\_EC = compute\_EC(A'_i) $
• $\mathbf{return} removed\_EC$

To update EC and IC:

update_EC_IC $(i, A, s, j, B, G, EC_1, EC_2, IC)$

• $removed\_EC = EC_1(A_i) \cup EC_2(B_j) $
• if $\#A_i == s$ This means, the entire interval is moved.
  • $EC_1 = \{ e_j \setminus removed_EC : e_j \in EC \wedge i \neq j \}$
• else
  • $EC_1 = { e_j \setminus removed_EC : e_j \in EC }$
• $IC = { s \in IC(A_i) : s \in IC }$

A function that actually update EC, IC and GAIN:

update_diff $(A, B, i, j, s, GAIN, G)$

• $update\_EC\_IC(i, A, s, j, B, G, EC_A, EC_B, IC_A)$
• $update\_EC\_IC(j, B, s, i, A, G, EC_B, EC_A, IC_B)$
• $GAIN = compute\_gain(A, B, EC_A, EC_B, IC_A, IC_B)$ This may be improved updating only intervals what were affected.

---

The main algorithm:

KL-SBG ($A, B, EC_A, EC_B, IC_A, IC_B)$

• $A_c = A$
• $B_c = B$
• $EC'_A = \{ e \cap EC_B : e \in EC_A \}$ to capture edges that connect partition $A$ with $B$ (consider using key values).
• $EC'_B = \{ e \cap EC_A : e \in EC_B \}$
• $IC'_A = IC_A$ consider using key values.
• $IC'_B = IC_B$
• $max\_par\_sum = 0$
• $max\_par\_sum\_set = \emptyset$
• $GAINS = compute\_gain(A_c, B_c, EC'_A, EC'_B, IC'_A, IC'_B)$
• while $A_c \neq \emptyset \wedge B_c \neq \emptyset$
  • $<i, j, g, s> = max\_diff(GAIN)$
  • $(A', B') = update\_sets(A_c, B_c, A_v, B_v, i, j, s)$
  • $update\_sum(par\_sum, g, max\_par\_sum, max\_par\_sum\_set, A', B')$
  • $update\_diff(A_c, B_c, i, j, s, GAIN, G)$
• $\mathbf{if}(max\_par\_sum\_set \neq \emptyset):$
  • $(A^{\star}, B^{\star}) = max\_par\_sum\_set$
  • $A = (A \setminus A^{\star}) \cup B^{\star}$
  • $B = (B \setminus B^{\star}) \cup A^{\star}$
• return