ShortestPathFinder

Catégories

Analyse spatiale

Transformers liés

NetworkFlowOrientator

NetworkTopologyCalculator

StreamOrderCalculator

StreamPriorityCalculator

Calcule le plus court chemin d'un nœud source vers un nœud destination dans un réseau basé sur la longueur ou le poids des arêtes.

Notes

  • Si ShortestPathFinder produit des résultats inattendus, envisagez d'utiliser AnchoredSnapper à la place. Entrez la ligne From-To par le port d'entrée Canddiate et utilisez la même valeur pour la Tolérance d'accrochage. Spécifiez le type d'accrochage = accrochage au point finalet Ajouter un sommet supplémentaire = NEVER..

  • Seules les entités linéaires avec des valeurs d'attribut de poids non négatives sont autorisées si le type de poids est défini sur Par un attribut ou Par deux attributs. Si une entité ne possède pas l'attribut spécifié dans l'attribut de poids en avant ou l'attribut de poids inversé, un poids nul est utilisé pour la ligne. Toute entité dont le poids est négatif sera sortie par le port <Rejeté>.

Configuration

Ports en entrée

Lignes définissant le réseau dans lequel trouver un ou plusieurs chemins. Les entités des lignes d'entrée doivent être un réseau topologiquement nodal avec des entités connectées uniquement aux extrémités des lignes. C'est-à-dire que toutes les entités doivent être séparées aux jonctions.

La ligne From-To contient des sommets qui définissent les nœuds source et destination du réseau. Elle peut contenir des arrêts intermédiaires avant la destination finale. Par exemple, une ligne From-To peut être utilisée pour trouver le chemin de A à B à C à D. Cela peut aussi être lu comme "le chemin de A à D qui passe aussi par B et C". Les lignes From-To peuvent être créées en reliant des points entre eux pour former une ligne, à l'aide des Transformers LineBuilder ou VertexCreator.

Note  Les arrêts intermédiaires d'une ligne From-To doivent correspondre exactement à un nœud existant dans les entités du réseau. Pour cela, vous pouvez utiliser le Transformer Chopper (pour découper le réseau en lignes à 2 points) ou le Transformer AnchoredSnapper (pour accrocher les points intermédiaires au réseau).

Ports de sortie

Pour chaque ligne From-To, si un chemin est trouvé, il sera produit comme une entité unique par le port Path. Cette entité de sortie contient les attributs et le système de coordonnées de la ligne From-To d'origine. La géométrie de l'entité de sortie est constituée de toutes les parties du réseau qui forment le chemin le plus court. Notez que si le Type de poids est défini sur Par un attribut ou Par deux attributs, le "chemin le plus court" est celui où la somme des valeurs des attributs de poids applicables est la plus faible.

Le poids total du chemin trouvé est donné par l'attribut _total_cost.

Si un chemin n'est pas trouvé pour une ligne From-To, alors la ligne From-To ressort par le port NoPath.

Toutes les autres entités du réseau qui ne sont pas utilisées dans le cadre du plus court chemin ressortent par le port Unused.

Les lignes From-To en entrée sont sorties par ce port. Si l'option Réorganiser la ligne From-To est Points intermédiaires seulement ou Tous les points, un attribut _reordered est ajouté pour indiquer si la ligne From-To a été réorganisée.

Toutes les entités non linéaires ressortent par le port <Rejected>, ainsi que toutes les lignes From-To ayant un coût négatif lorsque le paramètre Type de poids est défini à Par un attribut ou par deux attributs".

Les entités rejetées ont un attribut fme_rejection_code avec l'une des valeurs suivantes :

INVALID_DESTINATION_GEOMETRY_TYPE
INVALID_LINE_GEOMETRY_TYPE
INVALID_PARAMETER_WEIGHT

Paramètres

Regrouper par

Le comportement par défaut consiste à utiliser l'ensemble des entités d'entrée comme groupe. Cette option vous permet de sélectionner les attributs qui définissent les groupes à former. Vous pouvez sélectionner des attributs dans les entités en entrée Réseau et From-To.

Traitement des regroupements

