Giraph Source Code Analysis (6)-- Edge Analysis

1. In the Vertex class, vertices are stored in the form of adjacency tables. Each vertex has VertexId, VertexValue, OutgoingEdges and Halt. The halt variable of Boolean type is used to record the state of the vertex, and false means active,true represents the state of inactive. The snippet code is as follows.

Cdn.xitu.io/2019/8/12/16c84c9359655583?w=600&h=215&f=png&s=33609 ">

The 2.org.apache.giraph.edge.Edge interface is used to store the edges of vertices, and each edge contains two attributes, targetVertexId and edgeValue. The class diagram is as follows:

By default, Giraph uses the DefaultEdge class to store edges, which has two variables: I targetVertexId and E value,I are the vertex ID type, and E is the edge type. Note that the DefaultEdge class also inherits the ReusableEdge interface, and the definition of the ReusableEdge class contains the following text:

A complete edge, the target vertex and the edge value. Can only be one edge with a destination vertex id per edge map. This edge can be reused, that is you can set it's target vertex ID and edge value. Note: this class is useful for certain optimizations, but it's not meant to be exposed to the user. Look at MutableEdge instead.

As you can see from the above instructions, edge can be reused by changing the values of targetVertexId and value. That is, if each Vertex has multiple outgoing edges, only one DefaultEdge object will be created to store the edges.

3.org.apache.giraph.edge.OutEdges is used to store out-edges for each vertex. As you can see from the definition of the Vertex class, each edge of a vertex is stored in an edge object of type OutEdges, and the diagram of the OutEdges interface is as follows:

Giraph uses ByteArrayEdges by default, and all edges of each vertex are stored in byte []. When a vertex sends a message to its outgoing edge, it needs to traverse the edges object in the Vertex class. The sample code is as follows:

Note: as you can see from the definition of DefaultEdge, when you iterate through getEdges, the Edge object returned is the same object, but the value in the object has changed. Let's move on to the code to prove this point.

Look at the iterator () method of the ByteArrayEdges class, as follows:

The inner class ByteArrayEdgeIterator object is returned, which is defined as follows:

Conclusion: when the output of the vertex is very large, this optimization is very good and can save memory very well. For example, in UK-2005 data, the maximum output of vertices is 5213.

Suppose that the exit vertex of vertex 1 has,. The code is as follows:

The output is as follows:

[2]

[3, 3]

[5, 5, 5]

Not as desired [2, 3, 5]