Skontrolujte, či je graf subgrafom iného grafu v mapegrafii, igraph

Chcem skontrolovať, či daný podgraf G jepodgraf iného väčšieho grafu G "pomocou igrafu. Upozorňujeme, že nejde o problém s izomorfizmom podgrafu, pretože chcem, aby bola odpoveď nepravdivá, ak je označenie niektorého z vrcholov alebo hrán odlišné. Chcem, aby bola odpoveď pravdivá iba vtedy, ak ak majú oba grafy rovnaké okrajové a vrcholové štítky a G je podgraf G ". Ako to dosiahnem v igraph? Vďaka.

odpovede:

Nie ste si istí, čo máte na mysli pod štítkami vrchol / hrana, aleVšimnite si, že algoritmus subisomorfizmu VF2 v igraphe podporuje farby vrcholu / okraja; dva vrcholy alebo hrany sa môžu zhodovať, ak sú ich farby rovnaké. Ak používate igraph od Pythonu, skontrolujte subisomorphic_vf2 metóda Graph trieda. Ak používate igraf z R, skontrolujte graph.subisomorphic.vf2 Funkcie. Obidve sú podporované igraph_subisomorphic_vf2 fungujú vo vrstve C.

aktualizovať: pretože máte reťazce ako štítky a niecelé čísla (ktoré by očakával algoritmus izomorfizmu VF2), musíte ich najprv skonvertovať na celočíselné indexy. V opačnom prípade by mal byť VF2 schopný robiť to, čo potrebujete. Príklad v rozhraní Pythonu v aplikácii igraph:

>>> g = Graph.Formula("A --> B --> C")
>>> g2 = Graph.Formula("A --> B")
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,1])
[[0, 1]]
>>> g.get_subisomorphisms_vf2(g2, color1=[0,1,2], color2=[0,2])
[]