This project has retired. For details please refer to its Attic page.
SccVertexValue 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  package org.apache.giraph.examples.scc;
19  
20  import it.unimi.dsi.fastutil.longs.LongArrayList;
21  
22  import java.io.DataInput;
23  import java.io.DataOutput;
24  import java.io.IOException;
25  
26  import org.apache.hadoop.io.Writable;
27  
28  /**
29   * Vertex value for the Strongly Connected Components algorithm. It keeps track
30   * of the parents of the vertex in order to traverse the graph backwards.
31   */
32  public class SccVertexValue implements Writable {
33  
34    /** Vertex's parents **/
35    private LongArrayList parents;
36  
37    /** Current vertex value **/
38    private long value = Long.MIN_VALUE;
39  
40    /** Indicates whether the vertex was trimmed, hence,
41     * it can't be part of the computation anymore.
42     */
43    private boolean active = true;
44  
45    /**
46     * Public constructor required for serialization.
47     */
48    public SccVertexValue() {
49    }
50  
51    /**
52     * Constructor
53     * @param value Initial value for this vertex.
54     */
55    public SccVertexValue(long value) {
56      this.value = value;
57    }
58  
59    @Override
60    public void readFields(DataInput in) throws IOException {
61      value = in.readLong();
62  
63      int size = in.readInt();
64      if (size != 0) {
65        for (int i = 0; i < size; i++) {
66          addParent(in.readLong());
67        }
68      }
69  
70      active = in.readBoolean();
71    }
72  
73    @Override
74    public void write(DataOutput out) throws IOException {
75      out.writeLong(value);
76  
77      int size = parents == null ? 0 : parents.size();
78      out.writeInt(size);
79      if (size != 0) {
80        for (long incomingId : parents) {
81          out.writeLong(incomingId);
82        }
83      }
84  
85      out.writeBoolean(active);
86    }
87  
88    /**
89     * Returns the list of parent vertices, i.e., vertices that are at the other
90     * end of incoming edges. If the vertex doesn't have any incoming edge, it
91     * returns null.
92     * @return List of the vertex's parents.
93     */
94    public LongArrayList getParents() {
95      return parents;
96    }
97  
98    /**
99     * Adds a vertex id to the list of parent vertices.
100    * @param vertexId It of the parent vertex.
101    */
102   public void addParent(long vertexId) {
103     // Initialize the list of parent vertices only when one attempts to add
104     // the first item, so we save some memory on vertices that have no incoming
105     // edges
106     if (parents == null) {
107       parents = new LongArrayList();
108     }
109     parents.add(vertexId);
110   }
111 
112   /**
113    * Clear parents list.
114    */
115   public void clearParents() {
116     parents = null;
117   }
118 
119   /**
120    * Sets the vertex value. At the end of the SCC computation, vertices with the
121    * same vertex value are part of the same component.
122    * @param value Vertex value.
123    */
124   public void set(long value) {
125     this.value = value;
126   }
127 
128   /**
129    * Returns the vertex value. At the end of the SCC computation, vertices with
130    * the same vertex value are part of the same component.
131    * @return Current vertex value.
132    */
133   public long get() {
134     return value;
135   }
136 
137   /**
138    * Remove this vertex from the computation.
139    */
140   public void deactivate() {
141     this.active = false;
142   }
143 
144   /**
145    * Indicates whether the vertex was removed in a Trimming phase.
146    * @return True if the vertex was trimmed, otherwise, return false.
147    */
148   public boolean isActive() {
149     return active;
150   }
151 
152   @Override
153   public String toString() {
154     return String.valueOf(value);
155   }
156 
157 }