[Networkit] allowing algorithms access to graph data structure internals

Christian Staudt christian.staudt at kit.edu
Wed Jul 16 14:04:52 CEST 2014


Hi Marvin,
I agree, friendship between Graph and various I algorithms is also quite ugly. But the problem with using GraphBuilder is that toGraph is sequential, needs O(m) time and temporarily twice the memory. Ideally we want to build the graph entirely in parallel and in place.

I’ve added the files to the Dev branch for further experimentation.

Chris


 

Am 16.07.2014 um 13:15 schrieb Marvin Ritter <marvin.ritter at gmail.com>:

> Hey folks,
> 
> stop messing up the "my" Graph interface! :p
> 
> I think adding a public addHalfEdge method is as worse as you can do. Christian and Florian mentioned the prime reasons.
> 
> I also dislike adding algorithm classes as friends to Graph. A cleaner solution would be adding a GraphBuilder class which contains the methods necessary to create graphs fast (and if possible also in parallel). At the end of your reader/generator you call a toGraph methods which creates a valid Graph instance. This way we only add a single friend class to Graph.
> 
> You can find a quick&dirty draft in the attachment. To use it put it in src/cpp/graph and add "friend class GraphBuilder;" to the Graph class.
> 
> Best regards,
> Marvin
> 
> 
> 
> 
> 
> On Tue, Jul 15, 2014 at 7:53 PM, Florian Weber <uagws at student.kit.edu> wrote:
> Hi,
> 
> 
> > *src/cpp/graph/../coarsening/ParallelPartitionCoarsening.h:24:20:
> > error: 'Graph' was not declared in this scope* *  virtual
> > std::pair<Graph, std::vector<node> > run(const Graph& G, const
> > Partition& zeta);*
> 
> 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, …).
> 
> To declare that a certain class Foo is your friend (and may touch your
> privates, as the saying goes), you don't have to define Foo yet. The
> following works perfectly fine:
> 
> class Bar {
>         int i;
>         friend class Foo; // forward-declare your friend
> };
> 
> class Foo {
>         void fun(Bar& x) const {x.i += 2;}
> };
> 
> 
> 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).
> 
> Regards,
> Florian
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> 
> 
> <GraphBuilder.h><ATT00001.c>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140716/7a461011/attachment.html>
-------------- 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/7a461011/attachment.sig>


More information about the NetworKit mailing list