Cet article a fait l'objet d'une traduction automatique.

CLR

Analyse du chemin le plus court à partir de graphiques à l'aide d'une procédure stockée CLR

James McCaffrey

Télécharger l'exemple de code

Analyse graphique devient de plus en plus important dans les applications logicielles.Ici, un graphe est une collection de nœuds et de coutures, pas une visualisation de données comme un graphique à barres.Cet article présente une démonstration de la façon d'effectuer une analyse de plus court chemin à l'aide d'une procédure stockée CLR de SQL.Les techniques présentées ici peuvent également être utilisés pour de nombreuses autres tâches programmation de l'accès aux données.

Analyse graphique du plus court chemin implique vraiment deux problèmes étroitement liés.La première consiste à déterminer le plus court chemin d'un nœud de démarrage graphique spécifié à un nœud de fin en termes de nombre de sauts.Le deuxième problème est de déterminer la longueur du chemin plus court si les connexions de graphique ont une sorte de poids.Par exemple, supposons que les noeuds dans un graphe représentent les gens et les bords entre les nœuds représentent une communication électronique.Vous pourriez être intéressés par le plus court nombre de sauts entre deux personnes, où vous êtes en supposant implicitement que chaque tronçon a un poids de 1.Ceci est similaire au jeu « six degrees of Kevin Bacon » ou le nombre de Erdos pour un chercheur.Si chaque arête du graphe a un poids — par exemple, ce qui représente une mesure de l'importance d'une relation, vous pouvez déterminer le chemin le plus court entre deux personnes qui prennent de l'importance du poids en compte.

Mais pourquoi utiliser une procédure stockée CLR ?Des algorithmes de plus court chemin traditionnels supposent que la représentation graphique de problème peut être complètement stockée dans la mémoire de la machine, généralement dans une liste de matrice ou de contiguïté.Pour grands graphes — par exemple, graphique représentant les réseaux sociaux, cette approche n'est souvent pas possible.Grands graphes peuvent être facilement stockés dans une base de données SQL.Une approche pour effectuer des analyses de plus court chemin de graphiques stockés dans une base de données SQL consiste à écrire une procédure de langue stockée SQL native.Article du MSDN Magazine , "Basée sur les graphiques le plus court chemin analyse avec SQL" (msdn.microsoft.com/magazine/jj863138), explique cette démarche en détail.Toutefois, une procédure stockée au lieu d'une approche purement de SQL en utilisant un CLR peut fournir nettement meilleure performance et une flexibilité beaucoup plus grande pour la personnalisation.

Jetez un oeil à la représentation graphique factice dans Figure 1.Le graphique a huit nœuds.Les chiffres à côté de chaque flèche représentent un poids.Le plus court chemin entre 222 et nœuds 444 est de 222 -> 555 -> 666 -> 777 -> 444, qui a une distance pondérée 1.0 + 1.0 + 1.0 + 2.0 = 5.0.Notez que 222 -> 333 -> 666 -> 777 -> 444 est également un plus court chemin de 222 444.

Figure 1 graphique factice pour l'analyse de plus court chemin

La figure 2 montre une capture d'écran d'un appel à un CLR stockée procédure nommée csp_ShortestPath qui détermine le plus court chemin entre 222 et nœuds 444.Dans ce cas le chemin le plus court s'affiche comme une chaîne délimitée par des points-virgules dans l'ordre inverse.La sortie est au fond de l'image.La partie supérieure de l'image contient des instructions SQL qui crée un graphique correspondant à celui de Figure 1.

Figure 2 appeler un CLR de plus court chemin, procédure stockée

Cet article suppose que vous avez avancé des compétences en programmation c# et une connaissance de base avec SQL.Je vous présente tout le code SQL pour créer le graphique factice et tous le code c# pour créer le CLR, procédure stockée, et je décris aussi plusieurs façons d'appeler la procédure stockée CLR.Tout le code de cet article est disponible à archive.msdn.microsoft.com/mag201305Graph.

Création de la base de données

Pour créer le graphique de base SQL factice, j'ai lancé Microsoft SQL Server Management Studio (SSMS) et connecté à une instance SQL Server .Procédures stockées CLR sont pris en charge par SQL Server 2005 et versions ultérieures.Tout d'abord, j'ai créé une base de données nommée dbShortPathWithCLR en utilisant les commandes suivantes :

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

