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) Deprecated. Since default strategies should be decided at a higher level.
FastLookupUndirectedSpecifics(Graph<V,E> graph, Map<V,UndirectedEdgeContainer<V,E>> vertexMap) Deprecated. Since default strategies should be decided at a higher level.
FastLookupUndirectedSpecifics(Graph<V,E> graph, Map<V,UndirectedEdgeContainer<V,E>> vertexMap, EdgeSetFactory<V,E> edgeSetFactory) Deprecated. Since default strategies should be decided at a higher level.
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
void	addEdgeToTouchingVertices(E e) Adds the specified edge to the edge containers of its 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) Removes the specified edge from the edge containers of its source and target vertices.

Methods inherited from class org.jgrapht.graph.specifics.UndirectedSpecifics

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

@Deprecated
public FastLookupUndirectedSpecifics(Graph<V,E> graph)

Deprecated. Since default strategies should be decided at a higher level.

Construct a new fast lookup undirected specifics.

Parameters:

graph - the graph for which these specifics are for

FastLookupUndirectedSpecifics

@Deprecated
public FastLookupUndirectedSpecifics(Graph<V,E> graph,
                                                 Map<V,UndirectedEdgeContainer<V,E>> vertexMap)

Deprecated. Since default strategies should be decided at a higher level.

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

FastLookupUndirectedSpecifics

@Deprecated
public FastLookupUndirectedSpecifics(Graph<V,E> graph,
                                                 Map<V,UndirectedEdgeContainer<V,E>> vertexMap,
                                                 EdgeSetFactory<V,E> edgeSetFactory)

Deprecated. Since default strategies should be decided at a higher level.

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.

edgeSetFactory - factory for the creation of vertex edge sets

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)

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)

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 void addEdgeToTouchingVertices(E e)

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:

e - the edge

removeEdgeFromTouchingVertices

public void removeEdgeFromTouchingVertices(E e)

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