Sélectionnez le moment du traitement où les groupes sont traités :

Quand toutes les entités sont reçues

Comportement par défaut. Le traitement ne se produira dans ce Transformer que lorsque toutes les entrées seront présentes.

Quand le groupe change (avancé)

Ce Transformer traitera les groupes en entrée dans l'ordre. Les changements de la valeur du paramètre Regrouper par sur le flux d'entrée déclencheront le traitement du groupe en cours de regroupement. Cela peut améliorer la vitesse globale (en particulier avec plusieurs groupes de taille égale), mais peut provoquer un comportement indésirable si les groupes en entrée ne sont pas ordonnés.

Il y a deux raisons typiques d'utiliser Quand le groupe change (avancé). La première concerne les données entrantes qui sont destinées à être traitées en groupes (et qui sont déjà classées ainsi). Dans ce cas, c'est la structure qui dicte l'utilisation de Regrouper par - et non des considérations de performance.

La seconde raison possible est le potentiel gain de performances.

Les gains de performance sont plus visibles quand les données sont déjà triées (ou lues en utilisant une déclaration SQL ORDER BY) puisque moins de travail est requis de la part de FME. Si les données doivent être ordonnées, elles peuvent être triées dans le traitement (bien que la surcharge de traitement supplémentaire puisse annuler tout gain).

Le tri devient plus difficile en fonction du nombre de flux de données. Il peut être quasiment impossible de trier des flux de données multiples dans l'ordre correct, car toutes les entités correspondant à une valeur Regrouper par doivent arriver avant toute entité (de tout type d'entité ou jeu de données) appartenant au groupe suivant. Dans ce cas, l'utilisation de Regrouper par avec Lorsque toutes les entités sont reçues peut être une approche équivalente et plus simple.

Note  De multiples types d'entités et entités de multiples jeux de données ne vont généralement pas arriver dans l'ordre correct.

Comme pour beaucoup de scénarios, tester différentes approches dans votre traitement avec vos données est le seul moyen sûr d'identifier le gain de performance.

Dimension

Sélectionnez le type de coordonnées à utiliser pour identifier les connexions topologiques :

  • 2D : Utiliser les coordonnées x, y et ignorer les coordonnées z.

  • 3D : Utiliser les coordonnées x, y et z.

Type de Poids

Les valeurs qui résultent du Type de poids sont additionnées pour toutes les lignes d'entrée par rapport à la ligne From-To, et la somme la plus courte devient le chemin le plus court. Sélectionnez un type :

Par longueur

Le poids de chaque ligne d'entrée est fixé à la longueur de la ligne. L'orientation de la ligne n'est pas prise en compte.

Par la longueur (en avant seulement)

Le poids de chaque ligne d'entrée est fixé à la longueur de la ligne. L'algorithme ne prend en compte que l'orientation originale des lignes lors de la recherche du chemin le plus court.

Par un attribut

Le poids de chaque ligne d'entrée est spécifié par l'attribut Poids en avant. L'algorithme ne tient compte que de l'orientation originale des lignes lors de la recherche du chemin le plus court.

Par deux attributs

L'algorithme du plus court chemin prendra en compte les deux directions des lignes d'entrée. L'orientation originale de la ligne d'entrée a le poids spécifié par l'attribut Poids en avant et l'orientation inversée de la ligne d'entrée a le poids spécifié par l'attribut Poids inverse.

Par la distance de la ligne droite (pas de réseaux)

Le poids est calculé comme la distance en ligne droite entre les sommets de la ligne From-To. Lorsque vous utilisez cette option, le paramètre Réorganiser les lignes From-To doit être défini sur Points intermédiaires uniquement ou Tous les points.

Attribut Poids en avant

Ce paramètre est utilisé quand le Type de poids est défini à Par un attribut ou Par deux attributs.

Attribut Poids Inversé

Ce paramètre est utilisé quand la paramètre Type de poids est défini à par deux attributs.

Autoriser les demi-tours

Indique si l'on doit autoriser l'inversion d'une ligne du réseau à être utilisée immédiatement après cette ligne. Si Non, les chemins qui s'inversent ne sont pas pris en compte lors de la recherche du plus court chemin.

