Package org.jgrapht.alg
Class NeighborIndex<V,E>
- java.lang.Object
-
- org.jgrapht.alg.NeighborIndex<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.util.EventListener
,GraphListener<V,E>
,VertexSetListener<V>
public class NeighborIndex<V,E> extends java.lang.Object implements GraphListener<V,E>
Maintains a cache of each vertex's neighbors. While lists of neighbors can be obtained fromGraphs
, they are re-calculated at each invocation by walking a vertex's incident edges, which becomes inordinately expensive when performed often.Edge direction is ignored when evaluating neighbors; to take edge direction into account when indexing neighbors, use
DirectedNeighborIndex
.A vertex's neighbors are cached the first time they are asked for (i.e. the index is built on demand). The index will only be updated automatically if it is added to the associated graph as a listener. If it is added as a listener to a graph other than the one it indexes, results are undefined.
- Since:
- Dec 13, 2005
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
NeighborIndex.Neighbors<V>
Stores cached neighbors for a single vertex.
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
(package private) java.util.Map<V,NeighborIndex.Neighbors<V>>
neighborMap
-
Constructor Summary
Constructors Constructor Description NeighborIndex(Graph<V,E> g)
Creates a neighbor index for the specified undirected graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.private NeighborIndex.Neighbors<V>
getNeighbors(V v)
java.util.List<V>
neighborListOf(V v)
Returns a list of vertices which are adjacent to a specified vertex.java.util.Set<V>
neighborsOf(V v)
Returns the set of vertices which are adjacent to a specified vertex.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.
-
-
-
Method Detail
-
neighborsOf
public java.util.Set<V> neighborsOf(V v)
Returns the set of vertices which are adjacent to a specified vertex. The returned set is backed by the index, and will be updated when the graph changes as long as the index has been added as a listener to the graph.- Parameters:
v
- the vertex whose neighbors are desired- Returns:
- all unique neighbors of the specified vertex
-
neighborListOf
public java.util.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 useneighborsOf(Object)
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 interfaceGraphListener<V,E>
- Parameters:
e
- the edge event.- See Also:
GraphListener.edgeAdded(GraphEdgeChangeEvent)
-
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 interfaceGraphListener<V,E>
- Parameters:
e
- the edge event.- See Also:
GraphListener.edgeRemoved(GraphEdgeChangeEvent)
-
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 interfaceVertexSetListener<V>
- Parameters:
e
- the vertex event.- See Also:
VertexSetListener.vertexAdded(GraphVertexChangeEvent)
-
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 interfaceVertexSetListener<V>
- Parameters:
e
- the vertex event.- See Also:
VertexSetListener.vertexRemoved(GraphVertexChangeEvent)
-
getNeighbors
private NeighborIndex.Neighbors<V> getNeighbors(V v)
-
-