Este artículo proviene de un motor de traducción automática.

CLR

Análisis de gráficos de rutas de acceso más cortas mediante un procedimiento almacenado en CLR

James McCaffrey

Descargar el ejemplo de código

Análisis gráfico se está volviendo cada vez más importante en aplicaciones de software. Aquí un gráfico es una colección de nodos y aristas, no una visualización de datos como un gráfico de barras. Este artículo presenta una demostración de cómo llevar a cabo análisis de ruta más corta usando un procedimiento almacenado de SQL CLR. Las técnicas presentadas aquí pueden utilizarse también para muchas otras tareas de programación de acceso a datos.

Análisis gráfico de la ruta más corta realmente implica dos problemas estrechamente relacionados. El primero es para determinar la ruta más corta de un nodo de inicio gráfico especificado a un nodo final en términos de número de saltos. El segundo problema consiste en determinar la longitud de la ruta más corta si las conexiones del gráfico tienen algún tipo de peso. Por ejemplo, supongamos que los nodos en un gráfico representan personas y los bordes entre nodos representan una comunicación por correo electrónico. Está interesado en el menor número de saltos entre dos personas, donde usted está asumiendo implícitamente que cada salto tiene un peso de 1. Esto es similar al juego de "seis grados de Kevin Bacon" o el número de Erdos para un investigador. Si el borde de cada gráfico tiene un peso, por ejemplo, que representa una medida de la importancia de una relación, puede determinar la ruta más corta entre dos personas que toman la importancia del peso en cuenta.

Pero ¿por qué utilizar un procedimiento almacenado de CLR? Algoritmos de ruta más corta tradicionales asumen que la representación gráfica de problema puede almacenarse completamente en la memoria de la máquina, por lo general en una lista matriz o adyacencia. Para gráficos grandes, por ejemplo, gráficos que representan las redes sociales, este enfoque a menudo no es factible. Gráficos grandes se pueden guardar cómodamente en una base de datos SQL. Un método para realizar análisis de ruta más corta de gráficos almacenados en una base de datos SQL consiste en escribir un procedimiento de lengua almacenado SQL nativo. Artículo de la MSDN Magazine , "Basados en gráficas Shortest-Path análisis con SQL" (msdn.microsoft.com/magazine/jj863138), explica que se acercan en detalle. Sin embargo, utilizando un CLR procedimiento almacenado en lugar de un enfoque SQL puro puede proporcionar dramáticamente mejor rendimiento y mayor flexibilidad para la personalización.

Echa un vistazo a la representación del gráfico simulado en figura 1. El gráfico tiene ocho nodos. Los números al lado de cada flecha representan un peso. La ruta más corta entre el nodo 222 y nodo 444 es 222 -> 555 -> 666 -> 777 -> 444, que tiene una distancia ponderada 1.0 + 1.0 + 1.0 + 2.0 = 5.0. Aviso que 222 -> 333 -> 666 -> 777 -> 444 es también una ruta más corta de 222 a 444.

Figura 1 maniquí gráfico para el análisis de la ruta más corta

Figura 2 muestra una captura de pantalla de una llamada a un CLR almacenado el procedimiento denominado csp_ShortestPath que determina la ruta más corta entre el nodo 222 y nodo 444. En este caso la ruta más corta se muestra como una cadena delimitada por punto y coma en orden inverso. La salida es en la parte inferior de la imagen. La parte superior de la imagen contiene sentencias SQL que crean un gráfico correspondiente a la figura 1.

Figura 2 llamando a una ruta más corta CLR procedimiento almacenado

Este artículo asume que ha avanzado habilidades de programación de C# y una familiaridad básica con SQL. Presento todo el código SQL para crear el gráfico simulado todo el código C# para crear el CLR procedimiento almacenado, y yo también describir varias maneras de llamar al procedimiento almacenado de CLR. Todo el código de este artículo está disponible en archive.msdn.microsoft.com/mag201305Graph.

Crear la base de datos

