[Networkit] Feedback req'd: Multi-edges

Christian Staudt christian.staudt at kit.edu
Thu Aug 13 19:26:55 CEST 2015


Hi Matteo

On 12 Aug 2015, at 16:02, Matteo Riondato <matteo at cs.brown.edu> wrote:

>> 
>> It’s possible to break the Graph data structure for performance reasons, that’s a conscious choice.
> 
> Interesting. Can you please elaborate on this, maybe with an example?

Just saying that the issue is known but we chose not to implement an expensive check, a choice pro performance and contra safety.


>> Checking during insertion whether an edge (u,v) already exists takes O(deg(u)) time, the resulting slowdown for graph generators and readers is of course not acceptable.
> 
> If I may comment on that, perhaps this decision of whether the slowdown is acceptable should be left to the user. I.e., it should be possible to have a “bool addEdge(vertex u, vertex v, …, bool check_for_dups)" and a similar flag for a buildGraph() function (names completely arbitrary, I don’t remember the nkit API).

Could be done. Then again, we probably want an expensive check to be off in normal usage, and would switch it on when debugging and testing, i.e. when we are already suspicious. The main problem I see with the missing check is that the error passes unnoticed when we are not.

> 
> Also, one could use a membership data structure to store which edges have been inserted, and the lookup would be O(1) in amortized time, at the price of O(E) additional space.

O(E) space is not something we can easily afford. We are targeting large networks and memory is likely to be the primary bottleneck in practice.

> By the way, it is kind of difficult to comment of what would hurt the complexity of some operations and what wouldn’t, as the documentation doesn’t contain time complexities for most operations.

Yes, that could definitely be improved.

> For example, how much time does “hasEdge(u,v)” take?

Needs to scan the vector of adjacent nodes associated with u until it finds the entry v.


> Yes, IMHO this is the valid observation for not having multigraphs as “first class citizens” (and perhaps at all). Most algorithms are not entirely straightforward to extend to multigraphs and actually many problems on graphs may not even have a unique extension to multigraphs.

The introduction of directed graphs is still keeping us busy after a year, but that was a necessary thing. Multi-graphs - not so much.

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/20150813/f1fd9571/attachment.sig>


More information about the NetworKit mailing list