vendredi 12 juin 2015

undirected weighted graph data structure in c++

I am learning C++ and I appreciate your support by answering my question to help me to understand fundamental concepts. I am sure I need to learn many stuff, but I need a some advice to help me to find the right way. The problem I have is explained in below.

I want to implement a class to create a graph in C++. As I noticed, I can use matrices, but I am not interested in matrices as you can see later. The graph is undirected and weighted. The graph is a vector of nodes and I use the standard library vector. Each node(vertex) of the graph has below parameters and some neighbors.

node_index, node_degree, X, Y , Z.

The neighbors are nodes too and I can define a vector of nodes for them. However, there are 3 reasons that I don't like to create a vector of nodes. First,I don't need the

Y,Z
from a neighbor. I also need weight between this node and each of its neighbors. Second, I need to calculate the node_degree, X for each node separately, and if I have duplicate nodes as neighbors, I need to update them manually that is extra work. Third, the graph would be be large and I don't want to waste the valuable memory for useless information.

Having said that, I was thinking of having a base class that later I can derive the Node class and Neighbor class from it. Then for neighbors I keep a vector of pointers to beginning of each neighbor. I don't know how, but I think I can cast that pointer to base class and by using it I can retrieve the information that I need from neighbor nodes.

In another words, I am trying to keep pointers to neighbors and when I update the neighbors parameters, I access to latest information of the nodes directly using pointers.

Would you please give a link to related topics that I should learn to implement it?

Please let me know if this is a very bad idea (by explaining the problems) and what is the better or best way to do this.

Aucun commentaire:

Enregistrer un commentaire