Directed/undirected Graph Structures A discussion on the topic.

[dexter 0]

On off-shoot of another topic:

I am sorry to ask that where I can find any information about implementation of mesh network topology? but easy to use? I am not familiar with the concept of "template" so what I found at Google is too difficult to absorb in a short time, and I need to finish my assignment at school in one month. Right now, I can't decide which data structure to implement topology, in order to easily search link such that I would know how many nodes neighbor a target node and which one sends and which one receives? especially when the topology is big and my algorithm need to search million times

  Woah. You have to code a simulation of a mesh network in C++? Sounds to me like you're going to have to develop a graph structure to be able to deal with that.
It's a bit off-topic for this thread, though, you might want to start a new one and I'd certainly be interested to discuss it.

Anyway, in the meantime, I'll go and find some pages that I found really handy when I was doing pathfinding and had to build an undirected graph to store the nodes and their paths.

sorry, off-topic? I thought I wanna find the resource of such stuff so I can post here... but according to your reply, you seem to get a clue of what I am doing, great~~ I wanna build a physical network which I can test my QoS routing method on it. I need undirected graph for physical network and directed graph for routing record. I tried to use two linked list to maintain nodes' and links' status, but the performance was too awful... whenever I remove a node, I need to traverse all nodes and all links, plus modify any related link.... It is absolutely a crappy structure... and the worst is, I don't even know how it failed after three day running... too many linked list, I hate to trace the bug...
So, do you find any handy resource? I really appreciate your kindness!!!

This site has some interesting implementation ideas for graph structures. One thing to note is that they build it from previous objects on the page, so it won't be perfect as-is, and somewhat obfuscated:
Data Structures and Algorithms with Object-Oriented Design Patterns in C++

There are a -lot- of websites around with info about graphs, 'directed graph structure C++' in google brings up a lot of results.

I also found Sedgewick's 'Algorithms in C++' very useful, too, if you can get your hands on it.

With the graph representation, it looks like you've taken the linked list approach. In my particular implementation, I had an array of vertices(nodes) and an array of edges(links). A vertex containing specific information about that location, and an edge as two references of two nodes specifying a link from one node to another.

Although, you could always go down the path of representing the graph as a matrix. The other thing to take note of is that an undirected graph can also be represented by a directed graph.

Heh, this aggravated me for weeks while I was trying to find the perfect way to implement it.


Out of interest, define 'school'... it seems like a rather advanced topic.

[hcwindclub 0]

Thank you so much! But I have no time to digest so much information right now, I will keep tracking this issue after couple days. Thanks a lot.