Re: Neighbors of a Vertex

Alf P. Steinbach wrote:
* Logan Shaw:
Mark P wrote:
Sam wrote:

I have a question about finding neighbors of a given vertex in a
graph.

Suppose there are n vertices in the graph, for one vertex P(x,y), how
can I find all its neighbors, which are away AT MOST r units from
P(x,y), in an efficient way, i.e. I don't want to compare the
distances of all possible pairs with P, which will take theta(n) time.

What do you mean by neighbors?

the poster is probably wanting us to assume that
vertexes are points in two-dimension space. Hence the notation "P(x,y)"
with no definition of "x" or "y"; we are apparently to assume they are
coordinates. This makes a lot of sense except for one thing: if that's
the case and if we look at the rest of the question, it's completely,
totally, 100% a red herring to mention that this is a graph. It's
really then a question about a set of points.

One reasonable interpretation is that each edge defines a distance.

If the distance is a property of the edge, then why do the vertexes
have x and y values?

Or I suppose it could be that the data structure is such that the
distances are stored on the edges, but it just so happens that this
is not the general case of a graph with weighted edges: instead, it
would be a graph where the weights obey the constraint that all the
vertexes could be points in 2-D space and the weights would correspond
to distance.

- Logan
.

Relevant Pages

  • Re: Cannot understand the detailedly the following code
    ... Input parameters are graph, vertexes start, node, end and path. ... Actually i'm not clear how to proceed writing this recursive function. ...
    (comp.lang.python)
  • Re: Is this an NP complete problem?
    ... the art of maths is to write it so that those of all specialisatons ... A graph G is a pair, where V is a set of vertexes, ... In one cut set, the lines are either red or yellow. ...
    (comp.theory)
  • Massive graph rcompress
    ... I have a task to represent graph that have ... vertexes or more using C++. ... So, what structure compress ... graphs data memory as much as possible? ...
    (comp.programming)
  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • Re: Standard graph API?
    ... I would rather have the weights be a separate dict ... >or function or whatever passed to the graph algorithm. ... [snip stuff about using dicts] ... "properties as separate mappings" and the Level 2 Graph API could add ...
    (comp.lang.python)