Recentemente me deparei com o problema de trabalhar com grafos com SQL. Dado o modelo de dados abaixo, como resolver (no fim do artigo existem alguns exemplos de grafos que podem ser usados para teste):

  1. Detectar se existem ciclos no grafo
  2. Encontrar todos os caminhos no grafo
create table graph (
	id varchar(100) primary key,
	name varchar(500) not null
);

create table node (
	id varchar(100),
	graph_id varchar(100) references graph(id),
	name varchar(500) not null,
	primary key (graph_id, id)
);

create table edge (
	id varchar(100),
	graph_id varchar(100) references graph(id),
	from_id varchar(100),
	to_id varchar(100),
	cost float not null,
	foreign key (graph_id, from_id) references node(graph_id, id),
	foreign key (graph_id, to_id) references node(graph_id, id)
);

Não vou entrar nos méritos no modelo, existem várias formas de modelar o grafo. O ponto principal é como escrever um query SQL para resolver o problema.

O algoritmo básico para detecção de ciclos consiste em uma busca em profundidade (Depth First Search, DFS). Basicamente, o algoritmo é resursivo e vai visitando todas as ramificações e se, em uma dessas ramificações, ele encontra um nó que já foi visitado, então existe um ciclo. Não vou entrar em muitos detalhes, aqui tem uma explicação da ideia. A questão é, como resolver esse problemas apenas com SQL? É possível usando recursive common table expressions (Recursive CTEs). Uma CTE é parecica com uma view, mas com a possibilidade de se auto-referenciar, permitindo uma consulta recursiva. Uma CTE recursiva tem o formato

with recursive cte_name (columns) as (
	-- base case
    select * from table
	union all
    -- recursive case (select based on the previous cte_name result)
	select * from cte_name
)
-- final resultset
select * from cte_name;

Encontrar ciclos Link para o cabeçalho

A ideia é ter uma consulta base e depois definir uma consulta recursiva em cima do resultado anterior. A consulta termina quando o segundo select (após o union all) retorna vazio. Com isso, a detecção de ciclos pode ser resolvida com a seguinte query.

with recursive graph_traversal as (
	select
        graph_id,
		from_id,
		to_id,
		concat(',', from_id, ',', to_id, ',') as nodes,
		(case when from_id = to_id then 1 else 0 end) as has_cycle
	from
		edge
    where
        graph_id = <GRAPH ID HERE>
	union all
	select
        e.graph_id,
		e.from_id,
		e.to_id,
		concat(graph_traversal.nodes, e.to_id, ',') as nodes,
		(case when graph_traversal.nodes like concat('%,', e.to_id, ',%') then 1 else 0 end) as has_cycle
	from
		graph_traversal
		join edge e on e.from_id = graph_traversal.to_id and e.graph_id = graph_traversal.graph_id
	where
		graph_traversal.has_cycle = 0
)
select exists(select 1 from graph_traversal where has_cycle = 1 limit 1) as has_cycle;

O caso base é a enumeração de todas as arestas do grafo. O detalhe é a coluna nodes que mantém uma lista de nós visitados, que é utilizada para detectar ciclos. Depois, temos a consulta recursiva sobre a CTE graph_traversal. Note que a consulta apenas continua se has_cycle = 0, para que a busca termine assim que um ciclo for encontrado, sem a necessidade de enumerar todas as possibilidades. Outro ponto que determina o fim da recursão é se o join retornar vazio, ou seja, não existir um próximo nó. Por fim, existe um select exists apenas para determinar se existe ou não o ciclo no grafo em questão. Lembrando que no fim desta página existem exemplos de grafos podem ser usados para testar a query acima.

Encontrar todos os caminhos Link para o cabeçalho

Nesse caso, o problema é basicamente o mesmo de antes, mas com a condição de parada indicada pelo nó de início e fim do grafo. Note que nesse caso, não é possível parar assim que encontrar um caminho, é necessário enumerar todas as possibilidades.

with recursive graph_traversal (graph_id, from_id, to_id, node_path, path_cost, has_cycle) as (
	select
        graph_id,
		from_id,
		to_id,
		concat(',', from_id, ',', to_id, ',') as node_path,
		cost as path_cost,
		(case when from_id = to_id then true else false end) as has_cycle
	from
		edge
    where
        graph_id = <GRAPH ID HERE>
        and
        from_id = <FROM ID HERE>
	union all
	select
        e.graph_id,
		e.from_id,
		e.to_id,
		concat(gt.node_path, e.to_id, ',') as node_path,
		gt.path_cost + e.cost as path_cost,
		(case 
			when gt.has_cycle then true
			when gt.node_path like concat('%%,', e.to_id, ',%%') then true
			else false 
		end) as has_cycle
	from
		graph_traversal as gt
		join edge as e on e.from_id = gt.to_id and e.graph_id = gt.graph_id
	where
		not gt.has_cycle
		or
		e.to_id = <TO ID HERE>
)
select
	trim(',' from gt.node_path) as path,
	gt.path_cost as cost
from
	graph_traversal as gt
