[Networkit] O(1) edge access
michael.hamann at kit.edu
Tue Jan 13 11:33:40 CET 2015
Dear NetworKit developers and users,
I'm wondering if we should (optionally) allow constant time access to specific
edges and their attributes. Imagine for example you want to increase the
weight of an edge (u, v). Currently this is an operation whose running time is
linear in the degree of both vertices which quickly leads to quadratic
implementations of linear algorithms. Another example are checks if certain
edges exist which are needed for swap operations in the configuration model
How could this work? What I've been thinking about is a hash map that is used
in the indexInOutEdgeArray() method and simply maps a pair (u, v) to the index
in the adjacency array of u. This map would need to be updated in addEdge(),
removeEdge() and swapEdge(). Other methods won't be affected but will
In order to not to increase the memory consumption for graphs where this kind
of access is not needed this map should be optional (similar to edge ids, just
that not having the map only affects the performance). The disadvantage here is
that this means that indexInOutEdgeArray() gets an additional if-clause.
However, given how many conditions it already has (one for every entry in the
adjacency array), I doubt this will have a significant performance impact.
For directed graphs the same map would also be needed for incoming edges.
What do you think about this feature?
More information about the NetworKit