[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>


More information about the NetworKit mailing list