[Networkit] allowing algorithms access to graph data structure internals

Marvin Ritter marvin.ritter at gmail.com
Sat Jul 19 01:36:19 CEST 2014


Ok, the must haves are pretty fair. About the should haves:

a) Memory footprint
Right now it is at about 1.5 * m (because we have G and all the half edges
in the builder). If you want to come down to 1 * m you have to move the
data from the builder to the graph. Not a big deal, but this will put the
builder object in an invalid or at least empty state.

b) Parallel toGraph
The best thing my mind came up with so far is letting every thread create
his own outEdges (thread 1 for edges form nodes 0-99, thread 2 for nodes
100-199, ...) and then combining those (thread 1 arrays for nodes 0-99,
thread 2 arrays for nodes 100-199, ...). Obviously that increase the amount
of data to be copied and adds some memory overhead.

Beside from that we should clarify what the methods should do:
addEdge(u, v)

it does not care if there is already an u->v or a v->u, it will always
create a new u->v and toGraph later a v->u (for undirected)

increaseWeight(u, v, ew)

u->v exists: increase weight
u->v does not exist: add edge u->v with weight ew, even if their is an edge
v->u


I created a new branch for GrapbBuilder.

Bests,
Marvin


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

>
> Am 16.07.2014 um 14:31 schrieb Marvin Ritter <marvin.ritter at gmail.com>:
>
> 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.
>
>
> The idea is to allow parallel construction of a graph.
>
> Must have:
> - one-sided edge modifications are thread-safe, i.e. the adjacency u -> v
> can be modified safely in a parallel loop over the nodes u
> - no locks
>
> Should have:
> - no sequential iteration over the nodes or edges
> - no memory footprint of 2x G
>
> _______________________________________________
> 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/20140719/8e8ff0b5/attachment.html>


More information about the NetworKit mailing list