Duplicate copies of GraphEdge stored within a graph

[bsaund]

A graph node currently stores in_edges and out_edges.
This duplicates each edge.
More importantly, it is possible to make inconsistent graphs where edges have different weights (and other properties) depending if looking from the "in_edges" or "out_edges" perspective.

[calderpg]

This is an unfortunate consequence of making it efficient to query all edges to/from a given node. It needs to be possible to find all in/out connections in an O(1) operation, and the easiest option is store in/out edges with each node. The most obvious modification would be

class Graph
{
  std::vector<GraphNode> nodes_;
  std::vector<GraphEdge> edges_;
}

with

class GraphNode
{
  T value_;
  std::vector<int64_t> in_edge_indices_;
  std::vector<int64_t> out_edge_indices_;
}

where edges_ is a single store for all the directed edges in the graph. Connectivity checks get a little trickier, but doable. This achieves de-duplication of edges, and probably doesn't affect A* or Dijkstra's performance too much.

Switching to a single vector of edges would probably affect the locality of edge lookups, although without testing it would be hard to know if the impact is good/bad/inconsequential.

[bsaund]

I was thinking we store the edges in the Graph? A GraphNode can store a map <other_node, GraphEdge*> for both in and out edges.
This gives O(|E|) lookup of all edges for a node (same as before), O(1) lookup of an edge to a particular other node (faster than before), and does not duplicate edges. It also becomes a straightforward extension to make an undirected graph.

[calderpg]

That solution has a couple issues:

• O(1) lookups are only true if you use unordered_map or equivalent, and a O(1) operation on a map is a lot more expensive than an O(1) operation on a vector (locatility, hash function, collisions, etc). The memory footprint of each node probably grows noticeably as well. I would guess, given benchmarks that have beeen done, that std::unordered_map has pretty poor performance in this use case compared to other options, but those other options involve pretty noticeable new dependencies. It's easy to forget that O(n) linear search over a small n in contiguous memory is fast.

• O(|E|) lookup of all edges is true, but now only via iterators. This mean you can no longer do

#pragma omp parallel for
for (size_t edge_idx = 0; edge_idx < in_edges.size(); edge_idx++)

That would be a significant loss in some cases, since that translates to no longer being able to automatically parallelize some collision checks during planning.