Package com.jgalgo.gen

Class UnionGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class UnionGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generate the union graph of two or more given graphs.

    The union graph of two graphs is a graph with all the vertices and edges from both graphs, without duplications. The set of vertices in the union graph is the union of the sets of vertices in the input graphs, as defined in sets theory. As for the edges, there are two ways to define the union:

    • Union by id: each edge is identified by its id. All edges of the two graphs are added to the union graph, and if an edge with the same id exist in both graph, it must have the same endpoints in both graphs. Otherwise, an exception is thrown. See edgeUnionById() for more details.
    • Union by endpoints: Each edge is identified by its endpoints. If an edge with the same endpoints exists in both graphs, it is added to the union graph only once. The edges are added by the order of the input graphs, and the first edge of each equivalent class of endpoints determine the identifier of the edge in the generated graph(s). The input graphs must not contains parallel edges. See edgeUnionByEndpoints() for more details.
    The above rules generalize to union of more than two graphs.

    By default, the edges union is by id. Use edgeUnionByEndpoints() and edgeUnionById() to change the union of edges.

    Weights are not copied by default. Use copyWeights(boolean, boolean) to copy the vertices/edges weights.

    Author:
    Barak Ugav

    • Constructor Detail

      • UnionGraphGenerator

        public UnionGraphGenerator()
        Create a new union graph generator that will use the default graph factory.

      • UnionGraphGenerator

        public UnionGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new union 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 Detail

      • 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 one of the input graphs have self edges, the method GraphFactory.allowSelfEdges() will be called. If one of the input graphs have parallel edges, or if two edges with the same endpoints and different identifiers exist in the input graphs, the method GraphFactory.allowParallelEdges() will be called. Note that parallel edges are not allowed (in each input graph independently) when union by endpoints is used (see edgeUnionByEndpoints()).

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

      • graphs

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

        Given two or more graphs, the union graph of the graphs is a graph with all the vertices and edges from all the graphs, without duplications. The set of vertices in the union graph is the union of the sets of vertices in the input graphs, as defined in sets theory. As for the edges, the union can be done by the edges identifiers, or by the edges endpoints (see the documentation of these methods 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 UnionGraphGenerator<V,​E> graphs​(Graph<V,​E>... graphs)
        Set the input graphs whose union graph will be generated (variable arguments version).

        Given two or more graphs, the union graph of the graphs is a graph with all the vertices and edges from all the graphs, without duplications. The set of vertices in the union graph is the union of the sets of vertices in the input graphs, as defined in sets theory. As for the edges, the union can be done by the edges identifiers, or by the edges endpoints (see the documentation of these methods 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

      • edgeUnionById

        public UnionGraphGenerator<V,​E> edgeUnionById()
        Set the union of edges to be by the edges identifiers.

        The union graph of two or more graphs using this method is a graph with all the vertex set that is the union of the vertex sets of the input graphs, and edge set constructed as follows: for each edge in the input graphs, if the edge identifier does not exist in the union graph, it is added to the union graph. If the edge identifier exists in the union graph, it must have the same endpoints in the input graphs and in the union graph. Otherwise, an exception is thrown.

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

        Self edges may be generated if one of the input graphs have self edges. Parallel edges may be generated if one of the input graphs have parallel edges, or if two edges with the same endpoints and different identifiers exist in the input graphs.

        In the following example two directed graphs are created, and the union 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> unionGraph = new UnionGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeUnionById() // override previous call to edgeUnionByEndpoints() if have been called
 		.generate();
 assert Set.of("A", "B", "C", "D").equals(unionGraph.vertices());
 assert Set.of(1, 2, 5).equals(unionGraph.edges());
 assert unionGraph.edgeSource(1).equals("A") && unionGraph.edgeTarget(1).equals("B");
 assert unionGraph.edgeSource(2).equals("A") && unionGraph.edgeTarget(2).equals("C");
 assert unionGraph.edgeSource(5).equals("A") && unionGraph.edgeTarget(5).equals("D");
        Returns:
        this generator

      • edgeUnionByEndpoints

        public UnionGraphGenerator<V,​E> edgeUnionByEndpoints()
        Set the union of edges to be by the edges endpoints.

        The union graph of two or more graphs using this method is a graph with all the vertex set that is the union of the vertex sets of the input graphs, and edge set constructed as follows: for each edge in the input graphs, if no edge with the same endpoints exist in the union graph, it is added to the union graph, with the same identifier. If an edge with the same endpoints exists in the union graph, it is not added to the union graph.

        The input graphs must not contains 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 one of the input graphs have self edges. Parallel edges are never generated when union by endpoints is used.

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

        In the following example two directed graphs are created, and the union 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> unionGraph = new UnionGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeUnionByEndpoints() // override previous call to edgeUnionById() if have been called
 		.generate();
 assert Set.of("A", "B", "C", "D").equals(unionGraph.vertices());
 assert Set.of(10, 20, 100).equals(unionGraph.edges());
 assert unionGraph.edgeSource(10).equals("A") && unionGraph.edgeTarget(10).equals("B");
 assert unionGraph.edgeSource(20).equals("A") && unionGraph.edgeTarget(20).equals("C");
 assert unionGraph.edgeSource(100).equals("A") && unionGraph.edgeTarget(100).equals("D");
        Returns:
        this generator

      • copyWeights

        public UnionGraphGenerator<V,​E> copyWeights​(boolean verticesWeights,
                                                  boolean edgesWeights)
        Determine if the vertices/edges weights will be copied from the input graphs to the generated graph(s).

        When creating a union of two graphs, where both input graphs have exactly the same weights, and there are no duplicate vertices and edges (the sets of vertices (edges) are disjoint), we simply copy the weights from the input graphs to the generated graph. However, when there are duplicate vertices and/or edges, or when the input graphs have different weights, we need to decide how to copy the weights to the generated graph. To define the rules, we first define the equivalence class of a vertex (edge) \(v\) in the generated graph as the set of vertices (edges) in the input graphs that are mapped to \(v\). These are the vertices with the same identifier across the input graphs. The equivalence class of an edge \(e=(u,v)\) depends on the union of edges rule: if the union of edges is by id, the equivalence class is the set of edges in the input graphs with the same identifier as \(e\). If the union of edges is by endpoints, the equivalence class is the set of edges in the input graphs with the endpoints as \((u,v)\). Given the definition of the equivalence class, we define the rules for copying the weights of each vertex (edge) \(v\) as follows: We examine the equivalence class of \(v\) ordered by the order of the input graphs. For each vertex (edge) \(v_i\) in the equivalence class, if it has a weight keyed by a key not yet seen in the equivalence class, we copy the weight to \(v\), else we ignore it. Note that we do not distinguish between default weights and user set weights, as long as the graph containing \(v_i\) have the weights we consider it as \(v_i\) having the weight. For each weights type in the generated graph(s), the default weight is the default weight of the first input graph that have this weights type.

        By default, the vertices/edges weights are not copied. By default, if the vertices/edges weights are copied, all the weights are copied. Use verticesWeightsKeys(Set) and edgesWeightsKeys(Set) to copy only specific weights.

        In the following example, two directed graphs are created, both have a vertices weights keyed by "w1", but with different default weights. The union graph of the two graphs is generated, and the vertices weights are copied from the input graphs. The default weight of the vertices weights in the generated graph is the default weight of the first input graph that have this weights type. Vertex \(0\) exists in both graphs, so its weight is copied from the first graph. Vertex \(1\) exists only in the second graph, so its weight is copied from the second graph: 

         
 Graph<Integer, Integer> graph1 = Graph.newDirected();
 WeightsInt<Integer> g1_w1 = graph1.addVerticesWeights("w1", int.class, -1);
 graph1.addVertex(0);
 g1_w1.set(0, 100);

 Graph<Integer, Integer> graph2 = Graph.newDirected();
 WeightsInt<Integer> g2_w1 = graph2.addVerticesWeights("w1", int.class, -2);
 graph2.addVertex(0);
 graph2.addVertex(1);
 g2_w1.set(0, 200);
 g2_w1.set(1, 500);

 Graph<Integer, Integer> union = new UnionGraphGenerator<Integer, Integer>()
 		.graphs(graph1, graph2)
 		.copyWeights(true, false)
 		.verticesWeightsKeys(Set.of("w1"))
 		.generate();
 assert union.verticesWeightsKeys().equals(Set.of("w1"));
 WeightsInt<Integer> union_w1 = union.verticesWeights("w1");
 assert union_w1.defaultWeight() == -1;
 assert union_w1.get(0) == 100;
 assert union_w1.get(1) == 500;

        If multiple input graphs have weights with the same key but different types, an exception is thrown during the graph(s) generation.

        Parameters:
        verticesWeights - if true, the vertices weights will be copied
        edgesWeights - if true, the edges weights will be copied
        Returns:
        this generator

      • verticesWeightsKeys

        public UnionGraphGenerator<V,​E> verticesWeightsKeys​(Set<String> keys)
        Set the vertices weights keys to be copied from the input graphs to the generated graph(s).

        By default, no weights are copied to the union graph. Using copyWeights(boolean, boolean) the user can determine if the vertices weights will be copied, and if the edges weights will be copied, and all vertices/edges will be copied. This method allows the user to copy only specific weights. For this method to have any effect, copying the vertices weights must be enabled in the first place.

        Parameters:
        keys - the vertices weights keys to be copied
        Returns:
        this generator

      • edgesWeightsKeys

        public UnionGraphGenerator<V,​E> edgesWeightsKeys​(Set<String> keys)
        Set the edges weights keys to be copied from the input graphs to the generated graph(s).

        By default, no weights are copied to the union graph. Using copyWeights(boolean, boolean) the user can determine if the vertices weights will be copied, and if the edges weights will be copied, and all vertices/edges will be copied. This method allows the user to copy only specific weights. For this method to have any effect, copying the edges weights must be enabled in the first place.

        Parameters:
        keys - the edges weights keys to be copied
        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