Test if directed graph is connected

Not super-elegant, but:

justConnectedQ = Max @ MapThread[Min, {#, Transpose[#]}, 2] < Infinity & @*
                 GraphDistanceMatrix

Create all possible pairs of vertices (and their reverse) and calculate the maximum of their minimum graph distance. Sounds horrible? Looks even more scary in code

justConnectedQ[g_?GraphQ] := Max[Min[GraphDistance[g, #1, #2] & @@@
  {#, Reverse[#]}] & /@ Subsets[VertexList[g], {2}]] < Infinity

justConnectedQ@Graph@{a -> b, c -> b}
justConnectedQ@Graph@{a -> b, b -> c}
justConnectedQ@Graph@{a -> b, b -> c, c -> a}
(* False *)
(* True *)
(* True *)

Here is my entry:

justConnectedQ[g_] := 
 With[{am = AdjacencyMatrix@TransitiveClosureGraph[g], 
   n = VertexCount[g]},
   Total[Unitize[am + Transpose[am]], 2] == n (n - 1)
 ]

TransitiveClosureGraph[g] creates a (directed) graph in which $u$ and $v$ are connected iff there is a (directed) path from $u$ to $v$.

We take the adjacency matrix of the transitive closure graph, symmetrize it, and check if the result represents a complete graph (i.e. every node is reachable from any other). We do this by counting the number of 1s in the matrix (through summing them).

This solution is faster than the one with GraphDistanceMatrix and much much faster than the one with GraphDistance. Note that last time I benchmarked GraphDistance, it was very slow and computing all shortest path to one vertex took as long as computing all-pair shortest paths with GraphDistanceMatrix (i.e. I suspect a performance bug).

On this graph: g = RandomGraph[{5000, 25000}]; I measure 14 seconds for the GraphDistanceMatrix-based solution vs. 2.8 seconds for my solution. This is still much slower than ConnectedGraphQ and WeaklyConnectedGraphQ while we know than in theory it doesn't need to be.