CLR

Анализ графов для поиска кратчайшего пути с применением хранимой процедуры CLR

Джеймс Маккафри

Исходный код можно скачать по ссылке.

Продукты и технологии:

CLR, C#, SQL Server

В статье рассматриваются:

• создание примера базы данных;
• создание хранимой процедуры CLR (CLR stored procedure);
• кодирование собственной очереди с приоритетами;
• создание хранимой процедуры с алгоритмом поиска кратчайшего пути;
• создание, развертывание и вызов хранимой процедуры.

Анализ графов (graph analysis) становится все важнее в программном обеспечении. Здесь под графом подразумевается набор узлов и ветвей (edges), а не тип визуализации данных вроде столбчатой диаграммы. В этой статье демонстрируется, как выполнять поиск кратчайшего пути с применением хранимой процедуры SQL CLR. Методику, представленную здесь, также можно использовать для многих других задач в области программирования доступа к данным.

Анализ графов для поиска кратчайшего пути (shortest-path graph analysis) на самом деле включает две близко связанные задачи. Сначала определяется кратчайший путь от указанного начального узла графа до конечного, выражаемый числом переходов (hops). Вторая задача — определение длины кратчайшего пути, если нужно учитывать некую весовую долю соединений графа (graph connections). Например, узлы в графе представляют людей, а ветви между узлами — коммуникацию по электронной почте. Возможно, вас интересует минимальное число переходов между двумя людьми, где вы неявно предполагаете, что весовая доля каждого перехода равна 1. Это аналогично игре «Шесть шагов до Кевина Бэйкона» («six degrees of Kevin Bacon») или числу Эрдеша (Erdos number) для исследователя. Если каждая ветвь графа имеет весовую долю (скажем, представляющую некую меру важности отношений), то, вероятно, вы захотите определить кратчайший путь между двумя людьми, принимая во внимание весовую долю важности отношений.

Но зачем использовать хранимую процедуру CLR? Традиционные алгоритмы поиска кратчайшего пути исходят из предположения, что представление графа может быть целиком загружено в память компьютера, обычно в виде матрицы или списка смежности (adjacency list). Для больших графов, например представляющих социальные сети, этот подход зачастую нереален. Большие графы удобно хранить в базе данных SQL. Один из подходов к анализу графов, хранящихся в базе данных SQL, — написать хранимую процедуру на языке SQL. В статье «Graph-Based Shortest-Path Analysis with SQL» (msdn.microsoft.com/magazine/jj863138) этот подход поясняется очень подробно. Однако применение хранимой процедуры CLR вместо чистого SQL может дать значительно более высокую производительность и намного большую гибкость в адаптации.

Взгляните на представление вымышленного графа на рис. 1. В этом графе восемь узлов. Числа рядом с каждой стрелкой представляют весовую долю. Кратчайший путь между узлами 222 и 444 — 222 → 555 → 666 → 777 → 444, который имеет взвешенное расстояние 1.0 + 1.0 + 1.0 + 2.0 = 5.0. Заметьте, что 222 → 333 → 666 → 777 → 444 также является кратчайшим путем от узла 222 к узлу 444.

Рис. 1. Вымышленный граф для поиска кратчайшего пути

На рис. 2 показан экранный снимок вызова хранимой процедуры CLR с именем csp_ShortestPath, которая определяет кратчайший путь между узлами 222 и 444. В этом случае кратчайший путь отображается в обратном порядке как строка, разделенная точками с запятыми. Этот вывод показывается внизу. В верхней части содержатся SQL-выражения, которые создают граф, соответствующий представленному на рис. 1.

Рис. 2. Вызов хранимой процедуры CLR для поиска кратчайшего пути

В этой статье предполагается, что вы обладаете «продвинутыми» навыками программирования на C# и имеете базовое представление о SQL. Я покажу весь SQL-код для создания вымышленного графа и весь код на C# для создания хранимой процедуры CLR, а также опишу несколько способов вызова такой процедуры. Полный исходный код для этой статьи доступен по ссылке archive.msdn.microsoft.com/mag201305Graph.

Создание базы данных

Чтобы создать вымышленный граф на основе SQL, я запустил Microsoft SQL Server Management Studio (SSMS) и подключился к экземпляру SQL Server 2008. Хранимые процедуры CLR поддерживаются версиями SQL Server от 2005 и выше. Сначала я создал базу данных dbShortPathWithCLR, используя следующие команды:

