Prev |  | Next

## 18.14. Built-in 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.

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.14.1. Find all shortest paths

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

Figure 18.73. Final Graph

Example request

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

    {
      "to" : "http://localhost:7474/db/data/node/391",
      "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/396",
      "nodes" : [ "http://localhost:7474/db/data/node/396", "http://localhost:7474/db/data/node/395", "http://localhost:7474/db/data/node/391" ],
      "length" : 2,
      "relationships" : [ "http://localhost:7474/db/data/relationship/234", "http://localhost:7474/db/data/relationship/243" ],
      "end" : "http://localhost:7474/db/data/node/391"
    }, {
      "start" : "http://localhost:7474/db/data/node/396",
      "nodes" : [ "http://localhost:7474/db/data/node/396", "http://localhost:7474/db/data/node/392", "http://localhost:7474/db/data/node/391" ],
      "length" : 2,
      "relationships" : [ "http://localhost:7474/db/data/relationship/235", "http://localhost:7474/db/data/relationship/241" ],
      "end" : "http://localhost:7474/db/data/node/391"
    } ]

### 18.14.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.74. Final Graph

Example request

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

    {
      "to" : "http://localhost:7474/db/data/node/398",
      "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/403",
      "nodes" : [ "http://localhost:7474/db/data/node/403", "http://localhost:7474/db/data/node/399", "http://localhost:7474/db/data/node/398" ],
      "length" : 2,
      "relationships" : [ "http://localhost:7474/db/data/relationship/245", "http://localhost:7474/db/data/relationship/251" ],
      "end" : "http://localhost:7474/db/data/node/398"
    }

### 18.14.3. Execute a Dijkstra algorithm with similar weights on relationships

Figure 18.75. Final Graph

Example request

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

    {
      "to" : "http://localhost:7474/db/data/node/421",
      "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/418",
      "nodes" : [ "http://localhost:7474/db/data/node/418", "http://localhost:7474/db/data/node/419", "http://localhost:7474/db/data/node/421" ],
      "length" : 2,
      "relationships" : [ "http://localhost:7474/db/data/relationship/267", "http://localhost:7474/db/data/relationship/268" ],
      "end" : "http://localhost:7474/db/data/node/421"
    }

### 18.14.4. Execute a Dijkstra algorithm with weights on relationships

Figure 18.76. Final Graph

Example request

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

    {
      "to" : "http://localhost:7474/db/data/node/412",
      "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/409",
      "nodes" : [ "http://localhost:7474/db/data/node/409", "http://localhost:7474/db/data/node/410", "http://localhost:7474/db/data/node/407", "http://localhost:7474/db/data/node/408", "http://localhost:7474/db/data/node/405", "http://localhost:7474/db/data/node/406", "http://localhost:7474/db/data/node/412" ],
      "length" : 6,
      "relationships" : [ "http://localhost:7474/db/data/relationship/254", "http://localhost:7474/db/data/relationship/256", "http://localhost:7474/db/data/relationship/258", "http://localhost:7474/db/data/relationship/261", "http://localhost:7474/db/data/relationship/263", "http://localhost:7474/db/data/relationship/264" ],
      "end" : "http://localhost:7474/db/data/node/412"
    }

Copyright © 2013 Neo Technology

Prev | Up | Next
| Home |