Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph
- To: mathgroup at smc.vnet.net
- Subject: [mg119559] Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph
- From: Szabolcs Horvát <szhorvat at gmail.com>
- Date: Thu, 9 Jun 2011 05:46:33 -0400 (EDT)
Dear MathGroup members, I was looking for the fastest possible way to find all vertices a certain vertex is connected to in a graph. I also asked about this here: http://codereview.stackexchange.com/questions/2871/fastest-way-to-find-all-neighbours-of-a-vertex-in-a-graph where people suggested using NeighborhoodGraph. Unfortunately it turns out that NeighborhoodGraph is considerably slower than my solution, which led me to believe that there might be a bug in it. I can't look at the implementation of NeighborhoodGraph because it is Locked. So, to get to the question: I'm still looking for ways to speed up finding neighbours in an undirected graph. My current solution is attached. Any suggestions to speed it up are most welcome. In[1]:= neighbours[g_Graph, v_] := Module[ {vl = VertexList[g], pos}, pos = Position[vl, v][[1, 1]]; Pick[VertexList[g], AdjacencyMatrix[g][[pos]], 1] ] In[2]:= tg = RandomGraph[{1000, Round[.3 1000^2]}]; In[3]:= neighbours[tg, 1]; // Timing Out[3]= {0.094, Null} In[4]:= a = Subgraph[tg, Append[neighbours[tg, 1], 1]]; // Timing Out[4]= {0.187, Null} In[5]:= b = NeighborhoodGraph[tg, 1]; // Timing Out[5]= {17.171, Null} In[6]:= IsomorphicGraphQ[a, b] Out[6]= True In[7]:= tg = RandomGraph[{4000, Round[.3 4000^2]}]; In[8]:= neighbours[tg, 1]; // Timing Out[8]= {1.375, Null}