Pattern Matching auf polymorphen Baum - Wie?



  • Hallo Leute,

    Ich habe schon mehrmals Pattern Matching auf polymorphen Baeumen gebraucht, z.B. im Parserbau. Meine bisherigen Loesungen gefallen mir nicht:

    • dynamic_cast auf jedem Element und allen Child-Elementen
    • Eine virtuelle .is(type) Funktion + Type Enum

    Beides ist weder sonderlich lesbar noch wartbar.

    Ich suche daher nach einer Loesung, das Konzept des Pattern Matchings irgendwie generisch zu kapseln. Hat vielleicht schon mal jemand von euch dasselbe Problem gehabt und einen Ansatz fuer mich?

    Gruessle,
    Der Kellerautomat



  • Graphisomorphie ist NP-vollstaendig, wie es bei Baeumen ausschaut, weiss ich nicht recht wenn die Reihenfolge von Kindknoten unerheblich sein soll.

    Ansonsten: tagged unions. Weiterhin gibt es die Moeglichkeit RTTI zu nutzen, bspw. typeid etc.



  • knivil schrieb:

    Graphisomorphie ist NP-vollstaendig

    Beweis?

    wie es bei Baeumen ausschaut, weiss ich nicht recht wenn die Reihenfolge von Kindknoten unerheblich sein soll.

    Lässt sich in linearer Zeit lösen.



  • Angenommen es gibt ein struct Token von dem mehrere Klassen abgeleitet sind:
    Wie wärs mit

    bool Token::isSameTokenType(const Token *t){
        return typeid(*this) == typeid(*t);
    }
    


  • Michael E. schrieb:

    knivil schrieb:

    Graphisomorphie ist NP-vollstaendig

    Beweis?

    Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete

    Lässt sich in linearer Zeit lösen.

    Lol Beweis? Lineare Zeit in Abhaengigkeit von was? Knoten, Kanten, Sternchen? ... Ich sag erstmal glaub ich nicht.

    Beispiel:

    a = [1 2 3 4 5 6 7]
    b = [3 1 5 6 7 2 4]
    

    Nummern bezeichnen deine Knoten die an einem Wurzelknoten haengen, b ist dein Pattern. Frage: Ist Menge b in a enthalten.



  • knivil schrieb:

    Michael E. schrieb:

    knivil schrieb:

    Graphisomorphie ist NP-vollstaendig

    Beweis?

    Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete

    Nett, dass du die vorherige Bemerkung entfernt hast. Nicht so nett, dass du das Problem von Graphisomorphie zu Subgraphisomorphie geändert hast. Für Graphisomorphie ist es nämlich nicht bekannt, ob es NP-vollständig ist (und es ist IMHO auch ziemlich unwahrscheinlich).

    Lässt sich in linearer Zeit lösen.

    Lol Beweis? Lineare Zeit in Abhaengigkeit von was? Knoten, Kanten, Sternchen? ... Ich sag erstmal glaub ich nicht.

    Na was wohl? Linear heißt bei Graphen linear in Knoten- und Kantenzahl. Da die bei Bäumen fast gleich sind, kannst du dir eins aussuchen.

    http://perso.ens-lyon.fr/eric.thierry/Graphes2010/marthe-bonamy.pdf



  • Graphisomorphie zu Subgraphisomorphie

    Und du hast den Kontext wohl vergessen ... Pattern matching.

    Na was wohl? Linear heißt bei Graphen linear in Knoten- und Kantenzahl. Da die bei Bäumen fast gleich sind, kannst du dir eins aussuchen.

    Das ist mir klar, aber ich wuerde das Pattern an sich auch mit einbeziehen, wie ich versucht habe im Beispiel darzulegen.



  • knivil schrieb:

    Graphisomorphie zu Subgraphisomorphie

    Und du hast den Kontext wohl vergessen ... Pattern matching.

    Nein, genauer gesagt hab ich mich noch nie mit Pattern Matching befasst und werde es auch jetzt nicht tun. Daher weiß ich auch nicht, ob wir hier nun Graph- oder Subgraphisomorphismus gebrauchen können. Ich bin lediglich auf deine Behauptung eingegangen, dass Graphisomorphie NP-vollständig sein soll. Wenn Graphisomorphie nicht das richtige Werkzeug für Pattern Matching ist, kannst du auch einfach zugeben, dass du ein "Sub-" vergessen hast.


Log in to reply