Gibt es eine Möglichkeit, ein Grafikobjekt mit Knoten und Kanten zu speichern?

Question

Ich habe versucht, die Standard-Serialisierung Art Dinge verwenden, Sachen wie:

FileOutputStream f_out; 
try { 
    f_out = new FileOutputStream("MAOS.data"); 
    ObjectOutputStream obj_out = new ObjectOutputStream (f_out);  
    obj_out.writeObject(s); 
    obj_out.flush(); 
    obj_out.close(); 

} catch (FileNotFoundException e) { 
    // TODO Auto-generated catch block 
    e.printStackTrace(); 
} catch (IOException e) { 
    // TODO Auto-generated catch block 
    e.printStackTrace(); 
} ; 

Aber das Problem scheint zu sein, dass, wenn mein Objekt s jede Rekursion bei ALL I enthält einen Stapelüberlauf zu bekommen. Wenn s ein Graph ist, der Knoten und Kanten enthält (mit Knoten, die über Kanten wissen, um die Aktivierung zu verteilen, und Kanten, die aus demselben Grund Knoten kennen), dann stapeln sie einen Stapel. Wenn ich Kanten ganz herausnehme und nur Knoten habe, die wissen, über welche Knoten sie die Aktivierung auch verbreiten sollen, passiert das Gleiche! Ich kann sogar versuchen, die ArrayList der Knoten zu speichern, die der Graph kennt, und der Stapel läuft wieder über!

Ich bin so frustriert!

Graphen sind nicht gerade seltsam und mysteriös, sicherlich wollte jemand einen vor mir retten. Ich sehe etwas über das Speichern von ihnen als XML-Dateien hier ... aber wenn mein Problem die Rekursivität ist, würde ich immer noch die gleichen Probleme haben, selbst wenn ich es anders gespeichert habe? Ich kann mir einfach nicht vorstellen, wie man eine Grafik machen kann, ohne dass es Verbindungen gibt!

Mache ich nur Dinge falsch, oder ist diese Objektserialisierung weniger stark als ich dachte? Oder muss ich die Idee, ein Diagramm zu speichern, einfach aufgeben?

-Jenny

bearbeiten, Teil des riesigen Stack-Trace:

Exception in thread "main" java.lang.StackOverflowError 
    at java.io.ObjectStreamClass.getPrimFieldValues(Unknown Source) 
    at java.io.ObjectOutputStream.defaultWriteFields(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject(Unknown Source) 
    at java.util.ArrayList.writeObject(Unknown Source) 
    at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
    at java.lang.reflect.Method.invoke(Unknown Source) 
    at java.io.ObjectStreamClass.invokeWriteObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.defaultWriteFields(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject(Unknown Source) 
    at java.util.ArrayList.writeObject(Unknown Source) 
    at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
    at java.lang.reflect.Method.invoke(Unknown Source) 
    at java.io.ObjectStreamClass.invokeWriteObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.defaultWriteFields(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject(Unknown Source) 
    at java.util.ArrayList.writeObject(Unknown Source) 
    at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
    at java.lang.reflect.Method.invoke(Unknown Source) 
    at java.io.ObjectStreamClass.invokeWriteObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.defaultWriteFields(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 
    at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject0(Unknown Source) 
    at java.io.ObjectOutputStream.writeObject(Unknown Source) 
    at java.util.ArrayList.writeObject(Unknown Source) 
    at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
    at java.lang.reflect.Method.invoke(Unknown Source) 
    at java.io.ObjectStreamClass.invokeWriteObject(Unknown Source) 
    at java.io.ObjectOutputStream.writeSerialData(Unknown Source) 

Answer 1

ist diese Art von Strukturen am besten wie folgt gespeichert:

collection of nodes, each node has a unique ID 
collection of edges, each edge has two node IDs (or however many nodes an edge connects to) 

ohne jegliche Rekursion. Erstellen Sie beim Lesen der Knoten ein Wörterbuch mit Knoten, die nach ihrer ID indiziert sind. Verwenden Sie dann das Wörterbuch, um die Kanten beim Lesen zu korrigieren. Die IDs müssen nicht Teil der Laufzeitstruktur der Objekte sein, sie müssen nur innerhalb des Datenstroms eindeutig sein, wenn der Stream geschrieben/gelesen wird.

Answer 2

Hmmm. Eine Lösung wäre, es zu einer Java-Bean zu machen und XMLEncoder/XMLDecoder zu verwenden. Dies ist eine Lösung, die ich in der Vergangenheit verwendet habe, um Klassen zu speichern und zu laden.

Answer 3

Java-Serialisierung kann mit beliebigen Graphen umgehen (obwohl nicht unbedingt sehr effizient). Wahrscheinlich liegt das Problem bei einer benutzerdefinierten Implementierung von writeObject. Vielleicht könnte ein Abschnitt der Stapelverfolgung helfen.

Answer 4

Ein nützliches Serialisierungsformat man beachten sollte, ist JSON, wo Wörterbücher (wie von @Skizz vorgeschlagen) leicht vertreten:

A JSONObject ist eine ungeordnete Auflistung von Name/Wert-Paaren. Seine äußere Form ist eine Zeichenfolge, die in geschweifte Klammern mit Doppelpunkten zwischen den Namen und Werten und Kommata zwischen den Werten und Namen eingeschlossen ist. Das interne Formular ist ein Objekt mit den Methoden get() und opt() für den Zugriff auf die Werte nach Namen und put() -Methoden zum Hinzufügen oder Ersetzen von Werten nach Namen. Die Werte können folgende Typen sein: Boolean, JSONArray, JSONObject, Number und String oder das JSONObject.NULL-Objekt.

Answer 5

Sie könnten die Bibliothek JGraphT verwenden, die das Serialisieren von Grafiken in eine Textdatei mit dem ML-Format unterstützt. GraphMLExporter Javadoc.

Answer 6

Java-Serialisierung ist in der Lage, zyklische Referenzen zu behandeln (ich nehme an, das ist, was Sie mit Rekursion meinen), aber es ist ein bekanntes Problem mit großen Graphen, here beschrieben.

Lassen Sie sich vom Datum des Artikels nicht abschrecken, folgen Sie einfach der Kette von Kommentaren danach.

Es scheint, dass Sie eine andere Serialisierungstechnik verwenden müssen, um dies zu erreichen. Mehrere wurden erwähnt, und einige performance metrics geben JSON gute Noten.