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}