Package com.jgalgo.adapt.jgrapht

Class JGraphTWrapper<V,E>

java.lang.Object
com.jgalgo.graph.AbstractGraph<V,E>
com.jgalgo.adapt.jgrapht.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:

  • Constructor Details

    • 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 Details

    • 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.

      The mapping of the vertices and edges indices to the original vertices and edges identifiers can be obtained by the Graph.indexGraphVerticesMap() and Graph.indexGraphEdgesMap() methods.

      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