  We consider directed graph algorithms in a streaming setting, focusing on
problems concerning orderings of the vertices. This includes such fundamental
problems as topological sorting and acyclicity testing. We also study the
related problems of finding a minimum feedback arc set (edges whose removal
yields an acyclic graph), and finding a sink vertex. We are interested in both
adversarially-ordered and randomly-ordered streams. For arbitrary input graphs
with edges ordered adversarially, we show that most of these problems have high
space complexity, precluding sublinear-space solutions. Some lower bounds also
apply when the stream is randomly ordered: e.g., in our most technical result
we show that testing acyclicity in the $p$-pass random-order model requires
roughly $n^{1+1/p}$ space. For other problems, random ordering can make a
dramatic difference: e.g., it is possible to find a sink in an acyclic
tournament in the one-pass random-order model using polylog$(n)$ space whereas
under adversarial ordering roughly $n^{1/p}$ space is necessary and sufficient
given $\Theta(p)$ passes. We also design sublinear algorithms for the feedback
arc set problem in tournament graphs; for random graphs; and for randomly
ordered streams. In some cases, we give lower bounds establishing that our
algorithms are essentially space-optimal. Together, our results complement the
much maturer body of work on algorithms for undirected graph streams.
