[Networkit] allowing algorithms access to graph data structure internals

Christian Staudt christian.staudt at kit.edu
Wed Jul 16 11:30:11 CEST 2014

Hi Moritz and Florian,

> I suspect that your problem is, that you don't include Graph.h in
> ParallelPartitionCoarsening.h in a proper way (this might be because you
> don't include it at all, because you include them cyclic, …).

I think I had a cyclic include and it was solved with a forward declaration of ParallelPartitionCoarsening in Graph.

> My solution was to add a method addHalfEdge(u,v), which only modifies u.
> The caller has to ensure each call addHalfEdge(u,v) is followed by one
> addHalfEdge(v,u). Since the direction is unclear, it is only supported
> for undirected graphs.

> Concerning the solution of Moritz: That one has the problem, that it
> leaves the class in a state with broken invariants, which isn't that
> much better compared to friendship (such functionality should normally
> be restricted -> private -> we are back at friendship).

Yes. It’s not easy to decide, but in the end I am not in favor of having a method like addHalfEdge, because
- any call to the method leaves the Graph in an inconsistent state
- even if the user follows up with a call to addHalfEdge(v, u), what ensures that the number of edges is counted consistently?
- for my case, I would not just need addHalfEdge, I would need increaseHalfEdgeWeight too and maybe more such methods, and that gets ugly and messes up the Graph interface too much

Friendship makes it at least explicit that we are now, how shall I put it, playing with the privates in non-safe way. The graph interface on the other hand should communicate what safe usage of the object is. It should not allow leaving the object in an inconsistent state unless it’s unavoidable for performance reasons, and should not invite the user to do so.



-------------- 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/20140716/ca331b2a/attachment.sig>

More information about the NetworKit mailing list