Which data structure to represent a triangular undirected graph

Question

I was wanting to create a graph similar to this in C++:

enter image description here

The one I will implement will have more edges and vertices, but will use this triangle style. I was wanting to create something that I could perform various search algorithms on in order to find shortest paths to selected vertices (or longest without loops etc.). It is an unweighted graph to begin with; however, I was planning to give the edges weights in the future.

I was having some trouble with how I would represent this graph for a couple of reasons: since I want to have more vertices (maybe 105 vertices), any kind of list would be tedious to write out which vertices are connected to which in every object (or is there a way to automate the assignment of members of a vertex object signifying the connectedness?). Also, I was finding it strange trying to implement it in a 2d array because the array is square in nature, and I am dealing with triangles; thinking about the weighting of edges and assigning a value in between two vertices made it even less intuitive with an array.

• user7043: Is it actually a "real" undirected graph, or just a bunch of recursive triangles? Which details need to be stored and which are assumed?
• han42: I was trying to make it a graph since I don't know any other way for finding paths other than breadth first/depth first/Dijkstra so I would need to store which vertices are connected to which so I can make a queue. Maybe later I would store a weight for every pair of vertices somewhere. I guess it doesn't matter if it's "real" because the searches wont create any loops, I don't think.
• Giorgio: Is it going to be always complete like the one shown in the picture? Or is it possible that some elements (small triangles) are missing?
• han42: Like the one in the picture, so you can assume no edge are missing.

Answer 1

You may not necessarily need to solve your problem through a specialized data structure; you can, for instance, find an addressing scheme for each node, which allows you to locate neighbouring nodes in O(1) time, and use a generic data structure to navigate.

A simple scheme here would be assigning to each node a tuple (n, m), where n is the tier and m is the index of the node (assuming 0-indexed, for a node to be valid 0 <= m <= n). For any node, deriving all possible neighbour nodes (ni, mi) is straightforward (smth like (n-1, m-1), (n-1,m), (n, m-1), (n, m+1) etc) - of these you keep those who are valid (0 <= mi <= ni < your triangle size here).

The values can be stored in a vector, the index of node (n, m) is, uniquely, n(n+1)/2 + m.