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:
- The serialization of a marked object
'a'contains implicitly all objects
'a'has a reference to, directly s.t:
a.b = b, or indirectly s.t.:
a.c.b = bfor some object
This basically define specific storage entries to specific objects. I then have "container" type objects that:
- can be serialized similarly (in fact their are or can-be "marked")
- they don't serialize in their storage entries the "marked" objects (with direct reference): if
a.bare both marked,
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:
- the multi-entry saving can only works through direct connections in "container" objects, and
- there are situations with undefined behavior such as if two "marked" objects
'b'both have a reference to an unmarked object
'c'. In this case my system will stores
'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.
E should be serialized but not blue objects because they are not reachable from
B is serialized in its own entry (i.e. file) and the question is how to choose where to serialize objects
Some thinking on this example:
Cis only reachable from
A, so its should be attached to it
- to reach
E, it is necessary to pass by
Eshould be attached to
- what about
D? Because after serialization if
Bis loaded (and not
Dshould also be loaded but not
Dshould be serialized in
I added the tag
database because I think the answer might come from that fields, even if the question is not really.