Para crear el gráfico ficticio basado en SQL, lanzó Microsoft SQL Server Management Studio (MEP) y conectarse a una instancia de una base de datos de SQL Server 2008. Procedimientos almacenado de CLR son soportados por SQL Server 2005 y posteriores. En primer lugar, he creado una base de datos denominada dbShortPathWithCLR utilizando los siguientes comandos:

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

Os recomiendo experimentar con una base de datos simulada en lugar de una base de datos de producción. Los comandos para crear una tabla que guardan los datos del nodo y borde son:

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

ID de nodo se almacena como SQL tipo bigint, que corresponde aproximadamente a C# tipo long.Los pesos de borde se almacenan como tipo real, que es sinónimo de SQL tipo float(24), que corresponde aproximadamente a C# tipo double.En muchas situaciones no se trate con un peso de borde y la columna de edgeWeight puede ser omitida.

Los 14 Estados en figura 3 definir el gráfico.

Figura 3 definiendo el 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

Si comparas las declaraciones en figura 3 con la imagen en figura 1 verás que cada declaración corresponde a una arista entre nodos.

A continuación, se prepara la base de datos para el análisis de la ruta más corta:

    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

Los primeros tres comandos crean índices en las columnas fromNode, toNode y edgeWeight. Cuando trabaje con grandes gráficos, índices casi siempre son necesarios para dar un rendimiento razonable. Las dos siguientes declaraciones alteran la base de datos, por lo que se establece la propiedad confiable a "on". El valor predeterminado de la propiedad es "off". Voy a explicar por qué la propiedad confiable se debe establecer en "on" poco.

En este momento se crea el gráfico ficticio basada en SQL. El siguiente paso es utilizar el Visual Studio para crear un CLR procedimiento almacenado para realizar análisis de ruta más corta.

Creación de CLR procedimiento almacenado

Para crear el procedimiento almacenado CLR ruta más corta, he lanzado Visual Studio 2010. Para crear procedimientos CLR almacenado su desarrollo entorno debe incluir Microsoft .NET Framework 3.5 o posterior. Desde el archivo | Nuevo | Menú proyecto, he seleccionado la base de datos | SQL Server project group de la plantilla y luego selecciona la opción de Visual C# SQL CLR proyecto base de datos como se muestra en figura 4. Nombre de proyecto CreateStoredProc.

Figura 4 nuevo proyecto CLR en Visual Studio 2010

Tenga en cuenta que el .NET Framework 3.5 está seleccionado en el control de lista desplegable de diálogo nuevo proyecto. La versión del marco destino debe coincidir con la versión del marco en SQL Server que aloja la base de datos. Porque la base de datos simulada está en una instancia de SQL Server 2008, yo había concentrado en .NET Framework 3.5. Si hubiera sido la base de datos simulada en una instancia de SQL Server 2005, hubiera concentrado en .NET Framework 2.0. La documentación del procedimiento almacenado de CLR es un poco turbia en describir las correlaciones entre las versiones del framework en el entorno de desarrollo, en el SQL Server y en el proyecto de creación de procedimiento almacenado de C#. Usted podría tener que recurrir a un poco de ensayo y error.

Después de hacer clic en Aceptar para crear el proyecto de creación del procedimiento almacenado CLR, Visual Studio solicita a una solicitud de información sobre el modelo de autenticación y nombre de la base de datos de destino (ver figura 5). Después de hacer clic en aceptar en el cuadro de diálogo Nueva referencia de base de datos, Visual Studio carga un nuevo proyecto pero no directamente crear una plantilla. Para generar una plantilla, haga clic en el nombre del proyecto: CreateStoredProc en este caso — y seleccione Añadir | Nuevo elemento en el menú contextual (ver figura 6).

Figura 5 nueva base de datos referencia para el proyecto

Figura 6 nuevo artículo procedimiento almacenado

