3
\$\begingroup\$

I'm looking for the fastest way to find all neighbours of a vertex in an undirected Graph. Please improve on the code if possible.

neighbours[g_Graph, v_] :=
 Module[
  {vl = VertexList[g],
   pos},
  pos = Position[vl, v][[1, 1]];
  Pick[VertexList[g], AdjacencyMatrix[g][[pos]], 1]
 ]

I need it to work fast both for sparse and dense graphs.

  1. It is essential to the performance of this solution that it uses SparseArrays.
  2. This is a bottleneck in my application. Since my graph is constantly changing, trying to precompute neighbours or using memoization will complicate things significantly.

I'd like to stress that speed is essential here. Here's a graph to test on:

max = 4000;
c = 0.3;

tg = RandomGraph[{max, Round[c max^2]}];

neighbours[tg, 1]; // Timing
\$\endgroup\$
  • \$\begingroup\$ There is a Neighborhood function in the Combinatorica package. I would expect their implementation to be as fast as possible. Have you compared it to yours in terms of performance? \$\endgroup\$ – trutheality Jun 9 '11 at 0:51
  • \$\begingroup\$ Yes, someone else suggested it in a now deleted reply. Unexpectedly and unfortunately Neighborhood is much slower. \$\endgroup\$ – Szabolcs Jun 9 '11 at 7:45
  • \$\begingroup\$ Another idea is to use EdgeList. I wish I knew how Mathematica represents graphs internally, then there'd be some insight into what is faster. There are also other things similar to AdjacencyMatrix you could try like ToAdjacencyLists, IncidenceMatrix, ToUnorderedPairs, but I don't have any insight into which one would be faster. \$\endgroup\$ – trutheality Jun 9 '11 at 8:14
2
\$\begingroup\$

As of Mathematica 9.0 we have the function AdjacencyList[g,v]. Since this is built into Mathematica, I would assume that it is the fastest implementation.

In[1]:= g = CompleteGraph[7];
In[2]:= AdjacencyList[g, 4]
Out[2]= {1, 2, 3, 5, 6, 7}
In[3]:= g = CompleteGraph[{3,4}];
In[4]:= EdgeList[g]
Out[4]= {1 <-> 4, 1 <-> 5, 1 <-> 6, 1 <-> 7, 2 <-> 4, 2 <-> 5, 2 <-> 6, 2 <-> 7, 3 <-> 4, 3 <-> 5, 3 <-> 6, 3 <-> 7}
In[5]:= AdjacencyList[g, 5]
Out[5]= {1, 2, 3}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Could you add an example to your answer? Thanks! \$\endgroup\$ – Ethan Bierlein Sep 20 '15 at 19:45
  • \$\begingroup\$ @EthanBierlein, thanks. The example will have to be pretty minimal, but sure. \$\endgroup\$ – Mike Pierce Sep 20 '15 at 19:51

protected by Ethan Bierlein Sep 20 '15 at 19:51

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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