Ricerca di sottografi ricorrenti

di
Alaskana
il
3 risposte
A
Alaskana
Pochi posts
Iscritto da
feb, 2019
Messaggi:
2

Ricerca di sottografi ricorrenti

Ciao a tutti,
Sto cercando di scrivere codice semplice in java per testare dei grafi diretti generati a random (in questo caso DAG) in cui trovare strutture identiche ricorrenti (quindi dei sottografi). So che un modo per identificare questi "patterns" è ad esempio usare la K-recurring substring ma il mio prof dice che ci sono altre tecniche note..che io non riesco a trovare.
Qualcuno può aiutarmi?

grazie

3 Risposte

  • Z
    Zartof
    Pochi posts
    Iscritto da
    mag, 2017
    Messaggi:
    10

    Re: Ricerca di sottografi ricorrenti

    Ciao Alaskana,
    non sono a conoscenza di altri algoritmi già affermati, ti dico solo quello che mi viene in mente di primo acchito:
    Se consideri le facce di un grafo (in un disegno planare chiaramente), puoi considerare le facce create da 3 nodi (e via via aumentando) e verificare se esistono esistono corrispondenze negli altri grafi. Fatto ciò puoi cominciare a creare sottografi (formati da facce adiacenti) e verificare ancora una volta se ci sono corrispondenze.
  • A
    Alaskana
    Pochi posts
    Iscritto da
    feb, 2019
    Messaggi:
    2

    Re: Ricerca di sottografi ricorrenti

    Grazie mille! In effetti poi facendo ulteriori ricerche di graph matching è venuto fuori un mondo...come l'algoritmo di ullmann etc...
    sono un pò complessi ma studiandone vari estratti poi si riesce a tirar fuori qualcosa
  • Z
    Zartof
    Pochi posts
    Iscritto da
    mag, 2017
    Messaggi:
    10

    Re: Ricerca di sottografi ricorrenti

    Perfetto! se posso chiedere, si tratta di un esercizio così fine a se stesso, o ha un impiego pratico questo cercare sottografi simili?
Devi accedere o registrarti per scrivere nel forum
3 risposte