[Networkit] request for comments: new API for edge attributes

Hamann, Michael (ITI) michael.hamann at kit.edu
Thu Jul 31 17:09:34 CEST 2014


On 31.07.2014 16:51, Florian Weber wrote:
>> What about parallel write access
>> (not a good idea for std::hash_map, I believe)?
> That really wouldn't be more of a problem than it is with the vector:
> * parallel inserts/removes are unsafe with both
> * parallel writes on the same attribute are unsafe with both
> * parallel writes on different attributes are safe with both
> (In Order to be absolutely sure, I even tried the last one with clangs
> thread-sanitizer and it found no problems.)

I think there is a difference that you have missed: When the edge ids 
have been initialized, you can construct the vector for edge attributes 
in the appropriate size which should be relatively fast. After the 
construction, you can write to it in parallel. However with the hash map 
you first need to insert sequentially all edges before you can write in 
parallel. I haven't done any benchmarks but I believe this should be a 
lot slower than the initialization of the vector. If calculating the 
attribute value can be parallelized I think you don't want to first 
initialize your hash_map sequentially. Btw. there is also another issue 
with the hash map: you need to have pairs that are independent of the 
order of the elements for undirected graphs.
> Then, for another thing: Currently there is a *huge* amount of code
> duplication in the switch-statements. I am aware that this is because
> you (rightfully) don't want to check things like whether the graph is
> directed inside a tight loop. I do however believe, that there is a
> better and most likely as fast approach: [...]
I agree and in fact I also thought about using templates for that 
purpose even though my suggestion would have been to simply use plain if 
statements in the loop in the template function as I would expect the 
compiler to remove the if. However I agree that your code is the better 
solution, especially as these accessor functions can be used in all 
iterators as you noted.

> And since I am already at it: I think it might be a great thing to be
> able to write something like this:
> void some_fun(const Graph& G) {
> 	for(auto&& edge: G.edges()) {
> 		use(edge);
> 	}
> }
> The basic idea behind that is to provide an iterator-interface over the
> edges/notes/whatever and then put those into a very simple class that
> only has to provide a begin()- and end()-method. It definitely isn't
> something that can be reasonably done until Monday, but all things
> considered it is certainly doable. Other advantages would be:
> * We could suddenly use all the great things from the algorithm-header
> that work on iterators.
> * We could implement the current loops in terms of those iterators
> making the net-increase in code-size relatively small.
+1 for that idea, especially given that we could (hopefully) export 
these iterators to Python.


More information about the NetworKit mailing list