Cyclic Graphs

[Tomi Maila]

In another thread Aristos Queue challenged us all to implement a cyclic graph in pure G. I open this new thread for discussing the (close to impossible) challenge.

QUOTE(Aristos Queue @ Aug 29 2007, 07:24 AM)

Now, my next challenge to everyone...

Do any of you recall me posting http://Anyone-have-a-DLL-with-a-function-to-dereference-memory-addresses-t8684.html' target="_blank">this request for a hack? The suggestion to use MoveBlock is an excellent one. You'll need that in order to complete the next challenge...

Write a VI Hierarchy to implement an arbitrary cyclic graph in pure G. To VIs not in the Graph.lvclass hierarchy, the graph objects should be perfect dataflow -- if you fork the wire, the entire graph replicates. The exposed API should allow you to create a connection between arbitrary nodes in the graph, including the creation of cycles. Inside the class, you may do many dataflow unsafe activities, far worse than the moment to moment crimes of the Map.

I have no idea if this is even possible. This is what we call "research." It's what I spend my spare time on. :-) Good night, and good luck.

[Jim Kring]

Hmmm, so we can take a hierarchical, by value object tree and cause objects to refer to each other by value...? That sounds both exciting and scary (if I'm understanding what AQ is asking us to try to do). I think that we will need to use MoveBlock in order to get an exact duplicate (handles/pointers and all -- similar to a hard link in Unix file system, I guess) to some graph node and then use SwapValue to insert that hard linked object into the graph (as one of the adjacent nodes some node). But how do we get the memory address of an object (since MoveBlock will only be used for getting a hard-link duplicate of the object)?

Am I off base here or am I heading in the right direction?

[Tomi Maila]

Just a thought experiment. What happens when you branch a wire that contains a cyclic graph? Wouldn't LabVIEW find itself in an infinite loop of copying the loop. We would need a copy-constructor to avoid this scenario. If you try to avoid this problem and implement a cyclic graph by storing the cyclic reference not by value but as some other sort of reference you end up into another problem. In this case when you branch a wire, LabVIEW doesn't understand that it needs to update the reference to refer to the new tree. To avoid this problem you would also need a copy constructor. One can create cyclic data structures with queues. The simplest example would be to enqueue the queue reference itself. But this is no longer a by value structure and once again, when you branch a wire, you don't get a by-value copy, unless you'd have a copy constructor.

So my gut feeling is that you can create some sort of cyclic data structures in LabVIEW, even with LVOOP. But what you cannot do is to get them behave properly when you branch a wire. Unless ofcourse AQ would be so kind that he considers copy constructors an important issue and adds them to the language

Tomi

[robijn]

A by value object can never contain itself. As in a cyclic graph it is a requirement to (indirectly) point to itself, it is impossible to implement this.

Hacking with pointers is another story. But that's not clean programming.

Joris

[ragglefrock]

[Accidentally deleted this post while I was editing it, here we go again...]

Here's an example that does a Graph-type container in a very simplistic, data-flow safe manner. I'm not claiming it's elegant, but please let me know if it fails to fit any requirements. It's just an array of nodes, where each node contains data and links to other nodes. The links are really just indices into the overall array.

To add nodes, you just append them to (or insert them into) the array. You don't really delete nodes, you just delete the links to the node you're removing and flag its index as the first node to replace when adding a new node. If you want, you can empty out its memory by replacing it with a dummy item.

It all seems data-flow safe, though. If you branch the array wire, you get a copy of the graph. There's no real tricks involved. The downside I guess is that don't really reclaim memory when you delete objects. The array will never shrink in size. You could maybe look at Variant Property storage if you wanted to circumvent this limitation.

[LAVA 1.0 Content]

Not directly related to Aristos' challenge, but wanted to share a BLOG I read that contains quite a few entries related to graph theory:

• Amortized Complexity - a Tool for Graph Algorithms (among others)
  
• Graph Theory
  

The first link is the latest in a series of computational complexity posts that seem appropriate to the discussion...

Happy reading

EDIT: Also, this post on sorting Not Quite Basics: Sorting Algorithms

[robijn]

QUOTE(LV Punk @ Sep 4 2007, 08:15 PM)

• http://scienceblogs.com/goodmath/2007/09/amortized_complexity_a_tool_fo.php' target="_blank">Amortized Complexity - a Tool for Graph Algorithms (among others)
  

This article clearly demonstrates very clearly points to think about when optimizing your generic classes. If you spend time to keep things organized well, you can save time later. Same goes for the balanced tree. Because of the way a balanced tree is organized and the "unpredictable" item-insertion time, it is a bad choice if we need real-time behaviour. However it can be very efficient and good for many problems. It's just that every structure has its own strategy and its own benefits.

What I thought of while reading the article was, if we want to use objects in a real-time environment, we also need to think about cleaning up space after use. In by value semantics, object data space will in most cases be cleaned up when the VI execution has ended. If you have a complex data structure in there, you may first want to "clear" the object data yourself. The time needed to cleanup the data will then be spent right then, and not whenever LabVIEW feels like cleaning up. It would be nice to know more about when LabVIEW cleans up data of objects. Maybe AQ can shed some light on this ?

BTW, I think also for by ref semantics real-time behaviour is possible, even with ref counting and auto destruction. I don't like scavanging, it's too unpredictable for a t&m environment. Doing the destructor call and the cleanup actions immediately when a ref is released and the object becomes unused (i.e. use count decremented to zero) means you know where in the diagram cleanup time is needed (or might be needed).

Joris

[Aristos Queue]

QUOTE(robijn @ Sep 7 2007, 06:14 AM)

It would be nice to know more about when LabVIEW cleans up data of objects. Maybe AQ can shed some light on this ?

LV doesn't clean up objects ever. Just as it does not clean up arrays or strings. The terminals are allocated when the VI loads. The terminal values may be stomped on when the VI runs. When a VI closes, the terminal space is deallocated. See the online documentation for the Request Deallocation primitive (in the palettes since LV7.1 I think) for details.