NewsForumsCodeLogsGallerySpecsSearch

Cyclic Prevention...

BlitzMax Forums/BlitzMax Programming/Cyclic Prevention...

Arowx(Posted 2009) [#1]
OK so you need your code to create possibly complex object 'graphs', objects linked to other objects.

That's fine for linear or even basic branched structures, but how do you prevent it from going round in circles with cyclic links e.g.

ObjectA -> ObjectB -> ObjectA

Regards

Allan


ziggy(Posted 2009) [#2]
Design your logic to avoid this. There's not any fixed rule that fixes the issue automagically.
There's one possibility:
Method SecurePointTo(MyObj:TMyClass)
?debug
    Local Obj:TMyClass = MyObj
    Local Cycles:int = 0
    While Obj.Pointer<>null then
        If Obj.Pointer = self then
            throw "cycle found"
        End if
        Obj = Obj.Pointer
        Cycles:+1
        if cycles >=100000 then
            throw "too many branches. Process stoped for security"
        end if
    Wend
?
    self.Pointer = MyObj
End method

This is a security code that could work, for a certain type, suposing that the field Pointer is used to create the potentially cyclic dependencie.
Not the best code in the world, but it could be usefull while designing the object for a given application.
Not tested, as I'm not on my code machine right now. Just to give an idea!


Arowx(Posted 2009) [#3]
Hey cheers ziggy, so in my case if I just have a root Object and test to ensure I'm not continually cycling past it!


Czar Flavius(Posted 2009) [#4]
Are you avoiding this because of memory-leak concerns or program logic concerns?


Brucey(Posted 2009) [#5]
Design your logic to avoid this.

That is the key.

If you feel you must build cyclic relationships then you will need to ensure you can trap infinite recursions.


Warpy(Posted 2009) [#6]
A graph with no cycles in it is a tree. So, you need to make sure you're making a tree.

If you're joining "free" objects together, that is, objects that are not already linked to something else, there's no chance of a cycle occurring, clearly. This is also true if you're joining one linked object to a free object.

If you're joining two linked objects to each other, you need to check if they belong to the same tree. If they do belong to the same tree, a cycle will always arise, but if they do not belong to the same tree, a cycle will never arise.


I had this problem when I made my game "penpals". What I did was add a "root object" field, a "parent object" field, and a list of "children" for each object.
When an object is created, its root is itself and its parent is null.
When a free object O1 is linked to another object O2, its root is set to O2's root, O2 becomes O1's parent, and O1 is added to O2's list of children.

When an object which already has a parent is joined to another object which already has a parent, things get trickier. The first object's tree must be "reversed" by adding its old parent to its list of children, then recursively performing this operation on the old parent until you get to a parentless object. The object you want to join is now parentless and can be linked as before.

You can check out my code if you want at somethingorotherwhatever.com. In fact, this has inspired me to make a more simple example for you. I'll see if I can get that done tonight.


Warpy(Posted 2009) [#7]
PS by the way, if you need to check for cycles while traversing a graph you've already constructed, one method is to keep a list of all the nodes you've already been to. If you get to a node which is already on the list, you've got a cycle.


Arowx(Posted 2009) [#8]
Cheers everyone got it sorted!

@Warpy ended up using a record of the traversed object 'graph' using a map for quick lookup access!

My database reflector now works with Tlist and TMap as well as ObjectA -> ObjectB -> ObjectA cyclic objects!

Next it's off to tackle mister BLOBy!

@Brucey: Any progress or helpful insights into BLOB's and Sqlite thinking of using Banks but as it's a reflector not sure how that's going to pan out?


Brucey(Posted 2009) [#9]
Any progress or helpful insights into BLOB's and Sqlite

I'll have a look at implementing blobs tonight - it's the only data type that I've yet to do - which should be easy enough given that it's just raw data.


Arowx(Posted 2009) [#10]
@Brucey Excellent I've got to make lots more tests up and setup the framework to handle BLOB's!

I'm keen to share this with the community once it's at Beta and I have tidied up the code a bit, which is the best way to do that svn/googlecode?