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 the Chvatal graph. 036 * 037 * <p> 038 * In the mathematical field of graph theory, the Chvátal graph is an undirected 039 * graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970). It 040 * is triangle-free: its girth (the length of its shortest cycle) is four. It is 041 * 4-regular: each vertex has exactly four neighbors. And its chromatic number 042 * is 4: it can be colored using four colors, but not using only three. It is, 043 * as Chvátal observes, the smallest possible 4-chromatic 4-regular 044 * triangle-free graph; the only smaller 4-chromatic triangle-free graph is the 045 * Grötzsch graph, which has 11 vertices but is not regular. 046 * </p> 047 * 048 * Source : <a 049 * href="http://en.wikipedia.org/wiki/Chv%C3%A1tal_graph">Wikipedia</a> 050 * 051 * @reference Chvátal, V. (1970), 052 * "The smallest triangle-free 4-chromatic 4-regular graph", Journal 053 * of Combinatorial Theory 9 (1): 93–94, 054 * doi:10.1016/S0021-9800(70)80057-6 055 */ 056public class ChvatalGenerator extends BaseGenerator { 057 058 private static final boolean[][] adjacencyMatrix = { 059 { false, true, false, true, true, true, false, false, false, false, 060 false, false }, 061 { false, false, true, false, false, false, true, true, false, 062 false, false, false }, 063 { false, false, false, true, false, false, false, false, true, 064 true, false, false }, 065 { false, false, false, false, false, false, false, false, false, 066 false, true, true }, 067 { false, false, false, false, false, false, false, false, true, 068 true, false, true }, 069 { false, false, false, false, false, false, true, false, true, 070 true, false, false }, 071 { false, false, false, false, false, false, false, false, false, 072 false, true, true }, 073 { false, false, false, false, false, false, false, false, true, 074 false, true, true }, 075 { false, false, false, false, false, false, false, false, false, 076 false, false, false }, 077 { false, false, false, false, false, false, false, false, false, 078 false, true, false }, 079 { false, false, false, false, false, false, false, false, false, 080 false, false, false }, 081 { false, false, false, false, false, false, false, false, false, 082 false, false, false }, }; 083 084 private static final double[][] coordinates = { { 0, 0 }, { 5, 0 }, 085 { 5, 5 }, { 0, 5 }, { 1, 2 }, { 2, 1 }, { 3, 1 }, { 4, 2 }, 086 { 4, 3 }, { 3, 4 }, { 2, 4 }, { 1, 3 } }; 087 088 /* 089 * (non-Javadoc) 090 * 091 * @see org.graphstream.algorithm.generator.Generator#begin() 092 */ 093 public void begin() { 094 for (int i = 0; i < 12; i++) { 095 String id = String.format("%02d", i + 1); 096 097 addNode(id); 098 sendNodeAttributeAdded(sourceId, id, "x", coordinates[i][0]); 099 sendNodeAttributeAdded(sourceId, id, "y", coordinates[i][1]); 100 } 101 102 for (int i = 0; i < 12; i++) { 103 for (int j = i; j < 12; j++) { 104 if (adjacencyMatrix[i][j]) 105 addEdge(String.format("%02d_%02d", i + 1, j + 1), 106 String.format("%02d", i + 1), 107 String.format("%02d", j + 1)); 108 } 109 } 110 } 111 112 /* 113 * (non-Javadoc) 114 * 115 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 116 */ 117 public boolean nextEvents() { 118 return false; 119 } 120}