Package com.jgalgo.gen

Class SymmetricDifferenceGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class SymmetricDifferenceGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generate a graph that contains the edges that exist in one of two input graphs but not in both.

    Given two graphs with the same vertex set \(G_1 = (V, E_1)\) and \(G_2 = (V, E_2)\), the symmetric difference graph \(G = (V, E)\) is defined as \(E = (E_1 \setminus E_2) \cup (E_2 \setminus E_1)\). There are two ways to define equality between a pair of edges: by their id or by their endpoints. The default is by id. See the edgeDifferenceById() and edgeDifferenceByEndpoints() methods.

    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 Detail

      • SymmetricDifferenceGraphGenerator

        public SymmetricDifferenceGraphGenerator()
        Create a new symmetric difference graph generator that will use the default graph factory.

      • SymmetricDifferenceGraphGenerator

        public SymmetricDifferenceGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new symmetric difference 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 the graphs has self edges, the method GraphFactory.allowSelfEdges() will be called. If one of the graphs has parallel edges, the method GraphFactory.allowParallelEdges() will be called.

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

      • graphs

        public SymmetricDifferenceGraphGenerator<V,​E> graphs​(Graph<V,​E> graph1,
                                                           Graph<V,​E> graph2)
        Set the input graphs whose symmetric difference graph will be generated.

        Given two graphs with the same vertex set, the symmetric difference graph is defined as the graph with the same vertex set and edges that exist in one of the graphs but not in both.

        Parameters:
        graph1 - the first graph
        graph2 - the second graph
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if the graphs have different directionality or if their vertex sets are not equal

      • edgeDifferenceById

        public SymmetricDifferenceGraphGenerator<V,​E> edgeDifferenceById()
        Set the difference of edges to be by their id.

        Given two graphs with the same vertex set, the symmetric difference graph is defined as the graph with the same vertex set and edges that exist in one of the graphs but not in both. This method defines that one edge from the first graph is the same edge as another from the second graph if they have the same identifier. See edgeDifferenceByEndpoints() for an alternative definition.

        By default, the edges are compared by their id.

        When difference of edges is done by their id, if an edge from the first graph and an edge from the second graph have the same identifier, they also must have the same endpoints, otherwise an exception will be thrown during generation.

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

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

 Graph<String, Integer> graph2 = Graph.newDirected();
 graph2.addVertices(Set.of("A", "B", "C", "D"));
 graph2.addEdge("A", "C", 2);
 graph2.addEdge("A", "D", 10);

 Graph<String, Integer> difference = new SymmetricDifferenceGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeDifferenceById() // default, not really needed
 		.generate();
 assert Set.of("A", "B", "C", "D").equals(difference.vertices());
 assert Set.of(1, 10).equals(difference.edges());
 assert difference.edgeSource(1).equals("A") && difference.edgeTarget(1).equals("B");
 assert difference.edgeSource(10).equals("A") && difference.edgeTarget(10).equals("D");
        Returns:
        this generator

      • edgeDifferenceByEndpoints

        public SymmetricDifferenceGraphGenerator<V,​E> edgeDifferenceByEndpoints()
        Set the difference of edges to be by their endpoints.

        Given two graphs with the same vertex set, the symmetric difference graph is defined as the graph with the same vertex set and edges that exist in one of the graphs but not in both. This method defines that one edge from the first graph is the same edge as another from the second graph if they have the same endpoints. See edgeDifferenceById() for an alternative definition.

        By default, the edges are compared by their id.

        In the following example two directed graphs are created, and the symmetric difference graph of the two graphs is generated by the edges endpoints: 

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

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

 Graph<String, Integer> difference = new SymmetricDifferenceGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeDifferenceByEndpoints()
 		.generate();
 assert Set.of("A", "B", "C", "D").equals(difference.vertices());
 assert Set.of(2, 20).equals(difference.edges());
 assert difference.edgeSource(2).equals("A") && difference.edgeTarget(2).equals("C");
 assert difference.edgeSource(20).equals("A") && difference.edgeTarget(20).equals("D");
        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