В моем предыдущем посте я говорил о графических базах данных ( в частности, Neo4j ) и о том, как их можно применять к определенным классам задач, где данные могут иметь несколько степеней разделения в своих отношениях.
Что делает графические базы данных полезными, так это возможность находить пути отношений от одного узла к другому. Существует много алгоритмов для эффективного поиска путей в зависимости от варианта использования.
Рассмотрим график, который представляет карту города. Каждый узел на графике представляет собой пересечение двух или более улиц. Каждое направление улицы представлено в виде разных отношений: улицы с двусторонним движением будут иметь два отношения между одними и теми же двумя узлами, одно указывает от первого узла ко второму, а другое — от второго узла к первому. Улицы с односторонним движением будут иметь единую связь. Каждое отношение улицы также будет иметь свойство расстояния . Вот как может выглядеть одна такая карта:
Вот код для создания этого графа в базе данных с использованием
клиента REST, над которым я работал (инициализация соединения не показана):
$intersections = array(
"First & Main",
"Second & Main",
"Third & Main",
"First & Oak",
"Second & Oak",
"Third & Market",
);
$streets = array(
// start, end, [direction, distance, name]
array(0, 1, array('direction'=>'east', 'distance'=>2, 'name'=>'Main St.')),
array(0, 3, array('direction'=>'south', 'distance'=>2, 'name'=>'First Ave.')),
array(0, 4, array('direction'=>'south', 'distance'=>3, 'name'=>'Park Dr.')),
array(1, 0, array('direction'=>'west', 'distance'=>2, 'name'=>'Main St.')),
array(1, 2, array('direction'=>'east', 'distance'=>2, 'name'=>'Main St.')),
array(1, 4, array('direction'=>'south', 'distance'=>2, 'name'=>'Second Ave.')),
array(2, 1, array('direction'=>'west', 'distance'=>2, 'name'=>'Main St.')),
array(2, 5, array('direction'=>'south', 'distance'=>1, 'name'=>'Third Ave.')),
array(3, 0, array('direction'=>'north', 'distance'=>2, 'name'=>'First Ave.')),
array(3, 4, array('direction'=>'east', 'distance'=>2, 'name'=>'Oak St')),
array(4, 3, array('direction'=>'west', 'distance'=>2, 'name'=>'Oak St.')),
array(4, 1, array('direction'=>'north', 'distance'=>2, 'name'=>'Second Ave.')),
array(5, 2, array('direction'=>'north', 'distance'=>1, 'name'=>'Third Ave.')),
array(5, 4, array('direction'=>'west', 'distance'=>2, 'name'=>'Market Alley')),
);
$nodes = array();
$intersectionIndex = new Index($client, Index::TypeNode, 'intersections');
foreach ($intersections as $intersection) {
$node = new Node($client);
$node->setProperty('name', $intersection)->save();
$intersectionIndex->add($node, 'name', $node->getProperty('name'));
$nodes[] = $node;
}
foreach ($streets as $street) {
$start = $nodes[$street[0]];
$end = $nodes[$street[1]];
$properties = $street[2];
$start->relateTo($end, 'CONNECTS')
->setProperties($properties)
->save();
}
Сначала мы устанавливаем список перекрестков на карте, а также список улиц, которые соединяют эти перекрестки. У каждой улицы будет отношение, в котором есть данные о направлении улицы, расстоянии и названии.
Затем мы создаем каждый узел пересечения. Каждый узел также добавляется в индекс. Индексы позволяют быстро найти сохраненные узлы. Узлы и отношения могут быть проиндексированы, и индексация может происходить в любом узле или поле отношения. Вы даже можете индексировать поля, которые не существуют в узле или взаимосвязи. Мы будем использовать индекс позже, чтобы найти начальную и конечную точки нашего пути по имени.
Наконец, мы создаем отношения для каждой улицы. К отношениям могут быть прикреплены произвольные данные, как и к узлам.
Теперь мы создаем способ найти и отобразить направления движения от любого перекрестка до любого другого перекрестка:
$turns = array(
'east' => array('north' => 'left','south' => 'right'),
'west' => array('north' => 'right','south' => 'left'),
'north' => array('east' => 'right','west' => 'left'),
'south' => array('east' => 'left','west' => 'right'),
);
$fromNode = $intersectionIndex->findOne("Second & Oak");
$toNode = $intersectionIndex->findOne("Third & Main");
$paths = $fromNode->findPathsTo($toNode, 'CONNECTS', Relationship::DirectionOut)
->setMaxDepth(5)
->getPaths();
foreach ($paths as $i => $path) {
$path->setContext(Path::ContextRelationship);
$prevDirection = null;
$totalDistance = 0;
echo "Path " . ($i+1) .":\n";
foreach ($path as $j => $rel) {
$direction = $rel->getProperty('direction');
$distance = $rel->getProperty('distance') * 100;
$name = $rel->getProperty('name');
if (!$prevDirection) {
$action = 'Head';
} else if ($prevDirection == $direction) {
$action = 'Continue';
} else {
$turn = $turns[$prevDirection][$direction];
$action = "Turn $turn, and continue";
}
$prevDirection = $direction;
$step = $j+1;
$totalDistance += $distance;
echo "\t{$step}: {$action} {$direction} on {$name} for {$distance} yards.\n";
}
echo "\tTravel distance: {$totalDistance} yards\n\n";
}
Обратите внимание, что в вызове `findPathsTo` мы указываем, что нам нужны только исходящие отношения. Таким образом мы не можем получить указания, которые могут привести нас в неверном направлении по улице с односторонним движением. Мы также устанавливаем максимальную глубину, поскольку глубина поиска по умолчанию равна 1. Также обратите внимание на вызов `setContext`, который указывает путь, по которому мы хотим, чтобы` foreach` проходил через отношения, а не узлы. Запуск этого дает следующие направления:
Path 1:
1: Head north on Second Ave. for 200 yards.
2: Turn left, and continue west on Main St. for 200 yards.
Travel distance: 400 yards
Мы вернули только один путь, потому что по умолчанию алгоритм поиска пути находит самый
короткий путь , то есть путь с наименьшим количеством отношений. Если переключить
в и
из перекрестков, мы можем получить направление обратно к исходной точке:
Path 1:
1: Head west on Main St. for 200 yards.
2: Turn left, and continue south on Second Ave. for 200 yards.
Travel distance: 400 yards
Path 2:
1: Head south on Third Ave. for 100 yards.
2: Turn right, and continue west on Market Alley for 200 yards.
Travel distance: 300 yards
На этот раз мы вернулись двумя путями, но один из них длиннее другого. Как это может быть, если мы используем
алгоритм кратчайшего пути ? Ответ в том, что
кратчайший путь относится только к числу связей в пути. Мы не говорили нашему поисковику пути обращать внимание на
стоимость одного пути по сравнению с другим. К счастью, мы можем сделать это довольно легко, сказав вызову `findPathsTo` использовать свойство каждого отношения при определении того, какой путь является наименее дорогим:
$paths = $fromNode->findPathsTo($toNode, 'CONNECTS', Relationship::DirectionOut)
->setAlgorithm(PathFinder::AlgoDijkstra)
->setCostProperty('distance')
->setMaxDepth(5)
->getPaths();
Мы говорим искателю пути использовать
алгоритм Дейкстры , алгоритм для поиска пути с
наименьшей стоимостью , который отличается от самого
короткого пути. Поскольку наша карта использует расстояние,
стоимость пути является суммой всех свойств расстояния отношений в этом пути. Запуск скрипта теперь дает нам только один путь, путь с наименьшим расстоянием:
Path 1:
1: Head south on Third Ave. for 100 yards.
2: Turn right, and continue west on Market Alley for 200 yards.
Travel distance: 300 yards
Если бы существовал другой путь с таким же общим расстоянием, он также был бы отображен. Стоимость пути игнорирует количество связей в пути. Если бы существовал путь с 3 отношениями на общую сумму 300 ярдов, а другой — с 1 отношением на общую сумму 300 ярдов, то отображались бы оба.
Neo4j имеет несколько встроенных алгоритмов поиска пути. Некоторые из них:
- кратчайший путь — найти пути с наименьшим количеством отношений
- dijkstra — найти пути с наименьшей стоимостью
- простой путь — найти пути без повторяющихся узлов
- все — найти все пути между двумя узлами
Neo4j также поставляется с выразительным API-интерфейсом обхода, который позволяет создавать собственные алгоритмы поиска пути для конкретных задач.