SimpleGraph: Traversing Graph

Please post bug reports, feature requests, or any question regarding the DELPHI AREA projects here.

According to the topic, what is your preferred solution?

Solution 1: Two Lists
0
Solution 2: One List
2
67%
Solution 3: Three Lists
1
33%
Solution 4: No List
0

SimpleGraph: Traversing Graph

Description:
Some objects on the graph are connected to some links, or connected to some other objects using links.

We are looking for a solution to:
• Speed up traversing connected objects.
• Doesn't have much overload for developers, who do not need to traverse graph.
Suggested Solutions:
1. Having two properties for each object to list its input and output links.
This solution is suggested by Adem. This solution offers the fasted way to traverse connected objects.
2. Having only one property for each object to list all its dependent objects.
The base object class (TGraphObject) has some mechanism, which derived classes can use to make their instances dependent to the other objects. In this case, when placement of an object changes, all dependent objects will be notified to adjust their position too. The GraphLink class is such a class.
Now, we can use these option to have a public property for each object to tell us which objects are dependent to this object, and use it for traversing the graph. Of course, the developer should check for proper object type, and use source and target properties of the link to determine direction of the link.
3. Having three properties for each object to list all its dependent objects, and also its input and output links.
This is combination of first and second solution, which is much more flexible than the others, and of course costs more.
4. Do not provide any new porperty for this purpose.
The developer is responsible to use provided events and Tag property of the object to impelement his/her own mechanism to traverse the graph.
Which solution do you prefer?
Kambiz

Kambiz

Posts: 2430
Joined: March 7th, 2003, 7:10 pm

Re: SimpleGraph: Traversing Graph

Kambiz wrote:1. Having two properties for each object to list its input and output links. .... This solution offers the fasted way to traverse connected objects.

How can one deside if a link is input or output. The link objects know that (source vs. target) but should the nodes know that as well??

Kambiz wrote:2. Having only one property for each object to list all its dependent objects.
The base object class (TGraphObject) has some mechanism, which derived classes can use to make their instances dependent to the other objects. In this case, when placement of an object changes, all dependent objects will be notified to adjust their position too. The GraphLink class is such a class.

AFAIK, message proccesing is asynchronous. Say that I am adding and/or deleting objects programmaticaly. Should I expect events to be handled by already deleted objects? The proper managment will be a mightmare. Spreading activation control will destroy all the benefis. I prefer this solution (having one list for the links) but just that. Leave the management to the end user.

Kambiz wrote:3. Having three properties for each object to list all its dependent objects, and also its input and output links.

Rejected for including the 2nd one.

Kambiz wrote:4. Do not provide any new porperty for this purpose.
The developer is responsible to use provided events and Tag property of the object to impelement his/her own mechanism to traverse the graph.

I am already using the tag property to refer to external objects. Actually, I have turned that property from integer to TObject. So, I prefer to leave this property as it is and go for option 2 (define a list and leave as to do whatever we like - unless my understanding about events is wrong).

So, I vote for 2 as being more creative than 4.

Fotis

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

Re: SimpleGraph: Traversing Graph

Kambiz wrote:Description:
[*]Having only one property for each object to list all its dependent objects.
The base object class (TGraphObject) has some mechanism, which derived classes can use to make their instances dependent to the other objects. In this case, when placement of an object changes, all dependent objects will be notified to adjust their position too. The GraphLink class is such a class.
Now, we can use these option to have a public property for each object to tell us which objects are dependent to this object, and use it for traversing the graph. Of course, the developer should check for proper object type, and use source and target properties of the link to determine direction of the link.

From what I gather by looking at the sources, I have the impression that the only way each and every TGraphNode can have any relationship whith one another through a TGraphLink.

In other words, if I could have a list of 'TGraphLink's in each TGraphNode, I have basically all the information necessary --because TGraphLink also knows which 'TGraphNode's it is connected to, and the directionality of the relationship.

To make life simpler for the developer, I would suggest we use a sinle property, such as, 'Objects' which is a list. [For the purposes of speed during insertion and deletion, I'd go for a double-linked list, instead of Borland's screwed-up TList.]

