Package org.jgrapht.graph.specifics
Class FastLookupDirectedSpecifics<V,E>
- java.lang.Object
-
- org.jgrapht.graph.specifics.DirectedSpecifics<V,E>
-
- org.jgrapht.graph.specifics.FastLookupDirectedSpecifics<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.io.Serializable
,Specifics<V,E>
public class FastLookupDirectedSpecifics<V,E> extends DirectedSpecifics<V,E>
Fast implementation of DirectedSpecifics. 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 aDirectedSpecifics
instead.- Author:
- Joris Kinable
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected java.util.Map<Pair<V,V>,java.util.Set<E>>
touchingVerticesToEdgeMap
Maps a pair of vertices <u,v> to a set of edges {(u,v)}.-
Fields inherited from class org.jgrapht.graph.specifics.DirectedSpecifics
edgeSetFactory, graph, vertexMap
-
-
Constructor Summary
Constructors Constructor Description FastLookupDirectedSpecifics(Graph<V,E> graph, java.util.Map<V,DirectedEdgeContainer<V,E>> vertexMap, java.util.Map<Pair<V,V>,java.util.Set<E>> touchingVerticesToEdgeMap, EdgeSetFactory<V,E> edgeSetFactory)
Construct a new fast lookup directed specifics.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
addEdgeToTouchingVertices(V sourceVertex, V targetVertex, E e)
Adds the specified edge to the edge containers of its source and target vertices.boolean
addEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, E e)
Adds the specified edge to the edge containers of its source and target vertices only if the edge is not already in the graph.protected void
addToIndex(V sourceVertex, V targetVertex, E e)
Add an edge to the index.E
createEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, java.util.function.Supplier<E> edgeSupplier)
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.java.util.Set<E>
getAllEdges(V sourceVertex, V targetVertex)
Returns a set of all edges connecting source vertex to target vertex if such vertices exist in this graph.E
getEdge(V sourceVertex, V targetVertex)
Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph.void
removeEdgeFromTouchingVertices(V sourceVertex, V targetVertex, E e)
Removes the specified edge from the edge containers of its source and target vertices.protected void
removeFromIndex(V sourceVertex, V targetVertex, E e)
Remove an edge from the index.-
Methods inherited from class org.jgrapht.graph.specifics.DirectedSpecifics
addVertex, degreeOf, edgesOf, getEdgeContainer, getVertexSet, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf
-
-
-
-
Constructor Detail
-
FastLookupDirectedSpecifics
public FastLookupDirectedSpecifics(Graph<V,E> graph, java.util.Map<V,DirectedEdgeContainer<V,E>> vertexMap, java.util.Map<Pair<V,V>,java.util.Set<E>> touchingVerticesToEdgeMap, EdgeSetFactory<V,E> edgeSetFactory)
Construct a new fast lookup directed specifics.- Parameters:
graph
- the graph for which these specifics are forvertexMap
- 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 Detail
-
getAllEdges
public java.util.Set<E> getAllEdges(V sourceVertex, V targetVertex)
Description copied from class:DirectedSpecifics
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 isnull
, returnsnull
. If both vertices exist but no edges found, returns an empty set.- Specified by:
getAllEdges
in interfaceSpecifics<V,E>
- Overrides:
getAllEdges
in classDirectedSpecifics<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:DirectedSpecifics
Returns an edge connecting source vertex to target vertex if such vertices and such edge exist in this graph. Otherwise returnsnull
. If any of the specified vertices isnull
returnsnull
In undirected graphs, the returned edge may have its source and target vertices in the opposite order.
-
addEdgeToTouchingVertices
public boolean addEdgeToTouchingVertices(V sourceVertex, V targetVertex, E e)
Description copied from class:DirectedSpecifics
Adds the specified edge to the edge containers of its source and target vertices.- Specified by:
addEdgeToTouchingVertices
in interfaceSpecifics<V,E>
- Overrides:
addEdgeToTouchingVertices
in classDirectedSpecifics<V,E>
- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexe
- 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 interfaceSpecifics<V,E>
- Overrides:
addEdgeToTouchingVerticesIfAbsent
in classDirectedSpecifics<V,E>
- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexe
- the edge- Returns:
- true if the edge was added, false otherwise
-
createEdgeToTouchingVerticesIfAbsent
public E createEdgeToTouchingVerticesIfAbsent(V sourceVertex, V targetVertex, java.util.function.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 interfaceSpecifics<V,E>
- Overrides:
createEdgeToTouchingVerticesIfAbsent
in classDirectedSpecifics<V,E>
- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexedgeSupplier
- 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:DirectedSpecifics
Removes the specified edge from the edge containers of its source and target vertices.- Specified by:
removeEdgeFromTouchingVertices
in interfaceSpecifics<V,E>
- Overrides:
removeEdgeFromTouchingVertices
in classDirectedSpecifics<V,E>
- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexe
- the edge
-
addToIndex
protected void addToIndex(V sourceVertex, V targetVertex, E e)
Add an edge to the index.- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexe
- the edge
-
-