Follow a Dependency Without Following It Forever

Separate reachability from path enumeration, handle cycles explicitly and interpret bounded traversal results without promising complete discovery.

13 sections · 4 questions · 1 coding challenge

1 / 13

The arrow keys move between sections too.

Unknown-Length Connections Needed Repeated Expansion

BOTIE

The early Neo4j use case described by the Cypher authors included access through variable-length relationships. A fixed sequence of joins or pattern segments cannot express every unknown chain length conveniently. Graph query languages therefore provide bounded or variable-length path matching.

The repeated step does not decide the answer’s grain. A list of reachable nodes, every distinct path and the shortest path are different questions. Our teaching traversal collects nodes once, which gives the visited set a clear purpose.

Sources for this history

The Dependency List Points Back to the Pump

P7 requires S1, S1 requires S2, and a later import says S2 requires P7. Botie’s recursive search keeps returning to the same equipment. Even if the cycle describes a real feedback dependency, our list of affected entities should not repeat forever.

We need to decide what the traversal is collecting and when a node has already been dealt with. For distinct reachable assets, a breadth-first search can remember visited IDs and stop expansion at a stated depth.

Invented maintenance records. Python exercises and workshop components expose the mechanism locally. Source-linked Cypher or SPARQL examples require the stated external database setup.

Step 1 of 2

A cycle returns to an already discovered node

P7, S1 and S2 form a directed cycle. S3 lies one step beyond S2.

Nodes and properties (4)

P7 · depth 0
S1 · depth 1
S2 · depth 2
S3 · depth 3

P7 to S1: DEPENDS_ON
S1 to S2: DEPENDS_ON
S2 to P7: DEPENDS_ON
S2 to S3: DEPENDS_ON

With maximum depth 2, the report includes S1 and S2, excludes the starting P7, and makes no completeness claim about deeper dependencies.

Step 2 of 2

Watch the frontier meet the cycle

Explore P7 with a maximum depth of two. The queue stores a node and its discovered depth.

The return edge to P7 cannot restart the search. S3 is outside the depth-two answer, rather than proven unreachable.
Action	Pending queue	Visited IDs
Initialise	P7 at 0	P7
Expand P7	S1 at 1	P7, S1
Expand S1	S2 at 2	P7, S1, S2
Reach depth limit at S2	Empty	P7, S1, S2
If depth were three	S3 at 3; P7 is already visited	P7, S1, S2, S3

Initialise
Pending queue
P7 at 0
Visited IDs
P7
Expand P7
Pending queue
S1 at 1
Visited IDs
P7, S1
Expand S1
Pending queue
S2 at 2
Visited IDs
P7, S1, S2
Reach depth limit at S2
Pending queue
Empty
Visited IDs
P7, S1, S2
If depth were three
Pending queue
S3 at 3; P7 is already visited
Visited IDs
P7, S1, S2, S3

The return edge to P7 cannot restart the search. S3 is outside the depth-two answer, rather than proven unreachable.

Traverse the dependency cycle within a stated depth

The visited set stops repeated expansion through the cycle, while the depth record identifies the explicitly bounded reachable set.

Traverse the dependency cycle within a stated depth

Botie must stop revisiting equipment and keep the report’s reach explicit.

BOTIE

Botie must stop revisiting equipment and keep the report’s reach explicit.

Choose an example

Directed dependency graph

Nodes and properties (4)

P7 · Asset
S1 · Asset
S2 · Asset
S3 · Asset

P7 to S1: DEPENDS_ON
S1 to S2: DEPENDS_ON
S2 to P7: DEPENDS_ON
S2 to S3: DEPENDS_ON

Edit the node and relationship records

nodes

kind

edges

source

target

type

source

target

type

source

target

type

source

target

type

Starting asset

Maximum hop depth

Result for these records

Follow the operations

