La correspondance des modèles dans les graphiques

Question

Je suis en train de trouver l'outil / algorithme pour les sections de recherche qui correspond à motif spécifié dans le graphique orienté, par exemple:.

A-> B-> C ou A ou <-> B-> C

S'il vous plaît, me suggérer sens de mes recherches.

I moyen appariement de formes. Je dois trouver tous les groupes de nœuds et d'arêtes, ce motif spécifié correspondant

Answer 1

est-ce pas problème de sous-graphe isomorphisme? Si oui, la page Wikipedia contient une section sur les algorithmes.

Answer 2

Graphique correspondance de motifs est la fonctionnalité au cœur de graphique réécriture outils , ils offrent le déjà mis en œuvre.

par exemple, GrGen vous écrire votre exemple motif en tant que: A -> B: B -> c: C, l'outil génère alors un adaptateur de modèle pour lui, qui est adapté aux caractéristiques du graphique hôte (optimisé en prenant des statistiques sur le graphique en compte).

Answer 3

En ce qui concerne les bibliothèques possibles que vous pouvez trouver une réponse ici Python Graph Library .

En ce qui concerne la mise en correspondance de motif, si vous connaissez le modèle que vous recherchez, il vous suffit de parcourir le graphique et comparer les chemins ou vous pouvez utiliser une fonction pour récupérer un chemin entre les nœuds et vérifier si le modèle existe.