Get best of the week

Vérification de l'isomorphisme de deux graphiques et recherche de sous-graphiques isomorphes: une approche basée sur l'analyse des chemins NB

Bonjour à tous.

Il y a une telle tâche - vérifier si deux graphiques sont isomorphes l'un à l'autre. Autrement dit, pour savoir si ces deux graphiques sont «le même» graphique, mais avec des nombres de sommets différents et, si les graphiques sont spécifiés graphiquement, avec des emplacements spatiaux différents. La solution à ce problème n'est pas aussi évidente qu'elle peut sembler à première vue: même pour les petits graphiques, un regard sur leur représentation graphique ne donnera pas toujours une réponse non ambiguë. Voir, par exemple, un dessin sur le même Wiki: en.wikipedia.org/wiki/Graph_isomorphism#Example .

Bien évidemment?

Mais il y a une tâche plus difficile: rechercher dans un «grand» graphe tous les sous-graphes isomorphes à un autre graphe «plus petit». Il s'agit d'une forêt encore plus "sombre". Ce n'est bien sûr pas entièrement sombre, mais la tâche, voyez-vous, n'est pas la plus facile.

Alors qu'est-ce que nous avons?

1. Pourquoi tout cela est-il nécessaire?


Et bien que le problème des (sous-) graphes isomorphes, comme nous l'avons déjà mentionné, soit compliqué, il est tout à fait nécessaire et utile. Pourquoi? Et puis, par exemple, pour rechercher dans la base de données des composés chimiques similaires à une molécule donnée par sa formule structurelle. Après tout, cela peut être imaginé comme un graphique, non? La chimio-informatique le fait - il existe une telle science. Mais il y a aussi des tâches de comparaison avec l'échantillon, diverses tâches bioinformatiques et bien d'autres choses intéressantes.

2. Comment résoudre ce problème?


L'approche classique pour résoudre ce problème a été établie par J. Ullman en 1976 [3], plus tard il a considérablement amélioré son algorithme [4]. De plus, cette approche a été développée plus avant dans les travaux de nombreux autres auteurs, par exemple Cordella et al. [2] (algorithme VF2), Bonnitsi et al. [1] (algorithme RI), etc.

En bref, l'essence de cette approche est «intelligente énumérer »les correspondances possibles des sommets du graphe échantillon B et du graphe A dans lequel il est recherché. Cette recherche rend «intelligent» la saisie de diverses conditions et restrictions qui vous permettent de supprimer les options inappropriées le plus tôt possible. Aussi, à ces fins, divers traitements préliminaires des données sources peuvent être effectués.

Nous ne nous engagerons pas à relire ces œuvres ici, mais nous inviterons le lecteur à en prendre connaissance de manière indépendante. Cependant, «un spectacle vaut mieux qu'une commande», et il convient de noter qu'il existe de bons exemples graphiques et des explications de ces algorithmes sur le Web. Voir, par exemple, ce qui suit:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - une très bonne et claire explication avec un exemple,
issue.life/questions/8176298 - étapes de l'algorithme VF2 avec un exemple .

Cependant, la question se pose - existe-t-il d'autres moyens et approches possibles pour résoudre ce problème, bien que dans certains cas particuliers? Et je voudrais vous présenter une des réponses possibles à cette question.

2. Isomorphisme des graphes et des chemins NB


Soyons immédiatement d'accord: sous NB-chemins (et non de l'anglais, mais simplement parce qu'il est si court), nous appellerons des chemins maximaux sans branchement, c'est-à-dire chemins non ramifiés au maximum longs d'un graphique.

