Search code examples
graphgraph-algorithmgremlingremlin-server

Compute shortest distance from a given vertex to a vertex with a defined property

A well understood problem in graph theory is to compute the shortest distance between two vertices.

What I want to do is find the shortest distance from a given vertex to the closest vertex which has a certain property-value (the exact vertex that this is, is unknown).

For example, find the shortest distance from V(1) to the closest vertex V(?) where V(?).property(color)==red.

An approach I've used for this before is to iteratively step outwards from a focal vertex, asking each unseen neighbor along the way whether it has that color=red.

I also upper bounded the number of outward steps for some added efficiency, i.e. limiting the search to the k step neighbourhood.

  1. Is there a better way to solve this problem?
  2. How might one code this using Gremlin? (I code primarily in Python and am unsure how to migrate the algorithm across)
Solution

  • As you said this is a well known problem in graph theory, and there are many algorithms, like: Dijkstra's, that solved this problem. you can read about them here.

    Also you can find many gremlin recipes here, including a simple shortest path algorithm.

    By changing the loop stop condition, I believe it will give you the desired result:

    g.V(1).repeat(out().simplePath()).until(has('color', 'red')).path().limit(1)