Liste de segments

Cet attribut liste les attributs des entités du réseau utilisées pour calculer le chemin.

Cette liste contient également un attribut _direction qui enregistre la direction du segment du plus court chemin par rapport à son entité réseau d'origine. Il sera soit "identique" soit "opposé", selon que l'entité originale du réseau a dû être inversée ou non.

Génération de liste

Quand activé, ajoute un attribut de liste des entités en sortie.

Liste de segments

Entrer un nom de liste.

Note  Les attributs de liste ne sont pas accessibles à partir du schéma de sortie dans FME Workbench, sauf s'ils sont d'abord traités à l'aide d'un Transformer qui opère sur eux, comme ListExploder ou ListConcatenator. Il est également possible d'utiliser AttributeExposer.

Ajouter à la liste

Tous les attributs: tous les attributs seront ajoutés aux entités en sortie.

Attributs sélectionnés : Active le paramètre Attributs sélectionnés où des attributs spécifiques peuvent être choisis pour inclusion.

Attributs sélectionnés

Activé lorsque l'option Ajouter à la liste est définie sur Attributs sélectionnés. Indiquez les attributs que vous souhaitez inclure.

Accrocher les points source et destination

Sélectionnez Oui pour fixer les points de la ligne From-To aux points d'extrémité les plus proches des lignes du réseau. Les points ne sont accrochés aux lignes du réseau que s'ils se trouvent dans la tolérance spécifiée dans Tolérance d'accrochage.

Note  La distance la plus courte est calculée selon la ligne From-To et n'est pas impactée par l'accrochage des points.

Tolérance d'accrochage

Les points de la ligne "Accrocher les points source et destination" vaut oui, les points de la ligne From-To seront accrochés aux lignes du réseau s'ils se trouvent dans cette tolérance.

Réordonner les lignes From-To

Indique si les points de la ligne From-To en entrée doivent être réordonnés pour trouver un chemin plus court. Cette option est utile lorsque l'ordre des points de la ligne From-To n'est pas important, comme dans les problèmes de voyageur de commerce. Une métaheuristique est utilisée pour trouver un ordre des points à faible poids .

Non : La ligne d'entrée From-To est utilisée telle quelle. Aucune optimisation n'est effectuée.

Automatique : La ligne d'entrée From-To est réorganisée automatiquement, sans qu'il soit nécessaire d'ajuster les paramètres par jeu de données. Ce mode tente de produire un bon résultat en peu de temps, mais peut ne pas fonctionner correctement pour tous les jeux de données. Pour les jeux de données dont les valeurs de poids diffèrent de moins d'une unité, utilisez le mode avancé.

Avancé : La ligne d'entrée From-To est réordonnée en fonction des paramètres Nombre d'itérations et Conditions de fin. Ce mode est utile lorsqu'un poids spécifique est souhaité, ou pour les jeux de données où le mode Automatique ne fournit pas un bon résultat.

Réorganiser les points

Points intermédiaires seulement : Les points de début et de fin de la ligne d'entrée From-To ne sont pas modifiés. Les points intermédiaires sont réorganisés.

Tous les points sauf le premier : Tous les points sauf le point de départ de la ligne d'entrée From-To sont réorganisés.

Tous les points sauf le dernier : Tous les points, sauf le point final de la ligne d'entrée From-To, sont réorganisés.

Tous les points (mode avancé uniquement) : Tous les points de la ligne d'entrée From-To sont réorganisés.

Nombre d'itérations

Le nombre de fois où il faut exécuter chaque étape de l'algorithme d'optimisation. Plus le nombre d'itérations est élevé, plus le résultat sera proche de la solution optimale. L'augmentation de ce paramètre accroît le temps de traduction.

Ce paramètre doit être défini comme un nombre entier positif. La valeur par défaut est 10000.

 

Conditions de complétion

Optimisation

Ce paramètre spécifie les critères à utiliser pour déterminer s'il faut terminer l'optimisation ou exécuter un autre cycle d'itérations. Les conditions d'achèvement sont évaluées à la fin de chaque cycle d'itérations.

