[Date Index]
[Thread Index]
[Author Index]
Re: Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph
*To*: mathgroup at smc.vnet.net
*Subject*: [mg119573] Re: Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph
*From*: Bob Hanlon <hanlonr at cox.net>
*Date*: Fri, 10 Jun 2011 06:40:04 -0400 (EDT)
You can get a minor improvement by changing your definition of neighbours
neighbours[g_Graph, v_] :=
Pick[VertexList[g], AdjacencyMatrix[g][[v]], 1]
Bob Hanlon
---- "Szabolcs Horv=C3=A1t" <szhorvat at gmail.com> wrote:
==========================
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}
--
Bob Hanlon
Prev by Date:
**Re: querries**
Next by Date:
**Re: I'm not able to see Mathematica demonstrations on the Internet**
Previous by thread:
**Fast way to find neighbours of vertices in a Graph & possible performance bug in NeighborhoodGraph**
Next by thread:
**Seaching in Pi a sequence. Looking for a faster method**
| |