4
\$\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\$
3
  • \$\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\$ Jun 9, 2011 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, 2011 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\$ Jun 9, 2011 at 8:14

1 Answer 1

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\$
0

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