Package com.jgalgo.gen

Class IntersectionGraphGenerator<V,E>

java.lang.Object
com.jgalgo.gen.IntersectionGraphGenerator<V,E>
Type Parameters:
V - the vertices type
E - the edges type
All Implemented Interfaces:
GraphGenerator<V,E>
public class IntersectionGraphGenerator<V,E> extends Object implements GraphGenerator<V,E>
Generate the intersection graph of two or more given graphs.

The intersection graph of two graphs is a graph with the vertex set which is the intersection of the vertex sets of the two graphs, and the edge set which is the intersection of the edge sets of the two graphs. There are two different ways to intersect the edges of the graphs:

  • Intersect by id: the edges are considered the same if they have the same id. Two edges with the same id in the two graphs are considered the same edge. If they do not have the same endpoints, an exception is thrown. This is the default.
  • Intersect by endpoints: the edges are considered the same if they have the same endpoints. Two edges with the same endpoints in the two graphs are considered the same edge. The id of the edge in the first graph is used as the id of the edge in the intersection graph.
The above rules generalize to intersection of more than two graphs.

By default, the edges intersection is by id. Use edgeIntersectByEndpoints() and edgeIntersectById() to change the intersection of edges.

Weights are not copied from the input graphs to the generated graph(s). In the future there might be an option to do so.

Author:
Barak Ugav

  • Constructor Details

    • IntersectionGraphGenerator

      public IntersectionGraphGenerator()
      Create a new intersection graph generator that will use the default graph factory.

    • IntersectionGraphGenerator

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

      The graph factory will be used to create the generated graph(s).

      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.

      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 all of of the input graphs have self edges, the method GraphFactory.allowSelfEdges() will be called. If all of the input graphs have parallel edges, the method GraphFactory.allowParallelEdges() will be called. Note that parallel edges are not allowed (in each input graph independently) when intersecting by endpoints is used (see edgeIntersectByEndpoints()).

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

    • graphs

      public IntersectionGraphGenerator<V,E> graphs(Collection<? extends Graph<V,E>> graphs)
      Set the input graphs whose intersection graph will be generated.

      Given two or more graphs, the intersection graph of the graphs is a graph with the vertex set which is the intersection of the vertex sets of the graphs, and the edge set which is the intersection of the edge sets of the graphs. There are two different ways to intersect the edges of the graphs, see edgeIntersectById() and edgeIntersectByEndpoints() for more details.

      Parameters:
      graphs - the input graphs
      Returns:
      this generator
      Throws:
      IllegalArgumentException - if less than two input graphs are provided, or if the graphs have different directionality

    • graphs

      @SafeVarargs public final IntersectionGraphGenerator<V,E> graphs(Graph<V,E>... graphs)
      Set the input graphs whose intersection graph will be generated.

      Given two or more graphs, the intersection graph of the graphs is a graph with the vertex set which is the intersection of the vertex sets of the graphs, and the edge set which is the intersection of the edge sets of the graphs. There are two different ways to intersect the edges of the graphs, see edgeIntersectById() and edgeIntersectByEndpoints() for more details.

      Parameters:
      graphs - the input graphs
      Returns:
      this generator
      Throws:
      IllegalArgumentException - if less than two input graphs are provided, or if the graphs have different directionality

    • edgeIntersectById

      public IntersectionGraphGenerator<V,E> edgeIntersectById()
      Set the intersection of edges to by the edges identifiers.

      The intersection graph of two or more graphs using this method is a graph with the vertex set which is the intersection of the vertex sets of the graphs, and the edge set constructed as follows: for each edge in the first graph, if the edge (identifier) exists in all of the graphs, it is added to the intersection graph. The endpoints of the edge must be the same for all graphs, otherwise an exception is thrown.

      A call to this method override a previous call to edgeIntersectByEndpoints(). By default, the intersection of edges is by id.

      Both self and parallel edges may be generated if such edges exist in all the input graphs.

      In the following example two directed graphs are created, and the intersection graph of the two graphs is generated by the edges identifiers: 

       
 Graph<String, Integer> graph1 = Graph.newDirected();
 graph1.addVertices(List.of("A", "B", "C"));
 graph1.addEdge("A", "B", 1);
 graph1.addEdge("A", "C", 2);

 Graph<String, Integer> graph2 = Graph.newDirected();
 graph2.addVertices(List.of("A", "B", "D"));
 graph2.addEdge("A", "B", 1);
 graph2.addEdge("A", "D", 5);

 Graph<String, Integer> intersectionGraph = new IntersectionGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeIntersectById() // override previous call to edgeIntersectByEndpoints() if have been called
 		.generate();
 assert Set.of("A", "B").equals(intersectionGraph.vertices());
 assert Set.of(1).equals(intersectionGraph.edges());
 assert intersectionGraph.edgeSource(1).equals("A") && intersectionGraph.edgeTarget(1).equals("B");
      Returns:
      this generator

    • edgeIntersectByEndpoints

      public IntersectionGraphGenerator<V,E> edgeIntersectByEndpoints()
      Set the intersection of edges to be by the edges endpoints.

      The intersection graph of two or more graphs using this method is a graph with the vertex set which is the intersection of the vertex sets of the graphs, and the edge set constructed as follows: for each edge in the first graph, if an edge (same endpoints, identifier may differ) exists in all of the graphs, it is added to the intersection graph. The identifier of the edge in the first graph is used as the identifier of the edge in the intersection graph.

      The input graphs must not contain parallel edges. If one of the input graphs contains parallel edges, an exception is thrown during the graph(s) generation. Self edges may be generated if such edges exist in all the input graphs. Parallel edges are never generated.

      A call to this method override a previous call to edgeIntersectById(). By default, the intersection of edges is by id.

      In the following example two directed graphs are created, and the intersection graph of the two graphs is generated by the edges endpoints. Note that the edge \(A, B\) exists in both graphs, but with different identifiers. In the generated graph, the edge \(A, B\) will appear only once, with identifier from the first graph: 

       
 Graph<String, Integer> graph1 = Graph.newDirected();
 graph1.addVertices(List.of("A", "B", "C"));
 graph1.addEdge("A", "B", 10);
 graph1.addEdge("A", "C", 20);

 Graph<String, Integer> graph2 = Graph.newDirected();
 graph2.addVertices(List.of("A", "B", "D"));
 graph2.addEdge("A", "B", 50);
 graph2.addEdge("A", "D", 100);

 Graph<String, Integer> intersectionGraph = new IntersectionGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeIntersectByEndpoints() // override previous call to edgeIntersectById() if have been called
 		.generate();
 assert Set.of("A", "B").equals(intersectionGraph.vertices());
 assert Set.of(10).equals(intersectionGraph.edges());
 assert intersectionGraph.edgeSource(10).equals("A") && intersectionGraph.edgeTarget(10).equals("B");
      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