# [Networkit] StronglyConnectedComponents iterative algorithm integration

Maximilian Vogel maximilian.vogel at student.kit.edu
Wed Dec 7 21:12:09 CET 2016

```Hi there,

On 02.12.2016 11:54, Michael Hamann wrote:
> Just a short note: In the internal vector that represents the
> neighbors of a node, there may be gaps (which are filled with "none",
> i.e. the maximum unsigned 64 bit integer value). Therefore, getting
> the ith neighbor is not possible in constant time with the current
> data structures unless you accept that it may be "none".
Ah, right. That explains the need for/usage of the forNeighborsOf-iterator.
> Maybe implementing a proper iterator interface in the graph class
> could make this easier? Then you could just store an iterator instead
> of the index i, and the iterator would take care of skipping the
> invalid neighbors.
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.
Placing the following code inside Graph class compiles (but hasn't been
tested):
class custom_iterator : public
std::iterator<std::bidirectional_iterator_tag, node> {
private:
node* p;
public:
custom_iterator(node* p) : p(p) { };
custom_iterator(const custom_iterator& it) : p(it.p) {};
*custom_iterator& operator++() { do {++p;} while (*p == none); return
*this; }*
custom_iterator operator++(int) {custom_iterator tmp(*this);
operator++(); return tmp;}
node& operator*() { return *p; }
bool operator==(const custom_iterator& rhs) { return p == rhs.p; }
bool operator!=(const custom_iterator& rhs) { return p != rhs.p; }
};
The crucial part obviously is the increment operator of the iterator. My
idea to skip the invalid the neighbors is to advance the pointer as long
the value it points to is none. (For the time being just ignore that the
decrement operator is missing.)

I could use this custom iterator to implement a function
Graph::neighborsBegin(node u):
custom_iterator neighborsBegin(node u) { auto it =
custom_iterator(&outEdges[u][0]); if (*it == none) ++it; return it;};

The reason for the initial increment is that outEdges[u][0] may have
been deleted resulting in none. Now, imagine that all edges of a node
have been deleted. Any increment to the iterator will stop somewhere
after outEdges[u].end() and then for-loops like "for (auto it =
v.begin(); it != it.end(); ++it)" are not guarenteed to terminate or
even behave properly. Some sort of guard is necessary that
neighborsBegin() and neighborsEnd() evaluate to the same iterator in
case the node has no neighbors at all, e.g. let both functions evaluate
to outEdges[u].begin() if degree[u] == 0. One issue may be that these
functions are not constant-time.
Whats the cleanest solution here? What is your idea?

In the context of the iterative SCC implementation not only the current
iterator but also either neighborsEnd or neighborsBegin need to be
stored in order to avoid deg(u)-calls to it.

Best,
Max

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161207/9cbe1b48/attachment.html>
```