Search the family of an element in a table

[mignoncharly]

Hi evryone,
i have started to write an "algorithm" that finds the Family of a given element in a table of 3 columns: Id, Source and Destination. When i say Family i mean each element (i.e. A) from Source that has a relation with another one in Destination and i have to find a family for that new (element) one (coming from A) and so on till there is no sucessor more. May be it would be clear with what i have done so far? please don't be rude :) Thanks (Approach below)

Array Source(), Destination(), BigArray() int
Variable i, j, k, N, found, pieceToFind int
Variable notFound boolean

//verify if pieceToFind exists in Source()
for i=0;i->N;i++
    if pieceToFind != Source(j)
       notFound <- true
       else found <- pieceToFind
//looking for A sucessors or predecessors
for i=0; i->N; i++
     for j=0; j->N; j++
          for k=0; k->N; k++
//here i want to bind A with the element located in Destination at the same NodeId index (i=0, A has value J) and store it in a new Array X()  and so on   
        while (found ... )
        .
        .
        .

i=0 J value (sucessor) of A : A->J
i=7 A -||- F : F->A
i=8 E -||- A : A->E

A->J F->A A->E store in BigArray()

//searching for the new Family of each tied value of A (J, F, E)

case1//if J exists in Source() and J = Source(j) <- A ignore
//if J found in Source() find sucessors

i=0 ignore

case2//if F exists in Source() and F = Source(j) <- A ignore
//if F found in Source() find sucessors

i=6 F value (sucessor) of Z : Z->F, Z->F store in BigArray()
i=7 ignore

//searching for the new Family of each tied value of F (Z)

case2.1// if Z exists in Source() and Z = Source(j) <- A ignore
//if Z found in Source() find sucessors
i=6 ignore

case3//if E exists in Source() and E = Source(j) <- A ignore
//if E found in Source() find sucessors

i=1 E value (sucessor) of B : B->E
i=2 Y -||- E : E->Y
i=3 Z -||- E : E->Z
i=8 ignore

B->E E->Y E->Z store in BigArray()

//searching for the new Family of each tied value of E (B,Y,Z)
case3.1// if B exists in Source() and B = Source(j) <- A ignore
//if B found in Source() find sucessors

i=1 ignore
i=4 B value(sucessor) of X : X->B, X->B store in BigArray()

case3.2// if Y exists in Source() and Y = Source(j) <- A ignore
//if Y found in Source() find sucessors

i=2 ignore

case3.3// if Z exists in Source() and Z = Source(j) <- A ignore
//if Z found in Source() find sucessors

i= 3 ignore
i=6 F value(sucessor) of Z: Z->F, Z->F store in BigArray()

//Looking now for duplication
BigArray=(A->J, F->A, A->E, Z->F, B->E, E->Y, E->Z, X->B, Z->F)

//if duplication exists, erase both
BigArray=(A->J, F->A, A->E, B->E, E->Y, E->Z, X->B)BigArray is the result i want to have at the end.

I can understand that some of you might not get what i have done so far but it was the best way for me to explain it like this. Thank you

(sorry english is not my first language :) )
Best Regards
Charly

 

[Mark44]

Hi evryone,
i have started to write an "algorithm" that finds the Family of a given element in a table of 3 columns: Id, Source and Destination. When i say Family i mean each element (i.e. A) from Source that has a relation with another one in Destination and i have to find a family for that new (element) one (coming from A) and so on till there is no sucessor more. May be it would be clear with what i have done so far? please don't be rude :) Thanks (Approach below)

I added code tags to your pseudocode in the original post. I think I put the ending code tag in the right place, but I'm not certain of it.

What you describe above isn't very clear to me. In the pseudocode below, you have three arrays, two of which match the columns you describe above. Is BigArray below supposed to represent the Id column?

You said above that each element from Source has a relation to another one in Destination. What sort of relation? How can we tell if an element in Source is related to something in Destination? It would be better to show a small example, with specific values in Source and in Destination, and show us what it means for one element to be related to something in another column (array). Also, I'm not following the successor business at all.

