I was wanting to create a graph similar to this in C++:
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.
Best Answer
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.