public interface Graph<T,U>
This interface defines the generic graph data structure.
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.
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.
Modifier and Type | Interface and 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.
|
Modifier and Type | Method and 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,
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.
|
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.
|
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.
|
java.util.Set<T> |
values()
Returns a Set that contains all of the unique values contained in the graph.
|
void addEdge(T origin, T destination, U edgeValue)
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.
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.boolean contains(T value)
value
- The value.T find(T rootValue, java.util.function.Predicate<T> predicate) throws CyclicException
rootValue
- The value of the node to start the traversal from.predicate
- The predicate used to find the node.CyclicException
- If there is a cycle in the graph.java.util.List<Graph.Edge<T,U>> getInboundEdges(T value)
value
- The value to find the edges for.java.util.List<Graph.Edge<T,U>> getOutboundEdges(T value)
value
- The value to find the edges for.java.util.List<Graph.Path<T>> getPaths(T origin, T destination)
origin
- The origin value.destination
- The destination value.void prune(T... excludes)
excludes
- The nodes to exclude from pruning.void removeEdge(T origin, T destination, U value)
origin
- The origin value.destination
- The destination value.value
- The edge value.void removeNode(T value) throws CyclicException
value
- The value to remove.CyclicException
- If the graph has any cycles in it.int size()
void traverse(T rootValue, boolean visitNodesOnce, Graph.EdgeFilter<T,U> edgeFilter, Graph.GraphConsumer<T,U> consumer) throws CyclicException
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.CyclicException
- If there is a cycle in the graph.void traverseUp(T rootValue, Graph.GraphVisitor<T,U> visitor) throws CyclicException
rootValue
- The value of the node to start the traversal from.visitor
- The GraphVisitor that is called for each edge.CyclicException
- If there is a cycle in the graph.java.util.Set<T> values()