SimpleGraph: Traversing Graph

[kokkoras]

OK, I see. But now listen to my story

I am visualizing conceptual graphs (CGs) (a kind of semantic networks used for knowledge representation). CGs contail concepts (rectangles) and relations (ovals). These can be connected with arrows (links) but it is possible to have free concepts. For example, the concept [student] means that there is an entity called student. [student: #Fotis] is an individual who is student. The CG: [Cat]->(on)->[Mat] says that some cat is on the mat. When I delete the relation (on) I want concepts [Cat] and [Mat] to stay on place. And the story goes like this. So, in my app, being able to have orphans is vital. Since I use TSimpleGraph for the visual part, It is clear that in my objects (concepts, relations, arrows, CGs) I use the kind of lists you requested for traversing my graphs, preventing deletion of objects, joining graphs, etc.

So, we have reached a point that personal requirements lead each one at different direction. In such cases the library either gets specialized by following one's requirements, or stays general enough (i.e. library) to satisfy both, at least in the base level.

I had understood that you had some reason for requesting something like this but you insisted on the iplementation issues without mentioning the reason. To be honest, I red your long post above very very quickly because I had understood your claims and I was trying to derive the reason.

For me, not allowing orphans is very application specific. TSimpleGraph is, more that anything else, a component for drawing graphs. Look at MSDraw, MSVision, Corel, etc. In all drawing apps, having an object laying on the canvas is common.

Anyway, I think the discussion was fruitful with reasonable input from both sides and Kambiz will judge with facts on how to go on.

Fotis

[Adem]

So, in my app, being able to have orphans is vital. Since I use TSimpleGraph for the visual part, It is clear that in my objects (concepts, relations, arrows, CGs) I use the kind of lists you requested for traversing my graphs, preventing deletion of objects, joining graphs, etc.

So, we have reached a point that personal requirements lead each one at different direction. In such cases the library either gets specialized by following one's requirements, or stays general enough (i.e. library) to satisfy both, at least in the base level.

I can see your worries now.

Actually, auto-orpan-removal is <b>not</b> my pre-requisite, it's a functionality that arises quite often; hence would be very useful to include in TSimpleGraph.

Secondly, 'auto-orpan-removal' is a bit of a misnomer, a better name would probably be 'auto-orpan-detection'. Meaning, orpaned objects notify the app when they become orphan. This is probably the most optimal solution.

Finally, 'auto-orpan-detection' would be a property option, it would not hinder your app in anyway.

And, who knows, you'd probably want to use it too. So, it's not an either or situation --i.e. it's not a case of your requirements clashing with mine. We'd be enriching TSimpleGraph without bloating or slowing it down.

[Adem]

I am visualizing conceptual graphs (CGs) (a kind of semantic networks used for knowledge representation). CGs contail concepts (rectangles) and relations (ovals). These can be connected with arrows (links) but it is possible to have free concepts. For example, the concept [student] means that there is an entity called student. [student: #Fotis] is an individual who is student. The CG: [Cat]->(on)->[Mat] says that some cat is on the mat. When I delete the relation (on) I want concepts [Cat] and [Mat] to stay on place. And the story goes like this. So, in my app, being able to have orphans is vital. Since I use TSimpleGraph for the visual part, It is clear that in my objects (concepts, relations, arrows, CGs) I use the kind of lists you requested for traversing my graphs, preventing deletion of objects, joining graphs, etc.

Interesting. I have a pet-project that's been going on for so many years. It's a linguistics sort of thing --morphological parser for agglutinable languages. While the name sounds like an academic project, this is purely to scratch my personal itch which is why it's never finished.

I have tried all sorts of things to help visualize the underlying structure --from TChart to Graphviz. TChart is good, but not for this sort of thing. Graphviz is good, but it's a pain to use with Delphi.

TSimpleGraph is the only candidate likely to be good enough all around.

I have one simple worry, though: I need an algorithm/method of relocating the nodes so that they dont overlap and that the most relevant nodes stay closer.

Do you know of such a thing?

[kokkoras]

I have one simple worry, though: I need an algorithm/method of relocating the nodes so that they dont overlap and that the most relevant nodes stay closer.
Do you know of such a thing?

Unfortunately, I don't. For the moment I have a very naive algorithm to auto locate the nodes on the camvas, for those cases I haven't placed the nodes myself. It works fine though for small graphs (<10 nodes). For hand located nodes, I currently store the positioning parameters in the knowledge base, but I plan to move them to a saved simpleGraph file since they have nothing to do with the knowledge base.

Regarding cats (and pets), the example is a common one used in the CG literature.

I also agree with the "orphan detection" nomeclature.

[Kambiz]

You are out of topic, aren't you?

Adem, I think you are more focused on your current case. SimpleGraph supposed to be a general purpose library and should kept generalized.

• Object Deletion:
  In the new release, there would be a new OnCanDelete event. This event is raised if Delete method of the object is called. Calling Free method of the object, releases the object without triggering the event.
  
• Auto Orphan Removal:
  Which object is an Orphan? A link not hooked to any node, a link not connecting two nodes, a node not connected to any link, or a node not connected to any node via a link?
  In my point of view, if somebody needs "Auto Orpan Removal", it's better to write his/her specific code in OnObjectRemove event. A more complex code is more difficult to maintain and improve.
  
• Tracking objects used as hook:
  In v2.0, when an object that is used as a hook is released, the interface doesn't release Unhook event. This bug will be fixed for the new release, and seems this bug is cause of some posts in this thread.
  
• Main Topic, Traversing Graph:
  Before creating this thread, already I was implemented "One List" solution. For the current implementation of the component it could be enough, but by extending the component, traversing the graph becomes a mess (I need this list to keep tracking dependencies).
  
  The "Two List" solution is only very good for traversing the graph and doesn't provide any aid for adding new features.
  
  Because I'm more interested to provide a generic graph component, and in the other hand there's only two votes, I go for "Three List" solution. Having two more list has some overloads, but provides much more flexibility. In the other hand, the overload is almost nothig for less than few thousnds objects on the graph. I don't think someone uses even more than a few hundreds objects on a graph.

For the new release I've added some new events, which may make your job much easier.

[elias]

Only two votes? here you have mine.
Only a few hundreds objects? I wouldn't be so sure.

[kokkoras]

I will be very happy with the features mentioned above (by Kambiz).

[Adem]

You are out of topic, aren't you?

There's always that odd chance that we weren't

Adem, I think you are more focused on your current case. SimpleGraph supposed to be a general purpose library and should kept generalized.

Actually, I don't have a current case per se. I was more like voicing the results of my frustration (results of the past decade) with various other components.

Object Deletion:
In the new release, there would be a new OnCanDelete event. This event is raised if Delete method of the object is called. Calling Free method of the object, releases the object without triggering the event.

This is good.

Auto Orphan Removal:
Which object is an Orphan? A link not hooked to any node, a link not connecting two nodes, a node not connected to any link, or a node not connected to any node via a link?
In my point of view, if somebody needs "Auto Orpan Removal", it's better to write his/her specific code in OnObjectRemove event. A more complex code is more difficult to maintain and improve.

By my definition, an orphan is an object that has no connection to another object --this definition covers, IMO, both the nodes and the links.

I have already given up on auto-orphan-removal, though. It is not worth the bother.

But, it would be nice if I could get a list of orphan objects through a single routine call.

Tracking objects used as hook:
In v2.0, when an object that is used as a hook is released, the interface doesn't release Unhook event. This bug will be fixed for the new release, and seems this bug is cause of some posts in this thread.

I am confused by this 'hook' metaphor. What is a hook??

Do you call a TGraphLink between any 2 TGraphNodes a hook. If not what is it?

Plus, why does the Source and Target be at the ends of Polyline.

I mean, I have no objections for the Polyline to be related (in some way) to Source and Target nodes, but IMHO Source and Target should be independent variables, and Polyline should adjust itself to what Source and Target are.

If this sentence sounds confused, it is because I am confused about all this Hook thing.

And, then, how can I do simple check like

function IsLinked(ASource, ATarget: TGraphNode): Boolean;

or, to find which nodes a given GraphLink connects:

procedure LinksNodes(ALink: TGraphLink; var ASource, ATarget: TGraphNode);

The "Two List" solution is only very good for traversing the graph and doesn't provide any aid for adding new features.

Mostly agreed.

Because I'm more interested to provide a generic graph component, and in the other hand there's only two votes, I go for "Three List" solution. Having two more list has some overloads, but provides much more flexibility.

I am fine with this.

In the other hand, the overload is almost nothig for less than few thousnds objects on the graph. I don't think someone uses even more than a few hundreds objects on a graph.

Well.. if you build <i><b>better mousetrap</b></i>, you'll be surprised to see how many <i><b>better mice</b></i> will flock in

For the new release I've added some new events, which may make your job much easier.

Thank you very much.

BTW, as I mentioned above, can you somehow separte the logic between the Polyline stuff and the nodes a TGraphLink connects to. For all I can see, PolyLine stuff is a special case of Line and that alone could make it something like TSomekindOfLine whose sole purpose is to draw a fancy line between 2 nodes.

[Kambiz]

I am confused by this 'hook' metaphor. What is a hook??

Do you call a TGraphLink between any 2 TGraphNodes a hook. If not what is it?

The name of link is confusing. I would rather to rename TGraphLink to TGraphLine or TGraphEdge but it's too late.

A hooked endpoint/startpoint is the endpoint/startpoint of a link, which is connected to an object (node or another link).

Plus, why does the Source and Target be at the ends of Polyline.

BTW, as I mentioned above, can you somehow separte the logic between the Polyline stuff and the nodes a TGraphLink connects to. For all I can see, PolyLine stuff is a special case of Line and that alone could make it something like TSomekindOfLine whose sole purpose is to draw a fancy line between 2 nodes.

This is the basic thing that I provided. Someone can subclass TGraphLink to have other kind of links. For example linkes with more than two connection points, or with curved/bezier lines.