Elysian Shadows

im my opinion the best solution: (i know i said there is not a best one, this one might suffer from some network congestion)

the network lets person X know that someone is looking for it.
person X then tell all its friends someone is looking for it.
they store a value something like person X - person X (next hop, person in question)
each friends lets all its friends know that someone is looking for person X, and you can get him through me.
those friends store in same format (jack , person X) (next hop, person in question)
and so the cycle continues.
if there is a link from A to B it will be found, and minimal memory will be used. because each person know only how
to get to person X by going to the next hop.

note: i didnt mention a system for not going in circles but im sure you can figuer out a way.

Isn't that just breadth first graph traversal starting from the end point?

bugmenot wrote:Isn't that just breadth first graph traversal starting from the end point?

yeah i guess you can look at it that way. but its not traversing anything at all, there is no computation. no pointers, nothing.
you just get a message at the node you are searching from that says, <next hop, looking for>
each subsequent node has a message tht says yeah i know how to get to looking for, but only the first step, that node has the next step and so on.
its alot more efficient than breadth first. the enrite network works together offering what they know as a whole. so you dont have to have large data structures.

I may have miss-understood your algorithm, are you doing breadth first or depth first? At the moment, I am assuming you are going from the target, iterating/traversing through its friends list and then iterating/traversing through the friend's friends list, etc.

After talking with a friend, we have a solution that has a complexity of O(1) for lookup if there is a connection between two people and a worse case complexity of O(n * 0.5) where n is the number of nodes in the network to add a friend.

The overall cost is better then any graph traversal where the worse case of lookup is O(n) and works well in situations where searches are frequent and data set changes are minimal.

The basic idea is that all the nodes are grouped into islands of connectivity where every node in an island is connected to every other node in some way and all have the same island ID.

bugmenot wrote:After talking with a friend, we have a solution that has a complexity of O(1) for lookup if there is a connection between two people and a worse case complexity of O(n * 0.5) where n is the number of nodes in the network to add a friend.

The overall cost is better then any graph traversal where the worse case of lookup is O(n) and works well in situations where searches are frequent and data set changes are minimal.

The basic idea is that all the nodes are grouped into islands of connectivity where every node in an island is connected to every other node in some way and all have the same island ID.

i think i know what you are talking about. but you might have to explain more.
this problem is capible of getting it down to O(1) but those solutions usually tend to a fat data structure.

as for the solution i gave. its not traversal. because the nodes are just talking with its neighbors.
there are not probing actions. as well as no wondering. if a connections exsis or multiple, the shortest path will allways be found
i cant remember what the BigOh is. its probably O(n-1) or something to that nature.

im not sure but i think its refered to as link state diagrams in networking.

As long as the original problem is only to find if a connection exists rather then finding the actual path (hence my earlier questions), we can get away with just storing the island Id per person (an int).

Your solution is still a traversal as the point of the execution is traversing through the nodes in the network breadth first.

Also, is the idea to be memory efficient or performance efficient?

bugmenot wrote:As long as the original problem is only to find if a connection exists rather then finding the actual path (hence my earlier questions), we can get away with just storing the island Id per person (an int).

Your solution is still a traversal as the point of the execution is traversing through the nodes in the network breadth first.

Also, is the idea to be memory efficient or performance efficient?

my original spec said that you had to produce the path. i mean its worthless information if you dont know what the connection is.
secondly. its not traversal !!! you need a sentinel to make it traversal.

think of it this way. traversal would be this:
if there were people holding hands in a long line. and i started at the beginning of the line, then followed each hand to the next and so on, that traversal.

what this idea is doing is not going down any path. all that happened is neighbors (nodes directly connected tell each other what information they have.)
the information gets spread over the network, but at no point does anyone traverse any link. they only share information.

if i get the message that there is a link between person A and B. can choose to traverse the network then.
it onty become a traversal when i choose to befriend that person, and in which case i know what the best path of traversal is. and i didn't use any traversal to findout if there is any path to that person.

sharing information with neighbors != traversal.

my original spec said that you had to produce the path. i mean its worthless information if you dont know what the connection is.

Looks like I missed that, need to rethink the solution.

secondly. its not traversal !!! you need a sentinel to make it traversal.

It is a breadth first traversal. You go through the targets friends, then the friend's friends, then the friend's friend's friends, etc. The diagram on the wiki page is describing the algorithm you are using.

1 is that target, and lets its friends 2, 3 and 4 know they can get to 1. 2, 3 and 4 tell their friends 5, 6, 7 and 8 that they can get to 1 via them. 5, 6, 7 and 8 let their friends 9, 10 11 and 12 know they can get to 1 via them and etc.

bugmenot wrote:

my original spec said that you had to produce the path. i mean its worthless information if you dont know what the connection is.

Looks like I missed that, need to rethink the solution.

secondly. its not traversal !!! you need a sentinel to make it traversal.

It is a breadth first traversal. You go through the targets friends, then the friend's friends, then the friend's friend's friends, etc. The diagram on the wiki page is describing the algorithm you are using.

no i dont go any further than the neighbors.

