1

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.

eSadr
  • 395
  • 5
  • 21
  • I've not used Boost Graph but generally, when there is a sub-library in Boost to do what you want to do, it's a good idea to at least look into it. – Cheers and hth. - Alf Jun 12 '15 at 21:44
  • There is nothing specific to C++ in your question. There are many ways to encode a graph data structure each with its advantages and drawbacks, which are usually tradeoffs between space and speed of traversal. My advice is to look into data structures and select the one that matches what you want to do with it, and only after deciding the data structure, think of implementing it in C++. – A.S.H Jun 12 '15 at 22:36
  • Related: https://stackoverflow.com/questions/47569823/creating-undirected-weighted-graph-from-adjancency-matrix-from-a-csv – alseether Dec 04 '17 at 12:52

1 Answers1

2

I advise you to use a Link structure, to represent an edge in the graph:

struct Link
{
  Node *N;
  float weight;
}

Then each Node can contain 

vector<Link> neighbors;

This way there is no duplication of Nodes. There is a duplication of weights, since if Node A has a Link pointing to Node B, then Node B has a Link with the same weight pointing to Node A. If that duplication of weight is a problem (e.g. if the graph is so big that storage of the weights is expensive, or if weights are often updated), then you can make Link bidirectional (two Node* and one weight) and give each Node

vector<*Link>

The code will be slightly more complicated in that case, but it is the price of efficiency.

Beta
  • 96,650
  • 16
  • 149
  • 150
  • Thanks a lot @Beta, I will try it and post the result. – eSadr Jun 13 '15 at 04:32
  • It works perfectly. I needed to use "forward declaration" of Node class before defining the struct Link. [http://stackoverflow.com/questions/553682/when-can-i-use-a-forward-declaration] – eSadr Jun 13 '15 at 15:47