SQLite Forum

Breadth-first graph traversal
Login
You will note that the current (next release) version of SQLite3 allows more than one "recursive select" so you can now do something like this:

```
create table edges(fromNode integer, toNode integer);
insert into edges(fromNode, toNode) values
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5),
    (4, 6),
    (5, 7),
    (6, 7);

with bfs_tree(startat, endat, visited, distance)
  as (
         select 1, 1, '/' || 1 || '/', 0
      union all
         select startat, toNode, visited || toNode || '/', distance + 1
           from edges, bfs_tree
          where fromNode == endat
            and instr(visited, '/' || toNode || '/') == 0
      union all
         select startat, fromNode, visited || fromNode || '/', distance + 1
           from edges, bfs_tree
          where toNode == endat
            and instr(visited, '/' || fromNode || '/') == 0
    )
  select *
    from bfs_tree
order by startat, endat, distance;
```

so that your edges become bi-directional with the following results:

```
┌─────────┬───────┬───────────────┬──────────┐
│ startat │ endat │    visited    │ distance │
├─────────┼───────┼───────────────┼──────────┤
│ 1       │ 1     │ /1/           │ 0        │
│ 1       │ 2     │ /1/2/         │ 1        │
│ 1       │ 2     │ /1/3/4/2/     │ 3        │
│ 1       │ 3     │ /1/3/         │ 1        │
│ 1       │ 3     │ /1/2/4/3/     │ 3        │
│ 1       │ 4     │ /1/2/4/       │ 2        │
│ 1       │ 4     │ /1/3/4/       │ 2        │
│ 1       │ 5     │ /1/2/4/5/     │ 3        │
│ 1       │ 5     │ /1/3/4/5/     │ 3        │
│ 1       │ 5     │ /1/2/4/6/7/5/ │ 5        │
│ 1       │ 5     │ /1/3/4/6/7/5/ │ 5        │
│ 1       │ 6     │ /1/2/4/6/     │ 3        │
│ 1       │ 6     │ /1/3/4/6/     │ 3        │
│ 1       │ 6     │ /1/2/4/5/7/6/ │ 5        │
│ 1       │ 6     │ /1/3/4/5/7/6/ │ 5        │
│ 1       │ 7     │ /1/2/4/5/7/   │ 4        │
│ 1       │ 7     │ /1/2/4/6/7/   │ 4        │
│ 1       │ 7     │ /1/3/4/5/7/   │ 4        │
│ 1       │ 7     │ /1/3/4/6/7/   │ 4        │
└─────────┴───────┴───────────────┴──────────┘
```

However, the reference to the recursion table in the recursion parts is still a reference to the current singleton being recursed.