He seleccionado el elemento del procedimiento almacenado y había llamado csp_ShortestPath.cs. Este nombre, sin la extensión .cs, se convertirá en el nombre del procedimiento almacenado en la base de datos de destino. Como una cuestión de estilo, yo generalmente anteponer nombres de procedimiento CLR almacenado con csp para distinguirlos de los procedimientos almacenados del sistema (sp), procedimientos almacenados (xp) y procedimientos almacenados definidos por el usuario (usp). Después de hacer clic en el botón Agregar, Visual Studio genera una plantilla ligera de una clase parcial denominada 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
  }
};

Cola de prioridad de un hombre pobre

El algoritmo de ruta más corta, presentado en este artículo requiere una estructura de datos cola de prioridad de acceso aleatorio. .NET Framework no suministrar una cola de prioridad incorporado que exactamente cubrirá las necesidades del algoritmo de ruta más corta, por lo que se debe codificar su propia cola de prioridad.

Una cola de prioridad es similar a una normal cola de first in first out (FIFO) con algunas diferencias. Los elementos en una cola de prioridad se supone que tienen algún tipo de campo de prioridad además de un campo de datos. Por ejemplo, un elemento de la cola de prioridad para un grupo de clientes esperando apoyo técnico puede ser el nombre del cliente y la cantidad de tiempo que el cliente ha estado esperando por servicio.

Colas de prioridad apoyan una operación de quitar que siempre quita el elemento con la más alta prioridad. Aquí, el significado de máxima depende en el contexto del problema y puede ser un valor mayor o un menor valor. Una cola de prioridad de acceso soporta una operación que modifica el campo de la prioridad de un elemento con un identificador especificado.

Este artículo presenta cola de prioridad de un hombre pobre, que hace el trabajo pero tiene mucho margen de mejora. El algoritmo de ruta más corta funciona con una cola de prioridad, donde elementos de la cola tienen dos campos: un ID de nodo (como 111 o 222) y un campo de distancia. El campo de distancia se utiliza el algoritmo para almacenar la mejor distancia conocida (más corta) entre el nodo de inicio y el nodo de elemento en cualquier momento durante la ejecución del algoritmo. El campo de distancia actúa como prioridad del elemento, y valores más pequeños para distancia representan mayor prioridad.

Por lo tanto, para soportar una cola de prioridad de acceso aleatorio, la plantilla de procedimiento almacenado de C# necesita un adicional mediante declaración que hace referencia el espacio de nombres System.Collections.Generic y dos definiciones de clase adicional definida por el programa coloca por debajo de la clase 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.</Sentence> <Sentence runat="server" id="tgt96" sentenceId="3f5f9f117726d09b9c8d06ffeb0ae23b" class="tgtSentence" >nodeID = nodeID;
    this.distance = distance;
  }
}

Yo uso el ámbito público para los campos de la clase para simplicidad.La cola de prioridad es esencialmente los artículos de una lista de NodeDistance:

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

Otra vez, yo uso el ámbito público para simplificar sólo.La operación de quitar quita el elemento de NodeDistance con el menor valor de distancia:

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

Método Dequeue llama a un método de ayuda para encontrar la ubicación del elemento que tiene la distancia más pequeña, guarda una referencia a ese tema y luego utiliza el método integrado de List.RemoveAt para quitar el elemento.

Método auxiliar IndexOfSmallestDist se define 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;
}

El método realiza una búsqueda lineal simple a través de la colección subyacente de la lista. Tenga en cuenta que este enfoque significa que Dequeue tiene funcionamiento de O(n).

La operación de Enqueue se define como:

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

La operación de cambio de prioridad se define como:

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

Método ChangePriority llama método IndexOf que localiza la posición de un elemento NodeDistance, dado el ID del elemento, y se define como:

private int IndexOf(long nodeID)
{
  for (int i = 0; i < list.Count; ++i)
    if (list[i].</Sentence> <Sentence runat="server" id="tgt114" sentenceId="3cf090b90f8c3a55b9769d1ef0a25ba4" class="tgtSentence" >nodeID == nodeID)
      return i;
  return -1;
}

