Package com.jgalgo.gen

Class LineGraphGenerator<V,E>

java.lang.Object
com.jgalgo.gen.LineGraphGenerator<V,E>
Type Parameters:
V - the vertices type, which is the edges type of the input graph
E - the edges type
All Implemented Interfaces:
GraphGenerator<V,E>
public class LineGraphGenerator<V,E> extends Object implements GraphGenerator<V,E>
Generates the line graph given an existing graph.

Given a graph \(G=(V,E)\), the line graph \(L=(E,H)\) is the graph whose vertices are the edges of \(G\) and a pair of such two vertices are connected by an edge if the corresponding edges in the original graph share an endpoint. For directed graphs, two vertices are connected if their corresponding edges form a path of size two in the original graph. The line graph \(L\) is directed if and only if the original graph \(G\) is directed.

The generate graph will not contains self edges, and no parallel edges. Specifically, if the original graph contains two parallel edges, meaning they share two endpoints rather than one, the generated line graph will contain only one edge between their corresponding vertices.

In the following example, the line graph of the original graph is generated. The vertices type of the original graph is URI, and the edges type is String. The vertices type of the generated line graph is String (the edges type of the original graph), and the edges type is Integer. The edges of the generated line graph are generated using the default edge builder provided by IdBuilderInt.defaultBuilder(). 

 
 Graph<URI, String> origGraph = ...;
 Graph<String, Integer> lineGraph = new LineGraphGenerator<String, Integer>()
 		.graph(origGraph)
 		.edges(IdBuilderInt.defaultBuilder())
 		.generate();
Author:
Barak Ugav

  • Constructor Details

    • LineGraphGenerator

      public LineGraphGenerator()
      Create a new line 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.

    • LineGraphGenerator

      public LineGraphGenerator(GraphFactory<V,E> factory)
      Create a new line 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.

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

    • graph

      public LineGraphGenerator<V,E> graph(Graph<?,V> graph)
      Set the input graph whose line graph this generator should generate.

      Given a graph \(G=(V,E)\), the line graph \(L=(E,H)\) is the graph whose vertices are the edges of \(G\) and a pair of such two vertices are connected by an edge if the corresponding edges in the original graph share an endpoint. For directed graphs, two vertices are connected if their corresponding edges form a path of size two in the original graph. The line graph \(L\) is directed if and only if the original graph \(G\) is directed. This method sets the input graph \(G\), and the generator will generate the line graph \(L\).

      The edges type of the input graph are the vertices type of the generated line graph. The vertices type of the input graph is not reflected in the output graph.

      Parameters:
      graph - the input graph for the generator, whose line graph should be generated. The generated graph(s) will be directed if and only if this input graph is directed
      Returns:
      this generator
      Throws:
      NullPointerException - if graph is null

    • edges

      public LineGraphGenerator<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

    • commonVertexWeights

      public LineGraphGenerator<V,E> commonVertexWeights(String weightsKey)
      Set the weights key that will store the common vertex between two edges.

      Each edge in the line graph connect two vertices if the two corresponding edges share a common endpoint. This method cause each such common endpoint to be saved as weight of an edge in the generated line graph(s). By default, no such weights are added to the generated graph(s). If two edges share more than one endpoint (parallel edges), an arbitrary one will be stored as weight. The weights will be stored in the generate graph(s) as edges object weights by default, or as int weights if the input graph was an IntGraph. See the following example: 

       
 Graph<URI, String> origGraph = ...;
 Graph<String, Integer> lineGraph = new LineGraphGenerator<String, Integer>()
 		.graph(origGraph)
 		.edges(IdBuilderInt.defaultBuilder())
 		.commonVertexWeights("common-vertex")
 		.generate();

 	WeightsObj<Integer, URI> commonVertexWeights = g.edgesWeight("common-vertex");
 	for (Integer lineEdge : g.edges()) {
 		String e1 = g.edgeSource(lineEdge);
 		String e2 = g.edgeTarget(lineEdge);
 		URI commonVertex = commonVertexWeights.get(lineEdge);
 		System.out.format("The vertex %s is a common vertex between two edges: %d %d", commonVertex, e1, e2);
 	}
      Parameters:
      weightsKey - key of the edges weights in the generated graph(s) that will store the common (original) endpoint vertex that is shared between the two connected corresponding edges, or null to not store these weights
      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