1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * distributed under the License is distributed on an "AS IS" BASIS,14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.15 * See the License for the specific language governing permissions and16 * limitations under the License.17 */1819package org.apache.giraph.edge;
2021import com.google.common.collect.ArrayListMultimap;
22import com.google.common.collect.UnmodifiableIterator;
2324import org.apache.giraph.utils.EdgeIterables;
25import org.apache.giraph.utils.Trimmable;
26import org.apache.hadoop.io.Writable;
27import org.apache.hadoop.io.WritableComparable;
2829import java.io.DataInput;
30import java.io.DataOutput;
31import java.io.IOException;
32import java.util.Iterator;
33import java.util.Map;
3435/**36 * {@link OutEdges} implementation backed by an {@link ArrayListMultimap}.37 * Parallel edges are allowed.38 * Note: this implementation is optimized for fast mutations,39 * but uses more space.40 *41 * @param <I> Vertex id42 * @param <E> Edge value43 */44publicclass HashMultimapEdges<I extends WritableComparable, E extends Writable>
45extends ConfigurableOutEdges<I, E>
46implements MultiRandomAccessOutEdges<I, E>, Trimmable {
47/** Multimap from target vertex id to edge values. */48private ArrayListMultimap<I, E> edgeMultimap;
4950 @Override
51publicvoid initialize(Iterable<Edge<I, E>> edges) {
52 EdgeIterables.initialize(this, edges);
53 }
5455/**56 * Additional initialization method tailored to the underlying multimap57 * implementation.58 *59 * @param expectedNeighbors Expected number of unique neighbors60 * @param expectedEdgesPerNeighbor Expected number of edges per neighbor61 */62publicvoid initialize(int expectedNeighbors, int expectedEdgesPerNeighbor) {
63 edgeMultimap = ArrayListMultimap.create(expectedNeighbors,
64 expectedEdgesPerNeighbor);
65 }
6667 @Override
68publicvoid initialize(int capacity) {
69// To be conservative in terms of space usage, we assume that the initial70// number of values per key is 1.71 initialize(capacity, 1);
72 }
7374 @Override
75publicvoid initialize() {
76 edgeMultimap = ArrayListMultimap.create();
77 }
7879 @Override
80publicvoid add(Edge<I, E> edge) {
81 edgeMultimap.put(edge.getTargetVertexId(), edge.getValue());
82 }
8384 @Override
85publicvoid remove(I targetVertexId) {
86 edgeMultimap.removeAll(targetVertexId);
87 }
8889 @Override
90public Iterable<E> getAllEdgeValues(I targetVertexId) {
91return edgeMultimap.get(targetVertexId);
92 }
9394 @Override
95publicint size() {
96return edgeMultimap.size();
97 }
9899 @Override
100public Iterator<Edge<I, E>> iterator() {
101// Returns an iterator that reuses objects.102returnnew UnmodifiableIterator<Edge<I, E>>() {
103/** Wrapped map iterator. */104private Iterator<Map.Entry<I, E>> mapIterator =
105 edgeMultimap.entries().iterator();
106/** Representative edge object. */107private ReusableEdge<I, E> representativeEdge =
108 getConf().createReusableEdge();
109110 @Override
111publicboolean hasNext() {
112return mapIterator.hasNext();
113 }
114115 @Override
116public Edge<I, E> next() {
117 Map.Entry<I, E> nextEntry = mapIterator.next();
118 representativeEdge.setTargetVertexId(nextEntry.getKey());
119 representativeEdge.setValue(nextEntry.getValue());
120return representativeEdge;
121 }
122 };
123 }
124125 @Override
126publicvoid write(DataOutput out) throws IOException {
127// We write both the total number of edges and the number of unique128// neighbors.129 out.writeInt(edgeMultimap.size());
130 out.writeInt(edgeMultimap.keys().size());
131for (Map.Entry<I, E> edge : edgeMultimap.entries()) {
132 edge.getKey().write(out);
133 edge.getValue().write(out);
134 }
135 }
136137 @Override
138publicvoid readFields(DataInput in) throws IOException {
139// Given the total number of pairs and the number of unique neighbors,140// we are able to compute the average number of edges per neighbors.141int numEdges = in.readInt();
142int numNeighbors = in.readInt();
143 initialize(numEdges, numNeighbors == 0 ? 0 : numEdges / numNeighbors);
144for (int i = 0; i < numEdges; ++i) {
145 I targetVertexId = getConf().createVertexId();
146 targetVertexId.readFields(in);
147 E edgeValue = getConf().createEdgeValue();
148 edgeValue.readFields(in);
149 edgeMultimap.put(targetVertexId, edgeValue);
150 }
151 }
152153 @Override
154publicvoid trim() {
155 edgeMultimap.trimToSize();
156 }
157 }