Je recommande vivement à expérimenter avec une base de données factice, plutôt qu'avec une base de données de production. Les commandes pour créer une table contenant des données de nœud et le bord sont :

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

ID de nœud est stockées sous SQL type bigint, qui correspond approximativement à c# de type long. Les poids de bord sont stockés en tant que type réel, qui est synonyme de SQL type float, qui correspond approximativement à c# type double (24). Dans de nombreuses situations, vous ne serez concerné avec un poids de bord et la colonne edgeWeight peut être omise.

Les 14 passages de Figure 3 définir le graphique.

Figure 3 Définition graphique

    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 vous comparez les passages de Figure 3 avec l'image en Figure 1 vous verrez que chaque instruction correspond à une arête entre les nœuds.

Ensuite, la base de données est préparée pour l'analyse de plus court chemin :

    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

Les trois premières requêtes créent des index sur les colonnes fromNode, toNode et edgeWeight. Lorsque vous travaillez avec grands graphiques, les index sont presque toujours nécessaires pour fournir des performances raisonnables. Les deux prochaines déclarations modifient la base de données ainsi la propriété trustworthy est définie sur « on ». La valeur par défaut de la propriété est « off ». Je vais vous expliquer pourquoi la propriété trustworthy doit être sur « on » peu de temps.

À ce stade, le mannequin graphique basée sur SQL est créé. L'étape suivante consiste à Visual Studio permet de créer un CLR procédure stockée pour effectuer des analyses de plus court chemin.

Création de la CLR, procédure stockée

Pour créer la procédure stockée de plus court chemin CLR, j'ai lancé Visual Studio 2010. Pour créer des procédures stockées CLR votre développement environnement doit inclure le Microsoft .NET Framework version 3.5 ou ultérieur. Partir du fichier | Nouveau | Menu projet j'ai choisi la base de données | SQL Server groupe de modèles de projet et sélectionné l'option de projet de base de données CLR SQL Visual c# comme le montre Figure 4. J'ai nommé le projet CreateStoredProc.

Figure 4 nouveau projet CLR dans Visual Studio 2010

Notez que le .NET Framework 3.5 est sélectionné dans le contrôle de liste déroulante de boîte de dialogue Nouveau projet. La version du framework cible doit correspondre à la version du framework sur le SQL Server hébergeant la base de données. Parce que la base de données factice est sur une instance de SQL Server 2008, je cible .NET Framework 3.5. Si la base de données factice avait été sur une instance de SQL Server 2005, j'ai avez adresserait .NET Framework 2.0. La documentation de procédure stockée CLR est un peu glauque en décrivant les corrélations entre les versions de framework sur l'environnement de développement, sur le SQL Server et dans le projet de création de procédure stockée c#. Vous devrez peut-être recourir à un peu de tâtonnement.

Après avoir cliqué sur OK pour créer le projet de création de procédure stockée CLR, Visual Studio invite avec une demande d'informations sur le modèle de nom et d'authentification de la base de données cible (voir Figure 5). Après avoir cliqué sur OK dans la boîte de dialogue nouvelle référence de base de données, Visual Studio charge un nouveau projet, mais n'est pas directement créer un modèle. Pour générer un modèle, faites un clic droit sur le nom du projet — CreateStoredProc dans ce cas — et sélectionnez Ajouter | Un nouvel élément dans le menu contextuel (voir Figure 6).

Figure 5 une nouvelle référence de base de données pour le projet

Figure 6 nouveau point, procédure stockée

J'ai sélectionné l'élément de la procédure stockée et la nommèrent csp_ShortestPath.cs. Ce nom, sans l'extension .cs, devient le nom de la procédure stockée dans la base de données cible. Comme une question de style, j'ai préfixer généralement les noms de procédures stockées CLR avec csp pour les distinguer des procédures stockées système (sp), étendu (xp) des procédures stockées et procédures stockées définies par l'utilisateur (usp). Après avoir cliqué sur le bouton Ajouter, Visual Studio a généré un modèle léger d'une classe partielle nommée 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
  }
};

File d'attente de priorité un pauvre homme

L'algorithme du plus court chemin présenté dans cet article nécessite une structure de données de file d'attente de priorité d'accès aléatoire. Le .NET Framework ne fournit pas une file d'attente de priorité intégré qui répondra exactement aux besoins de l'algorithme du plus court chemin, donc vous devez coder votre propre file d'attente prioritaire.