Donc, si nous avons deux graphiques qui sont isomorphes l'un à l'autre , alors pour toute représentation du premier graphique comme une séquence de chemins non ramifiés étendus au maximum (c'est-à-dire nos chemins NB), il existe toujours la même représentation du deuxième graphique qui lui correspond, et en même temps:

  • pour les graphes dirigés, les chemins correspondant les uns aux autres seront alignés,
  • les degrés des sommets correspondant les uns aux autres pour les graphes non orientés (et pour les graphes orientés, les nombres d'arêtes entrantes et sortantes, respectivement) seront égaux à
  • lors de la "combinaison" de telles représentations, nous aurons une correspondance des sommets des premier et deuxième graphiques.

Un exemple . Graphique A = {1-> 2, 1-> 6, 4-> 5, 5-> 1, 3-> 3}. Graphique B = {3-> 4, 3-> 5, 1-> 2, 2-> 3, 6-> 6}
Chemins A (chemins maximaux non ramifiés de A ): 1-> 2, 1-> 6, 4-> 5-> 1, 3-> 3
Chemins B (chemins maximaux non ramifiés de B ): 3-> 4, 3-> 5, 1-> 2-> 3, 6-> 6 Correspondance de sommets
: 1 ( A): 3 (B), 2 (A): 4 (B), 6 (A): 5 (B), 4 (A): 1 (B), 5 (A): 2 (B), 3 ( A): 6 (B).

Ainsi, le problème de la vérification de l'isomorphisme de deux graphes peut être résolu en trouvant de tels chemins correspondant les uns aux autres puis en vérifiant l'égalité des matrices d'adjacence construites en fonction de leur conservation de l'ordre des sommets dans les séquences de chemins obtenues (chaque sommet est ajouté une fois à la séquence, première «mention»). Dans notre exemple, les ordres de sommets suivants seront utilisés pour construire des matrices d'adjacence:

A : 1, 2, 6, 4, 5, 3
B : 3, 4, 5, 1, 2, 6

Matrice d'adjacence pour A pour un ordre donné de sommets:

image

Matrice d'adjacence pour B pour un ordre donné de sommets:

image

les matrices sont égales, donc les graphes A et B sont isomorphes.

De plus, cette approche (1) est applicable aux graphiques orientés et non orientés, (2) elle s'applique aux graphiques contenant plus d'un composant connecté / fortement connecté, (3) elle s'applique aux graphiques contenant plusieurs (multiples) arêtes et boucles, cependant (4) ne prend pas en compte les sommets pour lesquels aucune arête ne lui est incidente.

3. Eh bien, vérifié l'isomorphisme des graphiques. Mais qu'en est-il de la recherche de sous-graphiques?


Et ici, franchement, tout est beaucoup plus compliqué. Ici, nous aurons la restriction suivante: sur la base de l'essence même de la méthode, vous pouvez trouver non pas tous, mais seulement des sous-graphiques "inscrits" . Et nous appellerons le sous- graphe "inscrit" du graphe A un sous-graphe qui peut être "collé" à d'autres parties du graphe A uniquement en raison d'arêtes incidentes uniquement aux sommets limites de ses (sous-graphe) chemins non ramifiés de longueur maximale (de plus, le graphe A peut contenir autres composants connectés). Ne vous inquiétez pas, ci-dessous sera un exemple, et tout sera plus clair.

De plus, lors de la résolution de ce problème, en plus de trouver la correspondance des chemins NB des graphiques A et B en longueur (comme ce fut le cas avec la vérification de l'isomorphisme discuté ci-dessus), il est également nécessaire de rechercher séparément les correspondances possibles suivantes entre elles:

  • Correspondance des chemins NB - chaînes simples du graphique B aux chemins NB - chaînes simples / cycles simples du graphique A. De plus, initialement ces chemins dans le graphique A peuvent être plus longs - dans ce cas, leurs segments sont pris qui sont égaux en longueur au chemin souhaité de B.
  • Correspondance des chemins NB «fin» du graphique B à n'importe quel chemin NB du graphique A (dans ce cas, les chemins du graphique A peuvent également être plus longs - dans ce cas, leurs segments sont pris qui sont égaux en longueur au chemin souhaité du graphique B).

Regardons un exemple:

image

Lors de la recherche d'un sous-graphe isomorphe «inscrit» du graphique B dans la colonne A (voir figure ci-dessus), les correspondances suivantes seront trouvées:

  • chemin intérieur 2-> 3-> 4 de la colonne B: chemin intérieur 2-> 3-> 4 de la colonne A,
  • chemins de fin 1-> 2 et 10-> 2 de la colonne B: chemin de fin 0-> 2 de la colonne A et un fragment du chemin de fin 7-> 1-> 2 de la colonne A, à savoir 1-> 2,
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

Ainsi, en tant que sous-graphiques «inscrits» du graphique A qui sont isomorphes au graphique B, les 5 options suivantes peuvent être trouvées:

A1 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 9-> 10}
A2 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 10-> 11}
A3 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 12-> 13}
A4 = {0-> 2, 1-> 2, 2 -> 3, 3-> 4, 4-> 5, 4-> 6, 13-> 14}
A5 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 14-> 12}

