Faster determination if two nodes are connected in a graph

Question

In the code below connectedQ[g_,v1_,v2_] is a function to check if two nodes v1 and v2 in graph g are connected or not.
nodepairs1 and nodepairs2 are two examples of pair of nodes that I want to check.

myGraph = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 1, 5 <-> 6, 6 <-> 1, 3 <-> 5}];
nodepairs1 = {{1, 6}, {6, 5}, {5, 1}, {2, 1}};
nodepairs2 = {{1, 6}, {6, 5}, {5, 1}, {2, 6}, {1, 2}, {2, 3}, {2, 9}, {3, 4}};
connectedQ[g_, v1_, v2_] := MemberQ[VertexComponent[g, v1], v2]

Next I apply the function to the two pairs of nodes.

Apply[And, connectedQ[myGraph, Sequence @@ #]& /@ nodepairs1]
Apply[And, connectedQ[myGraph, Sequence @@ #]& /@ nodepairs2]

(* 
Out[375]= True
Out[376]= False *)

Output is True if all pairs of nodes are connected and False if at least one pair of nodes are not connected.

This code works but it's slow if there are a lot of node pairs to check (hundreds of thousands of pairs). So I'm trying to find a way to make it faster.

One possible way I could think is that returning False when it sees a pair which are not connected and not checking the remaining pairs anymore. How would you do this? Or do you have a better idea to do this fast?

Answer 1

Build an association that assigns an index for its connected component to every vertex:

a = Association[Join @@ MapIndexed[Thread[Rule[#1, #2[[1]]]] &, ConnectedComponents[myGraph]]]

Then you can check whether v1 and v2 belong to the same component like this:

a[v1] == a[v2]

To check many at once, you can use Lookup:

{v1, v2} = Transpose[nodepairs1];
And @@ MapThread[SameQ, {Lookup[a, v1], Lookup[a, v2]}]

{v1, v2} = Transpose[nodepairs2];
And @@ MapThread[SameQ, {Lookup[a, v1], Lookup[a, v2]}]

True

False

Using vectorized integer operations instead of MapThread can also give you some performance improvement. This is the code:

SameQ[Max[Unitize[Subtract[Lookup[a, v1], Lookup[a, v2]]]], 0]

OP's MemberQ-method looks quite $O(\text{$\#$vertices} \cdot \text{$\#$nodepairs})$-ish if not $O(\text{$\#$vertices}^2 \cdot \text{$\#$nodepairs})$-ish to me. The algorithmic complexity of my method should be in the ball park of

$$O(\text{$\#$vertices})$$

for computing the components (and the Association) and

$$ O(\log(\text{$\#$components}) \cdot \text{$\#$nodepairs})$$

for the lookup.

If your vertex labels are simply the consecutive integers starting from 1, then you can even use a simple packed array as lookup table. The build time is quite a bit faster and the lookup is seems to be two orders of magnitude faster.

Build the lookup table:

lookup = 
  Normal[
   SparseArray[
    Join @@ 
     MapIndexed[Thread[Rule[#1, #2[[1]]]] &, 
      ConnectedComponents[G]]]];

Do the check:

SameQ[Max[Unitize[Subtract[Lookup[a, v1], Lookup[a, v2]]]], 0]

Unfortunately, all these approaches do no allow for short-circuiting. This would require loop constructs like While in the "hot"part of the code. Since Mathematica is an interpreted language, it is not well-suited for such a task. (Although one might be able to tweak, e.g. NestWhile to make it work.) However, with the plain array lookup table, we can compile the lookup code:

cf = Compile[{{lookup, _Integer, 1}, {nodepairs, _Integer, 2}},
  Block[{bool, i},
   bool = True;
   i = 0;
   While[bool && (i < Length[nodepairs] - 1),
    ++i;
    bool = 
     bool && (Compile`GetElement[nodepairs, i, 1] == 
        Compile`GetElement[nodepairs, i, 2]);
    ];
   bool
   ],
  CompilationTarget -> "C",
  RuntimeAttributes -> {Listable},
  Parallelization -> True,
  RuntimeOptions -> "Speed"
  ];

You would just call it like this:

cf[lookup, nodepairs]

This would also work (even in parallel), if nodepairs were a list of lists of node pairs; then cf would thread over the outer list.

Answer 2

Nice and simple,

ConnectedVerticesQ[graph_,v1_,v2_] := UnsameQ[GraphDistance[graph,v1,v2],Infinity]

In my tests this is faster than the OP's connectedQ. It also has the advantage of not needing to precompute the connected components in a lookup table which you then have to keep track of.

Answer 3

b = Association @ KeyValueMap[Thread @* Rule] @  Map[First] @ 
    PositionIndex @ ConnectedComponents @ myGraph;

An alternative way to use Lookup:

allConnectedQ = SameQ @@ Lookup[Union @@ #] @ b &;

allConnectedQ @ nodepairs1

True

allConnectedQ @ nodepairs2

False