Une file d'attente prioritaire est semblable à une file d'attente de (FIFO) first-in-first-out normal avec quelques différences. Les éléments dans une file d'attente de priorité sont censés pour avoir une sorte de champ priorité en plus un champ de données. Par exemple, un élément de file d'attente de priorité pour un groupe de clients en attente pour le support technique peut être constituée du nom d'un client et la durée de que service attend le client.

Files d'attente de priorité soutiennent une opération Dequeue supprime toujours l'élément ayant la plus haute priorité. Ici, le sens de la plus haute dépend du contexte du problème et peut être une valeur plus grande ou plus petite valeur. Une file d'attente de priorité random access prend en charge une opération qui modifie le champ priorité d'un élément avec un ID spécifié.

Cet article présente la file d'attente de priorité un pauvre homme — celui qui fait le travail, mais a beaucoup de place pour l'amélioration. L'algorithme du plus court chemin opère sur une file d'attente de priorité où les éléments dans la file d'attente ont deux champs : un ID de nœud (par exemple 111 ou 222) et un champ de distance. Le champ de distance est utilisé par l'algorithme pour stocker la meilleure distance connue (plus courte) entre le nœud de démarrage et le nœud d'élément à tout moment pendant l'exécution de l'algorithme. Le champ distance agit comme priorité de l'élément, et des valeurs plus petites pour distance représentent une priorité plus élevée.

Ainsi, pour prendre en charge une file d'attente de priorité d'accès aléatoire, le modèle de procédure stockée c# doit supplémentaires à l'aide de la déclaration qui référence l'espace de noms System.Collections.Generic et deux définitions de classe définie par le programme supplémentaire placé au-dessous de la classe partielle de StoredProcedures :

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;
  }
}

J'utilise une portée publique pour les champs de la classe pour plus de simplicité. La file d'attente prioritaire est essentiellement un éléments de la liste de NodeDistance :

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

Encore une fois, j'utilise la portée publique pour plus de simplicité seulement. L'opération Dequeue supprime l'élément de NodeDistance avec la plus petite valeur de distance :

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

Méthode Dequeue appelle une méthode d'assistance pour trouver l'emplacement de l'élément qui a la plus petite distance, enregistre un renvoi à cet article et utilise ensuite la méthode List.RemoveAt intégrés pour supprimer l'élément.

Méthode d'assistance IndexOfSmallestDist est défini comme :

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;
}

La méthode effectue une recherche linéaire simple par le biais de la collection sous-jacente de la liste. Notez que cette approche signifie que Dequeue a l'exécution d'o (n).

L'opération de la file d'attente est définie comme :

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

L'opération de changement de priorité est définie comme :

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

Méthode ChangePriority appelle la méthode IndexOf qui localise la position d'un élément de NodeDistance, compte tenu ID de l'élément, d'assistance et est défini comme :

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

Encore une fois, notez que parce que la méthode IndexOf effectue une recherche linéaire, sa performance est o (n).

L'algorithme du plus court chemin a besoin de connaître le nombre d'éléments dans la file d'attente de priorité à un moment donné :

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

Pour résumer, la priorité d'accès aléatoire du pauvre file d'attente définie ici prend en charge une opération de la file d'attente ; une propriété Count ; une opération Dequeue supprime l'élément de NodeDistance avec la plus petite distance ; et une opération ChangePriority qui modifie la distance d'un élément spécifié. Opérations Dequeue et ChangePriority ont des performances d'o (n).

Pour grands graphes, les performances de l'algorithme du plus court chemin sont fortement tributaire de l'efficacité de la file d'attente de priorité utilisée. Exécution d'o (n) est souvent acceptable qu'il est possible de mettre en œuvre une file d'attente de priorité qui a de bien meilleures performances de O (log n). Ces implémentations généralement utilisent une structure de données tas binaire et sont assez difficiles. Je décris une file d'attente de priorité efficace dans mon article du Magazine Visual Studio , "priorité des files d'attente avec c#," disponible à bit.ly/QWU1Hv.

Créer la procédure stockée

Avec la file d'attente prioritaire personnalisés définis, l'algorithme du plus court chemin peut être implémenté. La signature de la méthode est la suivante :

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