What's more, this mechanism also speeds up messaging within TSimpleGraph because each and every node and link contains sufficient information about what other nodes to notify whan something happens (node deleted, moved or whatever).

Actually, a better variant of 'GraphLinks' property would be moving 'Objects' property to 'TGraphObject' (the base class). This would facilitate future expansion for TGraphLink; someone might come along and make TGraphLink connect to more than a pair of 'TGraphNode's. It is not such a wild idea when you really think about it.

So, with this relatively simple addition, TSimpleGraph becomes an even powerful component --and, I am not saying this to butter you up either
Active Member

Posts: 22
Joined: February 20th, 2006, 12:47 pm

Re: SimpleGraph: Traversing Graph

kokkoras wrote:
Kambiz wrote:1. Having two properties for each object to list its input and output links. .... This solution offers the fasted way to traverse connected objects.

How can one deside if a link is input or output. The link objects know that (source vs. target) but should the nodes know that as well??

Code: Select all
If GraphLink.Source = GraphObject then   GraphObject sees GraphLink as an output linkelse if GraphLink.Target = GraphObject then   GraphObject sees GraphLink as an input link

I think the third solution provides a better basment for future development of the control, without begin worry about backward compatibilities.
Kambiz

Kambiz

Posts: 2430
Joined: March 7th, 2003, 7:10 pm

Re: SimpleGraph: Traversing Graph

And how about links that have anchors on them? Then Adem's suggestion on where to define the property is better.

Is it possible on object deletion to have a behaviour like in the canClose Form? I would like to check various stuff in such an event handler and If everything is ok according to the logic of my app, to permit the deletion by settting canDeleteObject=true (in which case TSimpleGraph deletes the object) or prevent the deletion by setting canDeleteObject=false (in which case deletion is canceled).

Also, sending delete messages to the related objects puzzles me. Is it possible for an object to self destruct?? Deletion should be handled by the system, the way it is now.

fotis

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

Re: SimpleGraph: Traversing Graph

kokkoras wrote:Also, sending delete messages to the related objects puzzles me.

When I said sending notifications to objects, I meant this simple scenario:

Suppose a node or a link/node has been deleted by the application --the usual way.

In the Destructor of the link/node, it sends a notification to its 'Objects' so that those links/nodes remove the relationsip information from their own 'Objects' list.

