oracle.javatools.util

Class Graph<T>

java.lang.Object

java.util.AbstractCollection<T>

oracle.javatools.util.Graph<T>

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>

public class Graph<T>
extends java.util.AbstractCollection<T>

A directed graph consisting of vertices of type T. The graph may contain cycles, and is therefore not strictly a DAG. However, this class contains a cycle detection algorithm in the getSortedVertices() method.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Graph.Cycle
static class	Graph.CycleException
class	Graph.Visitor

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Map<T,oracle.javatools.util.Graph.Vertex<T>>	_vertices

Constructor Summary

Constructors

Constructor and Description
Graph()
Graph(java.util.Collection<T> vertices) Constructs a graph containing all elements in the specified collection as vertices.
Graph(Graph<T> original) Copy constructor.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(T vertex) Adds a vertex to the graph.
void	connect(T from, T to) Creates a connection between two vertices.
boolean	contains(java.lang.Object vertex)
java.util.Comparator<T>	createComparator() Creates a comparator that can be used to compare any two items in the graph based on their sorted order (i.e.
void	dfs(T start, boolean direction, Graph.Visitor visitor)
java.util.List<Graph.Cycle>	findCycles()
java.util.List<T>	findElementaryCycle(Graph.Cycle cycle)
java.lang.String	getCycleMessage(java.util.List<Graph.Cycle> cycles)
java.lang.String	getElementaryCycleMessage(java.util.List<Graph.Cycle> cycles) Returns the list of elementary cycles found, in the form of a numbered list suitable for displaying in an IDE dialog.
java.util.List<T>	getInwardEdges(T to) Returns the list of vertices that a connects to a specified vertex.
java.util.List<T>	getOutwardEdges(T from) Returns the list of vertices that a specified vertex connects to.
java.util.List<T>	getSortedVertices() Get an ordered list of vertices, sorted such that for any given vertex A with a directed edge to vertex B, index(B) < index(A).
java.util.List<T>	getSortedVertices(T startVertex) Get an ordered list of vertices, sorted such that for any given vertex A with a directed edge to vertex B, index(B) < index(A).
java.util.List<T>	getVerticesConnectedTo(T vertex) Get all vertices connected to the specified vertex.
java.util.Iterator<T>	iterator() Returns an iterator over the vertices in this graph.
boolean	remove(java.lang.Object vertex)
int	size()
Graph<T>	subgraph(java.util.Collection<T> vertices) Returns a new graph containing only the specified vertices.
static <Z> Graph<Z>	unmodifiableGraph(Graph<? extends Z> graph) Returns a graph based on the specified graph, but which does not permit modification.

Methods inherited from class java.util.AbstractCollection

addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Field Detail

_vertices

protected java.util.Map<T,oracle.javatools.util.Graph.Vertex<T>> _vertices

Constructor Detail

Graph

public Graph(Graph<T> original)

Copy constructor. Creates a new graph instance that is identical to the specified original graph.

Parameters:

original - a graph to copy.

Graph

public Graph()

Graph

public Graph(java.util.Collection<T> vertices)

Constructs a graph containing all elements in the specified collection as vertices.

Parameters:

vertices - vertices to add to the collection. Note that, per the general contract of Collection.add(E), the collection must not contain any duplicate elements. If it does, this constructor will throw an IllegalArgumentException.

Method Detail

dfs

public void dfs(T start,
       boolean direction,
       Graph.Visitor visitor)

createComparator

public java.util.Comparator<T> createComparator()
                                         throws Graph.CycleException

Creates a comparator that can be used to compare any two items in the graph based on their sorted order (i.e. the order returned by the #getSortedVertices(T) method).

The returned Comparator is not live-connected to the graph. If you make changes to the graph after retrieving a comparator, the comparator will no longer be correct.

Returns:

a comparator suitable for sorting vertices.

Throws:

Graph.CycleException

contains

public boolean contains(java.lang.Object vertex)

Specified by:

contains in interface java.util.Collection<T>

Overrides:

contains in class java.util.AbstractCollection<T>

add

public boolean add(T vertex)

Adds a vertex to the graph. The vertex will initially be disconnected.

Specified by:

add in interface java.util.Collection<T>

Overrides:

add in class java.util.AbstractCollection<T>

Parameters:

vertex - a vertex to add to the graph. It's illegal to add a vertex to the graph that is already present. Trying to do so will throw an IllegalArgumentException.

connect

public void connect(T from,
           T to)

Creates a connection between two vertices.

Parameters:

from - a vertex at the "from" end of a directed connection. The vertex must be added first using add(T).

to - a vertex at the "to" end of a directed connection. The vertex must be added first using add(T).

Throws:

java.lang.IllegalArgumentException - if you attempt to connect a vertex to itself, i.e. if from == to.

getOutwardEdges

public java.util.List<T> getOutwardEdges(T from)

Returns the list of vertices that a specified vertex connects to. The resulting set of vertices is non transitive, i.e. only includes vertices that have edges directly connected from the specified vertex.

Parameters:

from - a vertex that must be in the graph.

Returns:

a list of vertices that the specified vertex connects to.

getInwardEdges

public java.util.List<T> getInwardEdges(T to)

Returns the list of vertices that a connects to a specified vertex. The resulting set of vertices is non transitive, i.e. only includes vertices that have edges directly connected to the specified vertex.

Parameters:

to - a vertex that must be in the graph.

Returns:

a list of vertices that connect to the specified vertex.

subgraph

public Graph<T> subgraph(java.util.Collection<T> vertices)

Returns a new graph containing only the specified vertices. Any edges to vertices not in the specified collection are removed. this graph is unaffected by this operation.

Parameters:

vertices - a collection of vertices to retain.

Returns:

a subgraph of this graph containing only the specified vertices.

findCycles

public java.util.List<Graph.Cycle> findCycles()

Returns:

a list of all cycles in the graph; no member appears in more than one cycle

findElementaryCycle

public java.util.List<T> findElementaryCycle(Graph.Cycle cycle)

getCycleMessage

public java.lang.String getCycleMessage(java.util.List<Graph.Cycle> cycles)

Parameters:

cycles - the list returned by findCycles()

Returns:

formatted text message that enumerates and describes the cycles

getElementaryCycleMessage

public java.lang.String getElementaryCycleMessage(java.util.List<Graph.Cycle> cycles)

Returns the list of elementary cycles found, in the form of a numbered list suitable for displaying in an IDE dialog.

Parameters:

cycles - the list returned by findCycles()

Returns:

formatted text message that enumerates the elementary cycles, or null if there are none

iterator

public java.util.Iterator<T> iterator()

Returns an iterator over the vertices in this graph. The iterator is unsorted, i.e. its iteration order does not take dependencies into account. In fact, the implementation will return the vertices in the order in which they were added to the graph.

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in class java.util.AbstractCollection<T>

Returns:

an iterator over all vertices in this graph.

remove

public boolean remove(java.lang.Object vertex)

Specified by:

remove in interface java.util.Collection<T>

Overrides:

remove in class java.util.AbstractCollection<T>

Parameters:

@inheritDoc -

Returns:

@inheritDoc

size

public int size()

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in class java.util.AbstractCollection<T>

getSortedVertices

public java.util.List<T> getSortedVertices()
                                    throws Graph.CycleException

Get an ordered list of vertices, sorted such that for any given vertex A with a directed edge to vertex B, index(B) < index(A).

Returns:

an ordered list of vertices.

Throws:

Graph.CycleException

getSortedVertices

public java.util.List<T> getSortedVertices(T startVertex)
                                    throws Graph.CycleException

Get an ordered list of vertices, sorted such that for any given vertex A with a directed edge to vertex B, index(B) < index(A). This version of the method returns only vertices which are connected to a specified startVertex. Following standard graph theory terminology, a vertex A is connected to B if there is a path (not necessarily a direct path) from A to B.

In a dependency graph, this method essentially returns all of the downstream dependencies of the given vertex in an order which satisfies the dependencies.

The first vertex in the returned list will always be startVertex.

Parameters:

startVertex - the vertex to start from. If you pass null, this method will behave exactly the same as getSortedVertices().

Returns:

Throws:

Graph.CycleException

getVerticesConnectedTo

public java.util.List<T> getVerticesConnectedTo(T vertex)
                                         throws Graph.CycleException

Get all vertices connected to the specified vertex. A vertex A is connected to a vertex B if there is a path (not necessarily a direct path) from A to B.

Parameters:

vertex - a vertex. Must not be null.

Returns:

a collection of vertices connected to the specified vertex. The collection is unsorted.

Throws:

Graph.CycleException

unmodifiableGraph

public static <Z> Graph<Z> unmodifiableGraph(Graph<? extends Z> graph)

Returns a graph based on the specified graph, but which does not permit modification. Changes to the original graph will be reflected through the non modifiable version.

Parameters:

graph - the original graph.

Returns:

an unmodifiable version of the graph.