org.jgrapht.alg.util

Class NeighborCache<V,E>

java.lang.Object

org.jgrapht.alg.util.NeighborCache<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

EventListener, GraphListener<V,E>, VertexSetListener<V>

public class NeighborCache<V,E>
extends Object
implements GraphListener<V,E>

Maintains a cache of each vertex's neighbors. While lists of neighbors can be obtained from Graphs, they are re-calculated at each invocation by walking a vertex's incident edges, which becomes inordinately expensive when performed often.

The cache also keeps track of successors and predecessors for each vertex. This means that the result of the union of calling predecessorsOf(v) and successorsOf(v) is equal to the result of calling neighborsOf(v) for a given vertex v.

Since:

November 2017

Author:

Szabolcs Besenyei

Constructor Summary

Constructors

Constructor and Description
NeighborCache(Graph<V,E> graph) Constructor

Method Summary

Modifier and Type	Method and Description
void	edgeAdded(GraphEdgeChangeEvent<V,E> e) Notifies that an edge has been added to the graph.
void	edgeRemoved(GraphEdgeChangeEvent<V,E> e) Notifies that an edge has been removed from the graph.
List<V>	neighborListOf(V v) Returns a list of vertices which are adjacent to a specified vertex.
Set<V>	neighborsOf(V v) Returns the unique neighbors of the given vertex if it exists in the cache, otherwise it is initialized.
Set<V>	predecessorsOf(V v) Returns the unique predecessors of the given vertex if it exists in the cache, otherwise it is initialized.
Set<V>	successorsOf(V v) Returns the unique successors of the given vertex if it exists in the cache, otherwise it is initialized.
void	vertexAdded(GraphVertexChangeEvent<V> e) Notifies that a vertex has been added to the graph.
void	vertexRemoved(GraphVertexChangeEvent<V> e) Notifies that a vertex has been removed from the graph.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.event.GraphListener

edgeWeightUpdated

Constructor Detail

NeighborCache

public NeighborCache(Graph<V,E> graph)

Constructor

Parameters:

graph - the input graph

Throws:

NullPointerException - if the input graph is null

Method Detail

predecessorsOf

public Set<V> predecessorsOf(V v)

Returns the unique predecessors of the given vertex if it exists in the cache, otherwise it is initialized.

Parameters:

v - the given vertex

Returns:

the unique predecessors of the given vertex

successorsOf

public Set<V> successorsOf(V v)

Returns the unique successors of the given vertex if it exists in the cache, otherwise it is initialized.

Parameters:

v - the given vertex

Returns:

the unique successors of the given vertex

neighborsOf

public Set<V> neighborsOf(V v)

Returns the unique neighbors of the given vertex if it exists in the cache, otherwise it is initialized.

Parameters:

v - the given vertex

Returns:

the unique neighbors of the given vertex

neighborListOf

public List<V> neighborListOf(V v)

Returns a list of vertices which are adjacent to a specified vertex. If the graph is a multigraph, vertices may appear more than once in the returned list. Because a list of neighbors can not be efficiently maintained, it is reconstructed on every invocation, by duplicating entries in the neighbor set. It is thus more efficient to use neighborsOf(V) unless duplicate neighbors are important.

Parameters:

v - the vertex whose neighbors are desired

Returns:

all neighbors of the specified vertex

edgeAdded

public void edgeAdded(GraphEdgeChangeEvent<V,E> e)

Description copied from interface: GraphListener

Notifies that an edge has been added to the graph.

Specified by:

edgeAdded in interface GraphListener<V,E>

Parameters:

e - the edge event.

edgeRemoved

public void edgeRemoved(GraphEdgeChangeEvent<V,E> e)

Description copied from interface: GraphListener

Notifies that an edge has been removed from the graph.

Specified by:

edgeRemoved in interface GraphListener<V,E>

Parameters:

e - the edge event.

vertexAdded

public void vertexAdded(GraphVertexChangeEvent<V> e)

Description copied from interface: VertexSetListener

Notifies that a vertex has been added to the graph.

Specified by:

vertexAdded in interface VertexSetListener<V>

Parameters:

e - the vertex event.

vertexRemoved

public void vertexRemoved(GraphVertexChangeEvent<V> e)

Description copied from interface: VertexSetListener

Notifies that a vertex has been removed from the graph.

Specified by:

vertexRemoved in interface VertexSetListener<V>

Parameters:

e - the vertex event.