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:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected Map<Pair<V,V>,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.UndirectedSpecifics

edgeSetFactory, graph, vertexMap

Constructor Summary

Constructors

Constructor and Description
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.

Method Summary

Modifier and Type	Method and 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, 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.
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(E e) Deprecated.
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.UndirectedSpecifics

addEdgeToTouchingVertices, addVertex, degreeOf, edgesOf, getEdgeContainer, getVertexSet, incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

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 Detail

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 Detail

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

@Deprecated
public void removeEdgeFromTouchingVertices(E e)

Deprecated.

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:

e - the edge

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