giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alessandro Presta (JIRA)" <>
Subject [jira] [Updated] (GIRAPH-547) Allow in-place modification of edges
Date Thu, 14 Mar 2013 23:52:12 GMT


Alessandro Presta updated GIRAPH-547:

    Attachment: GIRAPH-547.patch

- Renamed the current MutableEdge to ReusableEdge, which must be considered a Giraph internal.
Introduced MutableEdge as an edge whose value can be mutated. This is what we expose to the
user when we want to allow in-place mutations.
- Added Vertex#getMutableEdge() which returns an iterable of mutable edges. The remove() method
of its iterator works as expected.
There is a default implementation that builds a new VertexEdges as we iterate, and specialized
implementations where it makes sense.
- Added setEdgeValue() for completeness since we have getEdgeValue().
- Added test cases to cover all default and specialized implementations.
- Removed unused PairListWritable class.
> Allow in-place modification of edges
> ------------------------------------
>                 Key: GIRAPH-547
>                 URL:
>             Project: Giraph
>          Issue Type: New Feature
>            Reporter: Alessandro Presta
>            Assignee: Alessandro Presta
>         Attachments: GIRAPH-547.patch
> This is a somewhat long term item.
> Because of some optimized edge storage implementations (byte array, primitive array),
we have a contract with the user that Edge objects returned by getEdges() are read-only.
> One concrete example where in-place modification would be useful: in the weighted version
of PageRank, you can store the weight sum and normalize each message sent, or you could more
efficiently normalize the out-edges once in superstep 0.
> The Pregel paper describes an OutEdgeIterator that allows for in-place modification of
edges. I can see how that would be easy to implement in C++, where there is no need to reuse
> Giraph "unofficially" supports this if one is using generic collections to represent
edges (e.g. ArrayList or HashMap).
> It may be trickier in some optimized implementations, but in principle it should be doable.
> One way would be to have some special MutableEdge implementation which calls back to
the edge data structure in order to save modifications:
> {code}
> for (Edge<I, E> edge : getEdges()) {
>   edge.setValue(newValue);
> }
> {code}
> Another option would be to add a special set() method to our edge iterator, where one
can replace the current edge:
> {code}
> for (EdgeIterator<I, E> it = getEdges().iterator(); it.hasNext();) {
>   Edge<I, E> edge =;
>   edge.setValue(newValue);
>   it.set(edge);
> }
> {code}
> We could actually implement the first version as syntactic sugar on top of the second
version (the special MutableEdge would need a reference to the iterator in order to call set(this)).

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see:

View raw message