1. Directed dependency graph
Nodes and properties (4)
- P7 · Asset
- S1 · Asset
- S2 · Asset
- S3 · Asset
- P7 to S1: DEPENDS_ON
- S1 to S2: DEPENDS_ON
- S2 to P7: DEPENDS_ON
- S2 to S3: DEPENDS_ON
Inspect the node and relationship records
```
{
  "nodes": [
    {
      "id": "P7",
      "kind": "Asset"
    },
    {
      "id": "S1",
      "kind": "Asset"
    },
    {
      "id": "S2",
      "kind": "Asset"
    },
    {
      "id": "S3",
      "kind": "Asset"
    }
  ],
  "edges": [
    {
      "id": "a",
      "source": "P7",
      "target": "S1",
      "type": "DEPENDS_ON"
    },
    {
      "id": "b",
      "source": "S1",
      "target": "S2",
      "type": "DEPENDS_ON"
    },
    {
      "id": "c",
      "source": "S2",
      "target": "P7",
      "type": "DEPENDS_ON"
    },
    {
      "id": "d",
      "source": "S2",
      "target": "S3",
      "type": "DEPENDS_ON"
    }
  ]
}
```

2. Read graph relationships

[
  {
    "id": "a",
    "source": "P7",
    "target": "S1",
    "type": "DEPENDS_ON"
  },
  {
    "id": "b",
    "source": "S1",
    "target": "S2",
    "type": "DEPENDS_ON"
  },
  {
    "id": "c",
    "source": "S2",
    "target": "P7",
    "type": "DEPENDS_ON"
  },
  {
    "id": "d",
    "source": "S2",
    "target": "S3",
    "type": "DEPENDS_ON"
  }
]

3. Choose a relationship type

[
  {
    "id": "a",
    "source": "P7",
    "target": "S1",
    "type": "DEPENDS_ON"
  },
  {
    "id": "b",
    "source": "S1",
    "target": "S2",
    "type": "DEPENDS_ON"
  },
  {
    "id": "c",
    "source": "S2",
    "target": "P7",
    "type": "DEPENDS_ON"
  },
  {
    "id": "d",
    "source": "S2",
    "target": "S3",
    "type": "DEPENDS_ON"
  }
]

4. Starting asset
```
P7
```
5. Maximum hop depth
```
2
```

6. Find bounded reachable nodes

[
  {
    "id": "P7",
    "depth": 0
  },
  {
    "id": "S1",
    "depth": 1
  },
  {
    "id": "S2",
    "depth": 2
  }
]

7. Set a constant
```
0
```

8. Keep rows passing a comparison

[
  {
    "id": "S1",
    "depth": 1
  },
  {
    "id": "S2",
    "depth": 2
  }
]

9. Collect distinct identifiers
1. 0S1
2. 1S2
10. Result
1. 0S1
2. 1S2

These components operate on the supplied records in your browser. They do not run a graph database or interpret Cypher.

1. Choose whether the answer contains nodes or routes

Reachability asks whether a node can be reached at all. Path enumeration retains the route, so two different paths to S2 can both be useful results. A global visited set is suitable for our distinct reachability answer, but would suppress alternative routes if we were trying to enumerate them.

State this before writing a recursion. The same graph can legitimately produce different answers under different output contracts.

The challenge returns distinct reachable IDs, excluding the starting ID.

2. Keep a queue of nodes still to explore

Breadth-first search begins with the starting node at depth zero. Remove the oldest queued entry, inspect its outgoing dependency edges and add unseen targets at the next depth. Mark a target visited when it is queued so two frontier nodes do not enqueue it repeatedly.

Because each step has equal hop cost, the first discovery gives the minimum number of relationships from the start. Weighted cost is a different question.

The queue is work still to do; the visited set records identities already discovered.

Expand the first frontier

This program only inspects the first step. The exercise must keep expanding safely.

Python