This makes the whole thing nicely event-driven and not CPU intensive (i.e. it doesn't have to search through a long list of objects every time a node is deleted).

Similarly, when a node is moved, all it has to notify is those objects that it is linked to. Again, without going thru a long list. The GUI gets updated much faster.

kokkoras wrote:Is it possible on object deletion to have a behaviour like in the canClose Form?

I agree with what you're suggesting and there could be an event such as OnFreeObject(Sender: TObject; Reason: TSomeReasons; var Allowed: Boolean).

kokkoras wrote:Is it possible for an object to self destruct??

Of course, this is possible. It may or may not be desirable to implement such a functionality.

We all know when it is not desirable, but there is at least one case where it can be desirable: Avoiding orphaned objects.

I mean, imagine an application where the user deletes everthing that links to a given object --i.e. that object now becomes an orphan.

In this case, the object attempts to free itself --while notifying the app through OnFreeObject() event. If the app says yes, then the object object ould free itself.

kokkoras wrote:Deletion should be handled by the system, the way it is now.

Sure, the app needs to be in control.

But, TGraphsObject.Objects (list) needs to be maintained by the component dynamically and in the background.
Active Member

Posts: 22
Joined: February 20th, 2006, 12:47 pm

Re: SimpleGraph: Traversing Graph

Adem wrote:In the Destructor of the link/node, it sends a notification to its 'Objects' so that those links/nodes remove the relationsip information from their own 'Objects' list.

that's nice!

Adem wrote:Similarly, when a node is moved, all it has to notify is those objects that it is linked to. Again, without going thru a long list. The GUI gets updated much faster.

I am not sure how seamlesly can this be integrated in to the current implementation.

Adem wrote:...Avoiding orphaned objects. I mean, imagine an application where the user deletes everthing that links to a given object --i.e. that object now becomes an orphan.

I can not see a reason why is this bad. My concern in for the case where I have many objects selected and issue a delete command. Is the order of deletion important? If deleted links should notify conected nodes and deleted nodes should notify connected links then there is a case of objects notifiying already deleted objects. That was my initial possition.

Regarding self-destruction, I have the impression (mainly from VCL help and common logic) that it is dengarous to call the destructor from within the object's methods.

Adem wrote:But, TGraphsObject.Objects (list) needs to be maintained by the component dynamically and in the background.

Sounds reasonable.

Fotis

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

Re: SimpleGraph: Traversing Graph

kokkoras wrote:
Adem wrote:Similarly, when a node is moved, all it has to notify is those objects that it is linked to. Again, without going thru a long list. The GUI gets updated much faster.

I am not sure how seamlesly can this be integrated in to the current implementation.

I don't see much difficulty in this. Except maybe a new state should be added to TGraphObjectState, namely, say, 'osResizing' so that there will not be any circular referencing between resizing and resized objects. Anything other that this could be transparent to the app developer.

kokkoras wrote:
Adem wrote:...Avoiding orphaned objects. I mean, imagine an application where the user deletes everthing that links to a given object --i.e. that object now becomes an orphan.

I can not see a reason why is this bad.

Well, there is this case: The initial case when you place an object on the form, for the first time (for that object). Technically, at that moment it is an orphan

And, unless you take measures against it, it will be wiped out there and then

So, my suggestion is this: TSimpleGraph should have a property (or option) such as OrphanRemoval: Boolean which is False by default.

And, if you're adding new objects, you set it to false first and then to true --if necessary. Or, BeginUpdate/EndUpdate blocks does just that (set it to false first and then to true --if necessary).

kokkoras wrote:My concern in for the case where I have many objects selected and issue a delete command. Is the order of deletion important? If deleted links should notify conected nodes and deleted nodes should notify connected links then there is a case of objects notifiying already deleted objects. That was my initial possition.

This is a non-issue I think. Because, the underlying design is very good --kudos to Kambiz--, if you look at TGraphObjectState you'll see that there is 'osDestroying' (much like TCompoents's csDestroying) that can be (and is) used for preventing recursive loops such as the one you mentioned.

kokkoras wrote:Regarding self-destruction, I have the impression (mainly from VCL help and common logic) that it is dengarous to call the destructor from within the object's methods.

Nope. It is done all over the place. There's just one catch: You should not do that in a way to cause recursion. And, that has already been taken care of by 'osDestroying' in TGraphObjectState.

IOW, there's nothing to worry.
Active Member

Posts: 22
Joined: February 20th, 2006, 12:47 pm

Re: SimpleGraph: Traversing Graph

Adem wrote:Well, there is this case: The initial case when you place an object on the form, for the first time (for that object). Technically, at that moment it is an orphan

And, unless you take measures against it, it will be wiped out there and then

Sorry, I can't quite follow you. Having orphans is important. Why being an orphan is bad? It's just a node with no links attached to it or a link object not connected to any node. You put it there and this affects no one else. You delete it and it just gets deleted without affecting other objects.

On the other hand, in any other operation that affects more objects, these are notified by proper events and behave as programmed.

Fotis

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

Re: SimpleGraph: Traversing Graph

kokkoras wrote:
Adem wrote:Well, there is this case: The initial case when you place an object on the form, for the first time (for that object). Technically, at that moment it is an orphan

And, unless you take measures against it, it will be wiped out there and then

Sorry, I can't quite follow you. Having orphans is important. Why being an orphan is bad? It's just a node with no links attached to it or a link object not connected to any node. You put it there and this affects no one else. You delete it and it just gets deleted without affecting other objects.

Let's look a little deeper into it. As you said, an orphan is an TGraphObject that is not attached to any other TGraphObject (IOW, it could be a node or a link).

Now, how do we find out when an object has become an orphan? There are basically 2 ways:

1) The TGraphObject itself decides that it has become an orphan the moment its Objects list becomes empty.

2) TSimpleGraph periodically (or when an object has been removed) goes through its Objects list and determines that a (number of) objects have become orphan(s).

