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.generator; 033 034import java.util.LinkedList; 035 036/** 037 * Generate a Lobster tree. Lobster are trees where the distance between any 038 * node and a root path is less than 2. In this generator, the max distance can 039 * be customized. 040 */ 041public class LobsterGenerator extends BaseGenerator { 042 /** 043 * Max distance from any node to a node of the root path. 044 */ 045 protected int maxDistance = 2; 046 /** 047 * Max degree of nodes. 048 */ 049 protected int maxDegree = 10; 050 /** 051 * Delete some node in step. 052 */ 053 protected boolean delete = false; 054 /** 055 * Average node count. Used in delete-mode to maintain an average count of 056 * nodes. 057 */ 058 protected int averageNodeCount = 200; 059 /** 060 * Used to generate new node index. 061 */ 062 protected int currentIndex = 0; 063 /** 064 * Node data. 065 */ 066 protected LinkedList<Data> nodes; 067 068 /** 069 * Main constructor to a Lobster generator. 070 */ 071 public LobsterGenerator() { 072 this(2, -1); 073 } 074 075 /** 076 * Constructor allowing to customize maximum distance to the root path and 077 * maximum degree of nodes. 078 * 079 * @param maxDistance 080 * max distance to root path 081 * @param maxDegree 082 * max degree of nodes 083 */ 084 public LobsterGenerator(int maxDistance, int maxDegree) { 085 this.maxDistance = maxDistance; 086 this.maxDegree = maxDegree; 087 this.nodes = new LinkedList<Data>(); 088 } 089 090 /** 091 * Constructor allowing to customize maximum distance to the root path. 092 * 093 * @param maxDistance 094 * max distance to root path 095 */ 096 public LobsterGenerator(int maxDistance) { 097 this(maxDistance, -1); 098 } 099 100 /* 101 * (non-Javadoc) 102 * 103 * @see org.graphstream.algorithm.generator.Generator#begin() 104 */ 105 public void begin() { 106 nodes.clear(); 107 add(new Data(newNodeId(), 0, true)); 108 } 109 110 /* 111 * (non-Javadoc) 112 * 113 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 114 */ 115 public boolean nextEvents() { 116 Data connectTo = null; 117 118 do { 119 connectTo = nodes.get(random.nextInt(nodes.size())); 120 } while (connectTo.distance >= maxDistance 121 || (maxDegree > 0 && connectTo.degree() >= maxDegree)); 122 123 Data newData = null; 124 125 if (connectTo.path && connectTo.degree() <= 1) 126 newData = new Data(newNodeId(), 0, true); 127 else 128 newData = new Data(newNodeId(), connectTo.distance + 1, false); 129 130 add(newData); 131 connect(connectTo, newData); 132 133 if (delete && nodes.size() > 1) { 134 double d = Math.min(nodes.size() - averageNodeCount, 135 averageNodeCount / 10); 136 137 d /= averageNodeCount / 10.0; 138 139 if (d > 0 && random.nextFloat() < d) { 140 Data delete = null; 141 142 do { 143 delete = nodes.get(random.nextInt(nodes.size())); 144 } while (delete.degree() > 1); 145 146 delNode(delete); 147 } 148 } 149 150 return true; 151 } 152 153 protected void add(Data data) { 154 nodes.add(data); 155 addNode(data.id); 156 } 157 158 protected void connect(Data d1, Data d2) { 159 d1.connected.add(d2); 160 d2.connected.add(d1); 161 162 addEdge(getEdgeId(d1, d2), d1.id, d2.id); 163 } 164 165 protected void delNode(Data d) { 166 for (Data c : d.connected) { 167 delEdge(getEdgeId(d, c)); 168 c.connected.remove(d); 169 } 170 171 delNode(d.id); 172 nodes.remove(d); 173 } 174 175 protected String newNodeId() { 176 return String.format("%04d", currentIndex++); 177 } 178 179 protected String getEdgeId(Data d1, Data d2) { 180 if (d1.hashCode() > d2.hashCode()) { 181 Data t = d1; 182 d1 = d2; 183 d2 = t; 184 } 185 186 return String.format("%s--%s", d1.id, d2.id); 187 } 188 189 protected static class Data { 190 String id; 191 int distance; 192 boolean path; 193 LinkedList<Data> connected; 194 195 Data(String id, int distance, boolean path) { 196 this.id = id; 197 this.distance = distance; 198 this.connected = new LinkedList<Data>(); 199 this.path = path; 200 } 201 202 int degree() { 203 return connected.size(); 204 } 205 } 206}