Méthode csp_ShortestPath accepte trois paramètres d'entrée et possède deux paramètres de résultat. Paramètre startNode contient l'ID de nœud du nœud pour commencer la recherche. Rappelons que dans la définition de table SQL, toNode et colonnes fromNode sont définis comme SQL type bigint, qui correspond au type de langage c# depuis longtemps. Lorsque la procédure stockée définissant un CLR, les paramètres de la procédure utilisent un modèle de type défini dans l'espace de noms System.Data.SqlTypes. Ces types sont généralement assez faciles mapper aux types SQL et c#. Ici, type bigint mappé à SqlInt64. Nombre de paramètre d'entrée est également déclarée comme type SqlInt64.

MaxNodesToCheck de paramètre d'entrée est utilisé pour empêcher la procédure stockée de rotation incontrôlable sur extrêmement grands graphes. Ici, maxNodesToCheck est déclaré comme type SqlInt32, qui correspond au type int de c#.

Si vous êtes nouveau sur les procédures stockées SQL, vous pourriez être surpris d'apprendre qu'ils ne peuvent avoir aucune valeur de retour explicite, ou peuvent retourner une valeur int, mais ils ne peuvent pas retourner explicitement un autre type de données. Donc dans les situations où un SQL procédure stockée doit retourner plusieurs valeurs, ou retourner une valeur qui n'est pas de type int, l'approche adoptée consiste à utiliser les paramètres de sortie. Ici, la procédure stockée CLR retourne le chemin le plus court sous forme de chaîne, tels que « 666, 444 ; 777 ; 222, 333 » et retourne également la distance totale du chemin plus court comme une valeur numérique, tels que 5.0. Donc paramètre out, pathResult est déclaré comme type SqlString et paramètre de sortie distResult est déclaré comme étant de type Sql­Double, correspondant aux types string c# et double, respectivement.

La définition de procédure stockée CLR continue en mettant en place des structures de quatre données :

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();

Comme l'algorithme du plus court chemin s'exécute, à un moment donné, l'algorithme doit accéder l'actuelle meilleure () connue totale distance la plus courte à partir du nœud de démarrage pour tous les autres nœuds. La collection de dictionnaires nommée « distance » détient cette information. La clé de dictionnaire est un ID de nœud et la valeur de dictionnaire est la plus courte distance totale connue. La collection de dictionnaires nommé magasins « précédents » l'ID de nœud prédécesseur immédiat à un ID de nœud de clé dans le plus court chemin. Par exemple, dans l'exemple illustré dans Figure 2, le nœud d'extrémité est 444. Son prédécesseur immédiat dans le plus court chemin est 777. Donc précédent [444] = 777. En substance, la collection précédente détient le chemin le plus court de manière codée.

La collection de dictionnaires, nommée « beenAdded » contient des informations indiquant si un nœud graphique a été ajouté à la file d'attente de priorité de l'algorithme. La valeur booléenne est une valeur factice, car il n'est pas vraiment nécessaire pour déterminer si un nœud est dans la collection. Vous pouvez utiliser une table de hachage au lieu d'une collection de dictionnaires. La file d'attente de priorité personnalisé nommé « PQ » a été défini et expliqué dans la section précédente de cet article.

La définition de procédure stockée continue :

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

L'objet SqlConnection est la seule connexion à la base de données du graphique de cible. Je déclare ici, afin que je puisse vérifier son état plus tard si une Exception se produit. Bien que pas strictement nécessaire, lorsque l'écriture CLR stocké procédures que je préfère créer explicitement local c# tapé variables qui correspondent à la SQL tapé variables de paramètre.

La définition continue :

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

Ces lignes de code initialisent le nœud de démarrage. La valeur dans la dictionnaire de distance est définie à 0.0 parce que la distance entre le nœud de démarrage et lui-même est égal à zéro. Le prédécesseur immédiat vers le nœud de démarrage n'existe pas alors la valeur -1 est utilisée pour indiquer cela. La file d'attente prioritaire est initialisé avec le nœud de démarrage et la collection de dictionnaires beenAdded est mis à jour.

La définition continue :

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

Lorsque les procédures stockées CLR d'écriture je préfère utiliser les blocs try-catch explicite plutôt que la plus élégante à l'aide de déclaration. Lorsque vous configurez la chaîne de connexion, vous avez deux options. Dans bien des cas, car la procédure stockée s'exécute sur le même ordinateur que la base de données SQL, vous pouvez simplement définir la chaîne de connexion « context connection = true. " Une connexion contextuelle en théorie fournira de meilleures performances qu'une connexion standard. Cependant, une connexion contextuelle présente plusieurs limites. Une des limites, c'est qu'il peut soutenir seulement un seul lecteur de données SQL. Comme vous le verrez bientôt, plus court chemin analyse souvent (mais pas toujours) nécessite deux lecteurs de données SQL.

