[Networkit] StronglyConnectedComponents iterative algorithm integration

Michael Hamann michael.hamann at kit.edu
Tue Dec 13 14:03:29 CET 2016


On 07.12.2016 21:12, Maximilian Vogel wrote:
> On 02.12.2016 11:54, Michael Hamann wrote:
> I have never implemented an iterator before, so bear with me. Basically,
> skipping invalid neighbors comes down to ignoring the none values,
> right? That means, a random access iterator is not possible, but a
> bidirectional iterator would be.
 > Whats the cleanest solution here? What is your idea?

Some comments/ideas:

- For the end, usually just a past-the-end pointer is used afaik.
- 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.
- 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.

- Having some wrapper class with "begin()" and "end()"-methods is also 
good/necessary e.g. for C++11-style for-loops. For example I could 
imagine the following:

for (node v : G.neighbors(u)) {
	do_something_with(u, v);

where G.neighbors() would not return a vector, but just a class storing 
(at least) a reference to the neighbors of u that implements an iterator 
interface (and possibly supports casting to a vector in order to not to 
break existing code).
- Having such an iterator interface for all edges and nodes would 
probably make sense, too.

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.


More information about the NetworKit mailing list