       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

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:= neighbours[g_Graph, v_] :=
Module[
{vl = VertexList[g],
pos},
pos = Position[vl, v][[1, 1]];
]

In:= tg = RandomGraph[{1000, Round[.3 1000^2]}];

In:= neighbours[tg, 1]; // Timing
Out= {0.094, Null}

In:= a = Subgraph[tg, Append[neighbours[tg, 1], 1]]; // Timing
Out= {0.187, Null}

In:= b = NeighborhoodGraph[tg, 1]; // Timing
Out= {17.171, Null}

In:= IsomorphicGraphQ[a, b]
Out= True

In:= tg = RandomGraph[{4000, Round[.3 4000^2]}];

In:= neighbours[tg, 1]; // Timing
Out= {1.375, Null}

```

• Prev by Date: Re: How show axes labels with AxesOrigin->{0,0,0} in 3D?
• Next by Date: Re: Using Cases or Position to Find Strings in a List of Strings
• Previous by thread: FindMinimum and Levenberg method
• Next by thread: Re: Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph