Good data structure for storing graph-like map

Question

I'm creating a strategy-based kingdom expansion game, where you start with one city and try to expand as far as possible from there. All the cities fit on a hexagon-grid and are connected by the edges of the hexagons.

Here's a diagram to illustrate what I'm trying to achieve:

Each city must be connected to another city by road, which means that all the cities are connected. At this point, I began to realize that this map is very similar to a graph, with the cities being nodes, and the roads being edges. I've already done some graph theory and implement multiple algorithms. However, when implementing it in a graph format (Map<Node, List<Edge>>), I ran into 2 problems:

There is no way to force that each node can only have 3 connections, with each being a multiple of 120º If it was stored in this format, it would be very difficult to render just loop it through for updating. I'm wondering if any of you have any better data structures that can be used for this. Any criticism, suggestions, or advice is welcome.

Thanks!

Ps. I've seen other questions that are somewhat related, however they either do not have an accepted answer or do not solve my problem.

Answer 1

Your first problem can be solved by implementing a custom list object or (as you only need three items) a custom tuple object instead of the default List<>. This way when you insert tiles you can do a quick sanity check to make sure the tiles are at a 120 degree angle. Something like:

public class NeighbourTuple {
    private Node city1, city2, city3;

    public NeighbourTuple(Node city1, Node city2, Node city3) {
        if (!citiesAt120DegreeAngle(city1, city2, city3)) {
            this.city1 = city1;
            this.city2 = city2;
            this.city3 = city3;
        } else {
            thrown new Exception("Cities are not at the correct angle!");
        }
    }


    private bool citiesAt120DegreeAngle(City city1, City city2, City city3) {
         ...
    }

}

Your second problem can be solved by using a secondary list (held by some central game manager or something) that holds every single tile in the game so you can update all of them easily.

Alternately you can do what people usually recommend when making a tile based game and just use a coordinate system. That is make a 2D array where each position corresponds to a city then just insert the cities into the array. Then you could get the neighbours using some algorithm. This might sound complicated but if you just shift some of your nodes up and down like so:

it becomes a lot more clear.