Wie serialisiere ich eine Diagrammstruktur?

Question

Flatfiles und relationale Datenbanken bieten uns einen Mechanismus zur Serialisierung strukturierter Daten.XML eignet sich hervorragend für die Serialisierung unstrukturierter baumartiger Daten.

Viele Probleme lassen sich jedoch am besten durch Grafiken darstellen.Ein thermisches Simulationsprogramm arbeitet beispielsweise mit Temperaturknoten, die über Widerstandskanten miteinander verbunden sind.

Was ist also der beste Weg, eine Diagrammstruktur zu serialisieren?Ich weiß, dass XML dies bis zu einem gewissen Grad kann – auf die gleiche Weise, wie eine relationale Datenbank ein komplexes Netz von Objekten serialisieren kann:Normalerweise funktioniert es, kann aber leicht hässlich werden.

Ich kenne die vom Programm graphviz verwendete Punktsprache, bin mir aber nicht sicher, ob dies der beste Weg ist.Diese Frage ist wahrscheinlich die Art von Frage, an der die Wissenschaft arbeiten könnte, und ich hätte gerne Verweise auf alle Artikel, die dies diskutieren.

Answer 1

Wie stellen Sie Ihr Diagramm im Gedächtnis dar?
Grundsätzlich haben Sie zwei (gute) Möglichkeiten:

• eine Adjazenzlistendarstellung
• eine Adjazenzmatrixdarstellung

wobei die Adjazenzlistendarstellung am besten für einen dünn besetzten Graphen und eine Matrixdarstellung für dichte Graphen verwendet wird.

Wenn Sie solche Darstellungen verwenden würden, könnten Sie diese Darstellungen stattdessen serialisieren.

Wenn es sein muss für Menschen lesbar Sie könnten sich dennoch dafür entscheiden, Ihren eigenen Serialisierungsalgorithmus zu erstellen.Sie könnten beispielsweise die Matrixdarstellung wie bei jeder „normalen“ Matrix aufschreiben:Drucken Sie einfach die Spalten und Zeilen sowie alle darin enthaltenen Daten aus:

   1  2  3
1 #t #f #f
2 #f #f #t
3 #f #t #f

(Dies ist eine nicht optimierte, nicht gewichtete Darstellung, kann aber für gerichtete Diagramme verwendet werden.)

Answer 2

Typischerweise werden Beziehungen in XML durch die Eltern-Kind-Beziehung dargestellt.XML kann Diagrammdaten verarbeiten, jedoch nicht auf diese Weise.Um Diagramme in XML zu verarbeiten, sollten Sie die verwenden xs:ID Und xs:IDREF Schematypen.

Nehmen Sie in einem Beispiel an, dass node/@id ein xs:ID-Typ und link/@ref ein xs:IDREF-Typ ist.Das folgende XML zeigt den Zyklus von drei Knoten 1 -> 2 -> 3 -> 1.

<data>
  <node id="1"> 
    <link ref="2"/>
  </node>
  <node id="2">
    <link ref="3"/>
  </node>
  <node id="3">
    <link ref="1"/>
  </node>
</data>

Viele Entwicklungstools unterstützen auch ID und IDREF.Ich habe Javas JAXB (Java XML Binding) verwendet.Es unterstützt diese durch die @XmlID und das @XmlIDREF Anmerkungen.Sie können Ihr Diagramm mit einfachen Java-Objekten erstellen und dann JAXB verwenden, um die eigentliche Serialisierung in XML durchzuführen.

Answer 3

XML ist sehr ausführlich.Wann immer ich es mache, rolle ich mein eigenes.Hier ist ein Beispiel für einen gerichteten azyklischen Graphen mit drei Knoten.Es ist ziemlich kompakt und macht alles, was ich brauche:

0: foo
1: bar
2: bat
----
0 1
0 2
1 2

Answer 4

Ein Beispiel, das Ihnen vielleicht bekannt ist, ist die Java-Serialisierung.Dies führt effektiv zu einer Serialisierung nach Diagramm, wobei jede Objektinstanz ein Knoten und jede Referenz eine Kante ist.Der verwendete Algorithmus ist rekursiv, überspringt jedoch Duplikate.Der Pseudocode wäre also:

serialize(x):
    done - a set of serialized objects
    if(serialized(x, done)) then return
    otherwise:
         record properties of x
         record x as serialized in done
         for each neighbour/child of x: serialize(child)

Eine andere Möglichkeit ist natürlich eine Liste von Knoten und Kanten, die als XML oder in einem anderen bevorzugten Serialisierungsformat oder als Adjazenzmatrix erstellt werden kann.

Answer 5

Adjazenzlisten und Adjazenzmatrizen sind die beiden gängigen Methoden zur Darstellung von Diagrammen im Speicher.Die erste Entscheidung, die Sie treffen müssen, wenn Sie sich zwischen diesen beiden entscheiden, ist, wofür Sie optimieren möchten.Adjazenzlisten sind sehr schnell, wenn Sie beispielsweise die Liste der Nachbarn eines Scheitelpunkts abrufen müssen.Wenn Sie andererseits viele Kantenexistenztests durchführen oder eine grafische Darstellung einer Markov-Kette haben, würden Sie wahrscheinlich eine Adjazenzmatrix bevorzugen.

Die nächste Frage, die Sie berücksichtigen müssen, ist, wie viel Sie in den Speicher unterbringen müssen.In den meisten Fällen, in denen die Anzahl der Kanten im Diagramm viel kleiner ist als die Gesamtzahl möglicher Kanten, ist eine Adjazenzliste effizienter, da Sie nur die tatsächlich vorhandenen Kanten speichern müssen.Ein guter Mittelweg besteht darin, die Adjazenzmatrix im komprimierten Sparse-Zeilenformat darzustellen, in dem Sie einen Vektor der Nicht-Null-Einträge von links oben nach unten rechts behalten, einen entsprechenden Vektor, der angibt, in welchen Spalten die Nicht-Null-Einträge zu finden sind, und ein dritter Vektor, der den Anfang jeder Zeile im Spalteneintragsvektor angibt.

[[0.0, 0.0, 0.3, 0.1]
 [0.1, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]
 [0.5, 0.2, 0.0, 0.3]]

kann dargestellt werden als:

vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3]
cols: [2,   3,   0,   0,   1,   4]
rows: [0,        2, null,  4]

Bei einer komprimierten Zeile mit geringer Dichte handelt es sich praktisch um eine Adjazenzliste (die Spaltenindizes funktionieren auf die gleiche Weise), aber das Format eignet sich etwas sauberer für Matrixoperationen.

Answer 6

Weniger akademisch, eher praktisch: in KubischerTest wir gebrauchen Xstream (Java) zum Serialisieren von Tests in und aus XML.Xstream verarbeitet diagrammstrukturierte Objektbeziehungen, sodass Sie vielleicht ein oder zwei Dinge lernen können, wenn Sie sich die Quelle und die resultierende XML-Datei ansehen.Da hast du recht hässlich Teilweise sehen die generierten XML-Dateien jedoch nicht schön aus.