Prev: Embedded external widget is not resized in tk frame
Next: EuroTcl 2010 : registration and abstract submission
From: Larry W. Virden on 15 Apr 2010 15:03
I have a set of data. This is a series of pairs of numbers. The first
represents an entity, and the second represents a relationship to
another entity.

For example:

1 0
2 0
3 1
4 2
5 0
6 5
7 6

and so forth.

There are over 1500 of these pairs.

I'm trying to figure out a method of determining the path from each
entity to 0. So for instance, as output for the above set I'd have
1 0
2 0
3 1 0
4 2 0
5 0
6 5 0
7 6 5 0

I'm trying to remember back to the dinosaur days when I was in school.
It seems like this is a sort of problem that I recall reading about,
but I don't recall the way to resolve it. Some sort of recursive look
up in an array is probably the best thing, given how small the data
is.

Anyone have any tips on approaches that would make this relatively
easy to do?

Thanks all.
From: Elchonon Edelson on 15 Apr 2010 16:06
Larry W. Virden wrote:
> I have a set of data. This is a series of pairs of numbers. The first
> represents an entity, and the second represents a relationship to
> another entity.
>
> For example:
>
> 1 0
> 2 0
> 3 1
> 4 2
> 5 0
> 6 5
> 7 6
>
> and so forth.
>
> There are over 1500 of these pairs.
>
> I'm trying to figure out a method of determining the path from each
> entity to 0. So for instance, as output for the above set I'd have
> 1 0
> 2 0
> 3 1 0
> 4 2 0
> 5 0
> 6 5 0
> 7 6 5 0
>
> I'm trying to remember back to the dinosaur days when I was in school.
> It seems like this is a sort of problem that I recall reading about,
> but I don't recall the way to resolve it. Some sort of recursive look
> up in an array is probably the best thing, given how small the data
> is.
>
> Anyone have any tips on approaches that would make this relatively
> easy to do?
>
> Thanks all.


You appear to be describing a tree. Or a directed graph. Do the
struct::tree or struct::graph modules in tcllib solve your problem?

--
Don't tell me the sky's the limit when there are footprints on the moon!
From: Shaun Deacon on 15 Apr 2010 16:20
Isn't this just a simple key/value array lookup ? Or am I missing
something ? ...

proc getPath {key} {
global data
set path $key
while { [info exists data($key)] } {
lappend path $data(key)
set key $data($key)
}
set path
}

set dataList {1 0 2 0 3 1 4 2 5 0 6 5 7 6}
foreach {entity ref} $dataList { set data($entity) $ref }

puts [getPath 4]
4 2 0
puts [getPath 7]
7 6 5 0

Shaun
From: Larry W. Virden on 16 Apr 2010 10:58
On Apr 15, 4:20 pm, Shaun Deacon <sdea...(a)fma.fujitsu.com> wrote:
> Isn't this just a simple key/value array lookup ? Or am I missing
> something ? ...

No, you are not missing anything. It was me, who apparently is getting
a lot older, a lot faster, than I knew.

Thanks!
 | 
Pages: 1
Prev: Embedded external widget is not resized in tk frame
Next: EuroTcl 2010 : registration and abstract submission