i don't have a sentinel that probes down the links
i dont use any pointers.
or any traversal methods.

all i do is have nodes tell their neighbors what they know about person X. not hey, im gonna tell my friends friends friends * what i know about person X.
there i no way you can tell me that is considered traversal.

if you think thats traversal you need to either a) go compose some RFC's because people need to know this. or b) go read some RFC's because.

Your program IS the sentinel that is probing the links:

a) they store a value something like person X - person X (next hop, person in question)
b) each friends lets all its friends know that someone is looking for person X, and you can get him through me.
c) those friends store in same format (jack , person X) (next hop, person in question)
d) and so the cycle continues.

b) is already one depth into the graph and you have just traversed a depth further in d) as you are going through b)'s friends.

Ask someone at work and see if they share the same opinion.

no i dont go any further than the neighbors.

Which is a breadth first traversal.
http://en.wikipedia.org/wiki/Breadth-first_traversal

In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

bugmenot wrote:Your program IS the sentinel that is probing the links:

a) they store a value something like person X - person X (next hop, person in question)
b) each friends lets all its friends know that someone is looking for person X, and you can get him through me.
c) those friends store in same format (jack , person X) (next hop, person in question)
d) and so the cycle continues.

b) is already one depth into the graph and you have just traversed a depth further in d) as you are going through b)'s friends.

Ask someone at work and see if they share the same opinion.

no i dont go any further than the neighbors.

Which is a breadth first traversal.
http://en.wikipedia.org/wiki/Breadth-first_traversal

In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

I dont know how to explain this any better.
nodes merely letting their neighbors know what information they have is not considered a tree traversal of any sort.

In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

the method i listed does not explore anything. and thats exactly why its not a traversal. just because you have neighbor in bold does not mean its applicable to my example.

i asked one Dr Alan L Tharp who who teaches at NCSU (datastructures) and he concurred that this method is not considered to be a traversal.
but stated, that when you start going down the tree from point a to point b following the links then it becomes a traversal. but the fact that each not tells its neighbors its info does not make it a traversal.

i still however doubt that you will change you position on the matter.

Consider if A knows B, B knows C and Z, C knows D. A to B is a link, B to C is a link, B to Z is a link, C to D is a link.

Using your method described above (unless it was described incorrectly), we with see if A is connected to D.

the network lets person X know that someone is looking for it.
person X then tell all its friends someone is looking for it.
they store a value something like person X - person X (next hop, person in question)
each friends lets all its friends know that someone is looking for person X, and you can get him through me.
those friends store in same format (jack , person X) (next hop, person in question)
and so the cycle continues.

Start at A, we tell all its friends that someone is looking it which leads us to B via the link from A to B.
Now we tell B's friends that someone is looking for A and you can get to via me (B). This leaves us at C and Z via the link from B to C and B to Z.
Now we tell C's and Z's friends that someone is looking for A and you can get to via them (C and Z). This leaves us at D via the link from C to D.

We have just traversed (read: pass through) through all the nodes in the tree using the links in each node from the parent to the child which is what Dr Alan L Tharp has described as a traversal algorithm. How are you not following the links between the node and its friends in your algorithm?

bugmenot wrote:Consider if A knows B, B knows C and Z, C knows D. A to B is a link, B to C is a link, B to Z is a link, C to D is a link.

Using your method described above (unless it was described incorrectly), we with see if A is connected to D.

the network lets person X know that someone is looking for it.
person X then tell all its friends someone is looking for it.
they store a value something like person X - person X (next hop, person in question)
each friends lets all its friends know that someone is looking for person X, and you can get him through me.
those friends store in same format (jack , person X) (next hop, person in question)
and so the cycle continues.

Start at A, we tell all its friends that someone is looking it which leads us to B via the link from A to B.
Now we tell B's friends that someone is looking for A and you can get to via me (B). This leaves us at C and Z via the link from B to C and B to Z.
Now we tell C's and Z's friends that someone is looking for A and you can get to via them (C and Z). This leaves us at D via the link from C to D.

We have just traversed (read: pass through) through all the nodes in the tree using the links in each node from the parent to the child which is what Dr Alan L Tharp has described as a traversal algorithm. How are you not following the links between the node and its friends in your algorithm?

im just telling you that this is network architecture theory, and that its not any kind of tree traversal.
i learnt this from professors with Ph.D's that are somewhat authorities on the subject. its not my own opinion.
its not something i want it to be this way. or my vendeta. its just the way it is. im not going to go up to a tenured professor
that has been publishing papers for longer that what i have been on this earth. and say, hey, theres this guy online who says you are wrong,
i think you need to revise you work.

can you do tree traversal in C++ without pointers and references? (i dont know, that why im asking)
if the answer is no. then i can prove that this in not traversal by making a program that performs this task with
no pointers or references. (i ask because i have never seen tree traversal without some form of pointer or reference.)

edit: and if you can do a tree traversal without pointers i would like to see how that done.

can you do tree traversal in C++ without pointers and references?

Yes. A link is not necessary has to be maintained via a pointer (*) or a reference (&), you can easily do this via a GUID. Out of interest, how are you maintaining the list of friends for a node?