Cependant, si nous ajoutons un bord supplémentaire 3-> 8 au graphique A, nous obtenons le graphique A '(ci-dessous dans la même figure). Et dans A 'il n'y aura plus de sous-graphes "inscrits" isomorphes au graphe B. En effet: l'arête 3-> 8 "divise" le chemin 2-> 3-> 4 du graphe A en deux et donc les chemins candidats pour le chemin intérieur 2 ->3-> 4 colonnes B ne seront pas trouvées.

4. Maintenant, l'algorithme lui-même


Nous pouvons maintenant passer à un examen plus détaillé de l'algorithme de recherche pour les sous - graphiques «inscrits» dans la colonne A qui sont isomorphes à une colonne B.

Ainsi, l'algorithme comprendra 4 étapes:

  • Prétraitement
  • Correspondant à
  • Amincissement,
  • Conclusion

Étape I. Prétraitement


À ce stade, nous trouvons tous les NB-chemins pour chacun des graphiques, ainsi que d'évaluer les facteurs qui limitent l'espace de choix pendant l'énumération. Ceux. nous faisons ce qui suit:

  1. Nous trouvons tous les NB-chemins dans la colonne A et les mettons dans un tableau dynamique (en C ++ - dans un vecteur)
  2. Nous trouvons tous les NB-chemins dans la colonne B et les mettons dans un tableau dynamique (vecteur) PathsB
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

Donc, nous avons NB-chemins sur les deux graphiques et les paramètres limites de p.p. 3-5.

Étape II. Cartographie


À ce stade, nous sélectionnerons les chemins NB candidats (ci-après simplement appelés «chemins candidats») dans la colonne A pour chacun des chemins NB de la colonne B. Marquage de chaque chemin candidat dans PathsA pour chaque i-ème chemin de PathsB [i ] sera écrit dans un tableau dynamique à deux dimensions (en C ++ - dans un vecteur de vecteurs) NPaths - respectivement dans le i-ème vecteur (i-ème ligne) - sous la forme d'un triplet ordonné de nombres: le numéro du chemin correspondant dans PathsA - le numéro de la position de départ dedans - la longueur du chemin .

Par exemple, PathsB [2] = {1, 0, 3, 3, 1, 3} signifie que les chemins PathsB [2] sont associés à 2 chemins candidats de A: de PathsA [1] - les 3 premiers éléments de chemin à partir de zéro ( initial), et de PathsA [3] - également 3 éléments à partir du premier (à côté de l'initiale).

Dans le même temps, nous rechercherons (sélectionnerons) des chemins candidats dans 4 directions:

  1. Rechercher des chemins candidats pour tous les chemins NB internes du graphique B à partir de PathsB, c'est-à-dire ceux dont les deux sommets limites sont connectés dans le graphe B avec au moins 2 autres sommets (quelle que soit la direction d'une telle connexion) et en même temps ce chemin n'est pas un cycle simple (orienté - pour les graphes orientés).
  2. Recherchez les chemins candidats pour les chemins NB de fin à partir de PathsB.
  3. Recherche de chemins candidats pour les chemins NB - boucles simples de PathsB.
  4. Recherche de chemins candidats pour les chemins NB - chemins simples à partir de PathsB.

