Hi Dmitrijs, On 01/14/2012 03:38 AM, Dmitrijs Ledkovs wrote:
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 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?
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: http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm 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 -- Tiago de Paula Peixoto <tiago@skewed.de>