Parce que cette procédure stockée CLR nécessite deux lecteurs, une chaîne de connexion standard comportant une clause qui définit la propriété MultipleActiveResultSets sur true est utilisée. Cette clause n'est pas actuellement pris en charge par les liaisons de contexte SQL. Parce que la procédure stockée utilise une connexion standard plutôt qu'une connexion de contexte, le niveau d'autorisation de base de données pour le projet de création de la procédure stockée Visual Studio doit être sur externes, comme le montre Figure 7. Toutefois, afin de définir cette propriété SQL base de données doit avoir sa propriété trustworthy définie sur "marche", comme indiqué dans Figure 2.

Figure 7 définition du niveau de base de données Permission

Pour résumer, lorsque vous créez la base de données de graphique, la propriété trustworthy de la base de données est définie sur « on ». Cela permet au projet de Visual Studio la propriété niveau d'autorisation de base de données externe. Cela permet la définition de procédure stockée à utiliser une connexion standard plutôt qu'une connexion contextuelle. Cela permet de propriété de la connexion MultipleActiveResultSets la valeur true. Et cela permet à deux lecteurs de données SQL dans la procédure stockée.

La définition de procédure stockée continue :

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

L'algorithme utilisé ici est une variante du plus court chemin de Dijkstra, l'un des plus célèbres en informatique. Bien que court, l'algorithme est très subtile et peut être modifié à bien des égards. Le cœur de l'algorithme est une boucle qui se termine lorsque la file d'attente prioritaire est vide. Ici, une test supplémentaire de validation basée sur le nombre total de noeuds de graphe traitées est ajoutée. À l'intérieur de la boucle principale, l'appel de Dequeue de file d'attente de priorité renvoie le nœud dans la file d'attente dont la distance totale connue (plus courte) meilleure à partir du nœud de démarrage. Si le nœud juste enlevé de la priorité la file d'attente est le nœud de fin, puis le chemin le plus court a été trouvé et la boucle se termine.

La définition continue :

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;
  }

Ces lignes de code obtenir tous les voisins de l'u de nœud actuel. Notez que cela nécessite un premier lecteur de données SQL. Chaque v de nœud voisin est vérifié pour voir si c'est la première apparition du nœud dans l'algorithme. Dans l'affirmative, un point NodeDistance avec v comme son nodeID est instancié et ajouté à la file d'attente prioritaire. Au lieu d'ajouter des nœuds à la file d'attente de priorité car elles sont rencontrées, une autre conception est initialement ajouter tous les nœuds dans le graphique à la file d'attente prioritaire. Toutefois, pour les très grands graphes cela pourrait exigent une très grande quantité de mémoire de la machine et durer très longtemps.

La boucle de lecture-tout-voisins interne continue :

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;

Ce code interroge la base de données pour obtenir la distance à partir du nœud actuel vous v nœud voisin actuel. Avis un deuxième lecteur de données est nécessaire pour ce faire. L'existence du deuxième lecteur de données entraîne les multiples modifications aux propriétés dont la propriété trustworthy de la base de données et le projet de Visual Studio la propriété Permission. Si votre analyse de plus court chemin utilise un graphe non pondéré — c'est-à-dire une où tous les poids de bord sont censés pour être 1 — vous pouvez simplifier en supprimant le second lecteur et son remplacement par

alt = distance[u.
nodeID] + 1;

for

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

Variable alt est une distance de test à partir du nœud de démarrage à l'actuel v de nœud voisin. Si vous examinez l'instruction d'assignation attentivement, vous verrez qu'alt est la plus courte distance connue de l'u de nœud à nœud début plus la distance réelle de nœud vous à nœud v. Cela représente une distance plus courte nouvelle potentielle par le v de nœud à nœud de démarrage.

La boucle de lecture-tout-voisins interne et la boucle de l'algorithme principal continuent avec :

if (alt < distance[v])
    {
      distance[v] = alt;
      previous[v] = u.
nodeID;
      PQ.ChangePriority(v, alt);
    }
  }  // sdr Read loop
  sdr.Close();
} // Main loop
conn.Close();