g={"nodes": [{"id": "P7", "kind": "Asset"}, {"id": "S1", "kind": "Asset"}, {"id": "S2", "kind": "Asset"}, {"id": "S3", "kind": "Asset"}], "edges": [{"id": "a", "source": "P7", "target": "S1", "type": "DEPENDS_ON"}, {"id": "b", "source": "S1", "target": "S2", "type": "DEPENDS_ON"}, {"id": "c", "source": "S2", "target": "P7", "type": "DEPENDS_ON"}, {"id": "d", "source": "S2", "target": "S3", "type": "DEPENDS_ON"}]}
frontier=['P7']
next_ids={e['target'] for e in g['edges'] if e['type']=='DEPENDS_ON' and e['source'] in frontier}
print(sorted(next_ids))

Output

['S1']

The next frontier comes from outgoing edges of the current frontier, not every edge in the graph.

3. Bound a real path query deliberately

The Cypher range *1..3 requests paths from one through three relationships. DISTINCT on the returned node removes repeated endpoints from different matching paths. The query below also excludes the starting node if a cycle returns to it.

Cypher’s relationship-reuse rules and a global-visited BFS are different mechanisms. For this bounded reachability question their intended endpoint set aligns, but the path rows and search work need not be identical.

A hop bound says how far the query may explore; it does not certify the graph has no deeper nodes.

Run in your own environment

Ask for dependencies within three hops

This uses established variable-length relationship syntax; newer quantified syntax is another documented option.

In an empty test database run CREATE (p:Asset {id:'P7'}),(a:Asset {id:'S1'}),(b:Asset {id:'S2'}),(c:Asset {id:'S3'}),(p)-[:DEPENDS_ON]->(a),(a)-[:DEPENDS_ON]->(b),(b)-[:DEPENDS_ON]->(p),(b)-[:DEPENDS_ON]->(c).

Bind asset to P7.

cypher

MATCH (a:Asset {id:$asset})-[:DEPENDS_ON*1..3]->(d:Asset)
WHERE d <> a
RETURN DISTINCT d.id AS dependency ORDER BY dependency

The result includes S1, S2 and S3. The chosen three-hop cap is part of the report’s scope.

Official documentation. Documentation checked 2026-10-16.

4. Interpret the depth boundary honestly

At depth two, S2 has been discovered but its outgoing edges are not expanded. S3 is therefore absent from the two-hop result. Calling that result “all dependencies” would overstate what was checked.

A depth cap also does not bound the number of nodes tightly in a high-degree graph. Add operational time and result-size limits, and report truncation or failure rather than presenting partial results as a complete answer.

The workshop caps the reachable set to protect responsiveness and reports a limit error rather than silently trimming it.

5. Filter allowed relationships before expanding them

An edge type restriction prevents unrelated meanings from entering the traversal. A tenant or access restriction serves a different purpose: it determines which data the caller may use at all. Apply those restrictions before or during expansion, including intermediate nodes.

A shallow traversal can still read forbidden data. Treat depth and output limits as resource controls, never as permission checks.

The fixture is fully permitted. Later retrieval applies a scoped graph before either dependency or document expansion.

6. Inspect cycles as domain evidence as well as an algorithm concern

A cycle in a supply dependency may be an impossible import or a real mutually dependent system. A visited set makes our computation terminate, but it does not decide whether the cycle is valid in the domain.

Keep enough edge identity and provenance to investigate it. If the application requires a directed acyclic hierarchy, enforce or audit that separate invariant rather than assuming the traversal repaired the data.

Algorithmic termination and domain correctness solve different problems.

Follow a Dependency Without Following It Forever

Unknown-Length Connections Needed Repeated Expansion

The Dependency List Points Back to the Pump

A cycle returns to an already discovered node

Watch the frontier meet the cycle

Traverse the dependency cycle within a stated depth

Traverse the dependency cycle within a stated depth

Result for these records

1. Choose whether the answer contains nodes or routes

2. Keep a queue of nodes still to explore

Expand the first frontier

3. Bound a real path query deliberately

Ask for dependencies within three hops

Questions on Parts 1 to 3

4. Interpret the depth boundary honestly

5. Filter allowed relationships before expanding them

6. Inspect cycles as domain evidence as well as an algorithm concern

Questions on Parts 1 to 6

Build with Botie

Practice. Find distinct dependencies within the hop budget