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.randomWalk; 033 034import static org.graphstream.algorithm.Toolkit.randomNode; 035 036import java.util.ArrayList; 037import java.util.Iterator; 038import java.util.LinkedList; 039 040import org.graphstream.graph.Edge; 041import org.graphstream.graph.Node; 042 043/** 044 * A basic entity that chooses edges at random eventually 045 * avoiding some edges based on a memory of recently traversed 046 * edges. 047 */ 048public class TabuEntity extends Entity { 049 /** 050 * The edge memory. 051 */ 052 protected LinkedList<Node> memory; 053 054 /** 055 * The edges weights of the current node. 056 */ 057 protected double weights[]; 058 059 /** 060 * Start the entity on the given node. 061 * @param start The starting node. 062 */ 063 @Override 064 public void init(RandomWalk.Context context, Node start) { 065 super.init(context, start); 066 if(memory != null) 067 memory.clear(); 068 } 069 070 @Override 071 public void step() { 072 tabuStep(); 073 } 074 075 /** 076 * Move the entity from its current node to another via an edge randomly chosen. 077 * 078 * <p> 079 * This method makes a list of all leaving edges of the current node. If the 080 * node has no leaving edge, the entity jumps to another randomly chosen node. 081 * Then an edge is chosen at random in the list of leaving edges. The edge is 082 * chosen uniformly if there are no weights on the edges, else, an edge with 083 * an higher weight has more chances to be chosen than an edge with a lower 084 * weight. 085 * </p> 086 * 087 * <p> 088 * When crossed, if the memory is larger than 0, the edge crossed is remembered 089 * so that the entity will not choose it anew until it crosses as many edges as 090 * the memory size. 091 * </p> 092 */ 093 protected void tabuStep() { 094 int n = current.getOutDegree(); 095 Iterator<? extends Edge> to = current.getLeavingEdgeIterator(); 096 ArrayList<Edge> edges = new ArrayList<Edge>(); 097 098 while (to.hasNext()) { 099 Edge e = to.next(); 100 101 if (!tabu(e.getOpposite(current))) { 102 edges.add(e); 103 } 104 } 105 106 n = edges.size(); 107 108 if (n == 0) { 109 jump(); 110 } else { 111 if (context.weightAttribute != null) { 112 if (weights == null || n > weights.length) 113 weights = new double[n]; 114 115 double sum = 0.0; 116 117 for (int i = 0; i < n; i++) { 118 weights[i] = weight(edges.get(i)); 119 sum += weights[i]; 120 } 121 122 for (int i = 0; i < n; ++i) 123 weights[i] /= sum; 124 125 double r = context.random.nextDouble(); 126 double s = 0; 127 128 for (int i = 0; i < n; i++) { 129 s += weights[i]; 130 131 if (r < s) { 132 cross(edges.get(i)); 133 i = n; 134 } 135 } 136 } else { 137 cross(edges.get(context.random.nextInt(n))); 138 } 139 } 140 } 141 142 /** 143 * Make the entity jump to a randomly chosen node. 144 */ 145 protected void jump() { 146 current = randomNode(context.graph, context.random); 147 context.jumpCount++; 148 } 149 150 /** 151 * Cross the given edge, eventually storing it in the memory and 152 * incrementing its count as well as the count of the current node. 153 * @param e The edge. 154 */ 155 protected void cross(Edge e) { 156 current = e.getOpposite(current); 157 addPass(e, current); 158 addToTabu(current); 159 } 160 161 /** 162 * Increment the count of the given node and edge. 163 * @param e The edge. 164 * @param n The node. 165 */ 166 protected void addPass(Edge e, Node n) { 167 e.setAttribute(context.passesAttribute, e.getNumber(context.passesAttribute) + 1); 168 n.setAttribute(context.passesAttribute, n.getNumber(context.passesAttribute) + 1); 169 } 170 171 /** 172 * Add a node to the tabu list. 173 * @param node The node to avoid. 174 */ 175 protected void addToTabu(Node node) { 176 if (context.entityMemory > 0) { 177 memory.addFirst(node); 178 179 if (memory.size() > context.entityMemory) 180 memory.removeLast(); 181 } 182 } 183 184 /** 185 * Is the given node tabu ? 186 * @param node The node to test. 187 * @return true if the node is tabu. 188 */ 189 protected boolean tabu(Node node) { 190 if (node.hasAttribute("tabu")) 191 return true; 192 193 if (context.entityMemory > 0) { 194 if (memory == null) 195 memory = new LinkedList<Node>(); 196 197 int n = memory.size(); 198 199 for (int i = 0; i < n; i++) { 200 if (node == memory.get(i)) 201 return true; 202 } 203 } 204 205 return false; 206 } 207}