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.examples;
20
21 import org.apache.giraph.graph.BasicComputation;
22 import org.apache.giraph.edge.Edge;
23 import org.apache.giraph.utils.ArrayListWritable;
24 import org.apache.giraph.graph.Vertex;
25 import org.apache.hadoop.io.IntWritable;
26 import org.apache.hadoop.io.NullWritable;
27
28 import com.google.common.base.Objects;
29 import com.google.common.collect.Maps;
30 import com.google.common.collect.Sets;
31
32 import java.io.IOException;
33 import java.util.Map;
34 import java.util.Set;
35
36 /**
37 * Demonstrates triangle closing in simple,
38 * unweighted graphs for Giraph.
39 *
40 * Triangle Closing: Vertex A and B maintain out-edges to C and D
41 * The algorithm, when finished, populates all vertices' value with an
42 * array of Writables representing all the vertices that each
43 * should form an out-edge to (connect with, if this is a social
44 * graph.)
45 * In this example, vertices A and B would hold empty arrays
46 * since they are already connected with C and D. Results:
47 * If the graph is undirected, C would hold value, D and D would
48 * hold value C, since both are neighbors of A and B and yet both
49 * were not previously connected to each other.
50 *
51 * In a social graph, the result values for vertex X would represent people
52 * that are likely a part of a person X's social circle (they know one or more
53 * people X is connected to already) but X had not previously met them yet.
54 * Given this new information, X can decide to connect to vertices (peoople) in
55 * the result array or not.
56 *
57 * Results at each vertex are ordered in terms of the # of neighbors
58 * who are connected to each vertex listed in the final vertex value.
59 * The more of a vertex's neighbors who "know" someone, the stronger
60 * your social relationship is presumed to be to that vertex (assuming
61 * a social graph) and the more likely you should connect with them.
62 *
63 * In this implementation, Edge Values are not used, but could be
64 * adapted to represent additional qualities that could affect the
65 * ordering of the final result array.
66 */
67 public class SimpleTriangleClosingComputation extends BasicComputation<
68 IntWritable, SimpleTriangleClosingComputation.IntArrayListWritable,
69 NullWritable, IntWritable> {
70 /** Vertices to close the triangle, ranked by frequency of in-msgs */
71 private Map<IntWritable, Integer> closeMap =
72 Maps.<IntWritable, Integer>newHashMap();
73
74 @Override
75 public void compute(
76 Vertex<IntWritable, IntArrayListWritable, NullWritable> vertex,
77 Iterable<IntWritable> messages) throws IOException {
78 if (getSuperstep() == 0) {
79 // send list of this vertex's neighbors to all neighbors
80 for (Edge<IntWritable, NullWritable> edge : vertex.getEdges()) {
81 sendMessageToAllEdges(vertex, edge.getTargetVertexId());
82 }
83 } else {
84 for (IntWritable message : messages) {
85 final int current = (closeMap.get(message) == null) ?
86 0 : closeMap.get(message) + 1;
87 closeMap.put(message, current);
88 }
89 // make sure the result values are sorted and
90 // packaged in an IntArrayListWritable for output
91 Set<Pair> sortedResults = Sets.<Pair>newTreeSet();
92 for (Map.Entry<IntWritable, Integer> entry : closeMap.entrySet()) {
93 sortedResults.add(new Pair(entry.getKey(), entry.getValue()));
94 }
95 IntArrayListWritable
96 outputList = new IntArrayListWritable();
97 for (Pair pair : sortedResults) {
98 if (pair.value > 0) {
99 outputList.add(pair.key);
100 } else {
101 break;
102 }
103 }
104 vertex.setValue(outputList);
105 }
106 vertex.voteToHalt();
107 }
108
109 /** Quick, immutable K,V storage for sorting in tree set */
110 public static class Pair implements Comparable<Pair> {
111 /** key
112 * @param key the IntWritable key */
113 private final IntWritable key;
114 /** value
115 * @param value the Integer value */
116 private final Integer value;
117 /** Constructor
118 * @param k the key
119 * @param v the value
120 */
121 public Pair(IntWritable k, Integer v) {
122 key = k;
123 value = v;
124 }
125 /** key getter
126 * @return the key */
127 public IntWritable getKey() { return key; }
128 /** value getter
129 * @return the value */
130 public Integer getValue() { return value; }
131 /** Comparator to quickly sort by values
132 * @param other the Pair to compare with THIS
133 * @return the comparison value as an integer */
134 @Override
135 public int compareTo(Pair other) {
136 return other.value - this.value;
137 }
138
139 @Override
140 public boolean equals(Object obj) {
141 if (this == obj) {
142 return true;
143 }
144 if (obj instanceof Pair) {
145 Pair other = (Pair) obj;
146 return Objects.equal(value, other.value);
147 }
148 return false;
149 }
150
151 @Override
152 public int hashCode() {
153 return Objects.hashCode(value);
154 }
155 }
156
157 /** Utility class for delivering the array of vertices THIS vertex
158 * should connect with to close triangles with neighbors */
159 public static class IntArrayListWritable
160 extends ArrayListWritable<IntWritable> {
161 /** Default constructor for reflection */
162 public IntArrayListWritable() {
163 super();
164 }
165 /** Set storage type for this ArrayListWritable */
166 @Override
167 @SuppressWarnings("unchecked")
168 public void setClass() {
169 setClass(IntWritable.class);
170 }
171 }
172 }