Una vez más, tenga en cuenta que debido a que el método IndexOf realiza una búsqueda lineal, su funcionamiento es O(n).

El algoritmo de ruta más corta necesita saber el número de elementos en la cola de prioridad en cualquier momento:

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

Para resumir, la prioridad de acceso aleatorio del pobre cola definida aquí soporta una operación Enqueue; una propiedad Count; una operación de quitar que quita el elemento de NodeDistance con la distancia más pequeña; y una operación de ChangePriority que modifica la distancia de un elemento especificado. Operaciones Dequeue y ChangePriority tienen O(n).

Para gráficos grandes, el rendimiento del algoritmo de ruta más corta es altamente dependiente de la eficacia de la cola de prioridad utilizada. Mientras que el rendimiento de O(n) a menudo es aceptable, es posible implementar una cola de prioridad que tiene mucho mejor rendimiento de O (log n). Estas implementaciones normalmente utilizan una estructura de datos heap binario y son muy difíciles. Describo una cola de prioridad eficiente en mi artículo de la revista Visual Studio , "prioridad colas con C#," disponible en bit.ly/QWU1Hv.

Crear el procedimiento almacenado

Con la cola de prioridad personalizado definida, se puede implementar el algoritmo de ruta más corta. La firma del método es:

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

Csp_ShortestPath método acepta tres parámetros de entrada y tiene dos parámetros de resultado. Parámetro startNode es el ID del nodo del nodo para comenzar la búsqueda. Recordemos que en la definición de tabla SQL, toNode y fromNode de columnas se definen como SQL tipo bigint, que corresponde a C# tipo largo. Al definir un CLR procedimiento almacenado, parámetros del procedimiento utilizan un modelo de tipo definido en el espacio de nombres System.Data.SqlTypes. Estos tipos suelen ser bastante fáciles asignar tipos SQL y C#. Aquí, tipo bigint mapas a SqlInt64. Parámetro de entrada personales también se declaran como un tipo SqlInt64.

Parámetro de entrada maxNodesToCheck se utiliza para evitar que el procedimiento almacenado girando fuera de control en gráficos extremadamente grandes. Aquí, maxNodesToCheck es declarado como tipo SqlInt32, que corresponde a C# tipo int.

Si eres nuevo en procedimientos almacenados de SQL, puede que se sorprenda al saber que no puede tener ningún valor explícito de retorno, o puede devolver un valor int, pero explícitamente no se vuelven a cualquier otro tipo de datos. Así en situaciones donde un SQL procedimiento almacenado debe devolver valores de dos o más, o devolver un valor que no es un tipo int, el planteamiento es utilizar parámetros. Aquí, el procedimiento CLR almacenado devuelve la ruta más corta como una cadena, como "444 777; 666 333; 222," y también devuelve la distancia total de la ruta más corta como un valor numérico, como 5.0. Parámetro pathResult es declarado como tipo SqlString así parámetro distResult es declarado como tipo Sql­doble, correspondientes a los tipos cadena de C# y doble, respectivamente.

La definición de procedimiento CLR almacenado continúa estableciendo estructuras de cuatro datos:

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 se ejecuta el algoritmo de ruta más corta, en un momento dado, el algoritmo debe acceder el actual mejor (más corta) total distancia conocida desde el nodo de inicio a todos los demás nodos. La colección de Diccionario llamada "distancia" contiene esta información. La clave del diccionario es un identificador de nodo y el valor del diccionario es la más corta distancia total conocida. La colección de Diccionario había llamado "anteriores" tiendas el ID de nodo antecesor inmediato a un ID de nodo clave en la ruta más corta. Por ejemplo, en el ejemplo mostrado en figura 2, el nodo final es 444. Su antecedente inmediato en la ruta más corta es 777. Lo anterior [444] = 777. En esencia la colección anterior es la ruta más corta real en forma codificada.

