Module org.jgrapht.core
Package org.jgrapht.generate

Class NamedGraphGenerator<V,​E>

  • Type Parameters:
    V - graph vertex type
    E - graph edge type
    public class NamedGraphGenerator<V,​E>
extends java.lang.Object
    Collection of commonly used named graphs
    Author:
    Joris Kinable

    • Constructor Detail

      • NamedGraphGenerator

        public NamedGraphGenerator()
        Constructs a new generator for named graphs

    • Method Detail

      • generateDoyleGraph

        public void generateDoyleGraph​(Graph<V,​E> targetGraph)
        Generates a Doyle Graph. The Doyle graph, sometimes also known as the Holt graph (Marušič et al. 2005), is the quartic symmetric graph on 27 nodes
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generalizedPetersenGraph

        public static Graph<java.lang.Integer,​DefaultEdge> generalizedPetersenGraph​(int n,
                                                                                  int k)
        Parameters:
        n - Generalized Petersen graphs $GP(n,k)$
        k - Generalized Petersen graphs $GP(n,k)$
        Returns:
        Generalized Petersen Graph
        See Also:
        GeneralizedPetersenGraphGenerator

      • generatePetersenGraph

        public void generatePetersenGraph​(Graph<V,​E> targetGraph)
        Generates a Petersen Graph. The Petersen Graph is a named graph that consists of 10 vertices and 15 edges, usually drawn as a five-point star embedded in a pentagon. It is the generalized Petersen graph $GP(5,2)$
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • dürerGraph

        public static Graph<java.lang.Integer,​DefaultEdge> dürerGraph()
        Generates a Dürer Graph. The Dürer graph is the skeleton of Dürer's solid, which is the generalized Petersen graph $GP(6,2)$.
        Returns:
        the Dürer Graph

      • generateDürerGraph

        public void generateDürerGraph​(Graph<V,​E> targetGraph)
        Generates a Dürer Graph. The Dürer graph is the skeleton of Dürer's solid, which is the generalized Petersen graph $GP(6,2)$.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateDodecahedronGraph

        public void generateDodecahedronGraph​(Graph<V,​E> targetGraph)
        Generates a Dodecahedron Graph. The skeleton of the dodecahedron (the vertices and edges) form a graph. It is one of 5 Platonic graphs, each a skeleton of its Platonic solid. It is the generalized Petersen graph $GP(10,2)$
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateDesarguesGraph

        public void generateDesarguesGraph​(Graph<V,​E> targetGraph)
        Generates a Desargues Graph. The Desargues graph is a cubic symmetric graph distance-regular graph on 20 vertices and 30 edges. It is the generalized Petersen graph $GP(10,3)$
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateNauruGraph

        public void generateNauruGraph​(Graph<V,​E> targetGraph)
        Generates a Nauru Graph. The Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It is the generalized Petersen graph $GP(12,5)$
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • möbiusKantorGraph

        public static Graph<java.lang.Integer,​DefaultEdge> möbiusKantorGraph()
        Generates a Möbius-Kantor Graph. The unique cubic symmetric graph on 16 nodes. It is the generalized Petersen graph $GP(8,3)$
        Returns:
        the Möbius-Kantor Graph

      • generateMöbiusKantorGraph

        public void generateMöbiusKantorGraph​(Graph<V,​E> targetGraph)
        Generates a Möbius-Kantor Graph. The unique cubic symmetric graph on 16 nodes. It is the generalized Petersen graph $GP(8,3)$
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBullGraph

        public void generateBullGraph​(Graph<V,​E> targetGraph)
        Generates a Bull Graph. The bull graph is a simple graph on 5 nodes and 5 edges whose name derives from its resemblance to a schematic illustration of a bull or ram
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateButterflyGraph

        public void generateButterflyGraph​(Graph<V,​E> targetGraph)
        Generates a Butterfly Graph. This graph is also known as the "bowtie graph" (West 2000, p. 12). It is isomorphic to the friendship graph $F_2$.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateClawGraph

        public void generateClawGraph​(Graph<V,​E> targetGraph)
        Generates a Claw Graph. The complete bipartite graph $K_{1,3}$ is a tree known as the "claw."
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBuckyBallGraph

        public void generateBuckyBallGraph​(Graph<V,​E> targetGraph)
        Generates a Bucky ball Graph. This graph is a 3-regular 60-vertex planar graph. Its vertices and edges correspond precisely to the carbon atoms and bonds in buckminsterfullerene. When embedded on a sphere, its 12 pentagon and 20 hexagon faces are arranged exactly as the sections of a soccer ball.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateClebschGraph

        public void generateClebschGraph​(Graph<V,​E> targetGraph)
        Generates a Clebsch Graph. The Clebsch graph, also known as the Greenwood-Gleason graph (Read and Wilson, 1998, p. 284), is a strongly regular quintic graph on 16 vertices and 40 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • grötzschGraph

        public static Graph<java.lang.Integer,​DefaultEdge> grötzschGraph()
        Generates a Grötzsch Graph. The Grötzsch graph is smallest triangle-free graph with chromatic number four.
        Returns:
        the Grötzsch Graph

      • generateGrötzschGraph

        public void generateGrötzschGraph​(Graph<V,​E> targetGraph)
        Generates a Grötzsch Graph. The Grötzsch graph is smallest triangle-free graph with chromatic number four.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBidiakisCubeGraph

        public void generateBidiakisCubeGraph​(Graph<V,​E> targetGraph)
        Generates a Bidiakis cube Graph. The 12-vertex graph consisting of a cube in which two opposite faces (say, top and bottom) have edges drawn across them which connect the centers of opposite sides of the faces in such a way that the orientation of the edges added on top and bottom are perpendicular to each other.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBlanusaFirstSnarkGraph

        public void generateBlanusaFirstSnarkGraph​(Graph<V,​E> targetGraph)
        Generates the First Blanusa Snark Graph. The Blanusa graphs are two snarks on 18 vertices and 27 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBlanusaSecondSnarkGraph

        public void generateBlanusaSecondSnarkGraph​(Graph<V,​E> targetGraph)
        Generates the Second Blanusa Snark Graph. The Blanusa graphs are two snarks on 18 vertices and 27 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateDoubleStarSnarkGraph

        public void generateDoubleStarSnarkGraph​(Graph<V,​E> targetGraph)
        Generates the Double Star Snark Graph. A snark on 30 vertices with edge chromatic number 4.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateBrinkmannGraph

        public void generateBrinkmannGraph​(Graph<V,​E> targetGraph)
        Generates the Brinkmann Graph. The Brinkmann graph is a weakly regular quartic graph on 21 vertices and 42 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateGossetGraph

        public void generateGossetGraph​(Graph<V,​E> targetGraph)
        Generates the Gosset Graph. The Gosset graph is a 27-regular graph on 56 vertices which is the skeleton of the Gosset polytope $3_{21}$.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateChvatalGraph

        public void generateChvatalGraph​(Graph<V,​E> targetGraph)
        Generates the Chvatal Graph. The Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970)
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateKittellGraph

        public void generateKittellGraph​(Graph<V,​E> targetGraph)
        Generates the Kittell Graph. The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateCoxeterGraph

        public void generateCoxeterGraph​(Graph<V,​E> targetGraph)
        Generates the Coxeter Graph. The Coxeter graph is a nonhamiltonian cubic symmetric graph on 28 vertices and 42 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateDiamondGraph

        public void generateDiamondGraph​(Graph<V,​E> targetGraph)
        Generates the Diamond Graph. The Diamond graph has 4 vertices and 5 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateEllinghamHorton54Graph

        public void generateEllinghamHorton54Graph​(Graph<V,​E> targetGraph)
        Generates the Ellingham-Horton 54 Graph. The Ellingham–Horton graph is a 3-regular bicubic graph of 54 vertices
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateEllinghamHorton78Graph

        public void generateEllinghamHorton78Graph​(Graph<V,​E> targetGraph)
        Generates the Ellingham-Horton 78 Graph. The Ellingham–Horton graph is a 3-regular graph of 78 vertices
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateErreraGraph

        public void generateErreraGraph​(Graph<V,​E> targetGraph)
        Generates the Errera Graph. The Errera graph is the 17-node planar graph
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateFolkmanGraph

        public void generateFolkmanGraph​(Graph<V,​E> targetGraph)
        Generates the Folkman Graph. The Folkman graph is the 20-vertex 4-regular graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateFranklinGraph

        public void generateFranklinGraph​(Graph<V,​E> targetGraph)
        Generates the Franklin Graph. The Franklin graph is the 12-vertex cubic graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateFruchtGraph

        public void generateFruchtGraph​(Graph<V,​E> targetGraph)
        Generates the Frucht Graph. The Frucht graph is smallest cubic identity graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateGoldnerHararyGraph

        public void generateGoldnerHararyGraph​(Graph<V,​E> targetGraph)
        Generates the Goldner-Harary Graph. The Goldner-Harary graph is a graph on 11 vertices and 27. It is a simplicial graph, meaning that it is polyhedral and consists of only triangular faces.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateHeawoodGraph

        public void generateHeawoodGraph​(Graph<V,​E> targetGraph)
        Generates the Heawood Graph. Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateHerschelGraph

        public void generateHerschelGraph​(Graph<V,​E> targetGraph)
        Generates the Herschel Graph. The Herschel graph is the smallest nonhamiltonian polyhedral graph (Coxeter 1973, p. 8). It is the unique such graph on 11 nodes and 18 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateHoffmanGraph

        public void generateHoffmanGraph​(Graph<V,​E> targetGraph)
        Generates the Hoffman Graph. The Hoffman graph is the bipartite graph on 16 nodes and 32 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateKrackhardtKiteGraph

        public void generateKrackhardtKiteGraph​(Graph<V,​E> targetGraph)
        Generates the Krackhardt kite Graph. The Krackhardt kite is the simple graph on 10 nodes and 18 edges. It arises in social network theory.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateKlein3RegularGraph

        public void generateKlein3RegularGraph​(Graph<V,​E> targetGraph)
        Generates the Klein 3-regular Graph. This graph is a 3-regular graph with 56 vertices and 84 edges, named after Felix Klein.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateKlein7RegularGraph

        public void generateKlein7RegularGraph​(Graph<V,​E> targetGraph)
        Generates the Klein 7-regular Graph. This graph is a 7-regular graph with 24 vertices and 84 edges, named after Felix Klein.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateMoserSpindleGraph

        public void generateMoserSpindleGraph​(Graph<V,​E> targetGraph)
        Generates the Moser spindle Graph. The Moser spindle is the 7-node unit-distance graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generatePappusGraph

        public void generatePappusGraph​(Graph<V,​E> targetGraph)
        Generates the Pappus Graph. The Pappus Graph is a bipartite 3-regular undirected graph with 18 vertices and 27 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generatePoussinGraph

        public void generatePoussinGraph​(Graph<V,​E> targetGraph)
        Generates the Poussin Graph. The Poussin graph is the 15-node planar graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • schläfliGraph

        public static Graph<java.lang.Integer,​DefaultEdge> schläfliGraph()
        Generates the Schläfli Graph. The Schläfli graph is a strongly regular graph on 27 nodes
        Returns:
        the Schläfli Graph

      • generateSchläfliGraph

        public void generateSchläfliGraph​(Graph<V,​E> targetGraph)
        Generates the Schläfli Graph. The Schläfli graph is a strongly regular graph on 27 nodes
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateTietzeGraph

        public void generateTietzeGraph​(Graph<V,​E> targetGraph)
        Generates the Tietze Graph. The Tietze Graph is an undirected cubic graph with 12 vertices and 18 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateThomsenGraph

        public void generateThomsenGraph​(Graph<V,​E> targetGraph)
        Generates the Thomsen Graph. The Thomsen Graph is complete bipartite graph consisting of 6 vertices (3 vertices in each bipartite partition. It is also called the Utility graph.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements

      • generateTutteGraph

        public void generateTutteGraph​(Graph<V,​E> targetGraph)
        Generates the Tutte Graph. The Tutte Graph is a 3-regular graph with 46 vertices and 69 edges.
        Parameters:
        targetGraph - receives the generated edges and vertices; if this is non-empty on entry, the result will be a disconnected graph since generated elements will not be connected to existing elements