Array Source(), Destination(), BigArray() int
Variable i, j, k, N, found, pieceToFind int
Variable notFound boolean

//verify if pieceToFind exists in Source()
for i=0;i->N;i++
    if pieceToFind != Source(j)
       notFound <- true
       else found <- pieceToFind
//looking for A sucessors or predecessors
for i=0; i->N; i++
     for j=0; j->N; j++
          for k=0; k->N; k++
//here i want to bind A with the element located in Destination at the same NodeId index (i=0, A has value J) and store it in a new Array X()  and so on  
        while (found ... )
        .
        .
        .

The names you chose for your explanation are very confusing. "A has value J" -- is this different from j that you're using in the for loop? Also, in your first for loop above, the loop index is i, but you're looking for Source(j), and you haven't initialized j yet.

A small confusion is that notFound is a boolean variable, but found is an int. The names suggest that these two would both be boolean, with one being the opposite of the other.

In the nested for loops, you have a comment about what you're trying to do, but haven't provided enough detail in your explanation for me to understand what's supposed to happen, and there's no pseudocode for me to attempt to understand.

I have no idea what you're trying to do in the work below.

i=0 J value (sucessor) of A : A->J
i=7 A -||- F : F->A
i=8 E -||- A : A->E

A->J F->A A->E store in BigArray()

//searching for the new Family of each tied value of A (J, F, E)

case1//if J exists in Source() and J = Source(j) <- A ignore
//if J found in Source() find sucessors

i=0 ignore

case2//if F exists in Source() and F = Source(j) <- A ignore
//if F found in Source() find sucessors

i=6 F value (sucessor) of Z : Z->F, Z->F store in BigArray()
i=7 ignore

//searching for the new Family of each tied value of F (Z)

case2.1// if Z exists in Source() and Z = Source(j) <- A ignore
//if Z found in Source() find sucessors
i=6 ignore

case3//if E exists in Source() and E = Source(j) <- A ignore
//if E found in Source() find sucessors

i=1 E value (sucessor) of B : B->E
i=2 Y -||- E : E->Y
i=3 Z -||- E : E->Z
i=8 ignore

B->E E->Y E->Z store in BigArray()

//searching for the new Family of each tied value of E (B,Y,Z)
case3.1// if B exists in Source() and B = Source(j) <- A ignore
//if B found in Source() find sucessors

i=1 ignore
i=4 B value(sucessor) of X : X->B, X->B store in BigArray()

case3.2// if Y exists in Source() and Y = Source(j) <- A ignore
//if Y found in Source() find sucessors

i=2 ignore

case3.3// if Z exists in Source() and Z = Source(j) <- A ignore
//if Z found in Source() find sucessors

i= 3 ignore
i=6 F value(sucessor) of Z: Z->F, Z->F store in BigArray()

//Looking now for duplication
BigArray=(A->J, F->A, A->E, Z->F, B->E, E->Y, E->Z, X->B, Z->F)

//if duplication exists, erase both
BigArray=(A->J, F->A, A->E, B->E, E->Y, E->Z, X->B)BigArray is the result i want to have at the end.

I can understand that some of you might not get what i have done so far but it was the best way for me to explain it like this. Thank you

(sorry english is not my first language :) )
Best Regards
Charly

 

[mignoncharly]

I added code tags to your pseudocode in the original post. I think I put the ending code tag in the right place, but I'm not certain of it.

What you describe above isn't very clear to me. In the pseudocode below, you have three arrays, two of which match the columns you describe above. Is BigArray below supposed to represent the Id column?

You said above that each element from Source has a relation to another one in Destination. What sort of relation? How can we tell if an element in Source is related to something in Destination? It would be better to show a small example, with specific values in Source and in Destination, and show us what it means for one element to be related to something in another column (array). Also, I'm not following the successor business at all.
The names you chose for your explanation are very confusing. "A has value J" -- is this different from j that you're using in the for loop? Also, in your first for loop above, the loop index is i, but you're looking for Source(j), and you haven't initialized j yet.

