I''m trying to figure out the best way to represent a network of nodes in an undirected graph. Each node can have n peers. I''d like to be able to derive the following: 1) Count all nodes in a given network 2) Retrieve all nodes closer than X steps away from a given node 3) Retrieve all nodes further than X steps away from a given node What''s the best way to represent this? Thanks, telstar

This first structure that comes to mind is a node object that contains a list of pointers to adjacent node objects.

Many of your operations will be recursive by nature.

quote:1) Count all nodes in a given network

If you can find a way to count the nodes as they are created beforehand, and keep a tally, then you won't have to calculate it later. But if you must, then you'd want to implement a recursive procedure that tallys the number of children it has, plus the number of children for each of its own children, and returns this sum. Since this is an undirected graph, you'd need to pass the source node as a parameter, and simply skip that "child" (since in terms of the search, it's a parent). This is basically a depth-first search, and the return value of the highest procedure call (the root) will tell you how many nodes are in the graph.

quote:2) Retrieve all nodes closer than X steps away from a given node

Same recursive procedure as above, although you have have to pass the "distance" as a parameter so the code knows just how deep it is in your search tree. Each function will make a list of all it's children (excluding source again), and return it. The only exception is if the depth is greater than X, and which point you return an empty list. In the end, you'll have to be merging lists, but since the elements are going to be unique it should be real easy.

quote:3) Retrieve all nodes further than X steps away from a given node

Same as above, only nodes less than X steps away only merge their children's children, and not their own children, into the lists.

I'd be happy to give some pseudo-code as well.

[edited by - Zipster on August 8, 2003 2:20:49 AM]

Thanks for the quick response. One thing I forgot to mention is that nodes belonging to 2 networks can break and join relationships decreasing or increasing the overall network size with one state change.

I''ll pump out some code based on what you suggested.

Thanks,
telstar