MySQL: извлечение субграфа?

Question

У меня есть список смежности большого графа, хранящийся в таблице.

v1 |  v2
1  |  2
1  |  3
1  |  4
2  |  5
3  |  5
3  |  6
4  |  7
7  |  9
5  |  10

Я пытаюсь извлечь график на 2 шага от вершины 1, чтобы он возвращал все ребра из списка выше, кроме (7,9) и (5,10).Мне удалось это:

SELECT * FROM stub_graph WHERE v1 IN (SELECT v1 FROM stub_graph WHERE v1=1 UNION select v2 FROM stub_graph WHERE v1=1) ;

Я не особенно доволен своим решением по двум причинам:

1. Наличие IN
2. Это можетизвлечь ссылки, такие как 1-2 и 2-5, но я не могу извлечь ссылки, такие как 6-7.

Есть ли хороший способ сделать это?

Просто вЕсли кто-то заинтересован в создании таблицы, вот код sql:

create table stub_graph(v1 int(11), v2 int(11));
insert into stub_graph VALUES(1,2);
insert into stub_graph VALUES(1,3);
insert into stub_graph VALUES(1,4);
insert into stub_graph VALUES(2,5);
insert into stub_graph VALUES(3,5);
insert into stub_graph VALUES(3,6);
insert into stub_graph VALUES(4,7);
insert into stub_graph VALUES(6,7);
insert into stub_graph VALUES(7,9);
insert into stub_graph VALUES(5,10);

Answer 1

Попробуйте это:

SELECT g1.v1 as Root, g2.v1 as Next g3.v1 as Final FROM stub_graph g1 
  LEFT JOIN stub_graph g2 on g2.v1 = g1.v2
  LEFT JOIN stub_graph g3 on g3.v1 = g2.v2
WHERE g1.v1 = 1

Если вы хотите (6-7), хотя вам нужно пройти на три уровня глубиной, так как это 3 прыжка от 1 (1-3, 3-6, 6-7).

Если вы хотите углубиться в произвольный процесс, вам нужно взглянуть на рекурсивный хранимый процесс, который, как мне кажется, поддерживают более поздние версии MySQL, но он выглядит подходящим для ваших нужд. В качестве альтернативы ссылка ниже имеет некоторые другие идеи.

что должно дать:

Root | Next | Final
   1 |    3 |     5
   1 |    3 |     6
   1 |    2 |     5
   1 |    4 |     7

См. Также эту ссылку на иерархические данные