Matching pattern nei grafici

Question

Sto cercando di trovare strumenti/algoritmo per la ricerca di sezioni che corrispondono al modello specificato nel grafico orientato, ad esempio:

A-> b-> c o o a <-> b-> c

Per favore, suggerisce la direzione delle mie ricerche.

Intendo la corrispondenza del pattern. Ho bisogno di trovare tutti i gruppi di nodi e bordi, che corrispondono al modello specificato

Answer 1

Non è questo il Problema di isomorfismo del sottografo? Se sì, la pagina Wikipedia contiene una sezione sugli algoritmi.

Answer 2

La corrispondenza del modello grafico è la funzionalità al centro di Strumenti di riscrittura del grafico, lo offrono pre-implementati.

In EG GRGEN scrivi il tuo modello di esempio come a: a -> b:> c: c, lo strumento genera quindi un matcher di pattern per esso, uno adattato alle caratteristiche del grafico host (ottimizzato da tenendo conto delle statistiche sul grafico).

Answer 3

Per quanto riguarda le possibili librerie puoi trovare una risposta qui Python Graph Library.

Per quanto riguarda la corrispondenza del pattern, se conosci il modello che stai cercando, devi solo attraversare il grafico e confrontare i percorsi o puoi usare una funzione per recuperare un percorso tra i nodi e verificare se il modello esiste.