18.13. Built-in Graph Algorithms

Prev		Next

18.13.1. Find all shortest paths
18.13.2. Find one of the shortest paths between nodes
18.13.3. Execute a Dijkstra algorithm with similar weights on relationships
18.13.4. Execute a Dijkstra algorithm with weights on relationships

Neo4j comes with a number of built-in graph algorithms. They are performed from a start node. The traversal is controlled by the URI and the body sent with the request.

algorithm

The algorithm to choose. If not set, default is shortestPath. algorithm can have one of these values:

shortestPath
allSimplePaths
allPaths
dijkstra (optional with cost_property and default_cost parameters)

max_depth

The maximum depth as an integer for the algorithms like ShortestPath, where applicable. Default is 1.

18.13.1. Find all shortest paths

The shortestPath algorithm can find multiple paths between the same nodes, like in this example.

Figure 18.64. Final Graph

Example request

POST http://localhost:7474/db/data/node/243/paths
Accept: application/json
Content-Type: application/json

{
  "to" : "http://localhost:7474/db/data/node/238",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

200: OK
Content-Type: application/json

[ {
  "start" : "http://localhost:7474/db/data/node/243",
  "nodes" : [ "http://localhost:7474/db/data/node/243", "http://localhost:7474/db/data/node/239", "http://localhost:7474/db/data/node/238" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/125", "http://localhost:7474/db/data/relationship/131" ],
  "end" : "http://localhost:7474/db/data/node/238"
}, {
  "start" : "http://localhost:7474/db/data/node/243",
  "nodes" : [ "http://localhost:7474/db/data/node/243", "http://localhost:7474/db/data/node/242", "http://localhost:7474/db/data/node/238" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/124", "http://localhost:7474/db/data/relationship/133" ],
  "end" : "http://localhost:7474/db/data/node/238"
} ]

18.13.2. Find one of the shortest paths between nodes

If no path algorithm is specified, a ShortestPath algorithm with a max depth of 1 will be chosen. In this example, the max_depth is set to 3 in order to find the shortest path between 3 linked nodes.

Figure 18.65. Final Graph

Final-Graph-Find-one-of-the-shortest-paths-between-nodes.svg

Example request

POST http://localhost:7474/db/data/node/250/path
Accept: application/json
Content-Type: application/json

{
  "to" : "http://localhost:7474/db/data/node/245",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

200: OK
Content-Type: application/json

{
  "start" : "http://localhost:7474/db/data/node/250",
  "nodes" : [ "http://localhost:7474/db/data/node/250", "http://localhost:7474/db/data/node/246", "http://localhost:7474/db/data/node/245" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/135", "http://localhost:7474/db/data/relationship/141" ],
  "end" : "http://localhost:7474/db/data/node/245"
}

18.13.3. Execute a Dijkstra algorithm with similar weights on relationships

Figure 18.66. Final Graph

Final-Graph-Execute-a-Dijkstra-algorithm-with-similar-weights-on-relationships.svg

Example request

POST http://localhost:7474/db/data/node/265/path
Accept: application/json
Content-Type: application/json

{
  "to" : "http://localhost:7474/db/data/node/268",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

200: OK
Content-Type: application/json

{
  "weight" : 2.0,
  "start" : "http://localhost:7474/db/data/node/265",
  "nodes" : [ "http://localhost:7474/db/data/node/265", "http://localhost:7474/db/data/node/266", "http://localhost:7474/db/data/node/268" ],
  "length" : 2,
  "relationships" : [ "http://localhost:7474/db/data/relationship/157", "http://localhost:7474/db/data/relationship/158" ],
  "end" : "http://localhost:7474/db/data/node/268"
}

18.13.4. Execute a Dijkstra algorithm with weights on relationships

Figure 18.67. Final Graph

Final-Graph-Execute-a-Dijkstra-algorithm-with-weights-on-relationships.svg

Example request

POST http://localhost:7474/db/data/node/256/path
Accept: application/json
Content-Type: application/json

{
  "to" : "http://localhost:7474/db/data/node/259",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

200: OK
Content-Type: application/json

{
  "weight" : 6.0,
  "start" : "http://localhost:7474/db/data/node/256",
  "nodes" : [ "http://localhost:7474/db/data/node/256", "http://localhost:7474/db/data/node/257", "http://localhost:7474/db/data/node/254", "http://localhost:7474/db/data/node/255", "http://localhost:7474/db/data/node/252", "http://localhost:7474/db/data/node/253", "http://localhost:7474/db/data/node/259" ],
  "length" : 6,
  "relationships" : [ "http://localhost:7474/db/data/relationship/144", "http://localhost:7474/db/data/relationship/146", "http://localhost:7474/db/data/relationship/148", "http://localhost:7474/db/data/relationship/151", "http://localhost:7474/db/data/relationship/153", "http://localhost:7474/db/data/relationship/154" ],
  "end" : "http://localhost:7474/db/data/node/259"
}