[Networkit] O(1) edge access

Michael Hamann 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 
generator.

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 
automatically profit.

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?

Michael



More information about the NetworKit mailing list