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 }