[graph-tool] How to implement graph version of map/reduce

Tiago de Paula Peixoto tiago at skewed.de
Mon Mar 10 10:38:00 CET 2014


On 03/09/2014 05:56 PM, cammil wrote:
>
> Is there a way to implement an arbitrary walking and/or reduction of a
> graph? I feel this is analogous to map/reduce for lists/iterables.
>
> This is my first foray into implementing graphs in software, and I'm not
> sure whether this is possible, desired or already existing in graph-tool
> implementation. I feel this type of functionality is essential if I am to
> use graph-tool for my experimentations.
>
> I am thinking something like: A function called "graph_walk" (which is
> analogous to map) which takes a "walk method" and a mapping function. The
> "walk method" might have several different parameters:
>
> e.g. revisit nodes allowed - Boolean
> maximum nodes to visit - +int
> minimum nodes to visit - +int
> spawn new walkers - function of the node/edge which returns boolean
> algorithm - breadth first / depth first / ...
> randomisation - function returning probability of walking down edge from
> node (defaults to function returning 1)

MapReduce has little meaning outside of a distributed context...

Take a look at the visitor interface in the search module, which seems
to give more or less what you are interested in:

   http://graph-tool.skewed.de/static/doc/search_module.html

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 901 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20140310/610e6112/attachment.asc>


More information about the graph-tool mailing list