Package org.savantbuild.util

Interface Graph<T,U>

All Known Implementing Classes:
HashGraph
public interface Graph<T,U>

This interface defines the generic graph data structure.

Graphs

Graphs are simple structures that model nodes with any number of connections between nodes. The connections are bi-directional and are called Edges. A two node graph with an edge between the nodes looks like this: 

 node1 <---> node2

The important point about Graphs is that implementations don't need to enforce a top level node that controls the entire structure like trees do. Instead, implementations can choose to have the graph store all of the nodes and the connections between them allowing for direct access to any node. These implementations should define how the direct access is managed and whether or not duplicate nodes can be stored.

Generics

There are two generics for a Graph. The first variable T is the content of the nodes themselves. Each node can stored a single value. The second generic is the value that can be associated with the Edge between nodes. This is carried throughout the entire graph structure making it very strongly typed.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static class 
    Graph.BasePath<T>
    A simple implementation for the Path interface.
    static interface 
    Graph.Edge<T,U>
    Interface for edges in the graph.
    static interface 
    Graph.EdgeFilter<T,U>
    Edge filter that determines if an edge should be included in a traversal.
    static interface 
    Graph.GraphConsumer<T,U>
    Consumer interface for graph traversal.
    static interface 
    Graph.GraphVisitor<T,U>
    Visitor interface for graph traversal.
    static interface 
    Graph.Path<T>
    Defines a path between two nodes in the graph.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(T origin, T destination, U edgeValue)
    Adds an edge between the node whose value is the origin value given and the node whose value is the destination value given.
    boolean
    contains(T value)
    Determines if the Graph contains the given value or not.
    T
    find(T rootValue, Predicate<T> predicate)
    Finds the first node in the graph that satisfies the predicate using a depth first traversal of the graph.
    List<Graph.Edge<T,U>>
    getInboundEdges(T value)
    Returns a list of all the inbound edges for the node whose value is given.
    List<Graph.Edge<T,U>>
    getOutboundEdges(T value)
    Returns a list of all the outbound edges for the node whose value is given.
    List<Graph.Path<T>>
    getPaths(T origin, T destination)
    Determines the path from the given origin value to given destination value.
    void
    prune(T... excludes)
    Removes all empty nodes from the graph except the given list of nodes.
    void
    removeEdge(T origin, T destination, U value)
    Removes the edge between the two nodes from the graph.
    void
    removeNode(T value)
    Removes the given value (node) from the graph and ensures that nothing is orphaned by the removal.
    int
    size()
     
    void
    traverse(T rootValue, boolean visitNodesOnce, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer)
    Traverses the graph in a depth-first manner starting at the node whose value is given.
    void
    traverseUp(T rootValue, Graph.GraphVisitor<T,U> visitor)
    Traverses the graph in a depth-first manner ending at the node whose value is given.
    Set<T>
    values()
    Returns a Set that contains all of the unique values contained in the graph.

  • Method Details

    • addEdge

      void addEdge(T origin, T destination, U edgeValue)
      Adds an edge between the node whose value is the origin value given and the node whose value is the destination value given. This method works well for implementations that only allow values to exist once.

      If there are no nodes for the given value, this method should create nodes for each value and then create an edge between them. This reduces the work required to edge values.

      Parameters:
      origin - The origin value that may or may not exist in the graph.
      destination - The destination value that may or may not exist in the graph.
      edgeValue - The value to associate with the edge.

    • contains

      boolean contains(T value)
      Determines if the Graph contains the given value or not.
      Parameters:
      value - The value.
      Returns:
      True if the value is in the graph, false otherwise.

    • find

      T find(T rootValue, Predicate<T> predicate) throws CyclicException
      Finds the first node in the graph that satisfies the predicate using a depth first traversal of the graph.
      Parameters:
      rootValue - The value of the node to start the traversal from.
      predicate - The predicate used to find the node.
      Returns:
      The value at the node or null if the node isn't found.
      Throws:
      CyclicException - If there is a cycle in the graph.

    • getInboundEdges

      List<Graph.Edge<T,U>> getInboundEdges(T value)
      Returns a list of all the inbound edges for the node whose value is given. This locates the first node with the value.
      Parameters:
      value - The value to find the edges for.
      Returns:
      The edges or an empty list if the node exists and has no edges or null if the node does not exist.

    • getOutboundEdges

      List<Graph.Edge<T,U>> getOutboundEdges(T value)
      Returns a list of all the outbound edges for the node whose value is given. This locates the first node with the value.
      Parameters:
      value - The value to find the edges for.
      Returns:
      The edges or an empty list if the node exists and has no edges or null if the node does not exist.

    • getPaths

      List<Graph.Path<T>> getPaths(T origin, T destination)
      Determines the path from the given origin value to given destination value.
      Parameters:
      origin - The origin value.
      destination - The destination value.
      Returns:
      A list of all the paths between the two nodes or an empty list if there are none or null if either of the nodes don't exist.

    • prune

      void prune(T... excludes)
      Removes all empty nodes from the graph except the given list of nodes.
      Parameters:
      excludes - The nodes to exclude from pruning.

    • removeEdge

      void removeEdge(T origin, T destination, U value)
      Removes the edge between the two nodes from the graph.
      Parameters:
      origin - The origin value.
      destination - The destination value.
      value - The edge value.

    • removeNode

      void removeNode(T value) throws CyclicException
      Removes the given value (node) from the graph and ensures that nothing is orphaned by the removal.
      Parameters:
      value - The value to remove.
      Throws:
      CyclicException - If the graph has any cycles in it.

    • size

      int size()
      Returns:
      The size of the graph (number of nodes).

    • traverse

      void traverse(T rootValue, boolean visitNodesOnce, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer) throws CyclicException
      Traverses the graph in a depth-first manner starting at the node whose value is given. The GraphConsumer is called for each edge in the graph.
      Parameters:
      rootValue - The value of the node to start the traversal from.
      visitNodesOnce - Determines if nodes should be visited once or multiple times during the traversal. Graphs can have nodes with multiple links to them. Therefore, a traversal might visit the same node twice. This flag determines if the traversal should visit nodes once only.
      edgeFilter - The edge filter used to control the traversal if necessary. If this is null, the identity filter is used, which essentially keeps all of the edges.
      consumer - The GraphConsumer that is called for each edge.
      Throws:
      CyclicException - If there is a cycle in the graph.

    • traverseUp

      void traverseUp(T rootValue, Graph.GraphVisitor<T,U> visitor) throws CyclicException
      Traverses the graph in a depth-first manner ending at the node whose value is given. This traverses down the Graph until a leaf is reached and then it begins calling the GraphConsumer on the way back up.
      Parameters:
      rootValue - The value of the node to start the traversal from.
      visitor - The GraphVisitor that is called for each edge.
      Throws:
      CyclicException - If there is a cycle in the graph.

    • values

      Set<T> values()
      Returns a Set that contains all of the unique values contained in the graph.
      Returns:
      All the values.