Shortest Path via SQLite

paths.sql

pragma foreign_keys=off;

drop table if exists vertices;
drop table if exists arestas;
drop table if exists restricoes;
drop view if exists std;
drop view if exists search;
drop view if exists shortest_path;
drop view if exists path;

begin transaction;

-- tabela dos nós da rede direcionada
create table if not exists vertices (
  id    int not null primary key,
  nome  text not null unique
);

-- tabela das arestas da rede direcionada
create table if not exists arestas (
  origem      int not null references vertices(id) on update cascade,
  destino     int not null references vertices(id) on update cascade,
  distancia   int not null,
  constraint unicidade unique(origem, destino) on conflict ignore
);

-- tabela dos parâmetros das restrições do problema
create table if not exists restricoes (
  ORIGEM  int not null  --> id do nó inicial dos percursos solução
    references vertices(id) on update cascade,
  DESTINO int not null  --> id do nó final dos percursos solução
    references vertices(id) on update cascade,
  constraint bounds check(ORIGEM <> DESTINO)
);

-- preenchimento arbitrário dos parâmetros das restrições do problema
create trigger t0_restricoes before insert on restricoes
when new.ORIGEM isnull and new.DESTINO isnull
begin
  insert into restricoes select min(origem), max(destino) from arestas;
  select raise(ignore);
end;

-- a linha inserida mais recentemente será a única da tabela
create trigger t1_restricoes after insert on restricoes
when (select count(1) from restricoes) > 1
begin
  delete from restricoes where rowid == 1;
  update restricoes set rowid=1;
end;

create trigger t2_restricoes before delete on restricoes
when (select count(1) from restricoes) == 1
begin
  select raise(abort, 'exclusão da única linha da tabela');
end;

create view if not exists std as select ',' as sep;

-- view dos percursos factíveis i.e. percursos aciclicos que satisfazem as
-- restrições de origem e destino
-- nota: REGEXP via Debian package sqlite3-pcre
create view if not exists search as
  with recursive this (lista, distancia) as (
    select -- percursos iniciais
      arestas.origem || sep || arestas.destino, --> [origem, destino]
      arestas.distancia
    from arestas, restricoes, std
    where
      -- a aresta não é um laço e satisfaz a restrição de origem
      arestas.origem <> arestas.destino
      and arestas.origem == restricoes.ORIGEM   --> lista ~ ORIGEM*
    union all
    select -- percursos extendidos
      this.lista || sep || arestas.destino,     --> lista + [destino]
      this.distancia + arestas.distancia
    from std, this inner join arestas on (
      -- a aresta pode ser concatenada à lista sem criar ciclo pois seu
      -- nó origem é o último da lista que não contém seu nó destino
      this.lista REGEXP "\b" || arestas.origem || "$"
      and this.lista NOT REGEXP "\b" || arestas.destino || "\b"
    )
    order by 2  --> distância em ordem crescente
  ) select this.*
    from this, restricoes
    where -- satisfaz a restrição de destino
      this.lista REGEXP "\b" || restricoes.DESTINO || "$";

-- percurso ótimo i.e.: o percurso factível com a menor distância
-- nota: a solução ótima pode não ser a única ou até não existir
create view if not exists shortest_path as select * from search limit 1;

-- view dos ids dos nós do percurso ótimo
create view if not exists path as
  with par as (
    select lista, sep from shortest_path, std
  ), split (p) as (
    select 1
    union all
    select p+instr(substr(lista, p), sep) as q from split, par where q > p
  ) select cast(substr(lista, p) as int) as id from split, par;

commit;

pragma foreign_keys=on; --> habilita integridade referencial

.import vertices.dat vertices
select printf("#vertices: %d", count(*)) from vertices;

.import arestas.dat arestas
select printf(" #arestas: %d", count(*)) from arestas;

insert into restricoes values (null, null);

select printf("Restrições:"||x'0A'||"  origem: %d"||x'0A'||" destino: %d", origem, destino) from restricoes;