Lors de la sélection de chemins candidats pour chaque ième chemin dans PathsB, ils sont comparés (c'est là que certains des paramètres de limiteur précédemment calculés sont utiles):

  • sa longueur et la longueur du chemin candidat (devrait être égale pour les cas 1 et 3, et pour les cas 2 et 4 le chemin candidat de PathsA peut également être plus long),
  • degrés de ses sommets limites et des sommets correspondants du chemin candidat (pour les sommets du chemin candidat, ces valeurs doivent être au moins le chemin de PathsB).

Si, selon les résultats de l'étape II, aucun chemin candidat de PathsA n'a été trouvé pour l'un des chemins de PathsB, alors on considère que A ne contient pas de sous-graphiques «inscrits» isomorphes à la colonne B.

Amincissement


Essayons maintenant de «presser» le graphique A. Nous n'y laissons que les bords qui sont entrés dans les chemins candidats que nous avons trouvés. Si en même temps, le graphe A a perdu au moins une arête par rapport à son état initial, alors nous revenons à l'étape I «Prétraitement»: les degrés des sommets du graphe A et, par conséquent, la liste des chemins candidats peuvent être réduits et, par conséquent, l'espace de recherche peut être réduit.

Étape III. Amincissement de la liste des chemins candidats


Le but de cette étape est d'éliminer davantage de candidats inappropriés. Pour ce faire, nous effectuons les étapes suivantes.

  1. L'exclusion de chemins candidats manifestement inappropriés sur la base des distances minimales entre les sommets de la colonne B. Le chemin candidat pour chaque chemin B [i] pour lequel au moins un chemin B [j] aucun chemin candidat n'a été trouvé pour le plus court la distance entre leurs sommets limites dans la colonne A était inférieure ou égale à la distance la plus courte entre les sommets limites correspondants des chemins PathsB [i] et PathsB [j] du graphique B.
  2. Une exception pour tous les cycles de PathsB aux chemins candidats non cycliques qui lui sont associés et vice versa.
  3. L'exception des chemins candidats similaires à la section 1, mais pas par le critère de la distance la plus courte entre les sommets frontières, mais par leurs (sommets frontières) à l'égalité ou l'inégalité mutuelle.

Par exemple, si:

  • l'élément de départ de PathsB [i] n'est pas égal à l'élément de départ de PathsB [j], et
  • l'élément final de PathsB [i] n'est pas égal à l'élément final de PathsB [j], et
  • l'élément de départ de PathsB [i] est égal à l'élément de fin de PathsB [j], et
  • l'élément de départ de PathsB [j] n'est pas égal à l'élément de fin de PathsB [i],

le chemin candidat le long du chemin PathsB [i] pour lequel au moins un chemin PathsB [j] aucun chemin candidat satisfaisant à la condition ci-dessus concernant l'égalité / l'inégalité de leurs (chemins candidats) initial et final, respectivement, est sujet à exclusion pics.

Autrement dit, nous éliminons les chemins candidats qui ne seront évidemment pas inclus dans les sous-graphiques souhaités - en fonction de la distance à tous les autres chemins candidats (ces chemins sont terriblement éloignés de tous les autres), en fonction de leur cyclicité / non-cyclicité, et également basé sur l'égalité / l'inégalité due de leurs sommets limites avec les sommets limites d'autres chemins candidats.

Si, selon les résultats de l'étape III, au moins 1 chemin candidat a été supprimé de PathsA, alors - encore une fois - la colonne A est mise à jour - seuls les bords qui sont inclus dans les chemins candidats restants y restent. Et, encore une fois, si en même temps, le graphique A «perd du poids» par au moins un bord, nous revenons à l'étape I «Prétraitement»: les degrés des sommets du graphique A et, par conséquent, la liste des chemins candidats peuvent être réduits et, par conséquent, peuvent être réduits espace de recherche.

Étape IV. Conclusion


Chaque combinaison possible de tous les chemins candidats restants définit un sous-graphique de la colonne A. Pour chacun de ces sous-graphiques, une matrice d'adjacence est construite en tenant compte de l'ordre des chemins candidats de la même manière que la matrice d'adjacence B00 a été construite pour le graphique B, puis ces matrices d'adjacence sont comparées.

S'ils sont égaux, les multiplicités des bords sont comparées (voir la section 3 du prétraitement de l'étape I). Si toutes ces conditions sont remplies, le sous-graphique trouvé est considéré comme isomorphe au graphique B et est ajouté à l'ensemble des résultats trouvés.

Au cours de l'étape IV «Conclusion», diverses vérifications supplémentaires peuvent être utilisées pour accélérer l'identification et le rejet d'un sous-graphique inapproprié.

5. Comment tout est confus ... Considérons un exemple d'algorithme


Je ne sais pas pour vous, mais ce serait incompréhensible pour moi sans exemple. Regardons un exemple.

