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.algorithm.util; 033 034import java.util.ArrayList; 035 036/** 037 * <p> 038 * Fibonacci heap is a data structure used mainly to implement priority queues. 039 * It stores pairs (key, value) in nodes. The structure is designed so that the 040 * following operations can be implemented efficiently: 041 * <ul> 042 * <li>Finding the node with minimal key</li> 043 * <li>Extracting the node with minimal key</li> 044 * <li>Decreasing the key of a given node</li> 045 * <li>Adding a new node</li> 046 * <li>Merging two heaps</li> 047 * <li>Deleting a node</li> 048 * </ul> 049 * 050 * <p> 051 * This implementation does not support directly the last operation, but there 052 * is a workaround. To delete a node, first decrease its key to something less 053 * than the current minimum, then just extract the minimum. 054 * 055 * <p> 056 * In order to compare keys, this implementation uses their natural order: they 057 * must implement {@link java.lang.Comparable} interface. The values can be of 058 * any type. 059 * 060 * <h3>Example</h3> 061 * 062 * <pre> 063 * FibonacciHeap<Integer, String> heap = new FibonacciHeap<Integer, String>(); 064 * // add some nodes and keep their references in order to be able to decrease 065 * // their keys later 066 * FibonacciHeap<Integer, String>.Node nodeA = heap.add(20, "A"); 067 * FibonacciHeap<Integer, String>.Node nodeB = heap.add(10, "B"); 068 * FibonacciHeap<Integer, String>.Node nodeC = heap.add(30, "C"); 069 * FibonacciHeap<Integer, String>.Node nodeD = heap.add(50, "D"); 070 * FibonacciHeap<Integer, String>.Node nodeE = heap.add(40, "E"); 071 * 072 * String s1 = heap.extractMin(); // "B" 073 * String s2 = heap.getMinValue(); // "A" 074 * heap.decreaseKey(nodeD, 5); 075 * String s3 = heap.extractMin(); // "D" 076 * //delete nodeC 077 * int kMin = heap.getMinKey(); // 20 078 * heap.decreaseKey(nodeC, kMin - 1); 079 * String s4 = heap.extractMin(); // C 080 * </pre> 081 * 082 * @author Stefan Balev 083 * 084 * @param <K> 085 * the type of the keys 086 * @param <V> 087 * the type of the values 088 */ 089public class FibonacciHeap<K extends Comparable<K>, V> { 090 091 /** 092 * This class encapsulates pairs (key, value) in nodes stored in Fibonacci 093 * heaps. Objects of this class cannot be instantiated directly. The only 094 * way to obtain a node reference is the return value of 095 * {@link FibonacciHeap#add(Comparable, Object)}. Typically these references 096 * are stored and then used in calls to 097 * {@link FibonacciHeap#decreaseKey(Node, Comparable)}. 098 * 099 * @author Stefan Balev 100 * 101 */ 102 public class Node { 103 protected K key; 104 protected V value; 105 protected Node parent; 106 protected Node child; 107 protected Node left; 108 protected Node right; 109 protected int degree; 110 protected boolean lostChild; 111 112 protected Node(K key, V value) { 113 this.key = key; 114 this.value = value; 115 parent = child = null; 116 left = right = this; 117 degree = 0; 118 lostChild = false; 119 } 120 121 protected void clear() { 122 parent = null; 123 if (child != null) { 124 child.clear(); 125 child = null; 126 } 127 left.right = null; 128 left = null; 129 if (right != null) 130 right.clear(); 131 } 132 133 protected void concatLists(Node y) { 134 Node r = right; 135 Node l = y.left; 136 right = y; 137 y.left = this; 138 l.right = r; 139 r.left = l; 140 } 141 142 protected void addChild(Node y) { 143 y.parent = this; 144 y.left = y.right = y; 145 y.lostChild = false; 146 degree++; 147 if (child == null) 148 child = y; 149 else 150 child.concatLists(y); 151 } 152 153 /** 154 * Returns the key stored in this node. 155 * @return the key stored in this node 156 */ 157 public K getKey() { 158 return key; 159 } 160 161 /** 162 * Returns the value stored in this node. 163 * @return the value stored in this node 164 */ 165 public V getValue() { 166 return value; 167 } 168 } 169 170 protected Node min; 171 protected int size; 172 protected ArrayList<Node> degList; 173 174 /** 175 * Creates a new empty Fibonacci heap. 176 */ 177 public FibonacciHeap() { 178 min = null; 179 size = 0; 180 degList = new ArrayList<Node>(); 181 } 182 183 /** 184 * Checks if the heap is empty. 185 * @return {@code true} if the heap is empty 186 * @complexity O(1) 187 */ 188 public boolean isEmpty() { 189 return size == 0; 190 } 191 192 /** 193 * Returns the number of nodes in the heap. 194 * @return the number of nodes in the heap 195 * @complexity O(1) 196 */ 197 public int size() { 198 return size; 199 } 200 201 /** 202 * Removes all the nodes in the heap 203 * @complexity This operation can be done in O(1) but this implementation takes O(<em>n</em>) 204 * in order to facilitate the garbage collection. 205 */ 206 public void clear() { 207 if (!isEmpty()) { 208 min.clear(); 209 min = null; 210 size = 0; 211 } 212 } 213 214 /** 215 * Adds a new node containing the given key and value to the heap. 216 * @param key the key of the new node 217 * @param value the value of the new node 218 * @return a reference to the new node. Typically this reference is stored and used in subsequent calls to 219 * {@link #decreaseKey(Node, Comparable)} 220 * @complexity O(1) 221 */ 222 public Node add(K key, V value) { 223 Node node = new Node(key, value); 224 if (isEmpty()) 225 min = node; 226 else { 227 min.concatLists(node); 228 if (node.key.compareTo(min.key) < 0) 229 min = node; 230 } 231 size++; 232 return node; 233 } 234 235 /** 236 * Merges two heaps. Warning: <b>this operation is destructive</b>. This method empties the parameter {@code heap}. 237 * @param heap the heap to be merged with this heap 238 * @complexity O(1) 239 */ 240 public void addAll(FibonacciHeap<K, V> heap) { 241 if (isEmpty()) 242 min = heap.min; 243 else if (!heap.isEmpty()) { 244 min.concatLists(heap.min); 245 if (heap.min.key.compareTo(min.key) < 0) 246 min = heap.min; 247 } 248 size += heap.size; 249 heap.min = null; 250 heap.size = 0; 251 } 252 253 /** 254 * Returns the minimal key in the heap. 255 * @return the minimal key in the heap 256 * @complexity O(1) 257 */ 258 public K getMinKey() { 259 return min.key; 260 } 261 262 /** 263 * Returns the value stored in the node containing the minimal key. 264 * @return the value stored in the node containing the minimal key 265 * @complexity O(1) 266 * 267 */ 268 public V getMinValue() { 269 return min.value; 270 } 271 272 /** 273 * Removes the node containing the minimal key from the heap. 274 * @return the value stored in the removed node 275 * @complexity O(log<em>n</em>) amortized running time 276 */ 277 public V extractMin() { 278 Node z = min; 279 Node x = z.child; 280 if (x != null) { 281 do { 282 x.parent = null; 283 x = x.right; 284 } while (x != z.child); 285 z.concatLists(x); 286 z.child = null; 287 } 288 if (z == z.right) 289 min = null; 290 else { 291 z.left.right = z.right; 292 z.right.left = z.left; 293 min = z.right; 294 consolidate(); 295 } 296 z.left = z.right = null; 297 size--; 298 return z.value; 299 } 300 301 protected void consolidate() { 302 Node w, x, y, t; 303 int d; 304 w = min; 305 degList.clear(); 306 do { 307 x = w; 308 w = w.right; 309 d = x.degree; 310 while (d >= degList.size()) 311 degList.add(null); 312 y = degList.get(d); 313 while (y != null) { 314 if (x.key.compareTo(y.key) > 0) { 315 t = x; 316 x = y; 317 y = t; 318 } 319 x.addChild(y); 320 degList.set(d, null); 321 d++; 322 if (d >= degList.size()) 323 degList.add(null); 324 y = degList.get(d); 325 } 326 degList.set(d, x); 327 } while (w != min); 328 329 min = null; 330 for (Node s : degList) 331 if (s != null) { 332 s.left = s.right = s; 333 if (min == null) 334 min = s; 335 else { 336 min.concatLists(s); 337 if (s.key.compareTo(min.key) < 0) 338 min = s; 339 } 340 } 341 } 342 343 /** Decreases the key of a given node 344 * @param x the node whose key is to be decreased. Must be a reference returned by {@link #add(Comparable, Object)}. 345 * @param key the new key 346 * @throws IllegalArgumentException if the new key is greater than the current. 347 * @complexity O(1) amortized running time 348 */ 349 public void decreaseKey(Node x, K key) { 350 if (key.compareTo(x.key) > 0) 351 throw new IllegalArgumentException( 352 "The new key must be less than the old"); 353 x.key = key; 354 Node y = x.parent; 355 if (y != null && x.key.compareTo(y.key) < 0) { 356 detach(x); 357 multiDetach(y); 358 } 359 if (key.compareTo(min.key) < 0) 360 min = x; 361 } 362 363 protected void detach(Node x) { 364 Node y = x.parent; 365 y.degree--; 366 if (x == x.right) 367 y.child = null; 368 else { 369 x.left.right = x.right; 370 x.right.left = x.left; 371 if (y.child == x) 372 y.child = x.right; 373 x.left = x.right = x; 374 } 375 min.concatLists(x); 376 x.parent = null; 377 x.lostChild = false; 378 } 379 380 protected void multiDetach(Node x) { 381 if (x.parent == null) 382 return; 383 if (x.lostChild) { 384 Node z = x.parent; 385 detach(x); 386 multiDetach(z); 387 } else 388 x.lostChild = true; 389 } 390}