4

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.

Improve this question
4
  • Is it actually a "real" undirected graph, or just a bunch of recursive triangles? Which details need to be stored and which are assumed? – user7043 May 21 '12 at 12:20
  • 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. – han42 May 21 '12 at 12:27
  • 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? – Giorgio May 22 '12 at 4:39
  • Like the one in the picture, so you can assume no edge are missing. – han42 May 22 '12 at 4:59
2

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.