Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.soft-sys.math.mathematica > #3038

Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph

Show all headers | View raw

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}

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread

Thread

Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph Szabolcs Horvát <szhorvat@gmail.com> - 2011-06-09 09:46 +0000

csiph-web