Module org.jgrapht.core
Package org.jgrapht.graph.specifics

Class FastLookupUndirectedSpecifics<V,E>

java.lang.Object
org.jgrapht.graph.specifics.UndirectedSpecifics<V,E>
org.jgrapht.graph.specifics.FastLookupUndirectedSpecifics<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
Serializable, Specifics<V,E>
public class FastLookupUndirectedSpecifics<V,E> extends UndirectedSpecifics<V,E>
Fast implementation of UndirectedSpecifics. This class uses additional data structures to improve the performance of methods which depend on edge retrievals, e.g. getEdge(V u, V v), containsEdge(V u, V v), addEdge(V u, V v). A disadvantage is an increase in memory consumption. If memory utilization is an issue, use a UndirectedSpecifics instead.
Author:
Joris Kinable
See Also:

  • Field Details

    • touchingVerticesToEdgeMap

      protected Map<Pair<V,V>,Set<E>> touchingVerticesToEdgeMap
      Maps a pair of vertices <u,v> to a set of edges {(u,v)}. In case of a multigraph, all edges which touch both u and v are included in the set.

  • Constructor Details

    • FastLookupUndirectedSpecifics

      public FastLookupUndirectedSpecifics(Graph<V,E> graph, Map<V,UndirectedEdgeContainer<V,E>> vertexMap, Map<Pair<V,V>,Set<E>> touchingVerticesToEdgeMap, EdgeSetFactory<V,E> edgeSetFactory)
      Construct a new fast lookup undirected specifics.
      Parameters:
      graph - the graph for which these specifics are for
      vertexMap - map for the storage of vertex edge sets. Needs to have a predictable iteration order.
      touchingVerticesToEdgeMap - Additional map for caching. No need for a predictable iteration order.
      edgeSetFactory - factory for the creation of vertex edge sets

  • Method Details

    • getAllEdges

      public Set<E> getAllEdges(V sourceVertex, V targetVertex)
      Description copied from class: UndirectedSpecifics
      Returns a set of all edges connecting source vertex to target vertex if such vertices exist in this graph. If any of the vertices does not exist or is null, returns null. If both vertices exist but no edges found, returns an empty set.
      Specified by:
      getAllEdges in interface Specifics<V,E>
      Overrides:
      getAllEdges in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - source vertex of the edge.
      targetVertex - target vertex of the edge.
      Returns:
      a set of all edges connecting source vertex to target vertex.

    • getEdge

      public E getEdge(V sourceVertex, V targetVertex)
      Description copied from class: UndirectedSpecifics
      Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph. Otherwise returns null. If any of the specified vertices is null returns null

      In undirected graphs, the returned edge may have its source and target vertices in the opposite order.

      Specified by:
      getEdge in interface Specifics<V,E>
      Overrides:
      getEdge in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - source vertex of the edge.
      targetVertex - target vertex of the edge.
      Returns:
      an edge connecting source vertex to target vertex.

    • addEdgeToTouchingVertices

      public boolean addEdgeToTouchingVertices(V sourceVertex, V targetVertex, E e)
      Description copied from interface: Specifics
      Adds the specified edge to the edge containers of its source and target vertices.
      Specified by:
      addEdgeToTouchingVertices in interface Specifics<V,E>
      Overrides:
      addEdgeToTouchingVertices in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      e - the edge
      Returns:
      true if the edge was added, false otherwise

    • addEdgeToTouchingVerticesIfAbsent

      public boolean addEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, E e)
      Description copied from interface: Specifics
      Adds the specified edge to the edge containers of its source and target vertices only if the edge is not already in the graph.
      Specified by:
      addEdgeToTouchingVerticesIfAbsent in interface Specifics<V,E>
      Overrides:
      addEdgeToTouchingVerticesIfAbsent in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      e - the edge
      Returns:
      true if the edge was added, false otherwise

    • createEdgeToTouchingVerticesIfAbsent

      public E createEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, Supplier<E> edgeSupplier)
      Description copied from interface: Specifics
      Creates an edge given an edge supplier and adds it to the edge containers of its source and target vertices only if the graph does not contain other edges with the same source and target vertices.
      Specified by:
      createEdgeToTouchingVerticesIfAbsent in interface Specifics<V,E>
      Overrides:
      createEdgeToTouchingVerticesIfAbsent in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      edgeSupplier - the function which will create the edge
      Returns:
      the newly created edge or null if an edge with the same source and target vertices was already present

    • removeEdgeFromTouchingVertices

      public void removeEdgeFromTouchingVertices(V sourceVertex, V targetVertex, E e)
      Description copied from class: UndirectedSpecifics
      Removes the specified edge from the edge containers of its source and target vertices.
      Specified by:
      removeEdgeFromTouchingVertices in interface Specifics<V,E>
      Overrides:
      removeEdgeFromTouchingVertices in class UndirectedSpecifics<V,E>
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      e - the edge

    • addToIndex

      protected void addToIndex(V sourceVertex, V targetVertex, E e)
      Add an edge to the index.
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      e - the edge

    • removeFromIndex

      protected void removeFromIndex(V sourceVertex, V targetVertex, E e)
      Remove an edge from the index.
      Parameters:
      sourceVertex - the source vertex
      targetVertex - the target vertex
      e - the edge