[Networkit] StronglyConnectedComponents iterative algorithm integration

Michael Hamann michael.hamann at kit.edu
Fri Dec 2 11:54:05 CET 2016


Hi everybody,

On 02.12.2016 11:08, Maximilian Vogel wrote:
> On 26.07.2016 09:58, Elisabetta Bergamini wrote:
>> About the function returning the i-th neighbor, I also think it would
>> be okay, if nobody sees any drawback.
> Well, one can argue that it is a "weird" API of the Graph class making
> it even more exuberant than it already is.
> Instead of storing the neighbors of a node explicitly or adding the
> function returning the i-th neighbor, I tried to find a solution to
> access the i-th neighbor. The workaround for Graph::getIthNeighbor(u, i)
> is to get the neighbors of u with Graph::neighbors(node u) which returns
> a vector of node ids and then access the i-th element of that vector. My
> idea to prevent the copying and returning of the vector is to return a
> const reference to the vector holding the node ids/neighbors. Then I
> took a look at the implementation of Graph::neighbors(node u). It uses
> the forNeighborsOf(node u)-iterator which essentially uses the
> forOutEdges-iterator to fill a vector with neighboring node ids. If this
> is work is carried out anyways, then a const reference won't save much
> at all. Also I believe that this implementation may lead to wrong
> results in the undirected case, but I need to check on that more
> thoroughly. Instead, two variations of the method should exist returning
> either a copy or const reference of the outEdges[u]-vector depending on
> the use case.
> If we keep the Graph::getIthNeighbour(node u, index i), I see no reason
> to expose a template parameter specifying whether the graph is directed
> or not as the graph also keeps this information internally.
> A change to Graph API seems necessary for either solution.

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".

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.

Best,
Michael



More information about the NetworKit mailing list