Is there ANY way to save a graph object containing nodes and edges?

Question

I've tried using the standard serializing type things, stuff like:

 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();
} ;

But the problem seems to be that if my object s contains any recursion at ALL I get a stack overflow. If s is a graph that contains nodes and edges (with nodes knowing about edges for purposes of spreading activation, and edges knowing about nodes for the same reason) then it stack overflows. If I take edges out entirely, and just have nodes that know about which nodes they're supposed to spread activation too, the same thing happens! I can even just try to save the ArrayList of nodes that the graph knows about, and the stack overflows again!

I'm so frustrated!

Graphs aren't exactly strange and mysterious, surely SOMEONE has wanted to save one before me. I'm seeing something about saving them as XML files here...but if my problem is the recursiveness, wouldn't I still be having the same problems even if I saved it differently? I just can't think of how you could make a graph without there being connections!

Am I just doing things wrong, or is this object serialization less powerful than I thought? Or do I need to just abandon the idea of saving a graph?

-Jenny

Edit, part of the HUGE 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

Hmmm. One solution would be to make it into a java bean and use XMLEncoder/XMLDecoder. This is a solution I've used in the past to save and load classes.

Answer 2

Java serialisation can cope with arbitrary graphs (although not necessarily very efficiently). Probably the problem lies with a custom implementation of writeObject. Perhaps a section of stack trace might help.

Answer 3

These sort of structures are best saved like this:

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)

without using any recursion. On reading the nodes, create a dictionary of nodes indexed by their ID. Then use the dictionary to fix up the edges when they're read. The IDs do not need to be part of the objects' run time structure, they only need to be unique within the data stream when the stream is written/read.

Skizz

Answer 4

A useful serialization format you should consider is JSON, where dictionaries (as suggested by @Skizz) are easily represented:

A JSONObject is an unordered collection of name/value pairs. Its external form is a string wrapped in curly braces with colons between the names and values, and commas between the values and names. The internal form is an object having get() and opt() methods for accessing the values by name, and put() methods for adding or replacing values by name. The values can be any of these types: Boolean, JSONArray, JSONObject, Number, and String, or the JSONObject.NULL object.

Answer 5

You could use the JGraphT library which supports serializing graphs into a text file with the ML format. GraphMLExporter Javadoc.

Answer 6

Java serialization is capable of handling cyclic references (I assume this is what you mean by recursion), but there is a known problem with large graphs that is described here.

Don't let the date of the article throw you off, just follow chain of comments after it.

It seems you will have to use another serialization technique to accomplish this. Several have been mentioned, and some performance metrics give JSON high marks.