use master
go
if exists(select * from sys.sysdatabases
  where name='dbShortPathWithCLR')
  drop database dbShortPathWithCLR
go
create database dbShortPathWithCLR
go
use dbShortPathWithCLR
go

Настоятельно рекомендую экспериментировать с такой базой данных, а не с производственной. Вот команды, необходимые для создания таблицы, которая хранит данные узлов и ветвей:

create table tblGraph
(
  fromNode bigint not null,
  toNode bigint not null,
  edgeWeight real not null
)
go

Идентификаторы узлов хранятся как SQL-тип bigint, который приблизительно соответствует C#-типу long, а весовые значения ветвей — как тип real, являющийся синонимом SQL-типа float(24) и примерно соответствующий C#-типу double. Во многих ситуациях вас не будут интересовать весовые значения ветвей, и столбец edgeWeight может быть опущен.

Граф определяют 14 выражений на рис. 3.

Рис. 3. Определение графа

insert into tblGraph values(111,222,1.0)
insert into tblGraph values(111,555,1.0)
insert into tblGraph values(222,111,2.0)
insert into tblGraph values(222,333,1.0)
insert into tblGraph values(222,555,1.0)
insert into tblGraph values(333,666,1.0)
insert into tblGraph values(333,888,1.0)
insert into tblGraph values(444,888,1.0)
insert into tblGraph values(555,111,2.0)
insert into tblGraph values(555,666,1.0)
insert into tblGraph values(666,333,2.0)
insert into tblGraph values(666,777,1.0)
insert into tblGraph values(777,444,2.0)
insert into tblGraph values(777,888,1.0)
go

Если сравнить выражения на рис. 3 с тем, что показано на рис. 1, станет ясно, что каждое выражение соответствует ветви между узлами.

Далее база данных подготавливается для поиска кратчайшего пути:

create nonclustered index idxTblGraphFromNode 
  on tblGraph(fromNode)
go
create nonclustered index idxTblGraphToNode 
  on tblGraph(toNode)
go
create nonclustered index idxTblGraphEdgeWeight 
  on tblGraph(edgeWeight)
go
alter database dbShortPathWithCLR set trustworthy on
go
select is_trustworthy_on from sys.databases
  where name = 'dbShortPathWithCLR'
go

Первые три выражения создают индексы в полях fromNode, toNode и edgeWeight. При работе с большими графами индексы почти всегда необходимы, чтобы обеспечить приемлемую производительность. Следующие два выражения изменяют базу данных так, чтобы свойство trustworthy выставить в «on». Значение этого свойства по умолчанию — «off». Вскоре я поясню, почему свойство trustworthy нужно установить как «on».

К этому моменту граф на основе SQL создан. Следующий шаг — создание с помощью Visual Studio хранимой процедуры CLR для выполнения поиска кратчайшего пути.

Создание хранимой процедуры CLR

Чтобы создать хранимую процедуру CLR для поиска кратчайшего пути, я запустил Visual Studio 2010. Для создания хранимых процедур CLR в вашей среде разработки должна присутствовать Microsoft .NET Framework 3.5 и выше. Из меню File | New | Project я выбрал Database | группу шаблонов проектов SQL Server, а затем указал Visual C# SQL CLR Database Project (рис. 4). Я присвоил проекту имя CreateStoredProc.

Один из подходов к анализу графов, хранящихся в базе данных SQL, — написать хранимую процедуру на языке SQL.

Рис. 4. Новый CLR-проект в Visual Studio 2010

Заметьте, что в диалоговом окне New Project в раскрывающемся списке выбрана .NET Framework 3.5. Весрия целевой инфраструктуры .NET Framework должна совпадать с ее версией, используемой в экземпляре SQL Server, где размещена база данных. Поскольку моя имитация базы данных находится в экземпляре SQL Server 2008, я выбрал .NET Framework 3.5 в качестве целевой инфраструктуры. Если бы эта база данных содержалась в экземпляре SQL Server 2005, я должен был бы ориентироваться на .NET Framework 2.0. В документации на хранимые процедуры CLR корреляция между версиями инфраструктуры в среде разработки, SQL Server и проекте C#, в котором создается хранимая процедура, описана довольно туманно. Возможно, вам придется прибегнуть к методу проб и ошибок.