A small confusion is that notFound is a boolean variable, but found is an int. The names suggest that these two would both be boolean, with one being the opposite of the other.

In the nested for loops, you have a comment about what you're trying to do, but haven't provided enough detail in your explanation for me to understand what's supposed to happen, and there's no pseudocode for me to attempt to understand.

I have no idea what you're trying to do in the work below.

Hi Mark44,
thank for taking your time to answer my question.
1) "I think I put the ending code tag in the right place, but I'm not certain of it." yes you did. It's ok.

2) " Is BigArray below supposed to represent the Id column?" No BigArray is supposed to be the final Array that would receive all my "relations" (i'm going to explain it further)

3) "You said above that each element from Source has a relation to another one in Destination. What sort of relation?" here i meant it like in an associative Array (index=>value). so during the Iteration(i=0, i->N,i++) if A is found, i save the 'A'=>'J' in BigArray. (I'm also thinking about how!? and if it possible?)

4) "How can we tell if an element in Source is related to something in Destination?" I thought it will be possible if they were in an associative Array?? ( :( )

5) "It would be better to show a small example, with specific values in Source and in Destination, and show us what it means for one element to be related to something in another column (array)." Did you see the the Picture i have joined to the Topic? A from Source is related to J in Destination, B from Source is related to C in Destination ... (i'll upload a specific Picture showing this "relation")

6) " "A has value J" -- is this different from j that you're using in the for Loop?" yes ist different. That J is the one in the Destination column.7) "Also, in your first for loop above, the loop index is i, but you're looking for Source(j), and you haven't initialized j yet." May be i had too much index. Because my thought were: if all these data (elements of source and Destination are considered as two Array in an Array, each Array could have ist own index for a searching issue!?)

8) "A small confusion is that notFound is a boolean variable, but found is an int. The names suggest that these two would both be boolean, with one being the opposite of the other" you are right. I wanted to save the PieceToFind in a variable and i choose "found". I could have choosen something else as Name variable.

9) "In the nested for loops, you have a comment about what you're trying to do, but haven't provided enough detail in your explanation for me to understand what's supposed to happen, and there's no pseudocode for me to attempt to understand." I couldn't move Forward because it was also hard for me to write a pseudocode but i'll try over again to explain.

10) "I have no idea what you're trying to do in the work below" I was certain of that ... don't worry i think i fill everything with anything but here is what i was supposed to do.

May be sucessor is not the right Name for what i wanted to describe.
If during the search (i=0, i<N,i++) whenever the element that to be find is found then save this element as index with his value (well, if A is that element then A->J) in an Array(). And i was considering each of his value as his "sucessors" (i.e. A->J, A->E) see table
After that. I continue to search now if his "sucessors" (J and E) are present in Source. If they are found do the the same thing as with A i.e. if E in found in Source() then save it as index with his value (E->Y) in an Array() and so on.

If something is not clear please feel free to ask. (Picture attached)
Thank you in advance

Charles

 

[Mark44]

2) " Is BigArray below supposed to represent the Id column?" No BigArray is supposed to be the final Array that would receive all my "relations" (i'm going to explain it further)

3) "You said above that each element from Source has a relation to another one in Destination. What sort of relation?" here i meant it like in an associative Array (index=>value). so during the Iteration(i=0, i->N,i++) if A is found, i save the 'A'=>'J' in BigArray. (I'm also thinking about how!? and if it possible?)

Now things make more sense, not that I know that your structures are associative arrays -- maps in C++ Standard Template Library (STL) jargon) or dictionaries as Python terms them. Each one is a collection of key-value pairs.

In your BigArray array, I would recommend adding four more elements, the ones for the leaf nodes H, I, J, K. Since these are leaf nodes (with no successors) they would have a special indicator (0?, NULL?) whose meaning is that they are the last nodes in the tree-like structure the array represents.

