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}