После щелчка кнопки OK для создания проекта хранимой процедуры CLR среда Visual Studio запрашивает информацию об имени и модели аутентификации целевой базы данных (рис. 5). Щелкните OK в диалоге New Database Reference, и Visual Studio загрузит новый проект, но не создаст шаблон явным образом. Чтобы сгенерировать шаблон, щелкните правой кнопкой мыши имя проекта (в данном случае — CreateStoredProc) и выберите Add | New Item из контекстного меню (рис. 6).

Рис. 5. Диалог New Database Reference для проекта

Рис. 6. Добавление нового элемента — Stored Procedure

Я выбрал элемент Stored Procedure и назвал его csp_ShortestPath.cs. Это имя без расширения .cs станет именем хранимой процедуры в целевой базе данных. Как правило, исходя из стилевых соображений, я предваряю имена хранимых процедур CLR префиксом csp, чтобы отличать их от системных (sp), расширенных (xp) и пользовательских хранимых процедур (usp). Щелкните кнопку Add, и Visual Studio сгенерирует облегченный шаблон частичного класса StoredProcedures:

using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
public partial class StoredProcedures
{
  [Microsoft.SqlServer.Server.SqlProcedure]
  public static void csp_ShortestPath()
  {
    // Сюда поместите свой код
  }
};

«Дешевый вариант» очереди с приоритетами

Алгоритм поиска кратчайшего пути, представленный в этой статье, требует структуры данных для очереди с приоритетами и с произвольным доступом. В .NET Framework нет встроенной очереди с приоритетами, которая точно отвечает требованиям этого алгоритма, поэтому вы должны написать код для собственной очереди.

Очередь с приоритетами (priority queue) похожа на обычную очередь FIFO (first-in-first-out) с несколькими отличиями. Предполагается, что у элементов в очереди с приоритетами имеется некое поле приоритета в дополнение к полю данных. Например, элемент очереди с приоритетами для группы клиентов, ожидающих технической поддержки, мог бы состоять из имени клиента и времени, в течение которого клиент ожидает обслуживания.

Очереди с приоритетами поддерживают операцию Dequeue, которая всегда удаляет элемент с наивысшим приоритетом. Здесь смысл слова «наивысший» зависит от контекста задачи и может быть наибольшим или наименьшим значением. Очередь с приоритетами с произвольным доступом поддерживает операцию, изменяющую поле приоритета элемента с указанным идентификатором.

В данной статье представлен «дешевый вариант» очереди с приоритетами (poor man’s priority queue) — она выполняет свою работу, но оставляет желать много лучшего. Алгоритм поиска кратчайшего пути работает с такой очередью, где у элементов два поля: nodeID (идентификатор узла) (скажем, 111 или 222) и distance (расстояние). Поле distance используется алгоритмом для сохранения лучшего (кратчайшего) известного расстояния между начальным узлом и узлом элемента в любой данный момент в течение выполнения алгоритма. Поле distance действует как приоритет элемента, и меньшие значения этого поля представляют более высокий приоритет.

Поэтому для поддержки такой очереди в C#-шаблоне хранимой процедуры требуются дополнительное выражение using, которое ссылается на пространство имен System.Collections.Generic, и два дополнительных определения класса, помещаемых за частичным классом StoredProcedures:

public class NodeDistance
{
  // Здесь поместите определение
}
public class MyPriorityQueue
{
  // Здесь поместите определение
}
Класс NodeDistance очень прост:
public class NodeDistance
{
  public long nodeID;
  public double distance;
  public NodeDistance(long nodeID, double distance)
  {
    this.nodeID = nodeID;
    this.distance = distance;
  }
}

Для простоты картины я использую открытые поля класса. По сути, очереди с приоритетами — это список элементов NodeDistance:

