  We consider the problem of sampling a bipartite graph with given vertex
degrees where a set $F$ of edges and non-edges which need to be contained is
predefined. Our general result shows that the repeated swap of edges and
non-edges in alternating cycles of at most size $2\ell-2$ ('$j$-swaps' with $j
\leq 2 \ell-2$) in a current graph lead to an ergodic Metropolis Markov chain
whenever $F$ does not contain a cycle of length $2 \ell$ with $\ell \geq 4.$
This leads to useful Markov chains whenever $\ell$ is not too large. If $F$ is
a forest, $4$- and $6$-swaps are sufficient. Furthermore, we prove that
$4$-swaps are sufficient when $F$ does not contain a matching of size $3.$ We
extend the Curveball algorithm of Strona et al. \cite{Strona2014b} to our
cases.
