¿Cómo agregar en cada enlace (un href) etiquetar un atributo rel con la ayuda de php?

Si todas las imágenes en $mydata no tienen el atributo "rel", entonces la solución es simple

$mydata = str_replace('<img ', '<img rel="lightbox"', $mydata);

En otros casos, solo si el carácter ">" no aparece en los valores de los atributos, este código funciona

function rel_adder( $matches ) {
    if ( strpos($matches[0], 'rel=') === false ) {
        return $matches[1].'rel="lightbox" '. $matches[2];
    } else {
        return $matches[0];
    }
}
$mydata = preg_replace_callback('#(<img )([^>]+)>#i', "rel_adder", $mydata);