Package org.graph4j.generators

Class RandomChordalGraphGenerator

java.lang.Object
org.graph4j.generators.AbstractGraphGenerator
org.graph4j.generators.RandomChordalGraphGenerator
public class RandomChordalGraphGenerator extends AbstractGraphGenerator
Generates a random chordal graph. A chordal graph is a graph where every cycle of four or more vertices has a chord. A chord is an edge that connects two non-consecutive vertices within the cycle, but it's not part of the cycle itself. Reference: Oylum Seeker, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taskin, (2022). Generation of random chordal graphs using subtrees of a tree. RAIRO - Operations Research. 56. 10.1051/ro/2022027.
Author:
Cristian Frăsinaru
See Also:

  • Constructor Details

    • RandomChordalGraphGenerator

      public RandomChordalGraphGenerator(int numVertices)
      Creates a generator for random chordal graphs with the specified number of vertices.
      Parameters:
      numVertices - the number of vertices of the generated graph.

    • RandomChordalGraphGenerator

      public RandomChordalGraphGenerator(int numVertices, int maxSubtreeSize)
      Creates a generator for random chordal graphs with the specified number of vertices, with the possibility to adjust the density of the generated graph. The smaller the value for maxSubtreeSize, the lower the density of the graph.
      Parameters:
      numVertices - the number of vertices of the generated graph.
      maxSubtreeSize - the maximum size of the subtrees that are used for the computation of the intersection graph.

  • Method Details

    • createGraph

      public Graph createGraph()
      Creates a random chordal graph.
      Returns:
      a random chordal graph.