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 java.lang.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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	HashGraph.HashEdge<T,U> This class is the edge between nodes in the graph.
protected static class	HashGraph.HashNode<T,U> This class is a single node in the HashGraph.

Nested classes/interfaces inherited from interface org.savantbuild.util.Graph

Graph.BasePath<T>, Graph.Edge<T,U>, Graph.EdgeFilter<T,U>, Graph.GraphConsumer<T,U>, Graph.GraphVisitor<T,U>, Graph.Path<T>

Constructor Summary

Constructors

Constructor and Description
HashGraph()

Method Summary

Modifier and Type	Method and Description
void	addEdge(T origin, T destination, U value) Adds an edge between the node whose value is the origin value given and the node whose value is the destination value given.
protected HashGraph.HashNode<T,U>	addNode(T value)
protected void	clearEdges(HashGraph.HashNode<T,U> node)
boolean	contains(T value) Determines if the Graph contains the given value or not.
boolean	equals(java.lang.Object o)
protected T	find(HashGraph.HashNode<T,U> root, java.util.Set<T> visited, java.util.function.Predicate<T> predicate)
T	find(T rootValue, java.util.function.Predicate<T> predicate) Finds the first node in the graph that satisfies the predicate using a depth first traversal of the graph.
java.util.List<Graph.Edge<T,U>>	getInboundEdges(T value) Returns a list of all the inbound edges for the node whose value is given.
protected HashGraph.HashNode<T,U>	getNode(T value)
java.util.List<Graph.Edge<T,U>>	getOutboundEdges(T value) Returns a list of all the outbound edges for the node whose value is given.
java.util.List<Graph.Path<T>>	getPaths(T origin, T destination) Determines the path from the given origin value to given destination value.
int	hashCode()
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()
protected void	traverse(HashGraph.HashNode<T,U> root, HashGraph.HashEdge<T,U> traversedEdge, boolean visitNodesOnce, java.util.Set<T> cycleCheck, java.util.Set<T> visited, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer, int depth)
void	traverse(T rootValue, boolean visitNodesOnce, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer) Performs a depth first traversal of the graph.
protected void	traverseUp(HashGraph.HashNode<T,U> root, java.util.Set<T> visited, Graph.GraphVisitor<T,U> consumer, int depth)
void	traverseUp(T rootValue, Graph.GraphVisitor<T,U> visitor) Performs a depth first traversal of the graph.
java.util.Set<T>	values() Returns a Set that contains all of the unique artifacts contained in the graph.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HashGraph

public HashGraph()

Method Detail

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(java.lang.Object o)

Overrides:

equals in class java.lang.Object

find

public T find(T rootValue,
              java.util.function.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 java.util.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 java.util.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 java.util.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 java.lang.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 java.util.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,
                 java.util.Set<T> visited,
                 java.util.function.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,
                        java.util.Set<T> cycleCheck,
                        java.util.Set<T> visited,
                        Graph.EdgeFilter<T,U> edgeFilter,
                        Graph.GraphConsumer<T,U> consumer,
                        int depth)

traverseUp

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