where
	gt.to_id = <TO ID HERE>
	and
	not gt.has_cycle;

A query é um tanto diferente da anterior. Primeiramente, tem a coluna cost a mais indicando o custo total do caminho até o momento. Outro detalhe é que a condição de início é dada por um nó de origem. Da mesma forma que na consulta anterior, só são enumerados os caminhos se o grafo não tem ciclos. No mais, a consulta é basicamente a mesma e o filtro pelo nó final é feito na consulta fora da CTE. A questão aqui é que a CTE está enumerando todos os caminhos a partir de um nó de origem até ao nó de destino desejado. No fim também é necessário remover algumas , no começo/fim de node_path para deixar o caminho bem arrumado.

Note que a consulta acima retorna o custo dos caminhos, dessa forma também é possível usar essa consulta para encontrar o caminho mínimo entre dois pontos. Obviamente que não é uma solução ideal, visto que ela enumera todos os caminhos possíveis e algoritmos de busca em largura (Beadth First Search, BFS) são muito melhores para isso. Porém, é uma forma de resolver o problema apenas com SQL, sem a necessidade de escrever nenhum outro algoritmo.

Bem, esse foi um desafio interessante que tive que resolver e nunca havia pensado em usar SQL para modelar e fazer operações em grafos. Abaixo seguem alguns exemplos para testar as consultas acima.

Alguns exemplos de grafos para teste Link para o cabeçalho

-- cycle 1
insert into graph (id, name) values ('cycle1', 'graph');

insert into node (graph_id, id, name) values ('cycle1', 'a', 'a');
insert into node (graph_id, id, name) values ('cycle1', 'b', 'b');
insert into node (graph_id, id, name) values ('cycle1', 'c', 'c');
insert into node (graph_id, id, name) values ('cycle1', 'd', 'd');

insert into edge (graph_id, from_id, to_id, cost) values ('cycle1', 'a', 'c', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle1', 'b', 'a', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle1', 'c', 'b', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle1', 'd', 'c', 0);

-- cycle 2

insert into graph (id, name) values ('cycle2', 'graph');

insert into node (graph_id, id, name) values ('cycle2', 'a', 'a');
insert into node (graph_id, id, name) values ('cycle2', 'b', 'b');
insert into node (graph_id, id, name) values ('cycle2', 'c', 'c');

insert into edge (graph_id, from_id, to_id, cost) values ('cycle2', 'a', 'c', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle2', 'b', 'a', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle2', 'c', 'b', 0);

-- cycle 3 and disjoint

insert into graph (id, name) values ('cycle_disjoint', 'graph');

insert into node (graph_id, id, name) values ('cycle_disjoint', 'a', 'a');
insert into node (graph_id, id, name) values ('cycle_disjoint', 'b', 'b');
insert into node (graph_id, id, name) values ('cycle_disjoint', 'c', 'c');
insert into node (graph_id, id, name) values ('cycle_disjoint', 'd', 'd');
insert into node (graph_id, id, name) values ('cycle_disjoint', 'e', 'e');

insert into edge (graph_id, from_id, to_id, cost) values ('cycle_disjoint', 'a', 'c', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle_disjoint', 'b', 'a', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle_disjoint', 'c', 'b', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('cycle_disjoint', 'd', 'e', 0);

-- no cycle

insert into graph (id, name) values ('no_cycle', 'graph');

insert into node (graph_id, id, name) values ('no_cycle', 'a', 'a');
insert into node (graph_id, id, name) values ('no_cycle', 'b', 'b');
insert into node (graph_id, id, name) values ('no_cycle', 'c', 'c');

insert into edge (graph_id, from_id, to_id, cost) values ('no_cycle', 'a', 'c', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('no_cycle', 'b', 'a', 0);
insert into edge (graph_id, from_id, to_id, cost) values ('no_cycle', 'b', 'c', 0);

-- loop

insert into graph (id, name) values ('loop', 'graph');

insert into node (graph_id, id, name) values ('loop', 'a', 'a');

insert into edge (graph_id, from_id, to_id, cost) values ('loop', 'a', 'a', 0);

-- no_connections

insert into graph (id, name) values ('no_connections', 'graph');

insert into node (graph_id, id, name) values ('no_connections', 'a', 'a');

-- path

insert into graph (id, name) values ('path', 'graph');

insert into node (graph_id, id, name) values ('path', 'a', 'a');
insert into node (graph_id, id, name) values ('path', 'b', 'b');
insert into node (graph_id, id, name) values ('path', 'c', 'c');
insert into node (graph_id, id, name) values ('path', 'd', 'd');
insert into node (graph_id, id, name) values ('path', 'e', 'e');
insert into node (graph_id, id, name) values ('path', 'f', 'f');

insert into edge (graph_id, from_id, to_id, cost) values ('path', 'a', 'b', 2);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'a', 'c', 5);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'a', 'f', 6.5);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'b', 'd', 3);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'c', 'e', 3);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'c', 'd', 1);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'd', 'f', 2);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'e', 'f', 2);
insert into edge (graph_id, from_id, to_id, cost) values ('path', 'e', 'a', 1);