[Tutor] Re: data structure and algorithm

[Brad Reisfeld]

Hi,
Thank you for the response.

This is complicated so I'll try to clarify...

The application on which I am working has to do with chemical reactions. A
given 'generic' reaction (what I called a 'function') applied to a chemical
species (what I called a 'symbol'), can result in a number of products (what
I called 'a list of symbols'). If I apply a reaction to a different species,
I get a different set of products.

If I apply reaction 'f1' to species 'A', I get products 'B','C','D', and
'E'.
If I then apply a new reaction 'f2' to one of the products, 'B', I get
products 'F' and 'G'.
If I apply the same reaction 'f2' to another one of the products, 'C', I get
products 'H','I', and 'J'.
And so forth. I think that you can see that after a few of these reactions,
a very large 'tree' can be formed.
I'll attempt some ASCII art here for the simple example (I hope the spacing
is retained properly):

            --        --
            |         | F       --
            | B -f2-> |         | K
            |         | G -f3-> | L
            |         --        | B
            |                   | N
            |         --        --
   A -f1->  |         | H
		| C -f2-> | I
            |         | J
            |         --
            | D
            |
            | E
            --

So, I am looking at applying a reaction to a chemical species, and then a
different reaction to its products, and then a different reaction to its
products, and so forth. I am then trying to see all of the reaction 'chains'
(e.g. A --f1--> B --f2--> F).
Along the way, a product may be identical to a product in another reaction
from a completely different sequence of reactions, but I don't think that
loops can occur in such a system (I could be wrong).

Let me know if you would like more information. If I have confused you
further, I apologize.

Thanks.

-Brad



====================================================


On  0, Brad Reisfeld <brad.reisfeld@colostate.edu> wrote:
> Hi,
> I would appreciate some advice with regard to an algorithm and data
> structure.

Interesting problem, but I need clarification on two points:

> Suppose that I have a number of functions (f1,..., fn) each of which take
a
> 'symbol' argument and return a list of such symbols. For example:
>
> f1(A) = [B,C,D,E]
> f2(B) = [F,G]
> f2(C) = [H,I,J]
> f3(G) = [K,L,B,N]

This is odd - four different functions, four different arguments.

What happens with, say, f2(A)?

> After applying the functions in a certain way, I would like to enumerate
the
> 'linkage' between the various symbols. Each 'symbol' may not be unique,
and
> may appear at various points in a 'chain'.
>
> For the example above, this linkage might be represented as
>
> A -> B -> F
> A -> B -> G -> K
> A -> B -> G -> L
> A -> B -> G -> B

There is a problem here. If loops are possible (B -> G -> B) then there are
infinitely many chains possible - just repeat that loop as often as you
want. What to do? Don't loops occur in your data, or what?

> A -> B -> G -> N
> A -> C -> H
> A -> C -> I
> A -> C -> J
> A -> D
> A -> E
>
> Although it is not necessary, it might be useful to have the functions
> applied for each item enumerated as well, e.g.
> 	A -> B -> F : (f1,f2)   or	A --f1--> B --f2--> F
>
> I'm not a computer scientist, but this seems as if this is basically a
tree
> structure in which we are moving from the 'trunk' to a given 'leaf'.
Perhaps
> this is something related to directory 'walking'.

It reminds me of grammars for languages, like for simple expressions:

<expression> -> <atom>
<expression> -> <expression> + <expression>
<atom> -> 0..9

That's a grammar for a formal language that can produce strings of the form
'3', '3 + 5', '3 + 7 + 9 + 1', etc.

> Does anyone have any ideas as to how I should code this structure and
> algorithm?

I'm thinking dictionaries and recursion but I'd like to have the points
above clarified :)

--
Remco Gerlich