What is the best way to program a lattice graph?

Question

What is the best way to program a graph like this:

I know I could use Adjacency list or Adjacency matrix:

//https://stackoverflow.com/questions/5493474/graph-implementation-c
//Clearer's answer

struct edge {
    int nodes[2];
    float cost; // add more if you need it
};

using graph = std::map<int, std::vector<edge>>;

, but then generating a lattice graph would be slightly inconvinient.

Would something like this suffice:

Edge
{
    Node * from;
    Node * to;
    int32_t weight;
};
struct Graph
{
    std::vector<std::vector<Node>> nodes;
    std::vector<Edge> edges;
    // all required operations
    ...
};

I will use it for stuff like A*, LPA* and similar. I already programmed A* and a regular 2d vector was enough, because every edge had similar cost, well, it had two costs, one for straight step one for diagonal, and you could easily calculate that with a simple function which takes two nodes and checks whether this edge would be a diagonal one by looking at the coordinates, but now I wan't different cost for each edge.

Answer 1

If the graph has a clear structure as in this case (there seems to be a rectangular grid with each vertex being connected to 8 neighboring vertices) then implicit representations can be convenient, e.g. a single vector<Node> where node at (i,j) might be at index i + j * ncols (depending on your coordinate system). However, if the nodes don't contain any further data, then you don't need that list of nodes and can just refer to them by their index.

For your algorithms, you likely want a fast query of all edges of a node. Assuming that your graph is undirected, we might treat each edge as directed as outgoing from the lower-numbered node, which allows us to define a total order over edges. You can then locate a particular edge via binary search in a sorted vector of edges, which has the same time complexity as looking up a value in std::map (but will be much faster in practice). To then get the neighboring edges, you have to look up all the edges from/to nodes (i±1,j±1). The “outgoing” edges will be directly adjacent in the sorted list of edges, reducing the search effort. Instead of searching for a particular edge, you could probably calculate the edge index with a closed form.

Since this is C++, the relevant coordinate ↔ index transformations can be encapsulated in convenient functions or wrapper types.

If all of that seems overengineered – in particular if your graphs are small (less than a million elements or so), then your “nested vector” idea seems fairly appropriate. However, your suggested definition of an Edge is potentially problematic:

struct Edge{
    Node* from;
    Node* to;
    int32_t weight;
};

Leaving aside issues of const-ness, this assumes that the Node objects are in a stable location. However, these pointers will be invalidated if you modify your vectors. This can be avoided by ensuring that the vectors have sufficient capacity before taking the address of any element in the vector, or by referring to nodes via their index as suggested above.

It is also not immediately clear how you would find the edges belonging to a node. If ensuring a total order allowing for search or some implicit encoding is not possible (or simply too much work), you might create data structures that help with such lookups. In addition to the vector<Edge> you might maintain a unordered_map<NodeId, vector<EdgeId>> that provides the indices of edges relating to a particular node. Your graph class would likely provide methods to encapsulate these details so that your main code does not have to concern itself with these details.

If you only have very few edges (up to 150 or so) I would not bother with any clever indexing and just do a linear search through the list of edges whenever I want to find a particular edge.