Efficient random graph generation can be achieved for directed and undirected networks using Charo del Genio's graph sampling algorithms, published in Del Genio, Kim, Toroczkai and Bassler, PLoSOne 5 (4), e10012 and Kim, Del Genio, Bassler and Toroczkai, arXiv:1109.4590.
See also the C implementation at http://www.biond.org/node/183 and http://www.biond.org/node/272.