Come serializzare una struttura grafica?

StackOverflow https://stackoverflow.com/questions/51783

  •  09-06-2019
  •  | 
  •  

Domanda

File flat e database relazionali ci forniscono un meccanismo per serializzare i dati strutturati.XML è eccellente per serializzare dati ad albero non strutturati.

Ma molti problemi sono meglio rappresentati dai grafici.Un programma di simulazione termica, ad esempio, funzionerà con nodi di temperatura collegati tra loro tramite bordi resistivi.

Allora qual è il modo migliore per serializzare una struttura grafica?So che XML può, in una certa misura, farlo, nello stesso modo in cui un database relazionale può serializzare una complessa rete di oggetti:di solito funziona ma può facilmente diventare brutto.

Conosco il linguaggio punto utilizzato dal programma graphviz, ma non sono sicuro che questo sia il modo migliore per farlo.Questa domanda è probabilmente il tipo di cosa su cui il mondo accademico potrebbe lavorare e mi piacerebbe avere riferimenti a qualsiasi articolo che ne parli.

È stato utile?

Soluzione

Come rappresenti il ​​tuo grafico in memoria?
Fondamentalmente hai due (buone) opzioni:

in cui la rappresentazione della lista di adiacenza è meglio utilizzata per un grafo sparso e una rappresentazione a matrice per i grafi densi.

Se utilizzassi tali rappresentazioni, potresti invece serializzarle.

Se deve essere leggibile dagli umani potresti comunque optare per la creazione del tuo algoritmo di serializzazione.Ad esempio potresti scrivere la rappresentazione della matrice come faresti con qualsiasi matrice "normale":basta stampare le colonne e le righe e tutti i dati in questo modo:

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

(questa è una rappresentazione non ottimizzata, non ponderata, ma può essere utilizzata per grafici orientati)

Altri suggerimenti

In genere le relazioni in XML vengono visualizzate dalla relazione genitore/figlio.XML può gestire i dati del grafico ma non in questo modo.Per gestire i grafici in XML dovresti usare il file xs:ID E xs:IDRIF tipi di schemi.

In un esempio, presupponiamo che node/@id sia un tipo xs:ID e che link/@ref sia un tipo xs:IDREF.Il seguente XML mostra il ciclo di tre nodi 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>

Molti strumenti di sviluppo supportano anche ID e IDREF.Ho utilizzato JAXB di Java (Java XML Binding.Li supporta attraverso il @XmlID e il @XmlIDREF annotazioni.Puoi costruire il tuo grafico utilizzando semplici oggetti Java e quindi utilizzare JAXB per gestire l'effettiva serializzazione in XML.

XML è molto dettagliato.Ogni volta che lo faccio, tiro il mio.Ecco un esempio di un grafico aciclico diretto a 3 nodi.È piuttosto compatto e fa tutto ciò di cui ho bisogno:

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

Un esempio che potresti conoscere è la serializzazione Java.Questo esegue effettivamente la serializzazione tramite grafico, in cui ogni istanza dell'oggetto è un nodo e ogni riferimento è un bordo.L'algoritmo utilizzato è ricorsivo, ma salta i duplicati.Quindi lo pseudocodice sarebbe:

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)

Un altro modo ovviamente è come un elenco di nodi e bordi, che può essere creato come XML, o in qualsiasi altro formato di serializzazione preferito, o come matrice di adiacenza.

Gli elenchi di adiacenza e le matrici di adiacenza sono i due modi comuni di rappresentare i grafici in memoria.La prima decisione che devi prendere quando decidi tra questi due è ciò per cui vuoi ottimizzare.Le liste di adiacenza sono molto veloci se hai bisogno, ad esempio, di ottenere la lista dei vicini di un vertice.D'altra parte, se stai eseguendo molti test sull'esistenza dei bordi o hai una rappresentazione grafica di una catena di Markov, probabilmente preferiresti una matrice di adiacenza.

La prossima domanda che devi considerare è quanto devi inserire nella memoria.Nella maggior parte dei casi, dove il numero di archi nel grafico è molto inferiore al numero totale di archi possibili, un elenco di adiacenze sarà più efficiente, poiché è necessario memorizzare solo gli archi effettivamente esistenti.Una via di mezzo è rappresentare la matrice di adiacenza in un formato di righe sparse compresse in cui si mantiene un vettore delle voci diverse da zero dall'alto a sinistra in basso a destra, un vettore corrispondente che indica in quali colonne si possono trovare le voci diverse da zero e un terzo vettore che indica l'inizio di ciascuna riga nel vettore di ingresso di colonna.

[[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]]

può essere rappresentato come:

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]

La riga sparsa compressa è effettivamente una lista di adiacenza (gli indici di colonna funzionano allo stesso modo), ma il formato si presta in modo un po' più pulito alle operazioni sulle matrici.

Su una nota meno accademica, più pratica, in CubicTest noi usiamo Xstream (Java) per serializzare i test da e verso xml.Xstream gestisce le relazioni tra oggetti strutturati a grafico, quindi potresti imparare una o due cose guardando la sua fonte e l'xml risultante.Hai ragione riguardo a brutto in parte, però, i file xml generati non hanno un bell'aspetto.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top