001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.graph.implementations; 033 034import java.security.AccessControlException; 035import java.util.Arrays; 036import java.util.Iterator; 037import java.util.NoSuchElementException; 038 039import org.graphstream.graph.Edge; 040import org.graphstream.graph.Node; 041 042/** 043 * Nodes used with {@link AdjacencyListGraph} 044 * 045 */ 046public class AdjacencyListNode extends AbstractNode { 047 protected static final int INITIAL_EDGE_CAPACITY; 048 protected static final double GROWTH_FACTOR = 1.1; 049 050 static { 051 String p = "org.graphstream.graph.node.initialEdgeCapacity"; 052 int initialEdgeCapacity = 16; 053 try { 054 initialEdgeCapacity = Integer.valueOf(System.getProperty(p, "16")); 055 } catch (AccessControlException e) { 056 } 057 INITIAL_EDGE_CAPACITY = initialEdgeCapacity; 058 } 059 060 protected static final char I_EDGE = 0; 061 protected static final char IO_EDGE = 1; 062 protected static final char O_EDGE = 2; 063 064 protected AbstractEdge[] edges; 065 protected int ioStart, oStart, degree; 066 067 // *** Constructor *** 068 069 protected AdjacencyListNode(AbstractGraph graph, String id) { 070 super(graph, id); 071 edges = new AbstractEdge[INITIAL_EDGE_CAPACITY]; 072 ioStart = oStart = degree = 0; 073 } 074 075 // *** Helpers *** 076 077 protected char edgeType(AbstractEdge e) { 078 if (!e.directed || e.source == e.target) 079 return IO_EDGE; 080 return e.source == this ? O_EDGE : I_EDGE; 081 } 082 083 @SuppressWarnings("unchecked") 084 protected <T extends Edge> T locateEdge(Node opposite, char type) { 085 // where to search ? 086 int start = 0; 087 int end = degree; 088 if (type == I_EDGE) 089 end = oStart; 090 else if (type == O_EDGE) 091 start = ioStart; 092 093 for (int i = start; i < end; i++) 094 if (edges[i].getOpposite(this) == opposite) 095 return (T) edges[i]; 096 return null; 097 } 098 099 protected void removeEdge(int i) { 100 if (i >= oStart) { 101 edges[i] = edges[--degree]; 102 edges[degree] = null; 103 return; 104 } 105 106 if (i >= ioStart) { 107 edges[i] = edges[--oStart]; 108 edges[oStart] = edges[--degree]; 109 edges[degree] = null; 110 return; 111 } 112 113 edges[i] = edges[--ioStart]; 114 edges[ioStart] = edges[--oStart]; 115 edges[oStart] = edges[--degree]; 116 edges[degree] = null; 117 118 } 119 120 // *** Callbacks *** 121 122 @Override 123 protected boolean addEdgeCallback(AbstractEdge edge) { 124 // resize edges if necessary 125 if (edges.length == degree) { 126 AbstractEdge[] tmp = new AbstractEdge[(int) (GROWTH_FACTOR * edges.length) + 1]; 127 System.arraycopy(edges, 0, tmp, 0, edges.length); 128 Arrays.fill(edges, null); 129 edges = tmp; 130 } 131 132 char type = edgeType(edge); 133 134 if (type == O_EDGE) { 135 edges[degree++] = edge; 136 return true; 137 } 138 139 if (type == IO_EDGE) { 140 edges[degree++] = edges[oStart]; 141 edges[oStart++] = edge; 142 return true; 143 } 144 145 edges[degree++] = edges[oStart]; 146 edges[oStart++] = edges[ioStart]; 147 edges[ioStart++] = edge; 148 return true; 149 } 150 151 @Override 152 protected void removeEdgeCallback(AbstractEdge edge) { 153 // locate the edge first 154 char type = edgeType(edge); 155 int i = 0; 156 if (type == IO_EDGE) 157 i = ioStart; 158 else if (type == O_EDGE) 159 i = oStart; 160 while (edges[i] != edge) 161 i++; 162 163 removeEdge(i); 164 } 165 166 @Override 167 protected void clearCallback() { 168 Arrays.fill(edges, 0, degree, null); 169 ioStart = oStart = degree = 0; 170 } 171 172 // *** Access methods *** 173 174 @Override 175 public int getDegree() { 176 return degree; 177 } 178 179 @Override 180 public int getInDegree() { 181 return oStart; 182 } 183 184 @Override 185 public int getOutDegree() { 186 return degree - ioStart; 187 } 188 189 @SuppressWarnings("unchecked") 190 @Override 191 public <T extends Edge> T getEdge(int i) { 192 if (i < 0 || i >= degree) 193 throw new IndexOutOfBoundsException("Node \"" + this + "\"" 194 + " has no edge " + i); 195 return (T) edges[i]; 196 } 197 198 @SuppressWarnings("unchecked") 199 @Override 200 public <T extends Edge> T getEnteringEdge(int i) { 201 if (i < 0 || i >= getInDegree()) 202 throw new IndexOutOfBoundsException("Node \"" + this + "\"" 203 + " has no entering edge " + i); 204 return (T) edges[i]; 205 } 206 207 @SuppressWarnings("unchecked") 208 @Override 209 public <T extends Edge> T getLeavingEdge(int i) { 210 if (i < 0 || i >= getOutDegree()) 211 throw new IndexOutOfBoundsException("Node \"" + this + "\"" 212 + " has no edge " + i); 213 return (T) edges[ioStart + i]; 214 } 215 216 @Override 217 public <T extends Edge> T getEdgeBetween(Node node) { 218 return locateEdge(node, IO_EDGE); 219 } 220 221 @Override 222 public <T extends Edge> T getEdgeFrom(Node node) { 223 return locateEdge(node, I_EDGE); 224 } 225 226 @Override 227 public <T extends Edge> T getEdgeToward(Node node) { 228 return locateEdge(node, O_EDGE); 229 } 230 231 // *** Iterators *** 232 233 protected class EdgeIterator<T extends Edge> implements Iterator<T> { 234 protected int iPrev, iNext, iEnd; 235 236 protected EdgeIterator(char type) { 237 iPrev = -1; 238 iNext = 0; 239 iEnd = degree; 240 if (type == I_EDGE) 241 iEnd = oStart; 242 else if (type == O_EDGE) 243 iNext = ioStart; 244 } 245 246 public boolean hasNext() { 247 return iNext < iEnd; 248 } 249 250 @SuppressWarnings("unchecked") 251 public T next() { 252 if (iNext >= iEnd) 253 throw new NoSuchElementException(); 254 iPrev = iNext++; 255 return (T) edges[iPrev]; 256 } 257 258 public void remove() { 259 if (iPrev == -1) 260 throw new IllegalStateException(); 261 AbstractEdge e = edges[iPrev]; 262 // do not call the callback because we already know the index 263 graph.removeEdge(e, true, e.source != AdjacencyListNode.this, 264 e.target != AdjacencyListNode.this); 265 removeEdge(iPrev); 266 iNext = iPrev; 267 iPrev = -1; 268 iEnd--; 269 } 270 } 271 272 @Override 273 public <T extends Edge> Iterator<T> getEdgeIterator() { 274 return new EdgeIterator<T>(IO_EDGE); 275 } 276 277 @Override 278 public <T extends Edge> Iterator<T> getEnteringEdgeIterator() { 279 return new EdgeIterator<T>(I_EDGE); 280 } 281 282 @Override 283 public <T extends Edge> Iterator<T> getLeavingEdgeIterator() { 284 return new EdgeIterator<T>(O_EDGE); 285 } 286}