effective C++ data structure to consider in this case

Answer 1

Have you considered a adjacency array for each node, which stores the nodes it is connected to, along with other data?

First, define a node

class Node
{
   int id_;
   std::vector<AdjacencyInfo> adjacency_;

}

Where the class AdjacencyInfo can store the myriad data which you need. You can change the Vector to a hashmap with the node id as the key if lookup speed is an issue. For fancy access you may want to overload the [] operator if it is an essential requirement.

So as an example

class Graph
{
     std::map<int, Node> graph_;
}

Answer 2

boost has a graph library: boost.graph. Check it out if it is useful in your case.

Answer 3

You should try to group stuff together when you can. You can group the information on each region together with something like the following:

class Region_Info {
  Region *ptr;
  int thickness;
  // Put other properties here.
};

Then, you can more easily create a data structure for your line segment, maybe something like the following:

class Line_Segment {
  int node_A;
  int node_D;
  int crosssectional_area;
  std::list<Region_Info>;
};

If you are limited to only 20 regions, then a list should work fine. A vector is also fine if you would prefer.

Answer 4

Well, as everyone else has noticed, that's a graph. The question is, is it a sparse graph, or a dense one? There are generally two ways of representing graphs (more, but you'll probably only need to consider these two) :

• adjacency matrix
• adjacency list

An adjacency matrix is basically a NxN matrix which stores all the nodes in the first row and column, and connection data (edges) as cells, so you can index edges by vertices. Sorry if my English sucks, not my native language. Anyway, you should only consider adjacency matrix if you have a dense graph, and need to find node->edge->node connections really fast. However, iterating through neighbours or adding/removing vertices in an adjacency matrix is slow, the first requiring N iterations, and the second resizing the array/vector you use to store the matrix.

Your other option is to use an adjacency list. Basically, you have a class that represents a node, and one that represents an edge, that stores all the data for that edge, and two pointers that point to the nodes it's connected to. The node class has a collection of some sort (a list will do), and keeps track of all the edges it's connected to. Then you'll need a manager class, or simply a bunch of functions that operate on your nodes. Adding/connecting nodes is trivial in this case as is listing neighbours or connected edges. However, it's harder to iterate over all the edges. This structure is more flexible than the adjacency matrix and it's better for sparse graphs.

I'm not sure that I understood your question completely, but if I did, I think you'd be better off with an adjacency matrix, seems like you have a dense graph with lots of interconnected nodes and only need connection info.

Wikipedia has a good article on graphs as a data structure, as well as good references and links, and finding examples shouldn't be hard. Hope this helps :
Link