Este artigo foi traduzido por máquina.
CLR
Análise de gráficos de caminho mais curto usando um procedimento CLR armazenado
Análise do gráfico está se tornando cada vez mais importante em aplicações de software. Aqui um gráfico é uma coleção de nós e arestas, não uma visualização de dados como um gráfico de barras. Este artigo apresenta uma demonstração de como realizar a análise de caminho mais curto, usando um procedimento armazenado do SQL CLR. As técnicas apresentadas aqui também podem ser usadas para muitas outras tarefas de programação de acesso a dados.
Análise de gráfico de caminho mais curto realmente envolve dois problemas intimamente relacionados. A primeira é para determinar o caminho mais curto para um nó final em termos de número de saltos de um nó de início do gráfico especificado. O segundo problema é determinar o comprimento do caminho mais curto, se gráfico conexões têm algum tipo de peso. Por exemplo, suponha que os nós em um gráfico representam as pessoas e as bordas entre os nós representam uma comunicação por e-mail. Você pode estar interessado no menor número de saltos entre duas pessoas, onde você está implicitamente supondo que cada salto tem um peso de 1. Isso é semelhante para o jogo de "seis graus de Kevin Bacon" ou o número de Erdos para um pesquisador. Se cada borda do gráfico tem um peso — por exemplo, que representa uma medida de importância de um relacionamento — talvez queira determinar o caminho mais curto entre duas pessoas, tendo a importância do peso em conta.
Mas por que usar um procedimento armazenado CLR? Algoritmos de caminho mais curto tradicionais assumem que a representação de gráfico do problema pode ser armazenada completamente na memória da máquina, geralmente em uma lista de matriz ou adjacência. Para grandes gráficos — por exemplo, gráficos que representam redes sociais — esta abordagem, muitas vezes não é viável. Grandes gráficos podem ser convenientemente armazenados em um banco de dados SQL. Uma abordagem para a realização de análise de caminho mais curto de gráficos armazenados em um banco de dados SQL é escrever um procedimento de linguagem armazenado SQL nativo. Artigo da MSDN Magazine, "Gráfico baseado em análise de caminho mínimo com SQL" (msdn.microsoft.com/magazine/jj863138), explica que a abordagem em detalhes. No entanto, um CLR procedimento armazenado em vez de uma abordagem essencialmente de SQL poderá oferecer melhora drasticamente o desempenho e flexibilidade muito maior para personalização.
Dê uma olhada a representação de gráfico fictício no Figura 1. O gráfico tem oito nós. Os números ao lado de cada seta representam um peso. O caminho mais curto entre nós 222 e 444 é 222 -> 555 -> 666 -> 777 -> 444, que tem uma distância ponderada 1.0 + 1.0 + 1.0 + 2.0 = 5.0. Observe que 222 -> 333 -> 666 -> 777 -> 444 é também um caminho mais curto de 222 a 444.
.png "gráfico fictício para análise de caminho mais curto")
Figura 1 gráfico fictício para análise de caminho mais curto
Figura 2 mostra um screenshot de uma chamada para um CLR armazenados procedimento denominado csp_ShortestPath que determina o caminho mais curto entre nós 222 e 444. Neste caso o caminho mais curto é exibido como uma seqüência de caracteres semicolon-delimited na ordem inversa. A saída está na parte inferior da imagem. A parte superior da imagem contém instruções SQL que cria um gráfico correspondente no Figura 1.
.png "chamando um caminho mais curto CLR procedimento armazenado")
Figura 2 chamando um caminho mais curto CLR procedimento armazenado
Este artigo pressupõe que você tem avançado conhecimento de programação de c# e uma familiaridade básica com SQL. Apresento todo o código SQL para criar o gráfico fictício e todos os o código c# para criar o CLR procedimento armazenado e eu também descrevem várias maneiras para chamar o procedimento armazenado CLR. Todo o código deste artigo está disponível em archive.msdn.microsoft.com/mag201305Graph.
Criando o banco de dados
Para criar o gráfico fictício baseado em SQL, lancei Microsoft SQL Server Management Studio (SSMS) e conectado a uma instância de um banco de dados do SQL Server 2008. Procedimentos armazenados CLR são suportados pelo SQL Server 2005 e posteriores. Primeiro, eu criei um banco de dados chamado dbShortPathWithCLR usando os seguintes comandos:
use master
go
if exists(select * from sys.sysdatabases
where name='dbShortPathWithCLR')
drop database dbShortPathWithCLR
go
create database dbShortPathWithCLR
go
use dbShortPathWithCLR
go
Recomendo vivamente a experimentar com um manequim de banco de dados em vez de um banco de dados de produção. Os comandos para criar uma tabela que armazenam dados de nó e borda são:
create table tblGraph
(
fromNode bigint not null,
toNode bigint not null,
edgeWeight real not null
)
go
Identificações de nó são armazenadas como SQL tipo bigint, que corresponde aproximadamente ao c# tipo long. Os pesos de borda são armazenados como tipo real, que é um sinônimo para SQL tipo float(24), que corresponde aproximadamente ao c# tipo double. Em muitas situações você não vai se preocupar com um peso de borda e a coluna de edgeWeight pode ser omitida.
As declarações de 14 Figura 3 definir o gráfico.
Figura 3 definindo o gráfico
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
Se você comparar as declarações de Figura 3 com a imagem em Figura 1 você verá que cada instrução corresponde a uma borda entre nós.
Em seguida, o banco de dados está preparado para análise de caminho mais curto:
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
As três primeiras declarações criam índices em colunas fromNode, toNode e edgeWeight. Ao trabalhar com grandes gráficos, índices quase sempre são necessárias para proporcionar um desempenho razoável. As próximas duas declarações alteram no banco de dados para a propriedade trustworthy é definida como "on". O valor padrão da propriedade é "off". Vou explicar por que a propriedade trustworthy deve ser definida para "on" em breve.
Neste ponto o manequim gráfico baseado em SQL é criado. O próximo passo é usar o Visual Studio para criar um CLR armazenados procedimento para executar análise de caminho mais curto.
Criar o CLR procedimento armazenado
Para criar o procedimento armazenado CLR caminho mais curto, lancei Visual Studio 2010. Para criar procedimentos armazenados CLR seu desenvolvimento ambiente deve incluir o Microsoft .NET Framework 3.5 ou posterior. Do arquivo | Novo | Projeto menu selecionei o banco de dados | SQL Server grupo de modelo de projeto e então selecionada a opção Visual c# projeto CLR SQL banco de dados como mostrado na Figura 4. Eu nomeei o projeto CreateStoredProc.
.png "novo projeto CLR no Visual Studio 2010")
Figura 4 novo projeto CLR no Visual Studio 2010
Observe que o .NET Framework 3.5 está selecionado no controle de lista suspensa de diálogo novo projeto. A versão do framework de destino deve coincidir com a versão do framework em SQL Server que hospeda o banco de dados. Porque o fictício banco de dados em uma instância do SQL Server 2008, eu destino .NET Framework 3.5. Se o banco de dados fictício tinha sido em uma instância do SQL Server 2005, eu seria já alvo .NET Framework 2.0. A documentação de procedimento armazenado CLR é um pouco obscura em descrever as correlações entre as versões de estrutura sobre o ambiente de desenvolvimento, no SQL Server e do projeto de criação de procedimento armazenado c#. Você pode ter que recorrer a um pouco de tentativa e erro.
Após clicar em OK para criar o projeto de criação de procedimento armazenado CLR, Visual Studio solicita um pedido de informações sobre o modelo de autenticação e o nome do banco de dados alvo (ver Figura 5). Após clicar em OK na caixa de diálogo novo banco de dados de referência, Visual Studio carrega um novo projeto, mas não criar diretamente um modelo. Para gerar um modelo, clique com botão direito no nome do projeto — CreateStoredProc neste caso — e selecione Add | Novo Item no menu de contexto (consulte Figura 6).
.png "novo referência de banco de dados para o projeto")
Figura 5 novo referência de banco de dados para o projeto
.png "Novo Item procedimento armazenado")
Figura 6 Novo Item procedimento armazenado
Selecionei o item Stored Procedure e o nome de csp_ShortestPath.cs. Este nome, sem a extensão. cs, vai se tornar o nome do procedimento armazenado no banco de dados alvo. Por uma questão de estilo, geralmente colocar nomes de procedimentos armazenados CLR com csp para distingui-los dos procedimentos armazenados do sistema (sp), estendida procedimentos armazenados (xp) e procedimentos armazenados definidos pelo usuário (usp). Depois de clicar no botão Adicionar, Visual Studio gerado um modelo leve de uma classe parcial chamada 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()
{
// Put your code here
}
};
Fila de prioridade de um homem pobre
O algoritmo do caminho mais curto apresentado neste artigo requer uma estrutura de dados de fila de prioridade de acesso aleatório. O .NET Framework não fornece uma fila de prioridade interna que será exatamente as necessidades do algoritmo do caminho mais curto, então você deve codificar sua própria fila de prioridade.
Uma fila de prioridade é semelhante a uma fila de (FIFO) primeiro-em-primeiro-out normal com algumas diferenças. Os itens em uma fila de prioridade se presume que tenham algum tipo de campo de prioridade, além de um campo de dados. Por exemplo, um item de fila de prioridade para um grupo de clientes à espera de apoio técnico pode consistir em nome do cliente e quanto tempo que o cliente tem sido esperando por serviço.
Filas de prioridade apoiar uma operação Dequeue que sempre remove o item com a prioridade mais alta. Aqui, o significado de mais alto depende do contexto do problema e pode ser um valor maior ou um menor valor. Uma fila de prioridade de acesso aleatório suporta uma operação que modifica o campo de prioridade de um item com uma ID especificada.
Este artigo apresenta a fila de prioridade de um homem pobre — que começa o trabalho feito, mas tem muito espaço para melhorias. O algoritmo do caminho mais curto opera em uma fila de prioridade onde itens na fila tem dois campos: uma ID de nó (como 111 ou 222) e um campo de distância. O campo de distância é usado pelo algoritmo para armazenar a melhor distância conhecida (menor) entre o nó de início e o item a qualquer momento durante a execução do algoritmo. O campo de distância atua como prioridade do item e menores valores para a distância representam maior prioridade.
Assim, para dar suporte a uma fila de prioridade de acesso aleatório, o modelo de procedimento armazenado c# precisa um adicional usando a instrução que referencia o namespace System.Collections.Generic e duas definições de classe definida pelo programa adicional colocada abaixo classe StoredProcedures parcial:
public class NodeDistance
{
// Definition here
}
public class MyPriorityQueue
{
// Definition here
}
Class NodeDistance is simple:
public class NodeDistance
{
public long nodeID;
public double distance;
public NodeDistance(long nodeID, double distance)
{
this.nodeID = nodeID;
this.distance = distance;
}
}
Eu uso o escopo público para os campos de classe para a simplicidade. A fila de prioridade é essencialmente uma lista de NodeDistance de itens:
public class MyPriorityQueue
{
public List<NodeDistance> list;
public MyPriorityQueue()
{
this.list = new List<NodeDistance>();
}
Novamente, eu uso o escopo público por simplicidade apenas. A operação Dequeue remove o item de NodeDistance com o menor valor de distância:
public NodeDistance Dequeue()
{
int i = IndexOfSmallestDist();
NodeDistance result = this.list[i];
this.list.RemoveAt(i);
return result;
}
Método Dequeue chama um método auxiliar para encontrar o local do item que tem a menor distância, salva uma referência a esse item e, em seguida, usa o método de List.RemoveAt a built-in para remover o item.
Método auxiliar IndexOfSmallestDist é definido como:
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;
}
O método faz uma pesquisa linear simples através da coleção de lista subjacente. Note-se que essa abordagem significa que Dequeue tem desempenho do (n).
A operação Enqueue é definida como:
public void Enqueue(NodeDistance nd)
{
list.Add(nd);
}
A operação de mudança de prioridade é definida como:
public void ChangePriority(long nodeID, double newDist)
{
int i = IndexOf(nodeID);
list[i].distance = newDist;
}
ChangePriority método chama o método auxiliar IndexOf que localiza a posição de um item de NodeDistance, dada a ID do item, e é definido como:
private int IndexOf(long nodeID)
{
for (int i = 0; i < list.Count; ++i)
if (list[i].nodeID == nodeID)
return i;
return -1;
}
Novamente, observe que, porque o IndexOf método executa uma pesquisa linear, seu desempenho é o (n).
O algoritmo do caminho mais curto precisa saber o número de itens na fila de prioridade a qualquer momento:
public int Count()
{
return this.list.Count;
}
Para resumir, a prioridade de acesso aleatório do coitado fila definida aqui suporta uma operação Enqueue; uma propriedade de contagem; a operação Dequeue que remove o item NodeDistance com a menor distância; e uma operação de ChangePriority que modifica a distância de um item especificado. Dequeue operações e ChangePriority têm desempenho do (n).
Para grandes gráficos, o desempenho do algoritmo de caminho mais curto é altamente dependente da eficiência da fila de prioridade usada. Embora muitas vezes o desempenho do (n) é aceitável, é possível implementar uma fila de prioridade que tem um desempenho muito melhor O (log n). Tais implementações normalmente usam uma estrutura de dados heap binário e são bastante complicadas. Descrevo uma fila de prioridade eficiente no meu artigo de revista Visual Studio , "prioridade filas com c#," disponível em bit.ly/QWU1Hv.
Criar o procedimento armazenado
Com a fila de prioridade personalizado definida, o algoritmo do caminho mais curto pode ser implementado. A assinatura do método é:
public static void csp_ShortestPath(System.Data.SqlTypes.SqlInt64
startNode, SqlInt64 endNode, SqlInt32 maxNodesToCheck,
out SqlString pathResult, out SqlDouble distResult)
{
Método csp_ShortestPath aceita três parâmetros de entrada e tem dois parâmetros de resultado. Parâmetro startNode contém a ID de nó do nó para começar a pesquisa. Lembre-se de que, na definição de tabela SQL, toNode e colunas fromNode são definidos como SQL tipo bigint, que corresponde ao tipo de c# muito tempo. Ao definir um CLR procedimento armazenado, parâmetros do procedimento usam um modelo de tipo definido no namespace System.Data.SqlTypes. Esses tipos são geralmente muito fácil para mapear tipos de SQL e c#. Aqui, tipo bigint mapas de SqlInt64. Endnodes de parâmetro de entrada também é declarado como tipo SqlInt64.
MaxNodesToCheck de parâmetro de entrada é usado para impedir que o procedimento armazenado girando fora de controle em gráficos extremamente grandes. Aqui, maxNodesToCheck é declarado como tipo SqlInt32, que corresponde ao c# tipo int.
Se você é novo para procedimentos armazenados SQL, você pode se surpreender ao saber que eles podem ter nenhum valor de retorno explícito, ou podem retornar um valor de int, mas eles explicitamente não é possível retornar qualquer outro tipo de dados. Assim, em situações onde um SQL procedimento armazenado deve retornar dois ou mais valores, ou retornar um valor que não é um tipo de int, a abordagem adoptada é usar parâmetros de saída. Aqui, o procedimento armazenado CLR retorna o caminho mais curto como uma seqüência de caracteres, tais como "444; 777; 666; 333; 222," e também retorna a distância total do caminho mais curto, como um valor numérico, como 5.0. Então fora o parâmetro pathResult é declarado como tipo SqlString e out parâmetro distResult é declarado como tipo Sqlduplo, correspondente ao c# tipos string e double, respectivamente.
A definição do procedimento armazenado CLR continua quatro dados estruturas:
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();
Como o algoritmo do caminho mais curto é executado, em qualquer ponto, o algoritmo precisa acessar a atual melhor (menor) total distância conhecida desde o nó de início para todos os outros nós. A coleção de dicionário chamada "distância" contém esta informação. A chave do dicionário é uma ID de nó e o valor do dicionário é a menor distância total conhecida. A coleção de dicionário chamado "anteriores" lojas a ID de nó do antecessor imediato para uma ID de nó chave o caminho mais curto. Por exemplo, no exemplo mostrado no Figura 2, o nó de extremidade é 444. Seu antecessor imediato o caminho mais curto é 777. Tão anterior [444] = 777. Em essência a coleção anterior contém o caminho mais curto real de forma codificada.
A coleção de dicionário chamada "beenAdded" contém informações que indicam se um nó de gráfico foi adicionado para a fila de prioridade do algoritmo. O valor booleano é um valor fictício, porque não é realmente necessário para determinar se um nó está na coleção. Você pode querer usar uma tabela de hash em vez de uma coleção de dicionário. A fila de prioridade personalizado denominada "PQ" foi definida e explicada na seção anterior deste artigo.
A definição de procedimento armazenado continua:
SqlConnection conn = null;
long startNodeAsLong = (long)startNode;
long endNodeAsLong = (long)endNode;
int maxNodesToCheckAsInt = (int)maxNodesToCheck;
O objeto SqlConnection é a única conexão com o banco de dados do gráfico de destino. Declaro-lo aqui para que eu possa verificar o seu estado mais tarde se ocorrer uma exceção. Embora não seja estritamente necessário, quando escrever CLR armazenados procedimentos que eu prefiro criar explicitamente local C# digitado variáveis que correspondem do SQL digitado variáveis de parâmetro.
A definição continua:
distance[startNodeAsLong] = 0.0;
previous[startNodeAsLong] = -1;
PQ.Enqueue(new NodeDistance(startNodeAsLong, 0.0));
beenAdded[startNodeAsLong] = true;
Estas linhas de código inicializar o nó de início. O valor da distância dicionário é definido como 0.0 porque a distância entre o nó de início a mesmo é zero. O predecessor imediato para o nó de início não existe um valor de -1 é usado para indicar isso. A fila de prioridade é inicializada com o nó de início, e a coleção de dicionário beenAdded é atualizada.
A definição continua:
try
{
string connString = "Server=(local);Database=dbShortPathWithCLR;" +
"Trusted_Connection=True;MultipleActiveResultSets=True";
conn = new SqlConnection(connString);
conn.Open();
double alt = 0.0; // 'Test distance'
Ao escrever o CLR procedimentos armazenados eu prefiro usar blocos try-catch explícito um pouco do que o mais elegante usando a instrução. Ao definir a String de conexão você tem duas opções. Em muitos casos, porque o procedimento armazenado é executado na mesma máquina que o banco de dados SQL, você pode simplesmente definir a seqüência de caracteres de conexão para "context connection = true." Uma conexão de contexto em teoria vai entregar um desempenho melhor do que uma conexão padrão. No entanto, uma conexão de contexto tem várias limitações. Uma limitação é que ela pode suportar apenas um simples leitor de dados SQL. Como você verá em breve, análise de caminho mais curto, muitas vezes (mas nem sempre) exige dois leitores de dados SQL.
Porque este procedimento armazenado CLR requer dois leitores, uma seqüência de caracteres de conexão padrão que inclui uma cláusula que define a propriedade MultipleActiveResultSets é usada. Esta cláusula não é suportada atualmente por ligações de contexto SQL. Porque o procedimento armazenado é usando uma conexão padrão, em vez de uma conexão de contexto, o nível de permissão de banco de dados para o projeto de criação do Visual Studio procedimento armazenado deve ser definido para o externo, como mostrado na Figura 7. No entanto, para definir essa propriedade o SQL banco de dados deve ter sua propriedade trustworthy definida como "on", como mostrado no Figura 2.
.png "configuração nível de permissão de banco de dados")
Figura 7 configuração nível de permissão de banco de dados
Para resumir, ao criar o banco de dados do gráfico, a propriedade trustworthy do banco de dados é definida como "on". Isso permite que o projeto de Visual Studio propriedade de nível de permissão de banco de dados seja definido como externo. Isto permite a definição de procedimento armazenado usar uma conexão padrão, em vez de uma conexão de contexto. Isso permite que a propriedade da conexão MultipleActiveResultSets ser definida como true. E isso permite que dois leitores de dados SQL no procedimento armazenado.
A definição de procedimento armazenado continua:
while (PQ.Count() > 0 &&
beenAdded.Count < maxNodesToCheckAsInt)
{
NodeDistance u = PQ.Dequeue();
if (u.nodeID == endNode) break;
O algoritmo usado aqui é uma variação do caminho mais curto de Dijkstra, um dos mais famosos na ciência da computação. Embora curto, o algoritmo é muito sutil e pode ser modificado de várias maneiras. O coração do algoritmo é um loop que termina quando a fila de prioridade está vazia. Aqui, uma verificação de sanidade adicionais com base no número total de nós do grafo processado é adicionada. Dentro do loop principal, a chamada de Dequeue de fila de prioridade retorna o nó na fila que tem a melhor distância total conhecida (mais curta) do nó de início. Se o nó apenas removido da prioridade de fila é o nó de extremidade, foi encontrado o caminho mais curto e o loop é encerrado.
A definição continua:
SqlCommand cmd = new SqlCommand(
"select toNode from tblGraph where fromNode=" + u.nodeID);
cmd.Connection = conn;
long v; // ID of a neighbor to 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;
}
Estas linhas de código obter todos os vizinhos para o u do nó atual. Observe que isso requer um leitor de dados SQL primeiro. Cada vizinho nó v é verificado para ver se é a primeira aparição do nó no algoritmo. Neste caso, um item de NodeDistance com v como seu nodeID é instanciado e adicionada à fila de prioridade. Em vez de adição de nós para a fila de prioridade como eles são encontrados, concepção alternativa é inicialmente adicionar todos os nós no gráfico para a fila de prioridade. No entanto, para gráficos muito grandes isso poderia exigir uma grande quantidade de memória da máquina e tomar muito tempo.
O loop de leitura-tudo-vizinhos interno continua:
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;
Este código consulta o banco de dados para obter a distância do nó atual para o atual v de nó vizinho. Note que um leitor de dados segundo é necessário fazer isso. A existência do segundo leitor de dados exige as várias alterações para propriedades, incluindo a propriedade trustworthy do banco de dados e o projeto de Visual Studio propriedade de permissão. Se a sua análise de caminho mais curto usa um gráfico não ponderado — ou seja, aquele onde todos os pesos de borda são assumidos como sendo 1 — você pode simplificar, eliminando o segundo leitor e substituindo
alt = distance[u.nodeID] + 1;
for
double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.nodeID] + d;
Variável alt está a uma distância de teste de nó iniciar ao atual v nó vizinho. Se você examinar a declaração de atribuição cuidadosamente, você verá que alt é a menor distância conhecida desde o início u de nó para nó, mais a distância real do nó você nó v. Isto representa uma distância menor nova potencial em v de nó para nó de início.
O loop interno de leitura-tudo-vizinhos e o loop principal algoritmo continuam com:
if (alt < distance[v])
{
distance[v] = alt;
previous[v] = u.nodeID;
PQ.ChangePriority(v, alt);
}
} // sdr Read loop
sdr.Close();
} // Main loop
conn.Close();
Se a distância de teste entre o nó de início e v é menor que a menor distância conhecida de nó iniciar v (armazenado na distância dicionário), então encontrou-se uma nova distância menor do início para v e distância de estruturas de dados locais, anterior e a fila de prioridade são actualizados em conformidade.
A lógica do procedimento armazenado agora determina se o loop principal algoritmo finalizado porque um caminho mais curto na verdade foi encontrado, ou encerrado porque nenhum caminho entre o nó de início e fim foi encontrado:
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;
Lembre-se de que há realmente dois resultados para essa implementação de caminho mais curto: o caminho mais curto, expressado em um ponto e vírgula -delimitado a seqüência na ordem inversa, e o caminho mais curto, medido pela soma dos pesos de borda entre nós no caminho mais curto. O procedimento armazenado usa os padrões de "NOTREACHABLE" e -1,0 para situações onde o nó de extremidade não é acessível a partir do nó de início. While loop extrai os nós de caminho mais curto do dicionário anterior e costura-los juntos de nó de extremidade para iniciar nó usando concatenação de seqüência de caracteres. Se você é ambicioso, você pode usar uma pilha e construir a seqüência de resultado do nó inicial para o nó final. Lembre-se de que os dois resultados são retornados através de distResult e pathResult de parâmetros.
A definição de procedimento armazenado conclui pela verificação de erros:
} // Try
catch(Exception ex)
{
pathResult = ex.Message;
distResult = -1.0;
}
finally
{
if (conn != null && conn.State == ConnectionState.Open)
conn.Close();
}
} // csp_ShortestPath()
Se ocorreu uma exceção — normalmente se o SQL Server ficar sem memória devido a um gráfico extremamente grande ou devido a uma conexão SQL tempo fora — o código tenta limpar a conexão SQL e retornar resultados que têm algum significado.
Construção, implantação e chamar o procedimento armazenado
Após certificar-se de que você tenha configurado o banco de dados Propriedade trustworthy para "on" e o nível de permissão de banco de dados externa, selecione Build CreateStoredProc Visual Studio Build menu. Se a compilação for bem-sucedida, selecione implantar criarProcArmazen menu Build para copiar o CLR procedimento armazenado de sua máquina de desenvolvimento para SQL Server que hospeda o gráfico baseado em SQL.
Há várias maneiras para chamar o procedimento armazenado CLR. O projeto de Visual Studio contém um modelo de teste, que você pode usar. Ou você pode chamar o procedimento armazenado diretamente do SSMS conforme Figura 2. Por exemplo:
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
Outra opção é chamar o procedimento armazenado CLR de dentro de uma aplicação c# usando ADO.NET, ao longo das linhas de Figura 8.
Ou, se você é um verdadeiro glutão de castigo, você pode chamar o procedimento armazenado CLR usando tecnologia LINQ .
Figura 8 chamar um procedimento armazenado de dentro usando ADO.NET c#
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 signature: (System.Data.SqlTypes.SqlInt64 startNode, SqlInt64 endNode, SqlInt32 maxNodesToCheck, out SqlString path)
cmd.CommandTimeout = commandTimeout; // Seconds
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;
Caminho mais do que apenas mais curto
O código e a explicação aqui apresentada devem permitir que você abordar a análise do gráfico de caminho mais curto usando um procedimento armazenado CLR. Além disso, você pode encontrar o paradigma de design útil em geral. Em vez de buscar dados de SQL para um aplicativo cliente e, em seguida, realiza a filtragem e processamento complexo no cliente, use um procedimento armazenado CLR para busca, filtragem e processo no servidor — e, em seguida, transferir resultados para o cliente. Eu encontrei esta abordagem extremamente útil em diversas situações com grandes bases de dados e requisitos de desempenho em tempo real.
Dr. James McCaffrey funciona para Microsoft Research em Redmond, Wash. Ele trabalhou em vários produtos Microsoft chaves, incluindo o Internet Explorer e Bing. Ele é graduado da Universidade da Califórnia em Irvine e a Universidade do Sul da Califórnia. Seu blog pessoal está em jamesmccaffrey.wordpress.com. Ele pode ser contatado em jammc@microsoft.com.
Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Darren Gehring (Microsoft)
Darren Gehring é um Gerenciador de teste Microsoft Research em Redmond, Wash. Antes de trabalhar na Microsoft Research, ele trabalhou no grupo de produtos de Microsoft SQL Server por 10 anos. Sua página está em research.microsoft.com/people/darrenge/.