20.18. Graph Algorithms

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. These are the parameters that can be used:

algorithm

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

  • shortestPath
  • allSimplePaths
  • allPaths
  • dijkstra (optionally 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.

Find all shortest paths

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

Figure 20.72. Final Graph

Final-Graph-Find-all-shortest-paths.svg

Example request

  • POST http://localhost:7474/db/data/node/50/paths
  • Accept: application/json; charset=UTF-8
  • Content-Type: application/json 
{
  "to" : "http://localhost:7474/db/data/node/56",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

  • 200: OK
  • Content-Type: application/json; charset=UTF-8 
[ {
  "relationships" : [ "http://localhost:7474/db/data/relationship/31", "http://localhost:7474/db/data/relationship/40" ],
  "nodes" : [ "http://localhost:7474/db/data/node/50", "http://localhost:7474/db/data/node/52", "http://localhost:7474/db/data/node/56" ],
  "directions" : [ "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/50",
  "length" : 2,
  "end" : "http://localhost:7474/db/data/node/56"
}, {
  "relationships" : [ "http://localhost:7474/db/data/relationship/32", "http://localhost:7474/db/data/relationship/38" ],
  "nodes" : [ "http://localhost:7474/db/data/node/50", "http://localhost:7474/db/data/node/53", "http://localhost:7474/db/data/node/56" ],
  "directions" : [ "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/50",
  "length" : 2,
  "end" : "http://localhost:7474/db/data/node/56"
} ]

Find one of the shortest paths

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 a maximum of 3 linked nodes.

Figure 20.73. Final Graph

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

Example request

  • POST http://localhost:7474/db/data/node/43/path
  • Accept: application/json; charset=UTF-8
  • Content-Type: application/json 
{
  "to" : "http://localhost:7474/db/data/node/49",
  "max_depth" : 3,
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "shortestPath"
}

Example response

  • 200: OK
  • Content-Type: application/json; charset=UTF-8 
{
  "relationships" : [ "http://localhost:7474/db/data/relationship/21", "http://localhost:7474/db/data/relationship/30" ],
  "nodes" : [ "http://localhost:7474/db/data/node/43", "http://localhost:7474/db/data/node/45", "http://localhost:7474/db/data/node/49" ],
  "directions" : [ "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/43",
  "length" : 2,
  "end" : "http://localhost:7474/db/data/node/49"
}

Execute a Dijkstra algorithm and get a single path

This example is running a Dijkstra algorithm over a graph with different cost properties on different relationships. Note that the request URI ends with /path which means a single path is what we want here.

Figure 20.74. Final Graph

Final-Graph-Execute-a-Dijkstra-algorithm-and-get-a-single-path.svg

Example request

  • POST http://localhost:7474/db/data/node/57/path
  • Accept: application/json; charset=UTF-8
  • Content-Type: application/json 
{
  "to" : "http://localhost:7474/db/data/node/61",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

  • 200: OK
  • Content-Type: application/json; charset=UTF-8 
{
  "relationships" : [ "http://localhost:7474/db/data/relationship/42", "http://localhost:7474/db/data/relationship/44", "http://localhost:7474/db/data/relationship/45" ],
  "nodes" : [ "http://localhost:7474/db/data/node/57", "http://localhost:7474/db/data/node/59", "http://localhost:7474/db/data/node/60", "http://localhost:7474/db/data/node/61" ],
  "directions" : [ "->", "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/57",
  "length" : 3,
  "weight" : 1.5,
  "end" : "http://localhost:7474/db/data/node/61"
}

Execute a Dijkstra algorithm with equal weights on relationships

The following is executing a Dijkstra search on a graph with equal weights on all relationships. This example is included to show the difference when the same graph structure is used, but the path weight is equal to the number of hops.

Figure 20.75. Final Graph

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

Example request

  • POST http://localhost:7474/db/data/node/63/path
  • Accept: application/json; charset=UTF-8
  • Content-Type: application/json 
{
  "to" : "http://localhost:7474/db/data/node/67",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

  • 200: OK
  • Content-Type: application/json; charset=UTF-8 
{
  "relationships" : [ "http://localhost:7474/db/data/relationship/50", "http://localhost:7474/db/data/relationship/54" ],
  "nodes" : [ "http://localhost:7474/db/data/node/63", "http://localhost:7474/db/data/node/68", "http://localhost:7474/db/data/node/67" ],
  "directions" : [ "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/63",
  "length" : 2,
  "weight" : 2.0,
  "end" : "http://localhost:7474/db/data/node/67"
}

Execute a Dijkstra algorithm and get multiple paths

This example is running a Dijkstra algorithm over a graph with different cost properties on different relationships. Note that the request URI ends with /paths which means we want multiple paths returned, in case they exist.

Figure 20.76. Final Graph

Final-Graph-Execute-a-Dijkstra-algorithm-and-get-multiple-paths.svg

Example request

  • POST http://localhost:7474/db/data/node/37/paths
  • Accept: application/json; charset=UTF-8
  • Content-Type: application/json 
{
  "to" : "http://localhost:7474/db/data/node/41",
  "cost_property" : "cost",
  "relationships" : {
    "type" : "to",
    "direction" : "out"
  },
  "algorithm" : "dijkstra"
}

Example response

  • 200: OK
  • Content-Type: application/json; charset=UTF-8 
[ {
  "relationships" : [ "http://localhost:7474/db/data/relationship/15", "http://localhost:7474/db/data/relationship/17", "http://localhost:7474/db/data/relationship/18" ],
  "nodes" : [ "http://localhost:7474/db/data/node/37", "http://localhost:7474/db/data/node/39", "http://localhost:7474/db/data/node/40", "http://localhost:7474/db/data/node/41" ],
  "directions" : [ "->", "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/37",
  "length" : 3,
  "weight" : 1.5,
  "end" : "http://localhost:7474/db/data/node/41"
}, {
  "relationships" : [ "http://localhost:7474/db/data/relationship/16", "http://localhost:7474/db/data/relationship/20" ],
  "nodes" : [ "http://localhost:7474/db/data/node/37", "http://localhost:7474/db/data/node/42", "http://localhost:7474/db/data/node/41" ],
  "directions" : [ "->", "->" ],
  "start" : "http://localhost:7474/db/data/node/37",
  "length" : 2,
  "weight" : 1.5,
  "end" : "http://localhost:7474/db/data/node/41"
} ]