Package org.jgrapht.alg.util

Class NeighborCache<V,​E>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:
    java.util.EventListener, GraphListener<V,​E>, VertexSetListener<V>
    public class NeighborCache<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 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.

    Author:
    Szabolcs Besenyei

    • Constructor Summary

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

    • 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.
      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 unique neighbors of the given vertex if it exists in the cache, otherwise it is initialized.
      java.util.Set<V> predecessorsOf​(V v)
      Returns the unique predecessors of the given vertex if it exists in the cache, otherwise it is initialized.
      java.util.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

    • Constructor Detail

      • NeighborCache

        public NeighborCache​(Graph<V,​E> graph)
        Constructor
        Parameters:
        graph - the input graph
        Throws:
        java.lang.NullPointerException - if the input graph is null

    • Method Detail

      • predecessorsOf

        public java.util.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 java.util.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 java.util.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 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 use neighborsOf(V) unless duplicate neighbors are important.
        Parameters:
        v - the vertex whose neighbors are desired
        Returns:
        all neighbors of the specified vertex