Message Boards Message Boards

3 Replies
1 Total Likes
View groups...
Share this post:

Subgraphs by neighbourhood

Posted 11 years ago

I work a lot with Graphs/GraphPlot but I cannot figure out how to do the very simple SubGraph definition of providing one vertix v from graph g and a depth to get sub graph h that has v and all vertices with a maximum distance d to v.

Help anyone, plz?

thx in advance, Erik
POSTED BY: Erik Itter
3 Replies
Posted 11 years ago
thx, that is exactly what I need, just did not imagine to find that function outside SubGraph
POSTED BY: Erik Itter
You need to use the NeighbourhoodGraph[] function.

If g is a Graph and v is the starting vertex, you can use
NeighborhoodGraph[g, v, d]
to get a subgraph of g including v and all nodes reachable in d hops.

One completely unobvious and potentially serious problem with NeighborhoodGraph is that is will automatically recompute the layout of the graph it returns (I really don't understand why it does this).  As a result, this function is much much slower than it should be.  This can be a serious problem is you use it in a loop (Table, etc.), but it doesn't show up during interactive use.  The issue and the workaround is described here:

The workaround:
NeighborhoodGraph[g, v, GraphLayout -> None]
I am very much hoping that this problem will be fixed in future versions ...  Users can't be expected to be able to find the cause of this (significant and unintuitive) slowdown on their own, and if layout calculations and neighborhood calculations are coupled, that is a significant usability problem.
POSTED BY: Szabolcs Horvát
Have you tried NeighborhoodGraph? If I am understanding correctly, this is what that function does. 
POSTED BY: Sean Clarke
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract