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 * Flower snark generator. 036 * 037 * <p> 038 * In the mathematical field of graph theory, the flower snarks form an infinite 039 * family of snarks introduced by Rufus Isaacs in 1975. As snarks, the flower 040 * snarks are a connected, bridgeless cubic graphs with chromatic index equal to 041 * 4. The flower snarks are non-planar and non-hamiltonian. 042 * </p> 043 * 044 * Source : <a href="http://en.wikipedia.org/wiki/Flower_snark">Wikipedia</a> 045 * 046 * @reference Isaacs, R. 047 * "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable." 048 * Amer. Math. Monthly 82, 221–239, 1975. 049 */ 050public class FlowerSnarkGenerator extends BaseGenerator { 051 052 private int nextStarNumber = 1; 053 054 /* 055 * (non-Javadoc) 056 * 057 * @see org.graphstream.algorithm.generator.Generator#begin() 058 */ 059 public void begin() { 060 addStar(); 061 addStar(); 062 addStar(); 063 064 addEdge(N.B, 1, N.B, 2); 065 addEdge(N.B, 2, N.B, 3); 066 addEdge(N.B, 3, N.B, 1); 067 068 addEdge(N.C, 1, N.C, 2); 069 addEdge(N.C, 2, N.C, 3); 070 addEdge(N.C, 3, N.D, 1); 071 addEdge(N.D, 1, N.D, 2); 072 addEdge(N.D, 2, N.D, 3); 073 addEdge(N.D, 3, N.C, 1); 074 075 flushCoords(); 076 } 077 078 /* 079 * (non-Javadoc) 080 * 081 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 082 */ 083 public boolean nextEvents() { 084 delEdge(N.B, nextStarNumber - 1, N.B, 1); 085 delEdge(N.C, nextStarNumber - 1, N.D, 1); 086 delEdge(N.D, nextStarNumber - 1, N.C, 1); 087 088 addStar(); 089 090 addEdge(N.B, nextStarNumber - 2, N.B, nextStarNumber - 1); 091 addEdge(N.B, nextStarNumber - 1, N.B, 1); 092 addEdge(N.C, nextStarNumber - 2, N.C, nextStarNumber - 1); 093 addEdge(N.C, nextStarNumber - 1, N.D, 1); 094 addEdge(N.D, nextStarNumber - 2, N.D, nextStarNumber - 1); 095 addEdge(N.D, nextStarNumber - 1, N.C, 1); 096 097 flushCoords(); 098 099 return true; 100 } 101 102 private void addStar() { 103 int i = nextStarNumber++; 104 105 addNode(N.A, i); 106 addNode(N.B, i); 107 addNode(N.C, i); 108 addNode(N.D, i); 109 110 addEdge(N.A, i, N.B, i); 111 addEdge(N.A, i, N.C, i); 112 addEdge(N.A, i, N.D, i); 113 } 114 115 protected static enum N { 116 A, B, C, D 117 } 118 119 private void addNode(N n, int i) { 120 addNode(getNodeId(n, i)); 121 } 122 123 protected String getNodeId(N n, int i) { 124 return String.format("%s%04d", n, i); 125 } 126 127 private void addEdge(N n1, int i1, N n2, int i2) { 128 addEdge(getEdgeId(n1, i1, n2, i2), getNodeId(n1, i1), getNodeId(n2, i2)); 129 } 130 131 private void delEdge(N n1, int i1, N n2, int i2) { 132 delEdge(getEdgeId(n1, i1, n2, i2)); 133 } 134 135 protected String getEdgeId(N n1, int i1, N n2, int i2) { 136 return String.format("%s%s", getNodeId(n1, i1), getNodeId(n2, i2)); 137 } 138 139 protected void flushCoords() { 140 double d = 2 * Math.PI / (nextStarNumber - 1); 141 142 for (int i = 1; i < nextStarNumber; i++) { 143 sendNodeAttributeChanged(sourceId, getNodeId(N.B, i), "x", null, 144 Math.cos((i - 1) * d)); 145 sendNodeAttributeChanged(sourceId, getNodeId(N.B, i), "y", null, 146 Math.sin((i - 1) * d)); 147 148 sendNodeAttributeChanged(sourceId, getNodeId(N.A, i), "x", null, 149 2 * Math.cos((i - 1) * d)); 150 sendNodeAttributeChanged(sourceId, getNodeId(N.A, i), "y", null, 151 2 * Math.sin((i - 1) * d)); 152 153 sendNodeAttributeChanged(sourceId, getNodeId(N.C, i), "x", null, 154 3 * Math.cos((i - 1) * d - d / 4.0)); 155 sendNodeAttributeChanged(sourceId, getNodeId(N.C, i), "y", null, 156 3 * Math.sin((i - 1) * d - d / 4.0)); 157 158 sendNodeAttributeChanged(sourceId, getNodeId(N.D, i), "x", null, 159 3 * Math.cos((i - 1) * d + d / 4.0)); 160 sendNodeAttributeChanged(sourceId, getNodeId(N.D, i), "y", null, 161 3 * Math.sin((i - 1) * d + d / 4.0)); 162 } 163 } 164}