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:
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.