Package com.jgalgo.gen

Class DifferenceGraphGenerator<V,​E>

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

    Given two graphs with the same vertex set \(G_1=(V,E_1)\) and \(G_2=(V,E_2)\), the difference graph \(G=(V,E)\) is a graph with the same vertex set that contains every edge that exists in \(E_1\) but not in \(E_2\). Saying one edge from \(E_1\) is the same edge as another from \(E_2\) can be defined by the edge id or by the edge endpoints. See edgeDifferenceById() and edgeDifferenceByEndpoints().

    By default, the edges are compared by their id. Use edgeDifferenceByEndpoints() to compare edges by their endpoints.

    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

      • DifferenceGraphGenerator

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

      • DifferenceGraphGenerator

        public DifferenceGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new 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 the first graph has self edges, the method GraphFactory.allowSelfEdges() will be called. If the first graph 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 DifferenceGraphGenerator<V,​E> graphs​(Graph<V,​E> graph1,
                                                  Graph<V,​E> graph2)
        Set the input graphs whose difference graph will be generated.

        Given two graphs with the same vertex set, the difference graph is a graph with the same vertex set that contains every edge that exists in the first graph but not in the second graph. Saying one edge from the first graph is the same edge as another from the second graph can be defined by the edge id or by the edge endpoints. See edgeDifferenceById() and edgeDifferenceByEndpoints().

        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 DifferenceGraphGenerator<V,​E> edgeDifferenceById()
        Set the difference of edges to be by their id.

        Given two graphs with the same vertex set, the difference graph is a graph with the same vertex set that contains every edge that exists in the first graph but not in the second graph. 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 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", "B", 10);
 graph2.addEdge("A", "C", 2);

 Graph<String, Integer> difference = new DifferenceGraphGenerator<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).equals(difference.edges());
 assert difference.edgeSource(1).equals("A") && difference.edgeTarget(1).equals("B");
        Returns:
        this generator

      • edgeDifferenceByEndpoints

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

        Given two graphs with the same vertex set, the difference graph is a graph with the same vertex set that contains every edge that exists in the first graph but not in the second graph. 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 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 DifferenceGraphGenerator<String, Integer>()
 		.graphs(graph1, graph2)
 		.edgeDifferenceByEndpoints()
 		.generate();
 assert Set.of("A", "B", "C", "D").equals(difference.vertices());
 assert Set.of(2).equals(difference.edges());
 assert difference.edgeSource(2).equals("A") && difference.edgeTarget(2).equals("C");
        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