La colección de Diccionario llamada "sumado" contiene información que indica si un nodo gráfico ha sido añadido a la cola de prioridad del algoritmo. El valor booleano es un valor ficticio porque realmente no es necesario para determinar si un nodo está en la colección. Puede utilizar una tabla hash en lugar de una colección Dictionary. La cola de prioridad personalizado denominada "PQ" fue definida y explicada en la sección anterior de este artículo.

Continúa la definición del procedimiento almacenado:

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

El objeto SqlConnection es la única conexión a la base de datos del gráfico de objetivo. Yo lo declaro aquí por lo que puedo observar su estado más adelante si se produce una excepción. Aunque no es estrictamente necesario, cuando la escritura CLR stored procedures que prefiero crear explícitamente local C# escribió variables que corresponden al SQL escribir variables de parámetros.

Continúa la definición:

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

Estas líneas de código inicializan el nodo de inicio. El valor de la distancia, el diccionario se establece en 0.0 porque la distancia desde el nodo de inicio a sí mismo es cero. El antecedente inmediato para el nodo de inicio no existe un valor de -1 se emplea para indicar esto. La cola de prioridad se inicializa con el nodo de inicio, y la colección de Diccionario sumado se actualiza.

Continúa la definición:

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

Cuando CLR de escribir procedimientos almacenados prefiere usar bloques try-catch explícito algo que más elegante mediante declaración. Cuando se configura la cadena de conexión tienes dos opciones. En muchos casos, porque el procedimiento almacenado se ejecuta en la misma máquina que la base de datos SQL, puede simplemente establecer la cadena de conexión en "conexión de contexto = true." Una conexión de contexto en teoría ofrecerá mejor rendimiento que una conexión estándar. Sin embargo, una conexión de contexto tiene varias limitaciones. Una limitación es que puede soportar sólo un solo lector de datos SQL. Como veremos pronto, análisis de ruta más corta a menudo (pero no siempre) requiere dos lectores de datos SQL.

Debido a este procedimiento CLR almacenado requiere dos lectores, se utiliza una cadena de conexión estándar que incluye una cláusula que establece la propiedad MultipleActiveResultSets en true. Esta cláusula no es compatible actualmente por las conexiones de contexto SQL. Porque el procedimiento almacenado está utilizando una conexión estándar en lugar de una conexión de contexto, se debe establecer el nivel de permiso de la base de datos para el proyecto de creación del procedimiento almacenado Visual Studio en externo, como se muestra en figura 7. Sin embargo, con el fin de establecer esta propiedad el SQL base de datos debe tener su propiedad confianza establecida en "on", como se muestra en figura 2.

Figura 7 establecer permisos de base de datos de nivel

Para resumir, al crear la base de datos del gráfico, la propiedad confiable de la base de datos se establece en "on". Esto permite que el proyecto de Visual Studio propiedad del nivel de permisos de base de datos se establece a externo. Esto permite la definición de procedimiento almacenado con una conexión estándar en lugar de una conexión de contexto. Esto permite la propiedad MultipleActiveResultSets de la conexión se establece en true. Y esto permite a dos lectores de datos SQL en el procedimiento almacenado.

Continúa la definición del procedimiento almacenado:

