This project has retired. For details please refer to its Attic page.
DefaultVertexResolver 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.graph;
20  
21  import org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable;
22  import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
23  import org.apache.giraph.edge.Edge;
24  import org.apache.hadoop.io.Writable;
25  import org.apache.hadoop.io.WritableComparable;
26  import org.apache.log4j.Logger;
27  
28  /**
29   * Default implementation of how to resolve vertex creation/removal, messages
30   * to nonexistent vertices, etc.
31   *
32   * @param <I> Vertex id
33   * @param <V> Vertex data
34   * @param <E> Edge data
35   */
36  @SuppressWarnings("rawtypes")
37  public class DefaultVertexResolver<I extends WritableComparable,
38      V extends Writable, E extends Writable>
39      extends DefaultImmutableClassesGiraphConfigurable<I, V, E>
40      implements VertexResolver<I, V, E> {
41    /** Class logger */
42    private static final Logger LOG = Logger.getLogger(
43        DefaultVertexResolver.class);
44  
45    /** Whether to create vertices when they receive a message */
46    private boolean createVertexesOnMessages = true;
47  
48    @Override
49    public Vertex<I, V, E> resolve(
50        I vertexId,
51        Vertex<I, V, E> vertex,
52        VertexChanges<I, V, E> vertexChanges,
53        boolean hasMessages) {
54      // This is the default vertex resolution algorithm
55  
56      // 1. If the vertex exists, first prune the edges
57      removeEdges(vertex, vertexChanges);
58  
59      // 2. If vertex removal desired, remove the vertex.
60      vertex = removeVertexIfDesired(vertex, vertexChanges);
61  
62      // 3. If creation of vertex desired, pick first vertex
63      // 4. If vertex doesn't exist, but got messages or added edges, create
64      vertex = addVertexIfDesired(vertexId, vertex, vertexChanges, hasMessages);
65  
66      // 5. If edge addition, add the edges
67      addEdges(vertex, vertexChanges);
68  
69      return vertex;
70    }
71  
72    /**
73     * Remove edges as specifed in changes given.
74     *
75     * @param vertex Vertex to remove edges from
76     * @param vertexChanges contains list of edges to remove.
77     */
78    protected void removeEdges(Vertex<I, V, E> vertex,
79                               VertexChanges<I, V, E> vertexChanges) {
80      if (vertex == null) {
81        return;
82      }
83      if (hasEdgeRemovals(vertexChanges)) {
84        for (I removedDestVertex : vertexChanges.getRemovedEdgeList()) {
85          vertex.removeEdges(removedDestVertex);
86        }
87      }
88    }
89  
90    /**
91     * Remove the vertex itself if the changes desire it. The actual removal is
92     * notified by returning null. That is, this method does not do the actual
93     * removal but rather returns null if it should be done.
94     *
95     * @param vertex Vertex to remove.
96     * @param vertexChanges specifies if we should remove vertex
97     * @return null if vertex should be removed, otherwise the vertex itself.
98     */
99    protected Vertex<I, V, E> removeVertexIfDesired(
100       Vertex<I, V, E> vertex,
101       VertexChanges<I, V, E> vertexChanges) {
102     if (hasVertexRemovals(vertexChanges)) {
103       vertex = null;
104     }
105     return vertex;
106   }
107 
108   /**
109    * Add the Vertex if desired. Returns the vertex itself, or null if no vertex
110    * added.
111    *
112    * @param vertexId ID of vertex
113    * @param vertex Vertex, if not null just returns it as vertex already exists
114    * @param vertexChanges specifies if we should add the vertex
115    * @param hasMessages true if this vertex received any messages
116    * @return Vertex created or passed in, or null if no vertex should be added
117    */
118   protected Vertex<I, V, E> addVertexIfDesired(
119       I vertexId,
120       Vertex<I, V, E> vertex,
121       VertexChanges<I, V, E> vertexChanges,
122       boolean hasMessages) {
123     if (vertex == null) {
124       if (hasVertexAdditions(vertexChanges)) {
125         vertex = vertexChanges.getAddedVertexList().get(0);
126       } else if ((hasMessages && createVertexesOnMessages) ||
127                  hasEdgeAdditions(vertexChanges)) {
128         vertex = getConf().createVertex();
129         vertex.initialize(vertexId, getConf().createVertexValue());
130       }
131     } else if (hasVertexAdditions(vertexChanges)) {
132       LOG.warn("resolve: Tried to add a vertex with id = " +
133           vertex.getId() + " when one already " +
134           "exists.  Ignoring the add vertex request.");
135     }
136     return vertex;
137   }
138 
139   /**
140    * Add edges to the Vertex.
141    *
142    * @param vertex Vertex to add edges to
143    * @param vertexChanges contains edges to add
144    */
145   protected void addEdges(Vertex<I, V, E> vertex,
146                           VertexChanges<I, V, E> vertexChanges) {
147     if (vertex == null) {
148       return;
149     }
150     if (hasEdgeAdditions(vertexChanges)) {
151       for (Edge<I, E> edge : vertexChanges.getAddedEdgeList()) {
152         vertex.addEdge(edge);
153       }
154     }
155   }
156 
157   /**
158    * Check if changes contain vertex removal requests
159    *
160    * @param changes VertexChanges to check
161    * @return true if changes contains vertex removal requests
162    */
163   protected  boolean hasVertexRemovals(VertexChanges<I, V, E> changes) {
164     return changes != null && changes.getRemovedVertexCount() > 0;
165   }
166 
167   /**
168    * Check if changes contain vertex addition requests
169    *
170    * @param changes VertexChanges to check
171    * @return true if changes contains vertex addition requests
172    */
173   protected boolean hasVertexAdditions(VertexChanges<I, V, E> changes) {
174     return changes != null && !changes.getAddedVertexList().isEmpty();
175   }
176 
177   /**
178    * Check if changes contain edge addition requests
179    *
180    * @param changes VertexChanges to check
181    * @return true if changes contains edge addition requests
182    */
183   protected boolean hasEdgeAdditions(VertexChanges<I, V, E> changes) {
184     return changes != null && !changes.getAddedEdgeList().isEmpty();
185   }
186 
187   /**
188    * Check if changes contain edge removal requests
189    *
190    * @param changes VertexChanges to check
191    * @return true if changes contains edge removal requests
192    */
193   protected boolean hasEdgeRemovals(VertexChanges<I, V, E> changes) {
194     return changes != null && !changes.getRemovedEdgeList().isEmpty();
195   }
196 
197   @Override
198   public void setConf(ImmutableClassesGiraphConfiguration<I, V, E> conf) {
199     super.setConf(conf);
200     createVertexesOnMessages = conf.getResolverCreateVertexOnMessages();
201   }
202 }