Algorithme pour comparer la similarité des chemins dirigés par graphe orienté

Question

J'ai un graphe orienté avec deux chemins dirigés en elle.

Je veux un algorithme pour déterminer la similitude entre les deux voies.

Ce message mentionne en utilisant Levenshtein pour déterminer une similitude approximative. Je me rends compte aussi que la distance Hamming utilise une même métrique.

Ma question est:

Comment gérez-vous le cas où deux chemins sont parallèles les uns aux autres. C'est si les deux chemins ont pas de nœuds similaires, mais seraient considérés comme « similaires » parce que leurs chemins se déplacent dans la même direction très proches les uns des autres.

Merci

Answer 1

La réponse simple est que c'est une question très difficile, et compte beaucoup sur votre définition de ce que signifie « similaires » dans un graphique. Dans la plupart des graphiques, vous pouvez réorganiser les nœuds de deux chemins disjoints de façon plane de manière à apparaître pour lancer « parallèle ».

Un bon endroit pour commencer à examiner les mesures de similarité plus avancées serait de considérer la matrice de contiguïté du graphique, et de regarder divers Google scholar .