public class MyPriorityQueue
{
  public List<NodeDistance> list;
  public MyPriorityQueue()
  {
    this.list = new List<NodeDistance>();
  }

И вновь я применяю область видимости public только ради простоты. Операция Dequeue удаляет элемент NodeDistance с наименьшим значением расстояния:

public NodeDistance Dequeue()
{
  int i = IndexOfSmallestDist();
  NodeDistance result = this.list[i];
  this.list.RemoveAt(i);
  return result;
}

Метод Dequeue вызывает вспомогательный метод для поиска местонахождения элемента с наименьшим расстоянием, сохраняет ссылку на этот элемент, а затем удаляет его с помощью встроенного метода List.RemoveAt.

Вспомогательный метод IndexOfSmallestDist определен так:

private int IndexOfSmallestDist() {
  double smallDist = this.list[0].distance;
  int smallIndex = 0;
  for (int i = 0; i < list.Count; ++i) {
    if (list[i].distance < smallDist) {
      smallDist = list[i].distance;
      smallIndex = i;
    }
  }
  return smallIndex;
}

Этот метод осуществляет простой линейный поиск в нижележащем наборе List. Заметьте, что этот подход означает, что Dequeue имеет производительность O(n).

Операция Enqueue определяется как:

public void Enqueue(NodeDistance nd)
{
  list.Add(nd);
}

а операция изменения приоритета — так:

public void ChangePriority(long nodeID, double newDist)
{
  int i = IndexOf(nodeID);
  list[i].distance = newDist;
}

Метод ChangePriority вызывает вспомогательный метод IndexOf, который находит позицию элемента NodeDistance по определенному идентификатору, и определяется следующим образом:

private int IndexOf(long nodeID)
{
  for (int i = 0; i < list.Count; ++i)
    if (list[i].nodeID == nodeID)
      return i;
  return -1;
}

И вновь обратите внимание на то, что из-за выполнения методом IndexOf линейного поиска его производительность равна O(n).

Алгоритму поиска кратчайшего пути нужно в любой момент знать количество элементов в очереди с приоритетами:

public int Count()
{
  return this.list.Count;
}

Подведем итог. «Дешевый вариант» очереди с приоритетами и произвольным доступом, определенный здесь, поддерживает операцию Enqueue, свойство Count, операцию Dequeue (удаляет элемент NodeDistance с наименьшим значением расстояния) и операцию ChangePriority (изменяет значения расстояния в указанном элементе). Операции Dequeue и ChangePriority имеют производительность O(n).

В случае больших графов производительность алгоритма поиска кратчайшего пути сильно зависит от эффективности используемой очереди с приоритетами. Хотя производительность O(n) зачастую вполне приемлема, можно реализовать очередь с приоритетами, обладающую гораздо более высокой производительностью — O(log n). В таких реализациях обычно применяют бинарную пирамидальную структуру данных (binary heap data structure), и они весьма изощренные. Эффективную очередь с приоритетами я описал в своей статье «Priority Queues with C#» для журнала «Visual Studio Magazine» (bit.ly/QWU1Hv).

Создание хранимой процедуры

Определив свою очередь с приоритетами, вы можете реализовать алгоритм поиска кратчайшего пути. Сигнатура метода выглядит так:

public static void csp_ShortestPath(System.Data.SqlTypes.SqlInt64
 startNode, SqlInt64 endNode, SqlInt32 maxNodesToCheck,
  out SqlString pathResult, out SqlDouble distResult)
{

Метод csp_ShortestPath имеет три входных параметра и два выходных. Параметр startNode хранит идентификатор узла, с которого начинается поиск. Вспомните, что в определении SQL-таблицы для полей fromNode и toNode указан SQL-тип bigint, соответствующий C#-типу long. В определении хранимой процедуры CLR параметры используют модель типов из пространства имен System.Data.SqlTypes. Эти типы обычно довольно легко проецируются и на SQL-типы, и на C#-типы. Здесь тип bigint проецируется на SqlInt64. Входной параметр endNode также объявлен как тип SqlInt64.

Параметр maxNodesToCheck предотвращает выход хранимой процедуры из-под контроля в чрезвычайно больших графах. Здесь maxNodesToCheck объявлен с типом SqlInt32, соответствующим C#-типу int.

Если вы новичок в хранимых процедурах SQL, то, возможно, удивитесь, узнав, что у них либо нет явно возвращаемого значения, либо они могут вернуть значение типа int, но никакой другой тип данных явно вернуть нельзя. Поэтому в ситуациях, где хранимая процедура SQL должна возвращать два и более значений или возвращать значение, отличное от типа int, используются выходные параметры. В данном случае хранимая процедура CLR возвращает кратчайший путь как строку, такую как «444;777;666;333;222», а также общую длину кратчайшего пути в виде числового значения, например 5.0. Поэтому выходной параметр pathResult объявлен с типом SqlString, а выходной параметр distResult — с типом SqlDouble; эти типы соответствуют C#-типам string и double.

Далее хранимая процедура CLR подготавливает четыре структуры данных:

Dictionary<long, double> distance = new Dictionary<long, double>();
Dictionary<long, long> previous = new Dictionary<long, long>();
Dictionary<long, bool> beenAdded = new Dictionary<long, bool>();
MyPriorityQueue PQ = new MyPriorityQueue();

В процессе выполнения алгоритму поиска кратчайшего пути нужно в любой момент получать доступ к текущему лучшему (кратчайшему) известному общему расстоянию от начального узла до всех остальных узлов. Эта информация хранится в наборе Dictionary с именем distance. Ключом словаря является идентификатор узла, а значение словаря — кратчайшее известное общее расстояние. Набор Dictionary с именем previous сохраняет идентификатор непосредственно предшествующего узла в кратчайшем пути. Так, в примере на рис. 2 конечным узлом является 444. Его непосредственный предшественник в кратчайшем пути — узел 777. Поэтому previous[444] = 777. По сути, набор previous хранит кратчайший путь в закодированном виде.

Набор Dictionary с именем beenAdded хранит информацию, указывающую, был ли узел графа добавлен в очередь с приоритетами, используемую алгоритмом. Булево значение является не более чем заглушкой, поскольку на деле оно не требуется для того, чтобы определить, находится ли некий узел в этом наборе. Возможно, вы предпочтете использовать Hashtable вместо набора Dictionary. Собственная очередь с приоритетами под именем PQ была определена и описана в предыдущем разделе этой статьи.

Тем временем, хранимая процедура продолжает работу:

SqlConnection conn = null;
long startNodeAsLong = (long)startNode;
long endNodeAsLong = (long)endNode;
int maxNodesToCheckAsInt = (int)maxNodesToCheck;

Объект SqlConnection — единственное соединение с целевой базой данных графа. Я объявляю его здесь, чтобы иметь возможность впоследствии проверить его состояние, если возникнет исключение. Хотя это не обязательно, при написании хранимых процедур CLR я предпочитаю явным образом создавать локальные типизированные переменные на C#, которые соответствуют типизированным параметрам SQL.

Затем хранимая процедура выполняет:

distance[startNodeAsLong] = 0.0;
previous[startNodeAsLong] = -1;
PQ.Enqueue(new NodeDistance(startNodeAsLong, 0.0));
beenAdded[startNodeAsLong] = true;

Эти строки кода инициализируют начальный узел. Значение в словаре distance задается равным 0.0, так как расстояние от начального узла до самого себя, естественно, нулевое. Непосредственный предшественник начального узла не существует, поэтому используется значение value –1, указывающее на этот факт. Очередь с приоритетами инициализируется начальным узлом, и словарный набор beenAdded обновляется.

Следующие операции хранимой процедуры:

try
{
  string connString = "Server=(local);Database=dbShortPathWithCLR;" +
    "Trusted_Connection=True;MultipleActiveResultSets=True";
  conn = new SqlConnection(connString);
  conn.Open();
  double alt = 0.0;

При написании хранимых процедур CLR я предпочитаю использовать явные блоки try-catch вместо более элегантного выражения using. Задавая строку подключения, вы может выбрать один из двух вариантов. Во многих случаях, так как хранимая процедура выполняется на том же компьютере, что и база данных SQL database, вы можете просто указать строку подключения в виде "context connection=true". Теоретически контекстное соединение обеспечит более высокую производительность, чем стандартное. Однако у контекстного соединения имеется несколько ограничений. Одно из них состоит в том, что оно может поддерживать только одного читателя данных SQL. Как вы вскоре увидите, поиск кратчайшего пути часто (но не всегда) требует двух читателей данных SQL.

Поскольку данная хранимая процедура CLR требует двух читателей, используется стандартная строка подключения, включающая блок, который задает свойство MultipleActiveResultSets как true. Этот блок в настоящее время не поддерживается контекстными соединениями SQL. Поскольку хранимая процедура использует стандартное соединение, а не контекстное, Database Permission Level для проекта Visual Studio, где создается хранимая процедура, должен быть установлен в External, как показано на рис. 7. Однако, чтобы задать это свойство, свойство trustworthy базы данных SQL должно быть установлено в «on», как было продемонстрировано на рис. 2.

Рис. 7. Задание Database Permission Level

Подведем итог. При создании базы данных графа свойство trustworthy этой базы данных выставляется в «on». Это позволяет задать свойство Database Permission Level проекта Visual Studio как External, что в свою очередь дает возможность определению хранимой процедуры использовать стандартное соединение вместо контекстного. Благодаря этому свойство MultipleActiveResultSets соединения устанавливается в true, а это позволяет использовать в хранимой процедуре двух читателей данных SQL.

Продолжим рассмотрение хранимой процедуры:

while (PQ.Count() > 0 && 
  beenAdded.Count < maxNodesToCheckAsInt)
{
  NodeDistance u = PQ.Dequeue();
  if (u.nodeID == endNode) break;

Применяемый здесь алгоритм является разновидностью алгоритма Дейкстры (Dijkstra) для поиска кратчайшего пути — одного из самых знаменитых в компьютерной науке. Хотя этот алгоритм короткий, он очень изощренный, и его можно модифицировать во многих отношениях. Центральное место в этом алгоритме занимает цикл, завершаемый, когда опустошается очередь с приоритетами. В данном случае я включил дополнительную проверку на основе общего количества обработанных узлов графа. Внутри основного цикла вызов Dequeue возвращает узел в очереди, имеющий лучшее (кратчайшее) известное общее расстояние от начального узла. Если только что удаленный из очереди узел является концевым, значит, кратчайший путь найден и цикл завершается.

Следующая часть хранимой процедуры:

SqlCommand cmd = new SqlCommand(
  "select toNode from tblGraph where fromNode=" + u.nodeID);
cmd.Connection = conn;
long v;  // идентификатор соседнего узла для u
SqlDataReader sdr = cmd.ExecuteReader();
while (sdr.Read() == true) {
  v = long.Parse(sdr[0].ToString());
  if (beenAdded.ContainsKey(v) == false) {
    distance[v] = double.MaxValue;
    previous[v] = -1;
    PQ.Enqueue(new NodeDistance(v, double.MaxValue));
    beenAdded[v] = true;
  }

В этих строках кода я получаю всех соседей текущего узла u. Заметьте, что это требует первого читателя данных SQL. Каждый смежный узел v проверяется на предмет его первого появления в алгоритме. Если да, создается экземпляр элемента NodeDistance с v в качестве его nodeID и добавляется в очередь с приоритетами. В качестве альтернативы вместо добавления узлов в очередь по мере того, как они встречаются алгоритму, можно изначально добавить все узлы в графе в очередь. Однако для очень больших графов это может потребовать слишком большого объема памяти на компьютере и занять очень много времени.

Вложенный цикл чтения всех соседей продолжается кодом:

SqlCommand distCmd =
  new SqlCommand("select edgeWeight from tblGraph where fromNode=" +
  u.nodeID + " and toNode=" + v);
distCmd.Connection = conn;
double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.nodeID] + d;

Этот код запрашивает базу данных, чтобы получить расстояние от текущего узла u до текущего смежного узла v. Заметьте, что для этого нужен второй читатель данных. Наличие второго читателя данных влечет за собой необходимость ряда изменений в свойствах, в том числе свойства trustworthy базы данных и свойства Permission проекта Visual Studio. Если ваш алгоритм поиска кратчайшего пути использует невзвешенный граф (unweighted graph), т. е. такой, где весовые доли всех ветвей предполагаются равными 1, тогда вы можете упростить код, исключив второго читателя данных и заменив эту строку:

alt = distance[u.nodeID] + 1;

на:

double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.nodeID] + d;

Переменная alt — это проверочное расстояние (test distance) от начального узла до текущего смежного узла v. Если вы внимательно изучите выражение присваивания, то заметите, что alt — это кратчайшее известное расстояние от начального узла до u плюс расстояние от узла u до узла v. Это отражает потенциально новый более короткий путь от начального узла до узла v.

Вложенный цикл чтения всех соседей и основной цикл алгоритма продолжаются так:

if (alt < distance[v])
    {
      distance[v] = alt;
      previous[v] = u.nodeID;
      PQ.ChangePriority(v, alt);
    }
  }  // цикл чтения sdr
  sdr.Close();
} // основной цикл
conn.Close();

Если проверочное расстояние от начального узла до v меньше, чем кратчайшее известное расстояние от начального узла до v (хранящееся в словаре distance), тогда найдено новое более короткое расстояние от начало до v и происходит соответствующее обновление локальных структур данных distance, previous и очереди с приоритетами.

Теперь логика хранимой процедуры определяет, почему завершен основной цикл алгоритма — из-за реального нахождения кратчайшего пути или потому, что между начальным и конечным узлами не найдено никакого пути:

pathResult = "NOTREACHABLE";
distResult = -1.0;
if (distance.ContainsKey(endNodeAsLong) == true) {
  double sp = distance[endNodeAsLong];
  if (sp != double.MaxValue) {
    pathResult = "";
    long currNode = endNodeAsLong;
    while (currNode != startNodeAsLong) {
      pathResult += currNode.ToString() + ";";
      currNode = previous[currNode];
    }
    pathResult += startNode.ToString();
    distResult = sp;

Вспомните, что для этой реализации поиска кратчайшего пути существует только два результата: кратчайший путь, выраженный как список в обратной порядке и разделенный точками с запятыми, и кратчайший путь, измеряемый суммой весов ветвей между узлами в этом пути. Хранимая процедура использует значения по умолчанию «NOTREACHABLE» и –1.0 на случаи, где конечный узел недостижим от начального узла. Цикл while извлекает узлы кратчайшего пути из словаря previous и сшивает их вместе от конечного узла к начальному, используя конкатенацию строк. Если вы достаточно амбициозны, то можете использовать стек и конструировать строку результата от начального узла к конечному. Также напомню, что эти два результата возвращаются через выходные параметры pathResult и distResult.

Определение хранимой процедуры завершается проверкой на ошибки:

} // try
  catch(Exception ex)
  {
    pathResult = ex.Message;
    distResult = -1.0;
  }
  finally
  {
    if (conn != null && conn.State == ConnectionState.Open)
      conn.Close();
  }
}  // csp_ShortestPath()

Если произошло исключение (обычно это бывает, когда SQL Server не хватает памяти из-за чрезвычайно большого размера графа или когда истекает срок ожидания соединения с SQL), код пытается очистить соединение с SQL и вернуть результаты, которые имеют какой-то смысл.

Создание, развертывание и вызов хранимой процедуры

Убедившись, что свойство trustworthy базы данных установлено в «on», а свойство Database Permission Level — в External, выберите Build CreateStoredProc из меню Build в Visual Studio. Если сборка пройдет успешно, выберите Deploy CreateStoredProc из меню Build, чтобы скопировать хранимую процедуру CLR с вашего компьютера разработки в SQL Server, где размещен граф на основе SQL.

Вызвать хранимую процедуру CLR можно несколькими способами. Проект Visual Studio содержит шаблон теста, которым вы можете воспользоваться. Или вызвать хранимую процедуру напрямую из SSMS, как показано на рис. 2. Например:

declare @startNode bigint
declare @endNode bigint
declare @maxNodesToCheck int
declare @pathResult varchar(4000)
declare @distResult float
set @startNode = 222
set @endNode = 444
set @maxNodesToCheck = 100000
exec csp_ShortestPath @startNode, @endNode, @maxNodesToCheck,
  @pathResult output, @distResult output
select @pathResult
select @distResult

Еще один вариант — вызов хранимой процедуры CLR из приложения на C#, используя ADO.NET нарядку с кодом, показанным на рис. 8.

Рис. 8. Вызов хранимой процедуры из C# с применением ADO.NET

SqlConnection sc = null;
string connString = "Server=" + dbServer + ";Database=" +
  database + ";Trusted_Connection=True";
sc = new SqlConnection(connString);
SqlCommand cmd = new SqlCommand("csp_ShortestPath", sc);
cmd.CommandType = System.Data.CommandType.StoredProcedure;  
// Сигнатура sp: (System.Data.SqlTypes.SqlInt64 startNode,
// SqlInt64 endNode, SqlInt32 maxNodesToCheck,
// out SqlString path)
cmd.CommandTimeout = commandTimeout;  // в секундах
SqlParameter sqlStartNode = cmd.Parameters.Add("@startNode",
  System.Data.SqlDbType.BigInt);
sqlStartNode.Direction = ParameterDirection.Input;
sqlStartNode.Value = sn;
// ...
cmd.ExecuteNonQuery();
string result = (string)cmd.Parameters["@pathResult"].Value;
distResult = (double)cmd.Parameters["@distResult"].Value;

Или, если вы себя совсем не жалеете, можете вызвать хранимую процедуру CLR, используя технологию LINQ.

Нечто большее, чем просто кратчайший путь

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

Джеймс Маккафри (Dr. James McCaffrey) — работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких ключевых продуктов Microsoft, в том числе Internet Explorer и Bing. Обладатель ученых степеней от Университета Калифорнии в Ирвине и Университета Южной Калифорнии. Ведет личный блог jamesmccaffrey.wordpress.com. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Microsoft Даррену Герингу (Darren Gehring).