We're not talking about the second case, because it is doing it the [wr/l]ong way. So, lets look at case #1 again.

If the TGraphObject is to decide to free itself as soon as its Objects list is empty, we have a singularity: The TGraphObject starts life with its Objects list empty [BTW, this is is the case being an orphan is <b>not</b> a bad thing], and because Objects list is empty, it means TGraphObject will self-destruct at the moment of creation. We dont want that.

There are 2 solutions to this, that I think could be used:

1) We can have OrphanRemoval: Boolean as a property (default False) for TGraphObject to prevent this sort of thing, but we need to set and reset it or every object. This takes too long.

A better soution would be to have that OrphanRemoval: Boolean, and if it is True, orphaned TGraphObject frees itself.

Now that I think about it, this is not a very good solution, because, for the duration that OrphanRemoval is False, we have no information which ones have been orphaned --we still have to go through TSimpleGraph's Object list. There is a better soution that works the way we would prefer.

2) TSimpleGraph has another internal list Orphans in which each TGraphObject (that has become an orphan) registers itself. And, if TSimpleGraph.OrphanRemoval is True, orphans in that list gets to be freed automatically. Otherwise, the application handles the orphans in that list.

I'd go for the latter (case 2). It is more elegant, and simple, IMHO.

[Actually, I could have written and tested all this in the time I wrote about it; but, your probing helped me to clarify a few things that I would have had to try and correct]

kokkoras wrote:On the other hand, in any other operation that affects more objects, these are notified by proper events and behave as programmed.

Yes.
Active Member

Posts: 22
Joined: February 20th, 2006, 12:47 pm

.....If the TGraphObject is to decide to free itself as soon as its Objects list is empty.....

WHY?????????? Let it live. A single node on the camvas. What's wrong with it?????

I don't have always my nodes conected to somethig.

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

kokkoras wrote:.....If the TGraphObject is to decide to free itself as soon as its Objects list is empty.....

WHY?????????? Let it live. A single node on the camvas. What's wrong with it?????

You haven't read the whole post, have you --admittedly, it was a long post

The whole post was a recourse on how to let it live, and still have auto-orphan-removal functionality.

And, finally, I think I have solved it in a way that does not affect current functionality.
Active Member

Posts: 22
Joined: February 20th, 2006, 12:47 pm

kokkoras wrote:.....If the TGraphObject is to decide to free itself as soon as its Objects list is empty.....

WHY?????????? Let it live. A single node on the camvas. What's wrong with it?????

You haven't read the whole post, have you --admittedly, it was a long post

I did red it. But why all these overhead? A node is created. Who else gives a s.... about it? no one. A node is deleted: All the objects in the conected objects list are notified and remove the dead from their own list.

Am I missing something?

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

.....and still have auto-orphan-removal functionality.....

Honestly, why do we need this?? You tell me how to do it. Ok fine. But you don't answer why? Does it give any advantage or what?

kokkoras
Moderator

Posts: 317
Joined: March 12th, 2005, 11:19 pm
Location: Thessaloniki, Greece

kokkoras wrote:.....and still have auto-orphan-removal functionality.....

Honestly, why do we need this?? You tell me how to do it. Ok fine. But you don't answer why? Does it give any advantage or what?

I am sorry --while assuming you did not read my post, I simply overlooked the possibility that I might not read yours.

Let me try to explain why I think auto-orphan-removal option is a good option to have.

Think of a TSimpleGraph representing a live network (of servers, devices etc).

And suppose, all the links to one of those nodes gets turned off, or the nodes that link to that node are turned off.

As a developer, would you want to write code everytime you need to find out which node has been orphaned? Even if all you need to know is whether it is orphaned, and if yes, just to remove it from the graph.

Well, I wouldn't. I'd like that node to be automatically freed. In doing that I will get an OnFreeObject(Sender: TObject; Reason: TSomeReasons; var Allowed: Boolean) event whose 'Reason' parameter will tell me that it was orphaned.

OnFreeObject() will, then, be a good place to update my app (update or delete a record in a DB, or adjust node count in the GUI etc.)

Are you still not convinced?