[Networkit] O(1) edge access

Marvin Ritter marvin.ritter at gmail.com
Tue Jan 13 12:00:44 CET 2015


Hi Michael,

I would prefer to have several benchmarks for the Graph class first (incl.
all important algorithms), before starting to make more performance
"improvements". C++ not always works as you would think and you never know
which optimisations a compilers does and dosen't.
E.g. I don't know if your map idea would work. For me there are a lot of
unknowns. Constructing a map of size O(m) will take long, not kidding, maps
are slow. Having a map for every node might even be better, as one node is
already a bucket index. Maps might have O(1) lookup, but there is a
constant factor. With m edges, it is likely that the internal buckets might
have several elements. Is this really faster than O(deg(v))? I don't know.
And don't forget that worst case performance is linear, so O(m).
Having good benchmarks we could implement the changes and measure the
improvements on a branch and then decide.

And just to put another idea: Having static graphs most of the time, we
could sort the arrays and do binary search. But again, binary search is not
always faster than linear. Short adjacency lists will be loaded into
cache...

Further you might want to rethink the ideas of splitting up the graph class
- either templates or subclasses. It is already chock-full of options.

Best regards,
Marvin

On Tue, Jan 13, 2015 at 11:33 AM, Michael Hamann <michael.hamann at kit.edu>
wrote:

> 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
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150113/b6459d53/attachment.html>


More information about the NetworKit mailing list