javax.ide.util
Class Graph<T>

java.lang.Object
  java.util.AbstractCollection<T>
      javax.ide.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.

Since:

2.0

Nested Class Summary

static class

Graph.CycleException

Field Summary

protected java.util.Map<T,javax.ide.util.Graph.Vertex<T>>

_vertices

Constructor Summary

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

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.
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,javax.ide.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 #add(T), the collection must not contain any duplicate elements. If it does, this constructor will throw an IllegalArgumentException.

Method Detail

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.

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:

vertex - @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.