Skip to content

Breadth First Search

Introduction

Breadth-first search finds the path with the fewest edges from a source node. It ignores edge weights. With a sink, it returns one shortest path to that node. Without one, it returns a shortest path to every node the source can reach, optionally only those within maxHop edges. Each path's weight is its number of edges.

When several paths have the fewest edges, the program returns one of them. To get all of them, use the Cypher allShortestPaths() pattern function (see Path functions).

Run breadth-first search from Cypher with CALL algo.shortestpath.bfs, or from Gremlin with LocalBFSShortestPathProgram. See Shortest Paths for how to run it, the output fields, the arguments shared by all shortest path algorithms, and sizing guidance.

Query Examples

Fewest edges between two nodes

The path with the fewest edges from vadas (person[v2]) to ripple (software[v5]) in the Modern example graph, following edges in either direction:

CALL algo.shortestpath.bfs({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    sourceNode: 'person[v2]',
    targetNode: 'software[v5]',
    undirected: true
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight

Output:

[
  {
    "vertexList": ["person[v2]", "person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e7]", "knows[e8]", "created[e10]"],
    "weight": 3.0
  }
]
graph.program(
  LocalBFSShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .source("person[v2]")
    .sink("software[v5]")
    .asUndirected(true)
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v2]", "person[v1]", "person[v4]", "software[v5]"],
    "edgeList": ["knows[e7]", "knows[e8]", "created[e10]"],
    "edgeResultList": [
      {"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"},
      {"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"},
      {"id": "created[e10]", "from": "person[v4]", "to": "software[v5]"}
    ],
    "weight": 3.0
  }
]

The path walks knows[e7] backwards, from vadas to marko, so edgeResultList shows that edge's stored direction, from person[v1] to person[v2].

The Cypher shortestPath() pattern function returns the same path:

MATCH p=shortestPath((u:person {name: 'vadas'})-[*..4]-(x:software {name: 'ripple'}))
RETURN [n IN nodes(p) | n.name]
// [vadas, marko, josh, ripple]

Nodes within a number of hops

Without a sink, maxHop(2) returns a path to every node within 2 edges of vadas:

CALL algo.shortestpath.bfs({
    labels: ['person', 'software'],
    relationshipTypes: ['knows', 'created'],
    sourceNode: 'person[v2]',
    undirected: true,
    maxHop: 2
    }) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
ORDER BY weight

Output:

[
  {
    "vertexList": ["person[v2]", "person[v1]"],
    "edgeList": ["knows[e7]"],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v2]", "person[v1]", "person[v4]"],
    "edgeList": ["knows[e7]", "knows[e8]"],
    "weight": 2.0
  },
  {
    "vertexList": ["person[v2]", "person[v1]", "software[v3]"],
    "edgeList": ["knows[e7]", "created[e9]"],
    "weight": 2.0
  }
]
graph.program(
  LocalBFSShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .source("person[v2]")
    .asUndirected(true)
    .maxHop(2)
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v2]", "person[v1]"],
    "edgeList": ["knows[e7]"],
    "edgeResultList": [{"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"}],
    "weight": 1.0
  },
  {
    "vertexList": ["person[v2]", "person[v1]", "person[v4]"],
    "edgeList": ["knows[e7]", "knows[e8]"],
    "edgeResultList": [
      {"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"},
      {"id": "knows[e8]", "from": "person[v1]", "to": "person[v4]"}
    ],
    "weight": 2.0
  },
  {
    "vertexList": ["person[v2]", "person[v1]", "software[v3]"],
    "edgeList": ["knows[e7]", "created[e9]"],
    "edgeResultList": [
      {"id": "knows[e7]", "from": "person[v1]", "to": "person[v2]"},
      {"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}
    ],
    "weight": 2.0
  }
]

ripple and peter are 3 edges away, so they are left out.

Parameters

Cypher argument Gremlin method Description Required Default Value
sourceNode source(String id) The ID of the node to start from Yes
targetNode sink(String id) The ID of the target node. Without it, the program returns a path to every reachable node No
undirected asUndirected(boolean undirected) Follow edges in both directions No false
maxHop maxHop(int hops) Without a sink, return only nodes within this many edges. 0 means no limit. A value greater than 0 cannot be combined with sink No 0

The common arguments also apply, except the weight and penalty ones. In Gremlin, breadth-first search ignores weightProperty, fixedPenalty and penaltyProperty. In Cypher, passing relationshipWeightProperty, fixedPenalty or penaltyProperty fails as an unknown argument.

Setting sink together with a maxHop greater than 0 fails with cannot set sink and maxHop at same time. In Cypher, setting targetNode with a maxHop greater than 0 fails with algo.shortestpath.bfs: set at most one of `targetNode` and `maxHop`.