This project has retired. For details please refer to its Attic page.
EdgeIterables xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * 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 and
16   * limitations under the License.
17   */
18  
19  package org.apache.giraph.utils;
20  
21  import com.google.common.collect.Iterables;
22  import org.apache.giraph.edge.Edge;
23  import org.apache.giraph.edge.EdgeFactory;
24  import org.apache.giraph.edge.OutEdges;
25  import org.apache.hadoop.conf.Configuration;
26  import org.apache.hadoop.io.Writable;
27  import org.apache.hadoop.io.WritableComparable;
28  import org.apache.hadoop.io.WritableUtils;
29  
30  import java.util.ArrayList;
31  import java.util.Collection;
32  import java.util.Collections;
33  import java.util.Comparator;
34  import java.util.Iterator;
35  
36  /**
37   * Utility methods for iterables of edges.
38   */
39  public class EdgeIterables {
40    /** Utility classes shouldn't be instantiated. */
41    private EdgeIterables() { }
42  
43    /**
44     * Compare two edge iterables element-wise. The edge value type needs
45     * to be Comparable.
46     *
47     * @param e1 First edge iterable
48     * @param e2 Second edge iterable
49     * @param <I> Vertex id
50     * @param <E> Edge value
51     * @return Whether the two iterables are equal element-wise
52     */
53    public static <I extends WritableComparable, E extends WritableComparable>
54    boolean equals(Iterable<Edge<I, E>> e1, Iterable<Edge<I, E>> e2) {
55      Iterator<Edge<I, E>> i1 = e1.iterator();
56      Iterator<Edge<I, E>> i2 = e2.iterator();
57      while (i1.hasNext()) {
58        if (!i2.hasNext()) {
59          return false;
60        }
61        if (!EdgeComparator.equal(i1.next(), i2.next())) {
62          return false;
63        }
64      }
65      return true;
66    }
67  
68    /**
69     * Make a deep copy of an edge iterable and return it as an {@link
70     * ArrayList}.
71     * Note: this method is slow since it has to deserialize all serialize all
72     * the ids and values. It should only be used in unit tests.
73     *
74     * @param edges Iterable of edges
75     * @param <I> Vertex id
76     * @param <E> Edge value
77     * @return A new list with copies of all the edges
78     */
79    public static <I extends WritableComparable, E extends WritableComparable>
80    ArrayList<Edge<I, E>> copy(Iterable<Edge<I, E>> edges) {
81      Configuration conf = new Configuration();
82      ArrayList<Edge<I, E>> edgeList =
83          new ArrayList<Edge<I, E>>(Iterables.size(edges));
84      for (Edge<I, E> edge : edges) {
85        edgeList.add(EdgeFactory.create(
86            WritableUtils.clone(edge.getTargetVertexId(), conf),
87            WritableUtils.clone(edge.getValue(), conf)));
88      }
89      return edgeList;
90    }
91  
92    /**
93     * Compare two edge iterables up to reordering. The edge value type needs
94     * to be Comparable.
95     *
96     * @param e1 First edge iterable
97     * @param e2 Second edge iterable
98     * @param <I> Vertex id
99     * @param <E> Edge value
100    * @return Whether the two iterables are equal up to reordering
101    */
102   public static <I extends WritableComparable, E extends WritableComparable>
103   boolean sameEdges(Iterable<Edge<I, E>> e1, Iterable<Edge<I, E>> e2) {
104     ArrayList<Edge<I, E>> edgeList1 = copy(e1);
105     ArrayList<Edge<I, E>> edgeList2 = copy(e2);
106     Comparator<Edge<I, E>> edgeComparator = new EdgeComparator<I, E>();
107     Collections.sort(edgeList1, edgeComparator);
108     Collections.sort(edgeList2, edgeComparator);
109     return equals(edgeList1, edgeList2);
110   }
111 
112   /**
113    * Get the size of edges. Optimized implementation for cases when edges is
114    * instance of {@link OutEdges} or {@link Collection} which only calls
115    * size() method from these classes.
116    *
117    * @param edges Edges
118    * @param <I> Vertex index
119    * @param <E> Edge value
120    * @return Size of edges
121    */
122   public static <I extends WritableComparable, E extends Writable> int size(
123       Iterable<Edge<I, E>> edges) {
124     if (edges instanceof OutEdges) {
125       return ((OutEdges) edges).size();
126     } else {
127       return Iterables.size(edges);
128     }
129   }
130 
131   /**
132    * Initialize edges data structure and add the edges from edgesIterable.
133    *
134    * If edgesIterable is instance of {@link OutEdges} or {@link Collection}
135    * edges will be initialized with size of edgesIterable,
136    * otherwise edges will be initialized without size.
137    *
138    * @param edges Edges to initialize
139    * @param edgesIterable Iterable whose edges to use
140    * @param <I> Vertex index
141    * @param <E> Edge value
142    */
143   public static <I extends WritableComparable, E extends Writable>
144   void initialize(OutEdges<I, E> edges, Iterable<Edge<I, E>> edgesIterable) {
145     if (edgesIterable instanceof OutEdges ||
146         edgesIterable instanceof Collection) {
147       edges.initialize(size(edgesIterable));
148     } else {
149       edges.initialize();
150     }
151     for (Edge<I, E> edge : edgesIterable) {
152       edges.add(edge);
153     }
154     if (edges instanceof Trimmable) {
155       ((Trimmable) edges).trim();
156     }
157   }
158 }