[jira] [Commented] (GIRAPH-141) mulitgraph support in giraph

[Alessandro Presta (JIRA)]

    [ 
https://issues.apache.org/jira/browse/GIRAPH-141?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13402234#comment-13402234
 ] 

Alessandro Presta commented on GIRAPH-141:
------------------------------------------

Here's another way to look at this: each edge has an associated id of type J, 
and the underlying BasicVertex will have edge value type WritableMap<J, E> 
(assume that WritableMap exists).

{code:java}

/**
 * Basic multigraph vertex.
 *
 * @param <I> Vertex id
 * @param <V> Vertex data
 * @param <J> Edge id
 * @param <E> Edge data
 * @param <M> Message data
 */
public abstract class BasicMultiVertex<I extends WritableComparable,
    V extends Writable, J extends WritableComparable, E extends Writable,
    M extends Writable> extends
    BasicVertex<I, V, WritableMap<J, E>, M> {

  // Iterates over all multi-edges
  // i.e. only returns one copy of the target vertex id for multiple edges
  // to that vertex
  @Override
  public abstract Iterator<I> iterator();

  // Iterates over all actual edges
  public abstract Iterator<Pair<I, J>> multiIterator();

  // Returns the multi-edge (i.e. a map edge id => edge value) to target
  // vertex
  @Override
  public abstract WritableMap<J, E> getEdgeValue(I targetVertexId);

  // Returns the single edge to target vertex and given edge id
  public abstract E getEdgeValue(I targetVertexId, J edgeId);

  // True iff there is a multi-edge (i.e. non-empty map)
  @Override
  public abstract boolean hasEdge(I targetVertexId);

  // Return actual number of edges (i.e. count multi-edges with proper
  // multiplicity)
  // NOTE:  this would break any algorithm that assumes the size of
  // iterator() to be equal to getNumOutEdges()
  @Override
  public abstract int getNumOutEdges();

  // Return the number of multi-edges (i.e. disregarding multiplicity)
  public abstract int getNumOutMultiEdges();

  // I guess here we send multiple copies of the same message.
  // I think actual multigraph algorithms wouldn't use this method anyway...
  // we could also add sendMsgToAllMultiEdges() which sends only one copy
  @Override
  public void sendMsgToAllEdges(M msg);
}

public class MutableMultiVertex<I extends WritableComparable,
    V extends Writable, J extends WritableComparable, E extends Writable,
    M extends Writable>
    extends BasicMultiVertex<I, V, J, E, M> {

  // generate new unused edge id (e.g. increment an integer counter)
  protected abstract J generateNewEdgeId();

  // specify the edge id
  public abstract boolean addEdge(I targetVertexId, J edgeId, E edgeValue);

  // uses a new unique edge id
  public boolean addEdge(I targetVertexId, E edgeValue) {
    return addEdge(targetVertexId, generateNewEdgeId(), edgeValue);
  }

  // this shouldn't change
  public void addEdgeRequest(I sourceVertexId, Edge<I, E> edge) {
    // ...
  }

  // we specify the edge id and we're good to go
  public void removeEdgeRequest(I sourceVertexId, I destVertexId, J edgeId) {
    // ...
  }
}
{code}

What do you think?
                
> mulitgraph support in giraph
> ----------------------------
>
>                 Key: GIRAPH-141
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-141
>             Project: Giraph
>          Issue Type: Improvement
>          Components: graph
>            Reporter: André Kelpe
>
> The current vertex API only supports simple graphs, meaning that there can 
> only ever be one edge between two vertices. Many graphs like the road network 
> are in fact multigraphs, where many edges can connect two vertices at the 
> same time.
> Support for this could be added by introducing an Iterator<EdgeWritable> 
> getEdgeValue() or a similar construct. Maybe introducing a slim object like a 
> Connector between the edge and the vertex is also a good idea, so that you 
> could do something like:
> {code} 
> for (final Connector<EdgeWritable, VertexWritable> conn: getEdgeValues(){
>      final EdgeWritable edge = conn.getEdge();
>      final VertexWritable otherVertex = conn.getOther();
>      doInterestingStuff(otherVertex);
>      doMoreInterestingStuff(edge);
> }
> {code} 

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: 
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira