4

My question is on the best way to cluster a graph of class instances around specifically marked objects (objects are the graph nodes and the references to each other are the directed edges of the graph). To better explain my question, let me explain my motivation:

I currently use a moderately complex system to serialize the data used in my projects:

  • "marked" objects have a specific attributes which stores a "saving entry": the path to an associated file on disc (but it could be done for any storage type providing the suitable interface)
  • Those object can then be serialized automatically (eg: obj.save())
  • The serialization of a marked object 'a' contains implicitly all objects 'b' for which 'a' has a reference to, directly s.t: a.b = b, or indirectly s.t.: a.c.b = b for some object 'c'

This basically define specific storage entries to specific objects. I then have "container" type objects that:

  1. can be serialized similarly (in fact their are or can-be "marked")
  2. they don't serialize in their storage entries the "marked" objects (with direct reference): if a and a.b are both marked, a.save() calls b.save() and stores a.b = storage_entry(b)

So, if I serialize 'a', it will serialize automatically all objects that can be reached from 'a' through the object reference graph, possibly in multiples entries. That is what I want, and it usually provides the functionalities I need. However, there are some structural limitations to this approach:

  1. the multi-entry saving can only works through direct connections in "container" objects, and
  2. there are situations with undefined behavior such as if two "marked" objects 'a'and 'b' both have a reference to an unmarked object 'c'. In this case my system will stores 'c' in both 'a' and 'b' making an implicit copy which not only double the storage size, but also change the object reference graph after re-loading.

I am thinking of generalizing the process. Apart for the practical questions on implementation (I am coding in python, and use Pickle to serialize my objects), there is a general question on the way to attach (cluster) unmarked objects to marked ones.

So, my questions are:

  • What are the important issues that should be considered? Basically why not just use any graph parsing algorithm with the "attach to last marked node" behavior.
  • Is there any work done on this problem, practical or theoretical, that I should be aware of?

Example of a simple object graph to serialize:

Circles are objects and arrow references. Orange circles are marked objects.

When serializing A, object B to E should be serialized but not blue objects because they are not reachable from A. Now, B is serialized in its own entry (i.e. file) and the question is how to choose where to serialize objects C to E, to A or B entry?

Some thinking on this example:

  • object C is only reachable from A, so its should be attached to it
  • to reach E, it is necessary to pass by B, so E should be attached to B
  • what about D? Because after serialization if B is loaded (and not A), D should also be loaded but not A. Thus D should be serialized in B entry.

Note: I added the tag database because I think the answer might come from that fields, even if the question is not really.

1

It looks like there's a missing conceptual step going on here. An object reference is not the object itself. So, perhaps consider serializing object references, and don't serialize object c inside a or b, for example. Serialize object c outside of them, and you save space and processing time.

Edit: Basically, it would work like this:

foreach(object reference in serializeable)
    serialize(object in global)
    serialize(object reference)

Then, when you deserialize, you just make the object reference point back to the correct object.

  • I am not sure to understand, I do want to serialize all objects reachable from a starting object. Eg: say we have a and b marked, and a.b=b, a.c=c and b.c=c. If I do a.save() then a, b and c should be serialized, a in a, b in b, and c in one (and only one) of them. So that if I later do load(entry_of_a) it retrieve everything. Now, I cannot serialize every objects (such as int, float, etc...) in separated entries, that would make too many of them. – Juh_ Aug 2 '13 at 17:14
  • That make me think: in the above example, if after saving a, I do load(entry_of_b), which is possible, I should get c in b.c. That is one of the constraint that need to be respected. The generalization is complicated..., and might not have a global solution. – Juh_ Aug 2 '13 at 17:18
  • 1
    Basically, instead of saving c inside a, you save c globally, then you save a reference to it inside a. Think of it like an address for a letter. The address is not the house, just helps find the house. – Zeroth Aug 2 '13 at 20:59
  • You set your deserializer to be able to remember that a has a reference to c and when the deserializer finds c, it sets a's reference to the newly reconstituted object. – Zeroth Aug 2 '13 at 21:02
  • What do you mean by saving c globally? In the case of file system, where would that be? [Note that marked objects are instance of self-made classes, and thus most of the content is stored in their attributes, i.e. in "sub-objects" c] – Juh_ Aug 3 '13 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.