En figue. les graphiques ci-dessous sont A = {1-> 2, 2-> 5, 5-> 15, 16-> 15, 5-> 5, 5-> 5, 5-> 4, 5-> 6, 7-> 6 , 6-> 8, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 0-> 12, 4-> 13, 13-> 14, 14-> 4 } et B = {1-> 1, 4-> 5, 5-> 1, 1-> 3, 3-> 3, 3-> 2, 2-> 7, 2-> 8, 9-> 10, 10-> 9, 1-> 6, 6-> 11, 11-> 12, 12-> 6}. Notre tâche consiste à trouver dans le graphique A tous les sous-graphiques «inscrits» isomorphes au graphique B. Le résultat est également illustré dans la figure: les sommets et bords trouvés du graphique A sont mis en évidence par une ligne épaisse, et les numéros des sommets correspondants du graphique B sont indiqués entre parenthèses (s'il existe plusieurs options, elles sont indiquées par fraction).

image

Lors de la résolution du problème de recherche dans la colonne A des sous-graphes «inscrits» isomorphes à la colonne B,nous avons les résultats suivants de l'algorithme.

Étape I: Toutes les actions et tous les calculs ont été effectués selon p.p. 1-5 de cette étape, voici les PathsA et PathsB résultants.

Chemins A:

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

Chemins B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

étapes II-III. La comparaison a montré que pour chaque chemin de PathsA, il y a au moins un chemin candidat de PathsB, et PathsA a été raccourci par les résultats de l'éclaircissage préliminaire. Au stade de l'amincissement principal (III), aucune réduction supplémentaire de PathsA ne s'est produite. En conséquence, PathsA et PathsB ont pris la forme:

PathsA:

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

Chemins B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

La comparaison finale des NPaths est la suivante:
NPaths:

i = 0: 3 0 2
i = 1: 4 0 2
i = 2: 2 0 2
i = 3: 7 0 2 8 0 2
i = 4: 7 0 2 8 0 2
i = 5: 6 0 2
i = 6: 5 0 2
i = 7: 0 0 3
i = 8: 1 0 4
i = 9: 9 0 3

Voici le temps de rappeler que chaque triplet ordonné de nombres dans NPaths [i] définit les Chemins correspondants B [i] chemin candidat de A dans le format: le numéro du chemin correspondant de PathsA - la position de départ du segment de ce chemin - la longueur du segment. Ainsi, il est facile de vérifier que les cheminsB [0] = {1-> 1} (i = 0: 3 0 2) correspondent à un seul chemin de A, à savoir le segment de PathsA [3] à partir du tout début et ayant une longueur de 2.

Stade IV. En conséquence, un sous-graphique unique A1 a été trouvé dans la colonne A, isomorphe à B. A1 = {0-> 12, 1-> 2, 2-> 5, 4-> 13, 5-> 4, 5-> 5, 5- > 6, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 13-> 14, 14-> 4}.

5. Et ensuite?


Et puis, en principe, c'est tout. Bien que pas tout à fait: l'auteur doit admettre que l'algorithme peut encore être finalisé et finalisé. Qu'y at-il à ajouter?

  1. Lorsque des caractéristiques supplémentaires des sommets des colonnes A et B sont introduites (par exemple, lorsque les composés sont donnés par les graphiques des composés chimiques, un code numérique correspondant à un et un seul atome (isotope) peut être associé à chaque sommet), le processus de recherche peut être accéléré en raison de la plus grande précision des comparaisons selon l'étape II: supplémentaire la condition de sélection des chemins candidats sera la correspondance des étiquettes de vertex.
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


Général sur les problèmes:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. Un algorithme d'isomorphisme sous-graphique et son application aux données biochimiques. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13 .
2. Cordella L, Foggia P, Sansone C, Vento M: un algorithme d'isomorphisme (sous) graphique pour faire correspondre de grands graphiques. Transactions IEEE sur l'analyse de modèles et l'intelligence artificielle. 2004, 26 (10): 1367-1372. 10.1109 / TPAMI.2004.75.
3. Ullmann Julian R.: Un algorithme pour l'isomorphisme sous-graphique. Journal de l'Association for Computing Machinery. 1976, 23: 31-42. 10.1145 / 321921.321925.
4. Ullmann Julian R.: Algorithmes à vecteur de bits pour la satisfaction des contraintes binaires et l'isomorphisme sous-graphique. J Exp Algorithmics. 2011, 15 (1.6): 1.1-1.6. 1,64

La prépublication de l'auteur écrite dans une langue plus officielle à ce sujet est l'algorithme le plus basé sur NB-Paths, qui contient également des informations sur une tentative de l'implémenter en C ++:
5. Chernoukhov SA 2020. Preprints.RU. Vérification de l'isomorphisme de deux graphes et recherche de sous-graphes isomorphes "inscrits": une approche basée sur l'analyse de l'approche des chemins non ramifiés à extension maximale pour résoudre le problème d'isomorphisme (sous) graphe. DOI: dx.doi.org/10.24108/preprints-3111977

Sources Internet utiles sur le sujet:
6. coderoad.ru/17480142/Is-li- exemple-simple-pour-explication-algorithme-Ulman
7. issue.life/questions / 8176298 .

More articles:


All Articles