In Java oder einer anderen imperativen Programmierung kann ein Graph als matrix oder adjacent list dargestellt werden. Das adjacent list könnte am beliebtesten sein, weil es kompakt und praktisch ist, da es array verwendet.
In der funktionalen Programmierung verwenden wir normalerweise mutable array nicht. Dann wie normalerweise präsentieren wir eine Grafik in OCaml oder andere funktionale Programmierung?
Ersetzen Sie das Array durch map ?
In ocaml 99, graph gibt es vier Arten von Möglichkeiten:
Kantensatzformular
Eine Methode besteht darin, alle Kanten aufzulisten, wobei eine Kante ein Knotenpaar ist. In dieser Form wird der gegenüberliegende Graph als folgender Ausdruck dargestellt:
%Vor%Wir nennen dieses Randklauselformular. Offensichtlich können isolierte Knoten nicht dargestellt werden.
Diagrammform
Eine andere Methode besteht darin, den gesamten Graphen als ein Datenobjekt darzustellen. Gemäß der Definition des Graphen als ein Paar von zwei Mengen (Knoten und Kanten) können wir den folgenden OCaml-Typ verwenden:
%Vor%Dann wird der obige Beispielgraph dargestellt durch:
%Vor%Wir nennen diese Graph-Term-Form. Beachten Sie, dass die Listen sortiert bleiben, sie sind wirklich gesetzt, ohne doppelte Elemente. Jede Kante erscheint nur einmal in der Kantenliste; eine Kante von einem Knoten x zu einem anderen Knoten y wird als (x, y) dargestellt, das Paar (y, x) ist nicht vorhanden. Die Diagrammform ist unsere Standarddarstellung. Vielleicht möchten Sie einen ähnlichen Typ mit Sets anstelle von Listen definieren.
Adjazenzlistenformular
Eine dritte Darstellungsmethode besteht darin, jedem Knoten die Gruppe von Knoten zuzuordnen, die zu diesem Knoten benachbart sind. Wir nennen dies das Adjazenzlistenformular.
menschenfreundliche Form
Die bisher vorgestellten Darstellungen sind zwar gut für die automatisierte Verarbeitung geeignet, aber ihre Syntax ist nicht sehr benutzerfreundlich. Das manuelle Eingeben der Begriffe ist umständlich und fehleranfällig. Wir können eine kompaktere und "human-friendly" Notation wie folgt definieren: Ein Graph (mit char-markierten Knoten) wird durch eine Reihe von Atomen und Termen vom Typ X-Y dargestellt. Die Atome stehen für isolierte Knoten, die X-Y-Terme beschreiben Kanten. Wenn ein X als Endpunkt einer Kante angezeigt wird, wird es automatisch als Knoten definiert. Unser Beispiel könnte geschrieben werden als:
%Vor%Ich denke, dass keiner der obigen vier Wege in Anbetracht der Effizienz der Verarbeitung gut genug ist.
Für record type graph-term form gibt es keine effiziente Möglichkeit, einen Knoten zu finden ( O(n) immer) und eine Kante zu finden, die an einen Knoten angehängt ist.
Es gibt zwei Dinge zu beachten: Darstellung eines Graphen und Zwischendatenstrukturen, die in einigen Graphalgorithmen verwendet werden.
Ich denke, dass die Form der Adjazenzliste die speicherfreundlichste Art ist, Graphen darzustellen. Könnte etwas verbessert werden, indem man Bäume oder Karten vom Typ
hat %Vor%Aber wenn Sie einen Algorithmus wie "stark verbundene Komponenten" oder "topologische Sortierung" ausführen wollen, werden diese Algorithmen höchstwahrscheinlich veränderbare Arrays verwenden, um sie zu implementieren.
Beachten Sie, dass in Sprachen wie Haskell die ST-Monade es ermöglicht, temporär veränderbare Zustände, d. h. Arrays, zu haben, im Gegensatz zum globalen Zustand. Funktionen, die dies verwenden, sind immer noch rein.
In Imperativsprachen hängt die Wahl der Diagrammdarstellung von dem Problem ab, das Sie lösen möchten.
Dasselbe gilt für funktionale Sprachen.
Ocamlgraph bietet genug Abstraktion, um einen Algorithmus unabhängig von der zugrundeliegenden Graphendarstellung zu schreiben, obwohl natürlich die Laufzeit des Algorithmus immer noch von der Implementierung abhängt.
Tags und Links functional-programming ocaml