uCTrbLRB

1pragma foreign_keys=off;
2
3drop table if exists vertices;
4drop table if exists arestas;
5drop table if exists restricoes;
6drop table if exists formatos;
7drop view if exists paths;
8drop view if exists shortest_path;
9
10begin transaction;
11
12-- tabela dos nós da rede
13create table if not exists vertices (
14  id    int not null primary key,
15  nome  text not null unique
16);
17
18-- tabela das arestas da rede
19create table if not exists arestas (
20  origem      int not null references vertices(id) on update cascade,
21  destino     int not null references vertices(id) on update cascade,
22  distancia   int not null,
23  constraint unicidade unique(origem, destino) on conflict ignore
24);
25
26-- view dos percursos factíveis i.e. percursos que satisfazem as restrições de
27-- origem e destino
28create view if not exists paths as
29  with recursive this (lista, distancia) as (
30    with start as ( -- arestas que iniciam prováveis percursos factíveis
31      select arestas.* from arestas, restricoes
32      where -- aresta não é laço e satisfaz a restrição de origem
33        arestas.origem <> arestas.destino
34        and arestas.origem == restricoes.origem --> lista ~ origem*
35    ) select -- percursos que somente contém nó origem e destino
36      printf(SEQ, start.origem, start.destino),
37      start.distancia
38    from start, formatos
39    union all
40    select -- percursos que contém nós intermediários
41      this.lista || printf(FMT, arestas.destino),
42      this.distancia + arestas.distancia
43    from this, arestas, formatos
44    where -- inclusão de aresta na lista é viável
45      not this.lista GLOB printf(ANY, arestas.destino) --> lista !~ *destino*
46      and this.lista GLOB printf(TAIL, arestas.origem) --> lista ~ *origem
47  ) select lista, distancia
48    from this, restricoes, formatos
49    where -- satisfaz a restrição de destino
50      this.lista GLOB printf(TAIL, restricoes.destino); --> lista ~ *destino
51
52-- view dos ids e nomes dos nós do percurso ótimo i.e. o percurso factível
53-- com a menor distância
54-- nota: a solução ótima pode não ser a única ou até não existir
55create view if not exists shortest_path as
56  with par (lista, m) as (
57    select lista, instr(lista, " ")
58    from paths order by distancia limit 1  --> percurso ótimo
59  ), self (p, id) as ( -- extrai ids da lista
60    select 1+m, substr(lista, 1, m) from par
61    union all
62    select p+m, substr(lista, p, m) from self, par where id <> ""
63  ) select cast(id as int) as id, nome from self natural join vertices;
64
65-- tabela dos parâmetros das restrições do problema
66create table if not exists restricoes (
67  origem  int not null  --> id do nó inicial dos percursos solução
68    references vertices(id) on update cascade,
69  destino int not null  --> id do nó final dos percursos solução
70    references vertices(id) on update cascade,
71  constraint chkBounds check(origem <> destino)
72);
73
74-- preenchimento arbitrário dos parâmetros das restrições do problema
75create trigger t0_restricoes before insert on restricoes
76when new.origem isnull and new.destino isnull
77begin
78  insert into restricoes select min(origem), max(destino) from arestas;
79  select raise(ignore);
80end;
81
82-- a linha inserida mais recentemente será a única da tabela
83create trigger t1_restricoes after insert on restricoes
84when (select count(1) from restricoes) > 1
85begin
86  delete from restricoes where rowid == 1;
87  update restricoes set rowid=1;
88end;
89
90create trigger t2_restricoes before delete on restricoes
91when (select count(1) from restricoes) == 1
92begin
93  select raise(abort, 'exclusão da única linha da tabela');
94end;
95
96-- tabela do formato para representar inteiros como strings que viabilizam o
97-- uso das listas de ids e formatos para montagem de wildcards padrão GLOB
98create table if not exists formatos (
99  FMT   text not null --> output de ids
100        constraint chkFMT check(FMT GLOB "%0[1-9]d "),
101  SEQ   text not null --> output de ids em sequência
102        constraint chkSEQ check(SEQ == FMT||FMT),
103  ANY   text not null --> pesquisa id em qualquer posição da lista - anywhere
104        constraint chkANY check(ANY == "*"||FMT||"*"),
105  TAIL  text not null --> pesquisa id no fim da lista - rightmost
106        constraint chkTAIL check(TAIL == "*"||FMT)
107);
108
109-- preenchimento dos formatos em função da representação do maior id
110create trigger t0_formatos before insert on formatos
111when new.FMT isnull and new.SEQ isnull and new.ANY isnull and new.TAIL isnull
112begin
113  insert into formatos
114    select FMT, FMT||FMT, "*"||FMT||"*", "*"||FMT
115    from ( -- formato para representar qualquer inteiro como string
116      select "%0"||length(cast(max(id) as text))||"d " as FMT from vertices
117    );
118  select raise(ignore);
119end;
120
121create trigger t1_formatos after insert on formatos
122when (select count(1) from formatos) > 1
123begin
124  delete from formatos where rowid == 1;
125  update formatos set rowid=1;
126end;
127
128create trigger t2_formatos before delete on formatos
129when (select count(1) from formatos) == 1
130begin
131  select raise(abort, 'exclusão da única linha da tabela');
132end;
133
134commit;
135
136pragma foreign_keys=on; --> assegura integridade referencial
137
138.import vertices.dat vertices
139select printf("%d vertices carregados", count(*)) from vertices;
140
141.import arestas.dat arestas
142select printf("%d arestas carregadas", count(*)) from arestas;
143
144insert into restricoes values (null, null);
145
146insert into formatos values (null, null, null, null);
147
148select printf("Parâmetros das restrições:"||x'0A'||" origem: %d"||x'0A'||" destino: %d", origem, destino) from restricoes;