How I see BigArray is a list of key-value pairs (i.e, a map (C++) or dictionary (Python)). For each element in the list, the key is the node ID, and the value is a tuple (a pair in this case),
$\begin{bmatrix} 0 & <A, B> \\ 1 & <B, C> \\ 2 & <C, G> \\ 3 & <C, H>\\ \vdots & \vdots \\ 10 & <H, 0> \\ 11 & <I, 0>\\ 12 & <J, 0>\\ 13 & <K, 0> \end{bmatrix}$
I used 0 (zero) as the marker in the last four pairs, but anything that wouldn't be confused with the existing nodes in your tree would work.

4) "How can we tell if an element in Source is related to something in Destination?" I thought it will be possible if they were in an associative Array?? ( :( )

Now I understand.

5) "It would be better to show a small example, with specific values in Source and in Destination, and show us what it means for one element to be related to something in another column (array)." Did you see the the Picture i have joined to the Topic? A from Source is related to J in Destination, B from Source is related to C in Destination ... (i'll upload a specific Picture showing this "relation")

6) " "A has value J" -- is this different from j that you're using in the for Loop?" yes ist different. That J is the one in the Destination column.7) "Also, in your first for loop above, the loop index is i, but you're looking for Source(j), and you haven't initialized j yet." May be i had too much index. Because my thought were: if all these data (elements of source and Destination are considered as two Array in an Array, each Array could have ist own index for a searching issue!?)

The problem as I see it is how to start with the tree-like structure you drew, and end up with a map or dictionary that represents which nodes are directly connected to which other nodes.

If the goal of this problem is only to automate the transformation from the tree-like structure in the drawing to the map/dictionary thing you're calling BigArray, I don't have any good suggestions at the moment. However, you could create BigArray by merely initializing it with the information as I laid out above (i.e., with NodeIDs and pairs of Source/Destination values. In this way the initialized structure could be used to answer questions such as
1) Is there a path from X to Y?
2) If there is a path between X and Y, how far away is it?
3) If there are multiple paths between X and Y, which one is the shortest?

May be sucessor is not the right Name for what i wanted to describe.

Successor is good name. In the tuples (pairs) that I described above, the second element is the successor of the first.

If during the search (i=0, i<N,i++) whenever the element that to be find is found then save this element as index with his value (well, if A is that element then A->J) in an Array(). And i was considering each of his value as his "sucessors" (i.e. A->J, A->E) see table
After that. I continue to search now if his "sucessors" (J and E) are present in Source. If they are found do the the same thing as with A i.e. if E in found in Source() then save it as index with his value (E->Y) in an Array() and so on.

 

[Mark44]

As a proof of concept of what I suggested, I wrote a C++ program that creates a map.
The map is a collection of key (node ID) and value (pairs of letters) pairs.

I inserted the first four and the last two map items, using your tree-like diagram, and then printed out the contents of the map. Here's the output from my program. In angle brackets are a node and its successor. If a node has no successor, it's a leaf node, I store ASCII 0. When I print the node pairs out, I print END.

Map size: 6
--------------------
Node ID: 0 -- <A, B>
Node ID: 1 -- <B, C>
Node ID: 2 -- <C, G>
Node ID: 3 -- <C, H>
Node ID: 4 -- <H, END>
Node ID: 5 -- <I, END>

 

[mignoncharly]

Now things make more sense, not that I know that your structures are associative arrays -- maps in C++ Standard Template Library (STL) jargon) or dictionaries as Python terms them. Each one is a collection of key-value pairs.

Cool. I'm happy being understood :) .The Problem is ... I'm not familiar with both language but with PHP and it is possible to have a structure that are associative Arrays (also in JavaScript!?).

In your BigArray array, I would recommend adding four more elements, the ones for the leaf nodes H, I, J, K.

Sorry but i don't get it.

Since these are leaf nodes (with no successors) they would have a special indicator (0?, NULL?) whose meaning is that they are the last nodes in the tree-like structure the array represents.