Après une boucle d'itérations : l'algorithme d'optimisation complète le nombre d'étapes spécifié dans le paramètre Nombre d'itérations.

Quand toutes les conditions sont passées : l'algorithme d'optimisation se termine après que toutes les conditions de complétion sont passées.

Quand une condition est passée : l'algorithme d'optimisation se termine quand n'importe laquelle des conditions de complétion est passée, quel que soit le statut des autres conditions.

Nombre de vérifications

Le nombre de fois que l'algorithme d'optimisation doit renvoyer le même résultat potentiel avant qu'il ne soit accepté. La définition d'une valeur élevée pour ce paramètre peut entraîner un temps de traduction très long ou faire en sorte que la traduction ne soit jamais terminée.

Ce paramètre doit être défini comme un nombre entier non négatif. Une valeur de 0 indique qu'aucune vérification n'est requise. La valeur par défaut est 1.

Notez que si cette condition est requise, paramétrer une très faible valeur pour Options d'optimisation  > Nombre d'itérations peut résulter en un traitement qui n'est pas complet puisqu'il diminue la probabilité de trouver le même résultat potentiel plusieurs fois.

Poids désiré

Le poids le plus élevé qui sera accepté comme valide. Si vous définissez ce paramètre à une valeur faible, la traduction risque de ne jamais être terminée.

Ce paramètre doit être défini sur une valeur non négative. Une valeur de 0 indique qu'il n'y a aucune restriction sur le poids qui sera accepté. La valeur par défaut est 0.

Boucles d'itérations

Le nombre minimum de fois qu'il faut exécuter l'algorithme d'optimisation complet.

Temps (minute)

Le nombre minimum de minutes durant lesquelles exécuter l'optimisation.

Conserver l'ordre des entités

Ce paramètre contrôle l'ordre dans lequel les entités quittent un Transformer.

Lorsqu'un Transformer a plus d'un port de sortie, les entités sortent généralement d'un port à la fois. Parfois, il peut être utile de garder l'ordre dans lequel les entités sont arrivées, en passant d'un port à l'autre si nécessaire. Cela permet de préserver l'ordre des entités, mais au prix d'une perte potentielle d'efficacité du traitement.

Sélectionner une méthode pour l'ordre des entités :

Par port de sortie (défaut)

Conserve seulement l'ordre d'entrée des entités tel qu'elles interviennent dans le groupe d'entités sortant d'un port de sortie donné.

Toutes les entités sortant d'un port de sortie retienne leur ordre relativement entre elles (dans le groupe) mais pas relativement aux entités sortant par d'autres ports de sortie.

Cette option est généralement la plus efficace quand de grandes quantités de textures sortent d'un port de sortie ensemble (tirant parti du traitement par lots).

Comme les entités sortants par différents ports de sortie peuvent ne pas sortir strictement dans l'ordre dans lequel elles étaient arrivées, l'ordre des ports de sortie peut être imprévisible.

A travers plusieurs ports de sortie

Préserve strictement l'ordre d'entrée des entités, quel que soit le port de sortie. Les entités ressortent une par une dans l'ordre où elles sont arrivées, en passant d'un port à l'autre si nécessaire. Cette option est généralement moins efficace car les gains de traitement du mode traitement par lots sont moins susceptibles de s'appliquer - cependant, l'ordre des entités est prévisible.

Éditer les paramètres des Transformers

À l'aide d'un ensemble d'options de menu, les paramètres du Transformer peuvent être attribués en faisant référence à d'autres éléments de traitement. Des fonctions plus avancées, telles qu'un éditeur avancé et un éditeur arithmétique, sont également disponibles dans certains Transformers. Pour accéder à un menu de ces options, cliquez sur à côté du paramètre applicable. Pour plus d'informations, voir Options de menus et paramètres de Transformer.

Définir les valeurs

Il existe plusieurs façons de définir une valeur à utiliser dans un Transformer. La plus simple est de simplement taper une valeur ou une chaîne de caractères, qui peut inclure des fonctions de différents types comme des références d'attributs, des fonctions mathématiques et de chaînes de caractères, et des paramètres de traitement. Il existe un certain nombre d'outils et de raccourcis qui peuvent aider à construire des valeurs, généralement disponibles dans le menu contextuel déroulant adjacent au champ de valeur.

