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 034/** 035 * Banana tree generator. A (n,k)-banana tree is composed of a root node and n 036 * k-stars with one leaf of each star connected to the root node. 037 * 038 * @reference Chen, W. C.; Lü, H. I.; and Yeh, Y. N. 039 * "Operations of Interlaced Trees and Graceful Trees." Southeast 040 * Asian Bull. Math. 21, 337-348, 1997. 041 * 042 */ 043public class BananaTreeGenerator extends BaseGenerator { 044 045 protected int k; 046 protected int currentStarIndex; 047 protected int edgeId; 048 protected boolean setCoordinates; 049 050 /** 051 * Build a new Banana tree generator with default star size. 052 */ 053 public BananaTreeGenerator() { 054 this(4); 055 } 056 057 /** 058 * Build a new Banana tree generator composing of k-stars. 059 * 060 * @param k 061 * size of star 062 */ 063 public BananaTreeGenerator(int k) { 064 this.k = k; 065 this.setCoordinates = true; 066 this.currentStarIndex = 0; 067 this.edgeId = 0; 068 } 069 070 /* 071 * (non-Javadoc) 072 * 073 * @see org.graphstream.algorithm.generator.Generator#begin() 074 */ 075 public void begin() { 076 addNode("root"); 077 } 078 079 /* 080 * (non-Javadoc) 081 * 082 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 083 */ 084 public boolean nextEvents() { 085 addNode(getNodeId(currentStarIndex, 0)); 086 087 for (int i = 1; i < k; i++) { 088 addNode(getNodeId(currentStarIndex, i)); 089 addEdge(String.format("E%04d", edgeId++), 090 getNodeId(currentStarIndex, 0), 091 getNodeId(currentStarIndex, i)); 092 } 093 094 addEdge(String.format("E%04d", edgeId++), 095 getNodeId(currentStarIndex, 1), "root"); 096 097 currentStarIndex++; 098 099 if (setCoordinates) 100 flushCoords(); 101 102 return true; 103 } 104 105 /** 106 * Format node id. 107 * 108 * @param star 109 * index of the star 110 * @param index 111 * index of the node in the star 112 * @return unique node id 113 */ 114 protected String getNodeId(int star, int index) { 115 return String.format("S%02d_%02d", star, index); 116 } 117 118 /** 119 * Set coordinates of nodes. 120 */ 121 protected void flushCoords() { 122 sendNodeAttributeChanged(sourceId, "root", "x", null, 0); 123 sendNodeAttributeChanged(sourceId, "root", "y", null, 0); 124 125 double r1 = 8.0; 126 127 for (int i = 0; i < currentStarIndex; i++) { 128 double a = i * 2 * Math.PI / currentStarIndex; 129 double rx = r1 * Math.cos(a); 130 double ry = r1 * Math.sin(a); 131 132 sendNodeAttributeChanged(sourceId, getNodeId(i, 0), "x", null, rx); 133 sendNodeAttributeChanged(sourceId, getNodeId(i, 0), "y", null, ry); 134 135 for (int j = 1; j < k; j++) { 136 double b = a - (j - 1) * 2 * Math.PI / (k - 1); 137 double r2 = 0.8 * r1 * Math.sin(Math.PI / currentStarIndex); 138 139 sendNodeAttributeChanged(sourceId, getNodeId(i, j), "x", null, 140 rx - r2 * Math.cos(b)); 141 sendNodeAttributeChanged(sourceId, getNodeId(i, j), "y", null, 142 ry - r2 * Math.sin(b)); 143 } 144 } 145 } 146}