Faster edge lookup #340
Description
Edge lookup is currently done by iterating over all edges:
template <typename T>
bool Graph<T>::findEdge(shared<const Node<T>> v1, shared<const Node<T>> v2,
unsigned long long &id) const {
// This could be made faster by looking for the edge hash, assuming we hash
// based on node data, instead of a unique integer
for (auto e : this->edgeSet) {
if ((e->getNodePair().first == v1) && (e->getNodePair().second == v2)) {
id = e->getId();
return true;
}
if (!e->isDirected() &&
((e->getNodePair().second == v1) && (e->getNodePair().first == v2))) {
id = e->getId();
return true;
}
}
id = 0;
return false;
}
This could probably be made a lot faster if we relied on two changes:
- Cache and update the Adjacency Matrix whenever a node or edge is added/removed/changed
- Utilize the cached Adjacency Matrix for all node and edge searches, using the superior hash lookup speed when the search space is larger
Or alternatively, we store a lookup table of edges with bucketing for repeat edges.