#### Archived

This topic is now archived and is closed to further replies.

# Database Representation of Undirected Graph (Peer Nodes)

This topic is 5548 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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]

##### Share on other sites
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

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 14
• 9
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
632912
• Total Posts
3009195
• ### Who's Online (See full list)

There are no registered users currently online

×