[Networkit] StronglyConnectedComponents iterative algorithm integration

Obada Mahdi omahdi at gmail.com
Fri Dec 2 12:42:11 CET 2016


Hi Maximilian and others,

some thoughts on this issue:

On Fri, Dec 2, 2016 at 11:08 AM, Maximilian Vogel <
maximilian.vogel at student.kit.edu> wrote:
​​[getIthNeighbor(u, i)]

> Well, one can argue that it is a "weird" API of the Graph class making it
> even more exuberant than it already is.
>
Agreed. T
he addition of `getIthNeighbor(u, i)` was meant as a hack and is by no
means a clean solution.
​
​
​

> ​[...]
>  Graph::neighbors(node u) which returns a vector of node ids and then
> access the i-th element of that vector.
> ​[...]
>  If this is work is carried out anyways, then a const reference won't save
> much at all.
>

​This is exactly why I hacked in `getIthNeighbour​()`. If you fetch all
neighbors of a node when visiting them, then running the algorithm on a
dense graph may have space complexity up to quadratic in the number of
nodes, if I am not mistaken, which compares unfavorly to the linear
requirements of Tarjan's SCC.

I think that Michael's suggestion (exposing a proper edge iterator
interface) may be the way to go. This would mimic the way the recursive
implementation works, which is also using an iterator that is implicitly
preserved on the stack over the course of descending calls.

Note on "gaps" in edge lists: I had only included a simple sentinel that
throws an exception in the proof-of-concept iterative implementation when
"none" is encountered as a fail-safe, which is definitely a TODO that could
be resolved with the iterator suggestion.

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

​As far as I can see, `NetworKit::Graph` only keeps an instance variable
around​. The template parameter makes a huge difference, because it can be
evaluated at compile-time. Testing against an instance variable incurs the
overhead of one extra memory access and comparison for every call.


Regards

Obada
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161202/1966a283/attachment.html>


More information about the NetworKit mailing list