Примеры OQGRAPH

Создание таблицы только с origid, destid

CREATE TABLE oq_backing (
  origid INT UNSIGNED NOT NULL, 
  destid INT UNSIGNED NOT NULL,  
  PRIMARY KEY (origid, destid), 
  KEY (destid)
);

Некоторые данные могут быть вставлены в базовые таблицы для последующих тестов:

INSERT INTO oq_backing(origid, destid) 
 VALUES (1,2), (2,3), (3,4), (4,5), (2,6), (5,6);

Теперь создаётся таблица OQGRAPH только для чтения.

Начиная с MariaDB 10.1.2 вы можете использовать следующий синтаксис:

CREATE TABLE oq_graph
ENGINE=OQGRAPH 
data_table='oq_backing' origid='origid' destid='destid';

Перед MariaDB 10.1.2 оператор CREATE должен соответствовать формату ниже — любые отличия приведут к ошибке.

CREATE TABLE oq_graph (
  latch VARCHAR(32) NULL,
  origid BIGINT UNSIGNED NULL,
  destid BIGINT UNSIGNED NULL,
  weight DOUBLE NULL,
  seq BIGINT UNSIGNED NULL,
  linkid BIGINT UNSIGNED NULL,
  KEY (latch, origid, destid) USING HASH,
  KEY (latch, destid, origid) USING HASH
) 
ENGINE=OQGRAPH 
data_table='oq_backing' origid='origid' destid='destid';

Создание таблицы с весом

В примерах на этой странице мы создадим вторую таблицу OQGRAPH и базовые таблицы, на этот раз с weight тоже.

CREATE TABLE oq2_backing (
  origid INT UNSIGNED NOT NULL, 
  destid INT UNSIGNED NOT NULL, 
  weight DOUBLE NOT NULL, 
  PRIMARY KEY (origid, destid), 
  KEY (destid)
);

INSERT INTO oq2_backing(origid, destid, weight)  
 VALUES (1,2,1), (2,3,1), (3,4,3), (4,5,1), (2,6,10), (5,6,2);

CREATE TABLE oq2_graph (
  latch VARCHAR(32) NULL,
  origid BIGINT UNSIGNED NULL,
  destid BIGINT UNSIGNED NULL,
  weight DOUBLE NULL,
  seq BIGINT UNSIGNED NULL,
  linkid BIGINT UNSIGNED NULL,
  KEY (latch, origid, destid) USING HASH,
  KEY (latch, destid, origid) USING HASH
) 
ENGINE=OQGRAPH 
data_table='oq2_backing' origid='origid' destid='destid' weight='weight';

Кратчайший путь

Значение latch равно 'dijkstras', а origid и destid используются для поиска кратчайшего пути между двумя узлами, например:

SELECT * FROM oq_graph WHERE latch='breadth_first' AND origid=1 AND destid=6;
+----------+--------+--------+--------+------+--------+
| latch    | origid | destid | weight | seq  | linkid |
+----------+--------+--------+--------+------+--------+
| dijkstras|      1 |      6 |   NULL |    0 |      1 |
| dijkstras|      1 |      6 |      1 |    1 |      2 |
| dijkstras|      1 |      6 |      1 |    2 |      6 |
+----------+--------+--------+--------+------+--------+

Обратите внимание, что узлы однонаправленные, поэтому пути от узла 6 к узлу 1 нет:

SELECT * FROM oq_graph WHERE latch='dijkstras' AND origid=6 AND destid=1;
Empty set (0.00 sec)

Использование функции GROUP_CONCAT может привести к более удобочитаемым результатам, например:

SELECT GROUP_CONCAT(linkid ORDER BY seq) AS path FROM oq_graph 
 WHERE latch='dijkstras' AND origid=1 AND destid=6;
+-------+
| path  |
+-------+
| 1,2,6 |
+-------+

Используя таблицу oq2_graph, кратчайший путь отличается:

SELECT GROUP_CONCAT(linkid ORDER BY seq) AS path FROM oq2_graph 
 WHERE latch='dijkstras' AND origid=1 AND destid=6;
+-------------+
| path        |
+-------------+
| 1,2,3,4,5,6 |
+-------------+

Причина в том, что вес между узлами 2 и 6 равен 10 в oq_graph2, поэтому кратчайший путь с учётом weight теперь проходит через большее количество узлов.

Возможные пункты назначения

SELECT GROUP_CONCAT(linkid) AS dests FROM oq_graph WHERE latch='dijkstras' AND origid=2;
+-----------+
| dests     |
+-----------+
| 5,4,6,3,2 |
+-----------+

Обратите внимание, что это возвращает все возможные пункты назначения по пути, а не только непосредственные ссылки.

Листовые узлы

Значение latch равно 'leaves', а origid или destid используется для поиска листовых узлов в начале или конце графа.

INSERT INTO oq_backing(origid, destid)  
 VALUES (1,2), (2,3), (3,5), (4,5), (5,6), (6,7), (6,8), (2,8);

Например, чтобы найти все достижимые узлы из origid, которые имеют только входящие ребра:

SELECT * FROM oq_graph WHERE latch='leaves' AND origid=2;
+--------+--------+--------+--------+------+--------+
| latch  | origid | destid | weight | seq  | linkid |
+--------+--------+--------+--------+------+--------+
| leaves |      2 |   NULL |      4 |    2 |      7 |
| leaves |      2 |   NULL |      1 |    1 |      8 |
+--------+--------+--------+--------+------+--------+

И чтобы найти все узлы, из которых можно найти путь к destid, которые имеют только исходящие ребра:

SELECT * FROM oq_graph WHERE latch='leaves' AND destid=5;
+--------+--------+--------+--------+------+--------+
| latch  | origid | destid | weight | seq  | linkid |
+--------+--------+--------+--------+------+--------+
| leaves |   NULL |      5 |      3 |    2 |      1 |
| leaves |   NULL |      5 |      1 |    1 |      4 |
+--------+--------+--------+--------+------+--------+

Резюме реализованных команд защелки

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

Использование целочисленных защелок контролируется системной переменной oqgraph_allow_create_integer_latch.

См. также

• Обзор OQGRAPH