[Networkit] Issue with Directed Graph and Question

Christian Staudt christian.staudt at kit.edu
Tue Oct 6 10:51:33 CEST 2015


Hi Michael,

On 05 Oct 2015, at 17:50, Michael Marcucci <onlycutch at gmail.com> wrote:

> First off great program works very nicely, and does not eat up my RAM.
> However I did have an issue running properties.StronglyConnectedComponents(g) on very large directed graphs.
> It fails on Ubuntu x64 with a Bus Error.
> My graph is 800,000 vertices & 135M edges.
> As a test of the software I pretended they were un-directed edges and the ConnectedComponents function worked fine.
> The machine has 160GB of RAM and only ~25GB are being used at the time of the failure so it is not a lack of resource issue.

How exactly does the failure look like? Can you show the code/output?

> 
> As for my question, the Betweenness and Closeness algorithms are they suitable for directed graphs? Most of the algorithms I have seen only use un-directed graphs. Is the Networkit algorithm doing something different, or accounting for directed-ness?

Here’s the policy: Any algorithm class that doesn’t work with a particular type of graph throws an exception from the constructor. It is possible for the class to check for directedness and do something different in that case.
(In general I recommend one class <-> one measure rather than one class <-> one algorithm, i.e. a class can contain multiple algorithms and run them depending on the input)

As for Betwenness and Closeness, they rely on the BFS and Dijkstra classes which compute shortest paths and handle directedness transparently.

Best,
Chris


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151006/ec7175a8/attachment.sig>


More information about the NetworKit mailing list