[Networkit] allowing algorithms access to graph data structure internals

Marvin Ritter marvin.ritter at gmail.com
Wed Jul 16 14:31:43 CEST 2014


Hi Christian,

GraphBuilder does not have to be sequential at all. The very simple
quick&dirty implementation I provided is sequential, but we can change it
any time without touching the readers/generators or the Graph class.I don't
see a big problem in getting rid of the extra memory and parallelizing
parts of toGraph. So a lot of room for optimization.

So I think we should create a list of requirements and use cases for the
GraphBuilder (e.g. which methods with which parameters have to be thread
safe?). Then we can set up some benchmarks and test cases before working on
a better implementation.

Marvin




On Wed, Jul 16, 2014 at 1:04 PM, Christian Staudt <christian.staudt at kit.edu>
wrote:

> 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>
>
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140716/0d3a67b3/attachment-0001.html>


More information about the NetworKit mailing list