Package com.jgalgo.adapt.jgrapht

Class JGraphTWrapper<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    Graph<V,​E>
    public class JGraphTWrapper<V,​E>
extends AbstractGraph<V,​E>
    An adapter from JGraphT graph to JGAlgo graph.

    The adapter is constructed with a JGraphT graph and implements the JGAlgo graph interface, and can be used with any JGAlgo algorithm. The adapter is a live view, so any change in the JGAlgo graph is reflected in the JGraphT graph and vice versa, but the underlying JGraphT graph should not be modified directly. Modifying the original JGraphT graph will invalidate the adapter.

    The capabilities of the graph (Graph.isDirected(), Graph.isAllowParallelEdges(), and Graph.isAllowSelfEdges()) are determined by the GraphType of the JGraphT graph. If the original JGraphT graph was weighted, the adapter will expose a single double weight type for edges, with the key passed in the constructor. New weights of vertices or edges can not be added to the graph as the underlying JGraphT graph support only a single double edge weight type.

    The adapter has much worse performance than the a regular JGAlgo graph. If memory is not an issue, it is probably better to copy the adapter to a regular JGAlgo graph and use it instead. For example: 

     
 org.jgrapht.Graph<V,E> originalGraph = ...;
 com.jgalgo.graph.Graph<V,E> wrappedGraph = new JGraphTWrapper<>(originalGraph);
 com.jgalgo.graph.Graph<V,E> regularGraph = wrappedGraph.immutableCopy(); // or just copy()
 ...

    For adapting the other way around, from JGAlgo to JGraphT, see JGraphTAdapter.

    Author:
    Barak Ugav
    See Also:
    Graph, Graph, JGraphTAdapter

    • Constructor Detail

      • JGraphTWrapper

        public JGraphTWrapper​(Graph<V,​E> graph)
        Constructs a new adapter from the given JGraphT graph without weights.
        Parameters:
        graph - the JGraphT graph to adapt

      • JGraphTWrapper

        public JGraphTWrapper​(Graph<V,​E> graph,
                      String edgeWeightKey)
        Constructs a new adapter from the given JGraphT graph optionally with weights.

        If the JGraphT graph is weighted, and the edgeWeightKey is not null, the adapter will expose a single double weight type for edges, with the given key. If the JGraphT graph is not weighted, the edgeWeightKey must be null.

        Parameters:
        graph - the JGraphT graph to adapt
        edgeWeightKey - the key of the edge weight to use, or null if the graph is not weighted
        Throws:
        IllegalArgumentException - if the graph not is weighted and the edgeWeightKey is not null

    • Method Detail

      • vertices

        public Set<V> vertices()
        Description copied from interface: Graph
        Get the set of all vertices of the graph.

        Each vertex in the graph is identified by a unique non null hashable object and the returned set is a set of all these identifiers.

        The Graph object does not expose an explicit method to get the number of vertices, but it can accessed using this method by g.vertices().size().

        Returns:
        a set containing all vertices of the graph

      • edges

        public Set<E> edges()
        Description copied from interface: Graph
        Get the set of all edges of the graph.

        Each edge in the graph is identified by a unique non null hashable object, and the returned set is a set of all these identifiers.

        The Graph object does not expose an explicit method to get the number of edges, but it can accessed using this method by g.edges().size().

        Returns:
        a set containing all edges of the graph

      • addVertex

        public void addVertex​(V vertex)
        Description copied from interface: Graph
        Add a new vertex to the graph.

        A vertex can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate vertices are not allowed.

        If the graph have a vertex builder, namely if Graph.vertexBuilder() does not return null, the method Graph.addVertex() can be used, which uses the vertex builder to create the new vertex object instead of requiring the user to provide it.

        Parameters:
        vertex - new vertex

      • addVertices

        public void addVertices​(Collection<? extends V> vertices)
        Description copied from interface: Graph
        Add multiple vertices to the graph.

        A vertex can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate vertices are not allowed.

        Parameters:
        vertices - new vertices

      • removeVertex

        public void removeVertex​(V vertex)
        Description copied from interface: Graph
        Remove a vertex and all its edges from the graph.
        Parameters:
        vertex - the vertex identifier to remove

      • removeVertices

        public void removeVertices​(Collection<? extends V> vertices)
        Description copied from interface: Graph
        Remove multiple vertices and all their edges from the graph.
        Parameters:
        vertices - the vertices to remove

      • renameVertex

        public void renameVertex​(V vertex,
                         V newId)
        Description copied from interface: Graph
        Set a new identifier for an existing vertex.

        This method changes the identifier of an existing vertex, while keeping the edges connecting to it, along with the weights associated with it.

        Parameters:
        vertex - an existing vertex in the graph
        newId - the new vertex identifier

      • outEdges

        public EdgeSet<V,​E> outEdges​(V source)
        Description copied from interface: Graph
        Get the edges whose source is source.

        In case the graph is undirected, the set will contain all edges whose source is one of their end points.

        The graph object does not expose an explicit method to get the (out) degree of a vertex, but it can accessed using this method by g.outEdges(vertex).size().

        Parameters:
        source - a source vertex
        Returns:
        all the edges whose source is source

      • inEdges

        public EdgeSet<V,​E> inEdges​(V target)
        Description copied from interface: Graph
        Get the edges whose target is target.

        In case the graph is undirected, the set will contain all edges whose target is one of their end points.

        The graph object does not expose an explicit method to get the (in) degree of a vertex, but it can accessed using this method by g.inEdges(vertex).size().

        Parameters:
        target - a target vertex
        Returns:
        all the edges whose target is target

      • getEdge

        public E getEdge​(V source,
                 V target)
        Description copied from interface: Graph
        Get the edge whose source is source and target is target.

        If the graph is not directed, the return edge is an edge that its end-points are source and target.

        In case there are multiple (parallel) edges between source and target, a single arbitrary one is returned.

        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        id of the edge or null if no such edge exists

      • getEdges

        public EdgeSet<V,​E> getEdges​(V source,
                                   V target)
        Description copied from interface: Graph
        Get the edges whose source is source and target is target.
        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        all the edges whose source is source and target is target

      • addEdge

        public void addEdge​(V source,
                    V target,
                    E edge)
        Description copied from interface: Graph
        Add a new edge to the graph.

        If the graph does not support parallel edges, and an edge between source and target already exists, an exception will be raised. If the graph does not support self edges, and source and target are the same vertex, an exception will be raised.

        An edge can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate edges are not allowed.

        If the graph have an edge builder, namely if Graph.edgeBuilder() does not return null, the method Graph.addEdge(Object, Object) can be used, which uses the edge builder to create the new edge object instead of requiring the user to provide it.

        Parameters:
        source - a source vertex
        target - a target vertex
        edge - a new edge identifier

      • addEdges

        public void addEdges​(EdgeSet<? extends V,​? extends E> edges)
        Description copied from interface: Graph
        Add multiple edges to the graph.

        The EdgeSet passed to this method contains both the edges themselves (the identifiers) and their endpoints (sources and targets), see EdgeSet.iterator(), EdgeIter.source(), EdgeIter.target(). An EdgeSet can be obtained from one of the methods of another Graph, or using EdgeSet.of(Set, Graph).

        If the graph does not support self edges and one of the added edges have the same vertex as source and target, an exception will be thrown. If the graph does not support parallel edges, and one of the added edges have the same source and target as one of the existing edges in the graph, or if two of the added edges have the same source and target, an exception will be thrown.

        An edge can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate edges are not allowed.

        In the following snippet, a maximum cardinality matching is computed on a graph, and a new graph containing only the matching edges is created: 

         
 Graph<V, E> g = ...;
 Set<E> matching = MatchingAlgo.newInstance().computeMaximumMatching(g, null).edges();

 Graph<V,E> matchingGraph = Graph.newUndirected();
 matchingGraph.addVertices(g.vertices());
 matchingGraph.addEdges(EdgeSet.of(matching, g));
        Parameters:
        edges - the set of new edges, from which the edges identifiers as well as the endpoints (source and target) of each edge are accessible (see EdgeSet.iterator(), EdgeIter.source(), EdgeIter.target()).

      • removeEdge

        public void removeEdge​(E edge)
        Description copied from interface: Graph
        Remove an edge from the graph.
        Parameters:
        edge - the edge to remove

      • removeEdges

        public void removeEdges​(Collection<? extends E> edges)
        Description copied from interface: Graph
        Remove multiple edges from the graph.
        Parameters:
        edges - the edges to remove

      • removeEdgesOf

        public void removeEdgesOf​(V vertex)
        Description copied from interface: Graph
        Remove all the edges of a vertex.
        Parameters:
        vertex - a vertex in the graph

      • removeOutEdgesOf

        public void removeOutEdgesOf​(V vertex)
        Description copied from interface: Graph
        Remove all edges whose source is source.
        Parameters:
        vertex - a vertex in the graph

      • removeInEdgesOf

        public void removeInEdgesOf​(V vertex)
        Description copied from interface: Graph
        Remove all edges whose target is target.
        Parameters:
        vertex - a vertex in the graph

      • renameEdge

        public void renameEdge​(E edge,
                       E newId)
        Description copied from interface: Graph
        Set a new identifier for an existing edge.

        This method changes the identifier of an existing edge, while keeping the source and target of the edge, along with the weights associated with it.

        Parameters:
        edge - an existing edge in the graph
        newId - the new edge identifier

      • moveEdge

        public void moveEdge​(E edge,
                     V newSource,
                     V newTarget)
        Description copied from interface: Graph
        Move an existing edge to new source and target vertices.

        This method changes the source and target of an existing edge, while keeping the identifier of the edge and the weights associated with it.

        Parameters:
        edge - an existing edge in the graph
        newSource - the new source vertex
        newTarget - the new target vertex

      • edgeSource

        public V edgeSource​(E edge)
        Description copied from interface: Graph
        Get the source vertex of an edge.

        If the graph is undirected, this function return an arbitrary end-point of the edge, but always other end-point than Graph.edgeTarget(Object) returns.

        Parameters:
        edge - the edge identifier
        Returns:
        the edge source vertex

      • edgeTarget

        public V edgeTarget​(E edge)
        Description copied from interface: Graph
        Get the target vertex of an edge.

        If the graph is undirected, this function return an arbitrary end-point of the edge, but always the other end-point than Graph.edgeSource(Object) returns.

        Parameters:
        edge - the edge identifier
        Returns:
        the edge target vertex

      • edgeEndpoint

        public V edgeEndpoint​(E edge,
                      V endpoint)
        Description copied from interface: Graph
        Get the other end-point of an edge.

        Given an edge \((u,v)\) and a vertex \(w\), assuming \(w\) is an endpoint of the edge, namely that \(w\) is either \(u\) or \(v\), the method will return the other endpoint which is not \(w\). If \(w=u\) the method will return \(v\), if \(w=v\) the method will return \(u\).

        Parameters:
        edge - an edge identifier
        endpoint - one of the edge end-point
        Returns:
        the other end-point of the edge

      • clear

        public void clear()
        Description copied from interface: Graph
        Clear the graph completely by removing all vertices and edges.

        This function might be used to reuse an already allocated graph object.

        Note that this function also clears any weights associated with the vertices or edges.

      • clearEdges

        public void clearEdges()
        Description copied from interface: Graph
        Remove all the edges from the graph.

        Note that this function also clears any weights associated with the edges.

      • vertexBuilder

        public IdBuilder<V> vertexBuilder()
        Description copied from interface: Graph
        Get the vertex builder of this graph.

        The vertex builder is used to create new vertices in the graph during the execution of Graph.addVertex(), in which the vertex identifier is not provided by the user. Not all graphs have a vertex builder, and may return a null value. In that case, Graph.addVertex() cannot be used, only Graph.addVertex(Object).

        Returns:
        the vertex builder of this graph, or null if the graph does not have a vertex builder

      • edgeBuilder

        public IdBuilder<E> edgeBuilder()
        Description copied from interface: Graph
        Get the edge builder of this graph.

        The edge builder is used to create new edges in the graph during the execution of Graph.addEdge(Object, Object), in which the edge identifier is not provided by the user. Not all graphs have an edge builder, and may return a null value. In that case, Graph.addEdge(Object, Object) cannot be used, only Graph.addEdge(Object, Object, Object).

        Returns:
        the edge builder of this graph, or null if the graph does not have an edge builder

      • ensureVertexCapacity

        public void ensureVertexCapacity​(int vertexCapacity)
        Description copied from interface: Graph
        Hint the implementation to allocate space for at least vertexCapacity vertices.

        The implementation may ignore any calls to this function.

        Parameters:
        vertexCapacity - the minimum number of vertices to allocate space for

      • ensureEdgeCapacity

        public void ensureEdgeCapacity​(int edgeCapacity)
        Description copied from interface: Graph
        Hint the implementation to allocate space for at least edgeCapacity edges.

        The implementation may ignore any calls to this function.

        Parameters:
        edgeCapacity - the minimum number of edges to allocate space for

      • verticesWeights

        public <T,​WeightsT extends Weights<V,​T>> WeightsT verticesWeights​(String key)
        Description copied from interface: Graph
        Get the vertices weights of some key.

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        T - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
        Parameters:
        key - key of the weights
        Returns:
        vertices weights of the key, or null if no container found with the specified key

      • addVerticesWeights

        public <T,​WeightsT extends Weights<V,​T>> WeightsT addVerticesWeights​(String key,
                                                                                 Class<? super T> type,
                                                                                 T defVal)
        Description copied from interface: Graph
        Add a new weights container associated with the vertices of this graph with default value.

        The created weights will be bounded to this graph, and will be updated when the graph is updated. To create an external weights container, for example in cases the graph is a user input we are not allowed to modify it, use Weights.createExternalVerticesWeights(Graph, Class, Object). 

         
 Graph<String, Int> g = ...;
 g.newVertex("Alice");
 g.newVertex("Bob");
 g.newVertex("Charlie");

 Weights<String> names = g.addVerticesWeights("name", String.class, "Unknown");
 names.set("Alice", "Miller");
 names.set("Bob", "Jones");

 assert "Miller".equals(names.get("Alice"))
 assert "Jones".equals(names.get("Bob"))
 assert "Unknown".equals(names.get("Charlie"))

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        T - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
        Parameters:
        key - key of the weights, null is not allowed
        type - the type of the weights, used for primitive types weights
        defVal - default value use for the weights container
        Returns:
        a new weights container

      • removeVerticesWeights

        public void removeVerticesWeights​(String key)
        Description copied from interface: Graph
        Remove a weight type associated with the vertices of the graph.

        See Weights for a complete documentation of the weights containers.

        Parameters:
        key - the key of the weights

      • verticesWeightsKeys

        public Set<String> verticesWeightsKeys()
        Description copied from interface: Graph
        Get the keys of all the associated vertices weights.

        See Weights for a complete documentation of the weights containers.

        Returns:
        the keys of all the associated vertices weights

      • edgesWeights

        public <T,​WeightsT extends Weights<E,​T>> WeightsT edgesWeights​(String key)
        Description copied from interface: Graph
        Get the edges weights of some key.

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        T - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
        Parameters:
        key - key of the weights
        Returns:
        edges weights of the key, or null if no container found with the specified key

      • addEdgesWeights

        public <T,​WeightsT extends Weights<E,​T>> WeightsT addEdgesWeights​(String key,
                                                                              Class<? super T> type,
                                                                              T defVal)
        Description copied from interface: Graph
        Add a new weights container associated with the edges of this graph with default value.

        The created weights will be bounded to this graph, and will be updated when the graph is updated. To create an external weights container, for example in cases the graph is a user input we are not allowed to modify it, use Weights.createExternalEdgesWeights(Graph, Class, Object). 

         
 Graph<String, Integer> g = ...;
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);
 g.addEdge("Dresden", "Leipzig", 14);

 Weights<String> roadTypes = g.addEdgesWeights("roadType", String.class, "Unknown");
 roadTypes.set(9, "Asphalt");
 roadTypes.set(13, "Gravel");

 assert "Asphalt".equals(names.get(9))
 assert "Gravel".equals(names.get(13))
 assert "Unknown".equals(names.get(14))

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        T - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
        Parameters:
        key - key of the weights, null is not allowed
        type - the type of the weights, used for primitive types weights
        defVal - default value use for the weights container
        Returns:
        a new weights container

      • removeEdgesWeights

        public void removeEdgesWeights​(String key)
        Description copied from interface: Graph
        Remove a weight type associated with the edges of the graph.

        See Weights for a complete documentation of the weights containers.

        Parameters:
        key - the key of the weights

      • edgesWeightsKeys

        public Set<String> edgesWeightsKeys()
        Description copied from interface: Graph
        Get the keys of all the associated edges weights.

        See Weights for a complete documentation of the weights containers.

        Returns:
        the keys of all the associated edges weights

      • isDirected

        public boolean isDirected()
        Description copied from interface: Graph
        Checks whether the graph is directed.
        Returns:
        true if the graph is directed, else false.

      • isAllowSelfEdges

        public boolean isAllowSelfEdges()
        Description copied from interface: Graph
        Checks whether self edges are supported.

        Self edges are edges with the same source and target, namely a vertex with an edge to itself.

        Returns:
        true if the graph support self edges, else false.

      • isAllowParallelEdges

        public boolean isAllowParallelEdges()
        Description copied from interface: Graph
        Checks whether parallel edges are supported.

        Parallel edges are multiple edges with identical source and target.

        Returns:
        true if the graph support parallel edges, else false.

      • indexGraph

        public IndexGraph indexGraph()
        Description copied from interface: Graph
        Get an Index graph view of this graph.

        The returned IndexGraph is a graph in which the identifiers of the vertices are always (0,1,2, ...,verticesNum-1), and the identifiers of the edges are always (0,1,2, ...,edgesNum-1). To maintain this, the index graph implementation may rename existing vertices or edges along the graph lifetime. This rename behavior is less user friendly, but allow for high performance boost as no hash tables are needed, a simple array or bitmap can be used to map each vertex/edge to a value/weight/flag. See IndexGraph for more information. The IndexGraph should not be used in scenarios where performance does not matter.

        The returned graph is a view, namely a graph that will contain the same vertices and edges (with different int identifiers), and the same associated weights, that is automatically updated when the original graph is updated, but not visa versa. The index graph returned should not be modified directly by adding/removing vertices/edges/weights, use the enclosing graph instead.

        If this graph is an Index graph, this method returns this graph.

        Returns:
        an IndexGraph view of this graph

      • indexGraphVerticesMap

        public IndexIdMap<V> indexGraphVerticesMap()
        Description copied from interface: Graph
        Get the index-id vertices mapping of this graph.

        A regular graph contains vertices and edges which are identified by a fixed int IDs. An IndexGraph view is provided by the Graph.indexGraph() method, which is a graph in which all methods are accessed with indices rather than fixed IDs. This method expose the mapping between the indices and the fixed IDs of the graph vertices.

        Note that the mapping may change during the graph lifetime, as vertices are added and removed from the graph, and a regular graph IDs are fixed, while a index graph indices are always (0,1,2, ...,verticesNum-1). The returned mapping object will be updated automatically in such cases.

        Returns:
        a mapping that map vertices IDs to vertices indices

      • indexGraphEdgesMap

        public IndexIdMap<E> indexGraphEdgesMap()
        Description copied from interface: Graph
        Get the index-id edges mapping of this graph.

        A regular graph contains vertices and edges which are identified by a fixed int IDs. An IndexGraph view is provided by the Graph.indexGraph() method, which is a graph in which all methods are accessed with indices rather than fixed IDs. This method expose the mapping between the indices and the fixed IDs of the graph edges.

        Note that the mapping may change during the graph lifetime, as edges are added and removed from the graph, and a regular graph IDs are fixed, while a index graph indices are always (0,1,2, ...,edgesNum-1). The returned mapping object will be updated automatically in such cases.

        Returns:
        a mapping that map edges IDs to edges indices