How I see BigArray is a list of key-value pairs (i.e, a map (C++) or dictionary (Python)). For each element in the list, the key is the node ID, and the value is a tuple (a pair in this case),
$\begin{bmatrix} 0 & <A, B> \\ 1 & <B, C> \\ 2 & <C, G> \\ 3 & <C, H>\\ \vdots & \vdots \\ 10 & <H, 0> \\ 11 & <I, 0>\\ 12 & <J, 0>\\ 13 & <K, 0> \end{bmatrix}$
I used 0 (zero) as the marker in the last four pairs, but anything that wouldn't be confused with the existing nodes in your tree would work.

That is it! But there is a "Problem" H couldn't be a leaf Node because it has a relation with F even though it is in Destination so it should be also marked as tuple. Same with I. (Its like a process ... which element has been used to produce/create this or that element. So which element includes the "creation" of let's say H? It would be <C, H> <F, H> and each one related to C and F and so on) (picture)

Now I understand.

The problem as I see it is how to start with the tree-like structure you drew, and end up with a map or dictionary that represents which nodes are directly connected to which other nodes.

I think I'm going to use a PHP library or something with graph framework... I'm not yet sure. Now i have to write this algorithm first and later the representation. :)

If the goal of this problem is only to automate the transformation from the tree-like structure in the drawing to the map/dictionary thing you're calling BigArray, I don't have any good suggestions at the moment. However, you could create BigArray by merely initializing it with the information as I laid out above (i.e., with NodeIDs and pairs of Source/Destination values.

In this way the initialized structure could be used to answer questions such as
1) Is there a path from X to Y?
2) If there is a path between X and Y, how far away is it?
3) If there are multiple paths between X and Y, which one is the shortest?

Hmmmm questions 2) and 3) are not part of my work.

Successor is good name. In the tuples (pairs) that I described above, the second element is the successor of the first.[/QUOTE]

Thank you for your time
Best Regards
Charles

 

[mignoncharly]

As a proof of concept of what I suggested, I wrote a C++ program that creates a map.
The map is a collection of key (node ID) and value (pairs of letters) pairs.

I inserted the first four and the last two map items, using your tree-like diagram, and then printed out the contents of the map. Here's the output from my program. In angle brackets are a node and its successor. If a node has no successor, it's a leaf node, I store ASCII 0. When I print the node pairs out, I print END.

Map size: 6
--------------------
Node ID: 0 -- <A, B>
Node ID: 1 -- <B, C>
Node ID: 2 -- <C, G>
Node ID: 3 -- <C, H>
Node ID: 4 -- <H, END>
Node ID: 5 -- <I, END>

Waouh ... cool.
As i said i should consider the fact that H and I couldn't be leaf node since they are present in Destination that imply they are also a tuple.
I'm trying with PHP Syntax and my be i could post it and you could see if the Logic is in it. Thank you

Charles

 

[Mark44]

As i said i should consider the fact that H and I couldn't be leaf node since they are present in Destination that imply they are also a tuple.

A leaf node is one that has no successor node. The pairs <A, B> and <C, G> mean that the successor of A is B and the successor of C is G. The pair <H, END> means that H has no successor. In my program I used ASCII 0 ('\0') instead of "END".

I'm trying with PHP Syntax and my be i could post it and you could see if the Logic is in it.

I'm not familar with PHP, but I'll give it a try to see if I understand what you have.

 

[Pepper Mint]

Waouh ... cool.
...
I'm trying with PHP Syntax and my be i could post it and you could see if the Logic is in it. Thank you

Charles

There are still a couple of things PHP is weak about or lacks. For example, threading. But it shouldn't be a big concern at all since today's technologies evolve to help bind everything together and to make life easier every day for end-users. For example, service orientation.
If the OP is only about algorithms, I think Mark's contribution is noted enough. I wanted to propose A* which was the first approach I learned in signal processing class 13 years ago.