Veronoi Diagram and Data locality

graph-tool
1

Hello,

This is my first post =)

To begin with - what an awesome package! The website is great, the docs are
amazing, the code is beautiful, sane autotools usage, very fast, pythonic!
Best software package ever!

I'm a beginner in graph theory. Any suggestions on books/tutorials which
can quickly take me from basics to advanced topics would be appreciated.

Now the question.

I'm doing numerical simulation over a veronoi graph. I'm storing data on
the vertexes and edges. The iterations go as following:

1) Using data on the edges ('incident pulses') I'm calculating the value of
the vertex ('node voltage')
2) Using value of the vertex, I'm calculating new values for the edges
('scattered pulses')
3) During next timestep scattered pulses become incident - repeat

In the future I may need to use symmetric directed graph and do more fun
things with incident and scattered pulses.

Now the slight problem arrises, when my graph + values is bigger than I can
store in RAM.

There is Global Arrays toolkit, which recently got GAiN (Global Arrays in
Numpy) which allow seamlessly use numpy/scipy over shared memory cluster.
But it will give good performance if arrays are exercising data locality
properties.

In my case I want property maps of vertixes & edges to be 'near each other'
based on connectivity. Such that my algorithm computes as many
vertexes/edges locally as possible. E.g. for a 2D latice I'm using
http://en.wikipedia.org/wiki/Z-order_curve.

Now I want something similar but for veronoi diagram.

I'm not familiar with graph theory, but I was playing around with
graph-tool and it seems like betweenness and/or communities give me
something what I want. Ideally I want to retrieve indexes which will sort
PropertyMap to exhibit data locality properties (Similar to Z-order curve).

Does graph-tool already does something like this?

Regards,

Dmitrijs.

attachment.html (2.29 KB)

2

Hi Dmitrijs,

Hello,

This is my first post =)

To begin with - what an awesome package! The website is great, the docs are amazing, the code is beautiful, sane autotools usage, very fast, pythonic!
Best software package ever!

Thanks!

Now the slight problem arrises, when my graph + values is bigger than
I can store in RAM.

There is Global Arrays toolkit, which recently got GAiN (Global Arrays
in Numpy) which allow seamlessly use numpy/scipy over shared memory
cluster. But it will give good performance if arrays are exercising
data locality properties.

In my case I want property maps of vertixes & edges to be 'near each
other' based on connectivity. Such that my algorithm computes as many
vertexes/edges locally as possible. E.g. for a 2D latice I'm using
Z-order curve - Wikipedia.

Now I want something similar but for veronoi diagram.

I'm not familiar with graph theory, but I was playing around with
graph-tool and it seems like betweenness and/or communities give me
something what I want. Ideally I want to retrieve indexes which will
sort PropertyMap to exhibit data locality properties (Similar to
Z-order curve).

Does graph-tool already does something like this?

graph-tool does not yet include vertex-ordering routines. In the case of
Delaunay triangulations, the order of the vertices will correspond
exactly to the order of points supplied. Thus, you may provide an
ordered list of points in order to obtain an ordered graph. Locality, in
this case, can be reasonably identified by (euclidean) distance.

Vertex ordering is relatively easy to implement (for a given predefined
order), so you can expect this to be in the next versions.

Note that if you want to _find_ the best partition for any given graph,
this is called the Graph Partition Problem, and is in general NP-hard. A
good starting-point heuristic is the Kernighan-Lin algorithm:

      Kernighan–Lin algorithm - Wikipedia

This is not yet implemented in graph-tool.

Notice however that, unfortunately, there is no way to use GAiN arrays
with graph-tool's algorithms, since they all expect simple (local)
arrays. So I'm not sure you will be able to accomplish much after
ordering your graphs...

Cheers,
Tiago