while (PQ.Count() > 0 && 
  beenAdded.Count < maxNodesToCheckAsInt)
{
  NodeDistance u = PQ.Dequeue();
  if (u.</Sentence> <Sentence runat="server" id="tgt185" sentenceId="f67f4403df82eb861bef6cd2ca90e14a" class="tgtSentence" >nodeID == endNode) break;

El algoritmo usado aquí es una variación de ruta más corta de Dijkstra, uno de los más famosos en Ciencias de la computación. Aunque corto, el algoritmo es muy sutil y puede ser modificado en muchos aspectos. El corazón del algoritmo es un bucle que termina cuando la cola de prioridad está vacía. Aquí, se agrega un control de cordura adicional basado en el número total de nodos del gráfico procesados. Dentro del bucle principal, la llamada de quitar cola de prioridad devuelve el nodo en la cola que tiene la mejor distancia total conocida (más corta) desde el nodo de inicio. Si el nodo recién quitados de la prioridad cola es el nodo final, entonces se ha encontrado la ruta más corta y el bucle termina.

Continúa la definición:

SqlCommand cmd = new SqlCommand(
  "select toNode from tblGraph where fromNode=" + u.</Sentence> <Sentence runat="server" id="tgt194" sentenceId="530d07990f7688b52b86c68a2cf05df6" class="tgtSentence" >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 líneas de código llegar a todos los vecinos a la u actual del nodo. Tenga en cuenta que esto requiere un primer lector de datos SQL. Cada vecino nodo v se revisa para ver si es la primera aparición del nodo en el algoritmo. Si es así, un elemento NodeDistance con v como su idNodo es instanciado y agrega a la cola de prioridad. En lugar de agregar nodos a la cola de prioridad como te encontraron, un diseño alternativo es inicialmente agregar todos los nodos en el gráfico a la cola de prioridad. Sin embargo, para gráficos muy grandes podría requerir una gran cantidad de memoria de la máquina y tomar mucho tiempo.

El bucle de lectura-todo-vecinos interno continúa:

SqlCommand distCmd =
  new SqlCommand("select edgeWeight from tblGraph where fromNode=" +
  u.</Sentence> <Sentence runat="server" id="tgt203" sentenceId="1a4730a2f2fa52f6b7d2b912423a10b2" class="tgtSentence" >nodeID + " and toNode=" + v);
distCmd.Connection = conn;
double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.</Sentence> <Sentence runat="server" id="tgt204" sentenceId="93742c90e89daae79b07b76ed50f874e" class="tgtSentence" >nodeID] + d;

Este código consulta la base de datos para obtener la distancia desde el nodo actual que la actual v de nodo vecino.Aviso un segundo lector de datos es necesario para ello.La existencia del segundo lector de datos requiere los cambios múltiples propiedades como la propiedad de base de datos confiable y el proyecto de Visual Studio la propiedad Permission.Si su análisis de la ruta más corta utiliza un gráfico no ponderado, es decir, uno donde todos los pesos de borde se supone que 1 — se puede simplificar eliminando el segundo lector y sustitución

alt = distance[u.</Sentence> <Sentence runat="server" id="tgt210" sentenceId="d39431e4040d00c2c3d04e13b91210f0" class="tgtSentence" >nodeID] + 1;

para

double d = Convert.ToDouble(distCmd.ExecuteScalar());
alt = distance[u.</Sentence> <Sentence runat="server" id="tgt213" sentenceId="93742c90e89daae79b07b76ed50f874e" class="tgtSentence" >nodeID] + d;

Alt variable es una distancia de la prueba desde el nodo de inicio a la actual v de nodo vecino.Si examina cuidadosamente la instrucción de asignación, verás que Alt es la distancia más corta conocida desde el comienzo de nodo a nodo u más la distancia real de nodo nodo v.Esto representa una potencial nueva distancia más corta de la v de nodo a nodo de inicio.

El lazo interno de leer todo de vecinos y el bucle principal del algoritmo continúan con:

if (alt < distance[v])
    {
      distance[v] = alt;
      previous[v] = u.</Sentence> <Sentence runat="server" id="tgt219" sentenceId="cef411acd16391710e77b437c85b0314" class="tgtSentence" >nodeID;
      PQ.ChangePriority(v, alt);
    }
  }  // sdr Read loop
  sdr.Close();
} // Main loop
conn.Close();

Si la distancia de la prueba desde el nodo de inicio a v es menor que la distancia más corta y conocida desde el nodo de inicio a v (almacenado en el Diccionario de distancia), entonces se ha encontrado una nueva distancia más corta desde el principio a v y distancia de las estructuras de datos locales, anterior y la cola de prioridad se actualizan en consecuencia.

Ahora, la lógica de procedimiento almacenado determina si el bucle principal del algoritmo terminó porque un camino más corto de hecho fue encontrado, o terminado porque no se encontró ningún camino entre el nodo de inicio y fin:

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;

