private double doSingleSwap(Deque<Pair<Vertex>> swaps) {
    
    Pair<Vertex> maxPair = null;
    double maxGain = Double.NEGATIVE_INFINITY;
    
    for (Vertex v_a : unswappedA) {
      for (Vertex v_b : unswappedB) {
        
        Edge e = graph.findEdge(v_a, v_b);
        double edge_cost = (e != null) ? e.weight : 0;
        // Calculate the gain in cost if these vertices were swapped
        // subtract 2*edge_cost because this edge will still be an external edge
        // after swapping
        double gain = getVertexCost(v_a) + getVertexCost(v_b) - 2 * edge_cost;
        
        if (gain > maxGain) {
          maxPair = new Pair<Vertex>(v_a, v_b);
          maxGain = gain;
        }
        
      }
    }
    
    swapVertices(A, maxPair.first, B, maxPair.second);
    swaps.push(maxPair);
    unswappedA.remove(maxPair.first);
    unswappedB.remove(maxPair.second);
    
    return getCutCost();
  }