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}