8
$\begingroup$

Is there a simple built-in way to check if a directed graph is connected?

Now, before you throw ConnectedGraphQ or WeaklyConnectedGraphQ at me, let me clarify that there are three different qualities of connectedness for directed graphs:

  • Weakly connected: the graph would be connected if all edges were replaced by undirected edges.
  • Connected: for each pair of vertices $u$ and $v$, there's a path from $u$ to $v$ or a path from $v$ to $u$ (or both).
  • Strongly connected: for each pair of vertices $u$ and $v$, there's a path from $u$ to $v$ and a path from $v$ to $u$.

The problem is that ConnectedGraphQ actually checks for strong connectivity on directed graphs, whereas I actually want to know if it's "just" connected.

Some simple test cases:

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

(I can solve this myself, but I'd like to know if there's an elegant/built-in way to do it.)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there a chance that Mathematica sets some metadata when constructing a graph which is used by (Weakly)ConnectedGraphQ so that it doesn't actually have to determine the connectedness then? $\endgroup$ – Martin Ender Mar 8 '16 at 13:48
  • $\begingroup$ @MartinBüttner Could be, the inner workings of Graph are a mystery to me (but I do know that it's complicated with several different kinds of internal representations that can have a sometimes significant impact on performance). That said, testing connectedness is a simple operation that can be clearly much much faster than my justConnectedQ above. IGraph/M does have testing functions for weak and strong connectedness and it is instantaneous for this graph. $\endgroup$ – Szabolcs Mar 8 '16 at 14:01
8
$\begingroup$

Not super-elegant, but:

justConnectedQ = Max @ MapThread[Min, {#, Transpose[#]}, 2] < Infinity & @*
                 GraphDistanceMatrix
$\endgroup$
6
$\begingroup$

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 *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.