9
$\begingroup$

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?

$\endgroup$

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Indeed, igraph's R package represents components not by a list of lists (like Mathematica), but by assigning a component index to each node. $\endgroup$
    – Szabolcs
    Feb 28 at 17:22
  • 1
    $\begingroup$ It is good to note that this approach works only for undirected graphs. Computing a transitive closure may be useful, if memory consuming, for directed graphs. $\endgroup$
    – Szabolcs
    Feb 28 at 17:22
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$
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
$\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.