Package org.jgrapht.alg
Class DirectedNeighborIndex<V,E>
java.lang.Object
org.jgrapht.alg.DirectedNeighborIndex<V,E>
- All Implemented Interfaces:
EventListener
,GraphListener<V,
,E> VertexSetListener<V>
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.
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
- Author:
- Charles Fry
-
Constructor Summary
ConstructorsConstructorDescriptionCreates a neighbor index for the specified directed graph. -
Method Summary
Modifier and TypeMethodDescriptionvoid
Notifies that an edge has been added to the graph.void
Notifies that an edge has been removed from the graph.Returns the set of vertices which are the predecessors of a specified vertex.predecessorsOf
(V v) Returns the set of vertices which are the predecessors of a specified vertex.successorListOf
(V v) Returns the set of vertices which are the successors of a specified vertex.successorsOf
(V v) Returns the set of vertices which are the successors of a specified vertex.void
Notifies that a vertex has been added to the graph.void
Notifies that a vertex has been removed from the graph.
-
Constructor Details
-
DirectedNeighborIndex
Creates a neighbor index for the specified directed graph.- Parameters:
g
- the graph for which a neighbor index is to be created.
-
-
Method Details
-
predecessorsOf
Returns the set of vertices which are the predecessors of 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 predecessors are desired- Returns:
- all unique predecessors of the specified vertex
-
predecessorListOf
Returns the set of vertices which are the predecessors of a specified vertex. If the graph is a multigraph, vertices may appear more than once in the returned list. Because a list of predecessors can not be efficiently maintained, it is reconstructed on every invocation by duplicating entries in the neighbor set. It is thus more efficient to usepredecessorsOf(Object)
unless duplicate neighbors are required.- Parameters:
v
- the vertex whose predecessors are desired- Returns:
- all predecessors of the specified vertex
-
successorsOf
Returns the set of vertices which are the successors of 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 successors are desired- Returns:
- all unique successors of the specified vertex
-
successorListOf
Returns the set of vertices which are the successors of a specified vertex. If the graph is a multigraph, vertices may appear more than once in the returned list. Because a list of successors can not be efficiently maintained, it is reconstructed on every invocation by duplicating entries in the neighbor set. It is thus more efficient to usesuccessorsOf(Object)
unless duplicate neighbors are required.- Parameters:
v
- the vertex whose successors are desired- Returns:
- all successors of the specified vertex
-
edgeAdded
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:
-
edgeRemoved
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:
-
vertexAdded
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:
-
vertexRemoved
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:
-