Package org.savantbuild.util

Class HashGraph<T,U>

java.lang.Object
org.savantbuild.util.HashGraph<T,U>
All Implemented Interfaces:
Graph<T,U>
public class HashGraph<T,U> extends Object implements Graph<T,U>

This class is used to construct and manage graph structures. This is a simple class that makes the navigation and usage of Graphs simple and accessible.

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 they don't enforce a top level node that controls the entire structure like trees do. Instead, the graph has access to all nodes and the connections between them. This makes finding a Node easy and then traversing the graph also easy.

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.

Internals

It is important to understand how the Graph works internally. Nodes are stored in a Map whose key is the value for the node. If the graph is storing Strings then only a single node can exist with the value foo. This means that the graph does not allow duplicates. Therefore it would be impossible to have two nodes whose values are foo with different edges. The key of the Map is a HashGraph.HashNode object. The node stores the value as well as all the edges.

Node values

Due to the implementation of the graph, all values must have a good equal and hashcode implementation. Using the object identity is allowed and will then manage the graph based on the heap location of the value objects (pointers are used for the java.lang.Object version of equals and hashcode).

Thread safety

The Graph is not thread safe. Classes must synchronize on the graph instance in order to protect multi-threaded use.

  • Constructor Details

    • HashGraph

      public HashGraph()

  • Method Details

    • addEdge

      public void addEdge(T origin, T destination, U value)
      Description copied from interface: Graph
      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.

      Specified by:
      addEdge in interface Graph<T,U>
      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.
      value - The value to associate with the edge.

    • contains

      public boolean contains(T value)
      Description copied from interface: Graph
      Determines if the Graph contains the given value or not.
      Specified by:
      contains in interface Graph<T,U>
      Parameters:
      value - The value.
      Returns:
      True if the value is in the graph, false otherwise.

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • find

      public 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.
      Specified by:
      find in interface Graph<T,U>
      Parameters:
      rootValue - The value of the node to start the traversal from.
      predicate - The predicate used to find the node.
      Returns:
      The value of the first node that matches the predicate starting at the rootValue node. Null if the rootValue not doesn't exist or if no nodes match the predicate.
      Throws:
      CyclicException - If there is a cycle in the graph.

    • getInboundEdges

      public List<Graph.Edge<T,U>> getInboundEdges(T value)
      Description copied from interface: Graph
      Returns a list of all the inbound edges for the node whose value is given. This locates the first node with the value.
      Specified by:
      getInboundEdges in interface Graph<T,U>
      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

      public List<Graph.Edge<T,U>> getOutboundEdges(T value)
      Description copied from interface: Graph
      Returns a list of all the outbound edges for the node whose value is given. This locates the first node with the value.
      Specified by:
      getOutboundEdges in interface Graph<T,U>
      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

      public List<Graph.Path<T>> getPaths(T origin, T destination)
      Description copied from interface: Graph
      Determines the path from the given origin value to given destination value.
      Specified by:
      getPaths in interface Graph<T,U>
      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.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • prune

      public void prune(T... excludes)
      Description copied from interface: Graph
      Removes all empty nodes from the graph except the given list of nodes.
      Specified by:
      prune in interface Graph<T,U>
      Parameters:
      excludes - The nodes to exclude from pruning.

    • removeEdge

      public void removeEdge(T origin, T destination, U value)
      Description copied from interface: Graph
      Removes the edge between the two nodes from the graph.
      Specified by:
      removeEdge in interface Graph<T,U>
      Parameters:
      origin - The origin value.
      destination - The destination value.
      value - The edge value.

    • removeNode

      public void removeNode(T value) throws CyclicException
      Description copied from interface: Graph
      Removes the given value (node) from the graph and ensures that nothing is orphaned by the removal.
      Specified by:
      removeNode in interface Graph<T,U>
      Parameters:
      value - The value to remove.
      Throws:
      CyclicException - If the graph has any cycles in it.

    • size

      public int size()
      Specified by:
      size in interface Graph<T,U>
      Returns:
      The size of the graph (number of nodes).

    • traverse

      public void traverse(T rootValue, boolean visitNodesOnce, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer) throws CyclicException
      Performs a depth first traversal of the graph. For each node, the GraphConsumer is called. The traversal WILL traverse the same node twice if it has multiple connections.
      Specified by:
      traverse in interface Graph<T,U>
      Parameters:
      rootValue - The value of the node to start the traversal from.
      visitNodesOnce - Determines if nodes are visited once if they have multiple links.
      edgeFilter - The EdgeFilter that is used to control the traversal.
      consumer - The GraphConsumer that is called for each edge.
      Throws:
      CyclicException - If there is a cycle in the graph.

    • traverseUp

      public void traverseUp(T rootValue, Graph.GraphVisitor<T,U> visitor) throws CyclicException
      Performs a depth first traversal of the graph. For each node, the GraphConsumer is called. The traversal WILL traverse the same node twice if it has multiple connections.
      Specified by:
      traverseUp in interface Graph<T,U>
      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

      public Set<T> values()
      Returns a Set that contains all of the unique artifacts contained in the graph.
      Specified by:
      values in interface Graph<T,U>
      Returns:
      All the artifacts.

    • addNode

      protected HashGraph.HashNode<T,U> addNode(T value)

    • clearEdges

      protected void clearEdges(HashGraph.HashNode<T,U> node)

    • find

      protected T find(HashGraph.HashNode<T,U> root, Set<T> visited, Predicate<T> predicate)

    • getNode

      protected HashGraph.HashNode<T,U> getNode(T value)

    • traverse

      protected void traverse(HashGraph.HashNode<T,U> root, HashGraph.HashEdge<T,U> traversedEdge, boolean visitNodesOnce, Set<T> cycleCheck, Set<T> visited, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer, int depth)

    • traverseUp

      protected void traverseUp(HashGraph.HashNode<T,U> root, Set<T> visited, Graph.GraphVisitor<T,U> consumer, int depth)