Recordemos que en realidad hay dos resultados para esta implementación de la ruta más corta: la ruta más corta, expresada como un punto y coma -­delimitado por cuerdas en orden inverso, y el camino más corto medido por la suma de los pesos de borde entre nodos de la ruta más corta.El procedimiento almacenado utiliza por defecto de "NOTREACHABLE" y -1,0 para situaciones donde el nodo final no es accesible desde el nodo de inicio.El tiempo bucle extrae el Diccionario anterior a los nodos de la ruta más corta y les cose juntos desde el nodo final para iniciar el nodo mediante la concatenación de cadenas.Si eres ambicioso puede utilizar una pila y construir la cadena de resultado desde comienzo de nodo a nodo del final.Hay que recordar que los dos resultados son devueltos vía distResult y parámetros pathResult.

La definición de procedimiento almacenado concluye comprobando errores:

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

Si se ha producido una excepción — normalmente si el SQL Server se queda sin memoria debido a un gráfico muy grande o un conexión de SQL time-out — el código intenta limpiar la conexión SQL y devolver resultados que tienen algún significado.

Construir, implementar y llamar al procedimiento almacenado

Después de asegurarse de que ha establecido la base de datos confiable propiedad en "on" y el nivel de permiso de la base de datos al exterior, seleccione CreateStoredProc de construir en el menú generar Visual Studio .Si tiene éxito la compilación, seleccione implementar crear­ProcAlmacenado en el menú generar, copiar el CLR procedimiento almacenado desde tu máquina de desarrollo para el SQL Server que aloja el gráfico basado en SQL.

Hay varias maneras de llamar al procedimiento almacenado de CLR.El proyecto de Visual Studio contiene una plantilla de prueba que se puede utilizar.O puede llamar al procedimiento almacenado directamente MEP como se muestra en figura 2.Por ejemplo:

    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

Otra opción es llamar al procedimiento almacenado de CLR de dentro de una aplicación en C# utilizando ADO.NET, a lo largo de las líneas de figura 8.

O, si eres un verdadero glotón para castigo, usted puede llamar al procedimiento CLR almacenado utilizando la tecnología LINQ .

Figura 8 llamar a un procedimiento almacenado desde dentro de C# utilizando 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 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;
// ...</Sentence> <Sentence runat="server" id="tgt243" sentenceId="be8adccfcc787171c4bcf039430b29a9" class="tgtSentence" >cmd.ExecuteNonQuery();
string result = (string)cmd.Parameters["@pathResult"].Value;
distResult = (double)cmd.Parameters["@distResult"].Value;

Más de sólo Shortest-Path

El código y la explicación presentada aquí deberían permitirle abordar el análisis gráfico de la ruta más corta usando un procedimiento almacenado de CLR.Además, puede interesar el paradigma del diseño en general.En lugar de recuperar datos de SQL para una aplicación cliente y luego haciendo filtrado y procesamiento complejo en el cliente, utilice un procedimiento almacenado de CLR fetch, el filtro y el proceso en el servidor y luego transferir resultados al cliente.He encontrado este enfoque extremadamente útil en varias situaciones con grandes bases de datos y requisitos para el rendimiento en tiempo real.

Dr.James McCaffrey trabaja para la investigación de Microsoft en Redmond, Washington Ha trabajado en varios productos clave de Microsoft Internet Explorer y Bing. Obtuvo títulos de la Universidad de California en Irvine y la Universidad del sur de California. Su blog personal es en jamesmccaffrey.wordpress.com. Puede ser contactado en jammc@microsoft.com.

Gracias al siguiente experto técnico por su ayuda en la revisión de este artículo: Darren Gehring (Microsoft)
Darren Gehring es un test manager en Microsoft Research en Redmond, Washington  Antes de trabajar en Microsoft Research, trabajó en el grupo de producto de Microsoft SQL Server durante 10 años.Su página Web está en research.microsoft.com/people/darrenge/.