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.HashSet; 035 036/** 037 * Build a graph using a lcf notation. 038 * 039 * Source : <a href="http://en.wikipedia.org/wiki/LCF_notation">Wikipedia</a> 040 * 041 */ 042public class LCFGenerator extends BaseGenerator { 043 044 /** 045 * Model a LCF notation. Such notations are noted [a0,a1,...,an]^k. This is 046 * translate as LCF object in this way : 047 * 048 * <pre> 049 * new LCF(k, a0, a1, ..., an) 050 * </pre> 051 * 052 */ 053 public static class LCF { 054 int repeat; 055 int[] steps; 056 057 public LCF(int repeat, int... steps) { 058 this.repeat = repeat; 059 this.steps = steps; 060 } 061 } 062 063 private int n; 064 private int initialRingSize; 065 private HashSet<String> crossed; 066 protected LCF lcf; 067 protected boolean canBeExtended; 068 069 /** 070 * Build a new graph generator using a LCF notation. 071 * 072 * @param lcf 073 * the lcf notation describing the graph 074 * @param initialRingSize 075 * initial amount of nodes 076 * @param canBeExtended 077 * true if the graph can be extended, ie. if a node can be added 078 * in a new #nextEvents() call 079 */ 080 public LCFGenerator(LCF lcf, int initialRingSize, boolean canBeExtended) { 081 this.lcf = lcf; 082 this.crossed = new HashSet<String>(); 083 this.initialRingSize = initialRingSize; 084 this.canBeExtended = canBeExtended; 085 } 086 087 /* 088 * (non-Javadoc) 089 * 090 * @see org.graphstream.algorithm.generator.Generator#begin() 091 */ 092 public void begin() { 093 addNode(getNodeId(0)); 094 addNode(getNodeId(1)); 095 addNode(getNodeId(2)); 096 097 addEdge(getEdgeId(0, 1), getNodeId(0), getNodeId(1)); 098 addEdge(getEdgeId(1, 2), getNodeId(1), getNodeId(2)); 099 addEdge(getEdgeId(2, 0), getNodeId(2), getNodeId(0)); 100 101 n = 3; 102 103 for (int i = n; i < initialRingSize; i++) 104 increaseRing(); 105 106 flushCoords(); 107 makeLCF(); 108 } 109 110 /* 111 * (non-Javadoc) 112 * 113 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 114 */ 115 public boolean nextEvents() { 116 if (canBeExtended) { 117 increaseRing(); 118 makeLCF(); 119 flushCoords(); 120 } 121 122 return canBeExtended; 123 } 124 125 protected void increaseRing() { 126 addNode(getNodeId(n)); 127 128 delEdge(getEdgeId(n - 1, 0)); 129 addEdge(getEdgeId(n - 1, n), getNodeId(n - 1), getNodeId(n)); 130 addEdge(getEdgeId(n, 0), getNodeId(n), getNodeId(0)); 131 132 n++; 133 } 134 135 protected void makeLCF() { 136 int i = 0; 137 int r = 0; 138 HashSet<String> added = new HashSet<String>(); 139 140 while (r < lcf.repeat && i < n) { 141 for (int k = 0; k < lcf.steps.length && i < n; k++) { 142 int j = (i + lcf.steps[k]) % n; 143 144 while (j < 0) 145 j += n; 146 147 String edge = getEdgeId(i, j); 148 149 if (!crossed.contains(edge) && !added.contains(edge)) 150 addEdge(edge, getNodeId(i), getNodeId(j)); 151 152 added.add(edge); 153 i++; 154 } 155 156 r++; 157 } 158 159 for (String edge : crossed) { 160 if (!added.contains(edge)) 161 delEdge(edge); 162 } 163 164 crossed.clear(); 165 crossed = added; 166 } 167 168 protected void flushCoords() { 169 double d = 2 * Math.PI / n; 170 171 for (int i = 0; i < n; i++) { 172 sendNodeAttributeChanged(sourceId, getNodeId(i), "x", null, 173 Math.cos(i * d)); 174 sendNodeAttributeChanged(sourceId, getNodeId(i), "y", null, 175 Math.sin(i * d)); 176 } 177 } 178 179 protected String getNodeId(int i) { 180 return String.format("%03d", i); 181 } 182 183 protected String getEdgeId(int i1, int i2) { 184 if (i1 > i2) { 185 int t = i1; 186 i1 = i2; 187 i2 = t; 188 } 189 190 return String.format("%03d_%03d", i1, i2); 191 } 192}