Utilisation de l'éditeur de texte

L'éditeur de texte fournit un moyen efficace de construire des chaînes de textes (dont les expressions régulières) à partir de données source diverses, telles que des attributs, des paramètres et des constantes, et le résultat est directement utilisé dans le paramètre.

Editeur de texte

Utilisation de l'éditeur arithmétique

L'éditeur arithmétique fournit un moyen simple de construire des expressions mathématiques à partir de plusieurs données source, telles que des attributs et des fonctions, et le résultat est directement utilisé dans un paramètre.

Éditeur arithmétique

Valeur conditionnelle

Définit des valeurs selon un ou plusieurs tests.

Fenêtre de définition de conditions

Contenu

Les expressions et chaînes de caractères peuvent inclure des fonctions, caractères, paramètres et plus.

Lors du paramétrage des valeurs - qu'elles soient entrées directement dans un paramètre ou construites en utilisant l'un des éditeurs - les chaînes de caractères et les expressions contenant des fonctions Chaîne de caractères, Math, Date et heure ou Entité FME auront ces fonctions évaluées. Par conséquent, les noms de ces fonctions (sous la forme @<nom_de_fonction>) ne doivent pas être utilisés comme valeurs littérales de chaîne de caractères.

Fonctions chaînes de caractères

Ces fonctions manipulent les chaînes de caractères.

Caractères spéciaux

 Un ensemble de caractères de contrôle est disponible dans l'éditeur de texte.

Fonctions mathématiques

Plusieurs fonctions sont disponibles dans les deux éditeurs.
Fonctions Date/heure Les fonctions de dates et heures sont disponibles dans l'Editeur texte.

Opérateurs mathématiques

Ces opérateur sont disponibles dans l'éditeur arithmétique.

Fonctions d'entités

Elles retournent des valeurs spécifiques aux entités.

Paramètres FME

Les paramètres FME et spécifiques au traitement peuvent être utilisés.
Créer et modifier un paramètre publié Créer ses propres paramètres éditables.

Options - Tables

Les Transformers avec des paramètres de style table possèdent des outils additionnels pour remplir et manipuler des valeurs.

Réordonner

Activé une fois que vous avez cliqué sur un élément de ligne. Les choix comprennent :

  • Ajouter une ligne
  • Supprimer une ligne
  • Déplacer la ligne en cours au dessus
  • Déplacer la ligne en cours en dessous
  • Déplacer la ligne en cours en haut de liste
  • Déplacer la ligne en cours en bas de liste

Couper, Copier et Coller

Activé une fois que vous avez cliqué sur un élément de ligne. Les choix comprennent :

  • Couper une ligne - supprime et copie dans le presse-papiers.
  • Copie une ligne dans le presse-papiers.
  • Colle une ligne depuis le presse-papiers.

Copier, copier et coller peuvent être utilisés au sein d'un Transformer ou entre Transfromers.

Filtre

Commencez à taper une chaîne de caractères, et la matrice n'affichera que les lignes correspondant à ces caractères. Recherche dans toutes les colonnes. Cela n'affecte que l'affichage des attributs dans le Transformer - cela ne change pas les attributs qui sont sortis.

Importer

Le bouton d'import remplit la table avec un jeu de nouveaux attributs lus depuis un jeu de données. L'application spécifique varie selon les Transformers.

Réinitialiser/Rafraîchir

Réinitialise la table à son état initial, et peut fournir des options additionnelles pour supprimer des entrées invalides. Le comportement varie d'un Transformer à l'autre.

Note : Tous les outils ne sont pas disponibles dans tous les Transformers.

FME Community

FME Community est l'endroit où trouver des démos, des tutoriaux, des articles, des FAQ et bien plus encore. Obtenez des réponses à vos questions, apprenez des autres utilisateurs et suggérez, votez et commentez de nouvelles entités.

Voir tous les résultats à propos de ce Transformer sur FME Community.