giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mayank Pundir (JIRA)" <>
Subject [jira] [Created] (GIRAPH-1032) Perform single and multi-seed Breadth First Search with a single algorithm.
Date Fri, 09 Oct 2015 02:48:26 GMT
Mayank Pundir created GIRAPH-1032:

             Summary: Perform single and multi-seed Breadth First Search with a single algorithm.
                 Key: GIRAPH-1032
             Project: Giraph
          Issue Type: New Feature
            Reporter: Mayank Pundir
            Priority: Minor

The idea is to have a single Breadth First Search implementation which can perform both single-seed
and multi-seed computation with a single algorithm. Multi-seed version maintains not only
the distance from the closest seed but also the closest seed. This can be used for performing
clustering, for example. In both versions, current distance from any of the sources can be
maintained as a global writable. In the multi-seed version, the closest source can be communicated
in messages while the single-seed version requires only empty messages.

This general implementation can accept two functions from the user:
- a function called initializeVertex (vertex, value) -> message that initializes the vertex
value and returns the message to be sent to its neighbors.
- a function called traverseVertex (vertex, value, messages) -> message that gets at most
once on each vertex. This function is called when the BFS traverses the vertex. 
Additionally, the implementation can accept the class type of the messages. This implementation
needs to be backward-compatible and support applications that were using previous BFS interface.

This message was sent by Atlassian JIRA

View raw message