Si la distance de test à partir du nœud de démarrage et v est inférieure à la plus courte distance connue à partir du nœud de démarrage à v (stocké dans le lointain Dictionary), puis une nouvelle distance plus courte du début à v a été trouvée et distance de structures de données locales, précédent et la file d'attente de priorité sont mises à jour en conséquence.

La logique de la procédure stockée détermine maintenant si la boucle de l'algorithme principal arrêter car un chemin le plus court a été en effet trouvé ou fermée car aucun chemin d'accès entre le nœud de démarrage et de fin a été trouvée :

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;

Rappelons qu'il y a vraiment deux résultats à cette implémentation de plus court chemin : le plus court chemin, exprimé en un point-virgule -­délimitée par la chaîne dans l'ordre inverse, et le plus court chemin mesuré par la somme des poids de bord entre les nœuds dans le plus court chemin. La procédure stockée utilise les valeurs par défaut de « NOTREACHABLE » et -1,0 pour les situations où le nœud de fin n'est pas accessible depuis le nœud de démarrage. Le tout en boucle les nœuds de plus court chemin des extraits du dictionnaire précédent et les assemble de noeud pour démarrer le nœud à l'aide de la concaténation de chaînes. Si vous êtes ambitieux, vous pouvez utiliser une pile et construire la chaîne de résultat de nœud début au nœud fin. Rappelons que les deux résultats sont retournés par les distResult et les paramètres pathResult.

La définition de procédure stockée se termine par la vérification des erreurs :

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

Si une Exception s'est produite — généralement si le SQL Server est à court de mémoire un graphique extrêmement volumineux ou en raison d'un time-out de la connexion SQL — le code tente de nettoyer la connexion SQL et retourner des résultats qui ont une signification.

Génération, le déploiement et l'appel de la procédure stockée

Après s'être assuré que vous avez configuré la base de données trustworthy propriété sur « on » et le niveau d'autorisation de base de données externe, sélectionnez construire CreateStoredProc dans le menu générer de Visual Studio . Si la génération réussit, sélectionnez déployer créer­procédure stockée dans le menu Générer pour copier le CLR procédure stockée sur votre machine de développement pour le SQL Server qui héberge le graphique basée sur SQL.

Il y a plusieurs façons d'appeler la procédure stockée CLR. Le projet Visual Studio contient un modèle de test, que vous pouvez utiliser. Ou vous pouvez appeler la procédure stockée directement à partir de SSMS, comme le montre Figure 2. Par exemple :

    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

Une autre option consiste à appeler la procédure stockée CLR depuis une application c# à l'aide de ADO.NET, le long des lignes de Figure 8.

Ou, si vous êtes un véritable masochiste, vous pouvez appeler la procédure stockée CLR à l'aide de la technologie LINQ .

La figure 8, appeler une procédure stockée de dans c# à l'aide de 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;
// ...
cmd.ExecuteNonQuery();
string result = (string)cmd.Parameters["@pathResult"].Value;
distResult = (double)cmd.Parameters["@distResult"].Value;

Plus que juste de plus court chemin

Le code et l'explication présentée ici devraient vous permettre d'aborder l'analyse graphique du plus court chemin à l'aide d'une procédure stockée CLR. En outre, vous pouvez trouver le paradigme de conception utile en général. Au lieu d'extraction de données de SQL pour une application cliente et puis faire de filtrage et de traitement complexe sur le client, utilisez une procédure stockée CLR à fetch, de filtre et de processus sur le serveur, puis transférer les résultats au client. J'ai trouvé cette approche est extrêmement utile dans plusieurs situations avec les grandes bases de données et les exigences de performances en temps réel.

Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Washington Il a travaillé sur plusieurs produits Microsoft clés, y compris Internet Explorer et Bing. Il est diplômé de l'Université de Californie à Irvine et de l'Université de Californie du Sud. Son blog est à jamesmccaffrey.wordpress.com. Il peut être contacté à jammc@microsoft.com.

Merci à l'expert technique suivant d'avoir relu cet article : Darren Gehring (Microsoft)
Darren Gehring est un gestionnaire de tests Microsoft Research à Redmond, Washington  Avant les travaux de Microsoft Research, il a travaillé dans le groupe de produits Microsoft SQL Server depuis 10 ans. Sa page Web est à research.microsoft.com/people/darrenge/.