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}