[Networkit] StronglyConnectedComponents iterative algorithm integration

Maximilian Vogel maximilian.vogel at student.kit.edu
Tue Jan 3 17:22:29 CET 2017


On 13.12.2016 14:03, Michael Hamann wrote:

> - Whenever you have increased the pointer, you must check if you've 
> reached the end before reading anything at that location - otherwise 
> you will get a segfault sooner or later. Therefore, you unfortunately 
> also need to know the begin and end pointer in the iterator - or just 
> store a reference to the underlying vector.
I tried increasing the pointer as long as there none values in order to 
return only actual neighbors. But then the pointer may be increased past 
the end unless I store the begin and end pointer within the iterator, 
yes. I don't think that a plain vector iterator does that actually. You 
do that yourself manually in constructs like: for (auto it = v.begin(); 
it != v.end(); ++it) { ... }
To me it does not appear to be a clean/elegant solution to store begin 
and and within the iterator. As you suggested, I think it's better to 
get rid of the gaps.

> - Iterators should also allow to get the weight or edge id of an edge 
> in O(1) and lead to a much more intuitive/efficient Python interface, 
> so we should think about exporting them in some way.
Right, weight and edge id if present should be delivered as well.

> Because of all the trouble with the gaps in the neighbors array I 
> wonder if it wouldn't make stuff both easier and faster if we got rid 
> of them. Whenever an edge is deleted, we could just do a swap with the 
> last element in the neighbors vector and then delete from the end. A 
> disadvantage is that then the semantics of iterating while deleting 
> neighbors would change.
I think so, too. To delete neighbors during iterating the erase-remove 
idiommay then be applied.
Do you happen to know why gaps were tolerated/managed/introduced in the 
first place and what other issues may have to be taken care of?


More information about the NetworKit mailing list