[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Name that data structure!

bahuvrihi

12/22/2008 10:38:00 PM

I'm using a data structure that I'm sure has been implemented and
studied to death several times over... but I don't know it's name.
The structure is simple: any given node may have one or more previous
nodes. Nodes can be re-used, so you get structures like this:

o one
|
|-o two (fork of 1)
| |
`---o three (fork of 2)
| |
| | o four
| | |
| `-`-o five (merge of 3,4)
| |
`-----`-o six (merge of 2,5)

The whole thing is ordered in the sense that n-1 logically occurs
before n. Kinda reminiscent of git, but I'm using this as a kind of
audit of how values progress though an analysis.

Any ideas? Thanks.



17 Answers

Tom Cloyd

12/22/2008 11:08:00 PM

0

Simon Chiang wrote:
> I'm using a data structure that I'm sure has been implemented and
> studied to death several times over... but I don't know it's name.
> The structure is simple: any given node may have one or more previous
> nodes. Nodes can be re-used, so you get structures like this:
>
> o one
> |
> |-o two (fork of 1)
> | |
> `---o three (fork of 2)
> | |
> | | o four
> | | |
> | `-`-o five (merge of 3,4)
> | |
> `-----`-o six (merge of 2,5)
>
> The whole thing is ordered in the sense that n-1 logically occurs
> before n. Kinda reminiscent of git, but I'm using this as a kind of
> audit of how values progress though an analysis.
>
> Any ideas? Thanks.
>
>
>
>
>
Unless I totally don't get it...which just might be the case...my
current major Ruby project is something very much like this. However,
I'm only just learning about classes, though, and obviously am not much
of a programmer. I do have the design concept of this thing - which I'm
calling a node relationship database - very well in hand, and am very
excited about its potential. In many ways, it mimics the behavior of
neurons in the brain.

I referred to this project a short while back, in connection with a post
asking what the point of classes in general might be (got some great
answers). I exposed most of my code as it was at that point (and it has
considerable documentation in it), and no one remarked about it.

But...depending upon how interesting other people's responses to you
are, if you're interested I could share the code and see if what I'm
doing is where you're interested in going.

t.

--

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tom Cloyd, MS MA, LMHC - Private practice Psychotherapist
Bellingham, Washington, U.S.A: (360) 920-1226
<< tc@tomcloyd.com >> (email)
<< TomCloyd.com >> (website)
<< sleightmind.wordpress.com >> (mental health weblog)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Gregory Brown

12/22/2008 11:11:00 PM

0

On Mon, Dec 22, 2008 at 5:38 PM, Simon Chiang <simon.a.chiang@gmail.com> wrote:

> o one
> |
> |-o two (fork of 1)
> | |
> `---o three (fork of 2)
> | |
> | | o four
> | | |
> | `-`-o five (merge of 3,4)
> | |
> `-----`-o six (merge of 2,5)
>
> The whole thing is ordered in the sense that n-1 logically occurs
> before n. Kinda reminiscent of git, but I'm using this as a kind of
> audit of how values progress though an analysis.

Except for the ordering, it kind of sounds like a digraph.

http://en.wikipedia.org/wiki/Digraph_%28math...

-greg

--
Technical Blaag at: http://blog.majesticseacr...
Non-tech stuff at: http://metametta.bl...
"Ruby Best Practices" Book now in O'Reilly Roughcuts:
http://rubybestpra...

Gregory Seidman

12/22/2008 11:13:00 PM

0

On Tue, Dec 23, 2008 at 07:38:00AM +0900, Simon Chiang wrote:
> I'm using a data structure that I'm sure has been implemented and
> studied to death several times over... but I don't know it's name.
> The structure is simple: any given node may have one or more previous
> nodes. Nodes can be re-used, so you get structures like this:
>
> o one
> |
> |-o two (fork of 1)
> | |
> `---o three (fork of 2)
> | |
> | | o four
> | | |
> | `-`-o five (merge of 3,4)
> | |
> `-----`-o six (merge of 2,5)
>
> The whole thing is ordered in the sense that n-1 logically occurs
> before n. Kinda reminiscent of git, but I'm using this as a kind of
> audit of how values progress though an analysis.
>
> Any ideas? Thanks.

Unless there's something more complicated that I am missing, this is a
directed, acyclic graph, usually abbreviated as a DAG.

--Greg


Tom Cloyd

12/22/2008 11:23:00 PM

0

Gregory Brown wrote:
> On Mon, Dec 22, 2008 at 5:38 PM, Simon Chiang <simon.a.chiang@gmail.com> wrote:
>
>
>> o one
>> |
>> |-o two (fork of 1)
>> | |
>> `---o three (fork of 2)
>> | |
>> | | o four
>> | | |
>> | `-`-o five (merge of 3,4)
>> | |
>> `-----`-o six (merge of 2,5)
>>
>> The whole thing is ordered in the sense that n-1 logically occurs
>> before n. Kinda reminiscent of git, but I'm using this as a kind of
>> audit of how values progress though an analysis.
>>
>
> Except for the ordering, it kind of sounds like a digraph.
>
> http://en.wikipedia.org/wiki/Digraph_%28math...
>
> -greg
>
>
I believe a directed graph could be a fair match, but somehow it misses
the essence of it, which is that any node can connect to any other, and
more importantly that what it's connecting to can be a GROUP of nodes
rather than just one. This sort of thing is critical to the function of
brains.

More than that (if one wishes to sweeten the pot significantly) the
nature of the relationship is highly variable as well. In my model, it
can be anything - a quality, a number (on any sort of scaling), a
concept. This model has the potential for storing about anything.

I plan to use it for storing bibleographical references, Internet links.
databases of concepts, etc.

The structure is NOT inherent, but rather is emergent, as the database
is built. One can certainly input stuff according to a pre-conceived
form, and I plan on doing this some of the time, but that's just a
variation on the basic design.

It took me a few days of idle thought to realize the power of this
thing. It's far beyond relational database thinking, which, after all,
has constraints built in for good reason. But they come at a price.
And...brains don't work that way.

t.

--

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tom Cloyd, MS MA, LMHC - Private practice Psychotherapist
Bellingham, Washington, U.S.A: (360) 920-1226
<< tc@tomcloyd.com >> (email)
<< TomCloyd.com >> (website)
<< sleightmind.wordpress.com >> (mental health weblog)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Robert Dober

12/22/2008 11:55:00 PM

0

Sounds like a marked graph to me, and not directed at all, or did I
miss the arrows? That of course is a very general
thing, I therefore doubt that this statement is helpfull.
I do not understand with what you mean that a node can be connected to
a group of nodes?
Do you mean that if the nodes are e.g. lower case letters, there might
be an edge X in e(a,{b,c}) (X being the marking)
without implying that there is X in e(a,b) and X in e(a,c)?
If that is the case you still have just a general graph only that you
have to expand the nodeset to its powerset.

Cheers
Robert

--=20
Il computer non =E8 una macchina intelligente che aiuta le persone
stupide, anzi, =E8 una macchina stupida che funziona solo nelle mani
delle persone intelligenti.
Computers are not smart to help stupid people, rather they are stupid
and will work only if taken care of by smart people.

Umberto Eco

Tom Cloyd

12/23/2008 12:54:00 AM

0

Robert Dober wrote:
> Sounds like a marked graph to me, and not directed at all, or did I
> miss the arrows? That of course is a very general
> thing, I therefore doubt that this statement is helpfull.
> I do not understand with what you mean that a node can be connected to
> a group of nodes?
> Do you mean that if the nodes are e.g. lower case letters, there might
> be an edge X in e(a,{b,c}) (X being the marking)
> without implying that there is X in e(a,b) and X in e(a,c)?
> If that is the case you still have just a general graph only that you
> have to expand the nodeset to its powerset.
>
> Cheers
> Robert
>
>
Robert,

I apologize for my mathematical illiteracy. I don't understand your
question, because I don't understand your symbolic representation. Sorry.

So, allow me to explain it in terms I do understand - in the terms I'm
using to work out the problem as I program the solution. Please realize
that this may or may not well relate to the structure Simon's interested
in. I think it does, but that's for him to say. For me, it's a practical
problem in highly flexible information storage and retrieval, and a good
chance for me to advance my Ruby skills. Here's a fundamental
specification for the model I'm implementing:

* A "node" is a unit of information. It can be anything: a word, phrase,
number, equation, pointer to something else - anything. It's just
something that can be connected (related) in some way to another node.
* I indicate a node like this: .n {information}
* The node indication begins with the first character after the space
following node indicator, and ends when another indicator or an EOL/CR
is read,
* I indicate a relationship similarly: .r {information}

I now can specify node relationships. Some examples:

n Tom .r is a .n poor programmer
n apple r. is not .n bridge building material
n e=mc**2 .r could be .n true

Obviously, these aren't sentences, so we do not use articles,
conjunctions, and the like.

Simple enough. Now, consider this:

I start with a database of nodes, and of relationships - note that each
gets a unique ascension number:
n1 {}
n2 {}
n3 {}
...

r1 {}
r2 {}
...

When I specify a relationship with a node not in the database of nodes,
it gets inserted there; ditto for relationship types (NOT to be confused
with relationships - which are sets of two nodes linked with a
relationship of a given type).

Relationships ALSO go in a database, and each also gets a unique
ascension number.

Here's three complex relationships, each with its number (I preface
relationship ascension numbers with a lowercase L - for link):

l43 n1 and n2 and n3 .r are .n true
l44 n4 and n5 and n5 .r are .n not true
l45 l44 and l43 .r are .n true

The last one is the form of a line detector in the human eye, a simple
but vital element or our brain. That's not my interest, but I AM
interested in being able to build structures LIKE this, and I think this
sort of cascading complexity is what Simon is getting at. I think of it
as a sequential sparse matrix, but what do I know? I probably have that
all garbled, but the logic itself I'm sure of. This WILL work, though it
well may not be optimal in my specification of it. I'm simply trying to
follow the maxim of 'get it to work, first', then 'get it to work well,
later'.

So, I'll stop here, and wait for comment, if any.

t.

--

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tom Cloyd, MS MA, LMHC - Private practice Psychotherapist
Bellingham, Washington, U.S.A: (360) 920-1226
<< tc@tomcloyd.com >> (email)
<< TomCloyd.com >> (website)
<< sleightmind.wordpress.com >> (mental health weblog)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Tom Cloyd

12/23/2008 12:58:00 AM

0

Addendum:

This model encompasses directed graphs, and non-directed ones too (are
those call "marked" graphs? am not familiar with that term).

E.g.

n apple .r is a .n fruit <= a directed relationship; as specified it
only goes one way.
n fruit .r contains .n apple <= another directed relationship.
n apple .r is a / contains .n fruit <= a way of building a
bi-relational relationship. Starting at either end of the relationship,
you "read" the component of the relation specified which you first
encounter, up to the "/"

t.

bahuvrihi

12/23/2008 7:56:00 AM

0

> Unless there's something more complicated that I am missing, this is a directed, acyclic graph, usually abbreviated as a DAG.
>

Ah, great! I think that's it.

http://en.wikipedia.org/wiki/Directed_acy...

As a followup, does anyone know of libraries that work on DAGs? I'm
looking into the Ruby Graph Library, but any recommendations are
welcome.

http://rgl.rubyforge.org/rgl/...

Tom, your project sounds interesting but more involved than what I'm
working on. Thanks everyone!

Ian Hobson

12/23/2008 12:19:00 PM

0

Tom Cloyd wrote:
>
>
> I now can specify node relationships. Some examples:
>
> .n Tom .r is a .n poor programmer
> .n apple r. is not .n bridge building material
> .n e=mc**2 .r could be .n true
>
> Obviously, these aren't sentences, so we do not use articles,
> conjunctions, and the like.
>
Hi Tom,

What you have described is the associative model of data (storage).

Each association is three things
A subject
The association (almost verb, but more accurately copula) such as
"is a", "sells", "knows programming language" etc
An Object

The subject and object can be either entities (real things) or an
association. Thus

((Ian, isa Person), Drives, (Vehicle, RegNo, AB54CDE))

The great strength is the distinction between entity (e.g. people, legal
entities, cars), and their relationships (supplier, customer, drives etc).
An entity has a life span and could be destroyed. When it ceases to
exist all relationships into which it entered, become void.
Relationships usually have start and end times.

Another feature is the implied inverse of the relationship. If I drive a
car, that car is driven by me.

So instead of a computer system having a suppliers database, a customers
database and an employees database, it has a database containing "legal
entities" and "people" who may have "supplier", "employee" or "customer"
relationship with the company. (There should be no legal entities as
employees - that is a data error). Clearly a supplier or employee could
also be a customer, and it is not unknown for an employee to be an
occasional supplier for one-off items.

Most accounts departments spend a lot of time sorting out problems with
customers who are also suppliers. Now they are easy to handle.

Note the unusual nature of an address change. I and where I live are
entities, with a "lives at" relationship between them. To alter where I
live, the system must creates a new address and alters my "live at"
relationship (dated when I move).

See if you can get hold of a copy of "The associative model of data" by
Simon Williams (ISBN 1-903453-00-3). Lazy Software (William's company)
are the publishers and gave away copies many years ago for marketing
purposes. They may still have copies. It contains a very clear
explanation of the what and how, and describes a general purpose user
interface for editing such structures.

I have long felt a PIM based on these principles (with some form of
schema definition language on top), would be a very powerful and
flexible tool.

Regards

Ian




Klaus Stein

12/23/2008 1:10:00 PM

0

Simon Chiang <simon.a.chiang@gmail.com> wrote:
> As a followup, does anyone know of libraries that work on DAGs? I'm
> looking into the Ruby Graph Library, but any recommendations are
> welcome.
>
If you want to do rather sophisticated things have a look at RSRuby which
connects Ruby to R (I use this for graph analysis and partly for graph
visualization).

(Thanks to the others for telling me about RGL ;-) , which looks fine)

Klaus
--
http://lapiz...

The Answer is 42. And I am the Answer. Now I am looking for the Question.