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 * Generate a Petersen graph.
036 * 
037 * <p>
038 * In the mathematical field of graph theory, the Petersen graph is an
039 * undirected graph with 10 vertices and 15 edges. It is a small graph that
040 * serves as a useful example and counterexample for many problems in graph
041 * theory. The Petersen graph is named for Julius Petersen, who in 1898
042 * constructed it to be the smallest bridgeless cubic graph with no
043 * three-edge-coloring. Although the graph is generally credited to Petersen, it
044 * had in fact first appeared 12 years earlier, in a paper by A. B. Kempe
045 * (1886). Donald Knuth states that the Petersen graph is "a remarkable
046 * configuration that serves as a counterexample to many optimistic predictions
047 * about what might be true for graphs in general."
048 * </p>
049 * 
050 * Source : <a href="http://en.wikipedia.org/wiki/Petersen_graph">Wikipedia</a>
051 * 
052 * @reference Petersen, Julius (1898), "Sur le théorème de Tait",
053 *            L'Intermédiaire des Mathématiciens 5: 225–227.
054 * 
055 */
056public class PetersenGraphGenerator extends BaseGenerator {
057
058        private int[][] nodes = { { 0, 2, 4, 1, 3 }, { 7, 6, 5, 9, 8 } };
059
060        /*
061         * (non-Javadoc)
062         * 
063         * @see org.graphstream.algorithm.generator.Generator#begin()
064         */
065        public void begin() {
066                makeCycle(0, 4);
067                makeCycle(5, 9);
068
069                double a = Math.PI / 2.0;
070                double d = 2.0 * Math.PI / 5.0;
071
072                for (int i = 0; i < 5; i++) {
073                        String id1 = getNodeId(nodes[0][i]);
074                        String id2 = getNodeId(nodes[1][i]);
075
076                        addEdge(getEdgeId(nodes[0][i], nodes[1][i]), id1, id2);
077
078                        double x = Math.cos(a);
079                        double y = Math.sin(a);
080
081                        sendNodeAttributeAdded(sourceId, id1, "x", x);
082                        sendNodeAttributeAdded(sourceId, id1, "y", y);
083
084                        sendNodeAttributeAdded(sourceId, id2, "x", 2 * x);
085                        sendNodeAttributeAdded(sourceId, id2, "y", 2 * y);
086
087                        a += d;
088                }
089        }
090
091        /*
092         * (non-Javadoc)
093         * 
094         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
095         */
096        public boolean nextEvents() {
097                return false;
098        }
099
100        protected void makeCycle(int i, int j) {
101                for (int k = i; k <= j; k++) {
102                        addNode(getNodeId(k));
103
104                        if (k > i)
105                                addEdge(getEdgeId(k - 1, k), getNodeId(k - 1), getNodeId(k));
106                }
107
108                addEdge(getEdgeId(i, j), getNodeId(i), getNodeId(j));
109        }
110
111        protected String getNodeId(int i) {
112                return String.format("%02d", i);
113        }
114
115        protected String getEdgeId(int i, int j) {
116                if (i > j) {
117                        j += i;
118                        i = j - i;
119                        j -= i;
120                }
121
122                return String.format("(%s;%s)", getNodeId(i), getNodeId(j));
123        }
124}