Package com.jgalgo.gen

Class ComplementGraphGenerator<V,E>

java.lang.Object
com.jgalgo.gen.ComplementGraphGenerator<V,E>
Type Parameters:
V - the vertices type
E - the edges type
All Implemented Interfaces:
GraphGenerator<V,E>
public class ComplementGraphGenerator<V,E> extends Object implements GraphGenerator<V,E>
Generates the complement graph of a given graph.

The complement graph of a graph \(G\) is a graph \(H\) on the same vertices such that \((u,v) \in E(H)\) if and only if \((u,v) \notin E(G)\). If \(G\) is a directed graph, then \(H\) is also directed. Whether or not self edges are generated is controlled by selfEdges(boolean).

In the following example, the complement graph of a given graph is generated. For each edge in the complement graph, it is asserted that an edge with the same endpoints does not exist in the original graph: 

 
 Graph<Integer, Integer> origGraph = null;
 Graph<Integer, Integer> complement = new ComplementGraphGenerator<Integer, Integer>()
 		.selfEdges(true)
 		.edges(IdBuilderInt.defaultBuilder())
 		.generate();
 for (Integer u : origGraph.vertices())
 	for (Integer v : origGraph.vertices())
 		assert origGraph.containsEdge(u, v) != complement.containsEdge(u, v);
Author:
Barak Ugav

  • Constructor Details

    • ComplementGraphGenerator

      public ComplementGraphGenerator()
      Create a new complement graph generator that will use the default graph factory.

      The graph factory will be used to create the generated graph(s) and it will also provide an edge builder if one was no explicitly set using edges(IdBuilder). The default graph builder does not have an edge builder, therefore it must be set manually.

    • ComplementGraphGenerator

      public ComplementGraphGenerator(GraphFactory<V,E> factory)
      Create a new complement graph generator that will use the given graph factory.

      The graph factory will be used to create the generated graph(s) and it will also provide an edge builder if one was no explicitly set using edges(IdBuilder).

      To generate int graphs, pass an instance of IntGraphFactory to this constructor.

      Parameters:
      factory - the graph factory that will be used to create the generated graph(s)

  • Method Details

    • graphFactory

      public GraphFactory<V,E> graphFactory()
      Get the graph factory that will be used to create the generated graph(s).

      It's possible to customize the factory before generating the graph(s), for example by using GraphFactory.addHint(GraphFactory.Hint) to optimize the generated graph(s) for a specific algorithm. If the factory has an edge builder it will be used to generate the edges of the generated graph(s) if it will not be overridden by edges(IdBuilder).

      During the graph(s) generation, the method GraphFactory.setDirected(boolean) of the given factory will be called to align the created graph with the generator configuration. If self edges are generated, the method GraphFactory.allowSelfEdges() will be called as well (see selfEdges(boolean)).

      Returns:
      the graph factory that will be used to create the generated graph(s)

    • graph

      public ComplementGraphGenerator<V,E> graph(Graph<V,?> graph)
      Set the input graph whose complement graph will be generated.

      Given a graph \(G\), the complement graph \(H\) is a graph on the same vertices such that \((u,v) \in E(H)\) if and only if \((u,v) \notin E(G)\). This method sets the input graph \(G\).

      This method must be called before the graph(s) generation.

      The edges type of the input graph is not reflected in the generated graph(s), as new edges will be generated which can be of any type.

      Parameters:
      graph - the input graph whose complement graph will be generated
      Returns:
      this generator

    • edges

      public ComplementGraphGenerator<V,E> edges(IdBuilder<E> edgeBuilder)
      Set the edge builder that will be used to generate edges.

      The edges will be generated using the provided edge builder, and the edge generator provided by the graph factory (if exists) will be ignored. The generation will happen independently for each graph generated. If this method is not called, or called with a null argument, the edge builder of the graph factory will be used. If the graph factory does not have an edge builder, an exception will be thrown during generation.

      Parameters:
      edgeBuilder - the edge builder, or null to use the edge builder of the graph factory
      Returns:
      this generator

    • selfEdges

      public ComplementGraphGenerator<V,E> selfEdges(boolean selfEdges)
      Set whether or not to generate self edges.

      By default, self edges are not generated.

      Parameters:
      selfEdges - if true, self edges will be generated
      Returns:
      this generator

    • generateIntoBuilder

      public GraphBuilder<V,E> generateIntoBuilder()
      Description copied from interface: GraphGenerator
      Generates a graph into a builder.

      This is the a more flexible way to generate a graph. The builder can be used to generate a mutable or immutable graph, or to add additional vertices or edges on top of the generated ones.

      Specified by:
      generateIntoBuilder in interface GraphGenerator<V,E>
      Returns:
      a new graph builder populated by the generator with the generator parameters