fr.inria.opengve.bridge.interfaces
Interface Graph<V,E extends Link<V>>

public interface Graph<V,E extends Link<V>>

A graph is a pair formed by a set of vertices and a birelation of the vertices, called the edge set. The Graph interface provides one set view of each of these sets. The order of the vertices or edges in the graph is defined as the order in which the iterators on the graph's set views return their elements. Some graph implementations may make specific guarantees as to their order (for example, breadth-first or depth-first order); others, may not.

All general-purpose graph implementation classes should provide three "standard" constructors: a void (no arguments) constructor which creates an empty modifiable graph, a second constructor taking a EdgeSet as arguments, and a constructor with a single argument of type Graph, which creates a new empty graph define as sub-Graph of the given one. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but all of the general-purpose graph implementations in the Pargoworks package comply.

Every class implementing this interface should only provide structure-modifying operations, that is, the methods that modify the graph on which they operate by adding or removing vertices or edges.

Some graph implementations have restrictions on the vertices and edges they may contain. For example, some implementations enforce bi-directional edges (undirected graphs, and some have restrictions on the types of their elements. Attempting to insert an ineligible element or set of elements throws an unchecked exception, typically NullPointerException or ClassCastException. Attempting to query the presence of an ineligible vertex or edge may throw an exception, or it may simply return false; some implementations will exhibit the former behavior and some will exhibit the latter. More generally, attempting an operation on an ineligible vertex or edge whose completion would not result in the insertion of an ineligible element into the graph may throw an exception or it may succeed, at the option of the implementation. Such exceptions are marked as "optional" in the specification for this interface.

Note: great care must be exercised if mutable objects are used as birelation elements. The behavior of a graph is not specified if the range of an object is changed in a manner that affects equals comparisons while the object is an element in a generating set of the graph. A special case of this prohibition is that it is not permissible for a graph to contain itself as an element.

Version:

1.0, 11/16/04

Author:

Ricardo Correa (correa@lia.ufc.br) and others

Method Summary

boolean	addEdge(E e) Add operation of the edge
boolean	addEdge(V o1, V o2) Add operation of the edge
boolean	addVertex(V o) Add an vertex to the graph.
Graph<V,E>	complement() Returns the complement of this graph.
HierarchicalSet<E>	edgeSet() Returns a set view of the edges of this graph.
HierarchicalSet<E>	getEdgesConnected(V v1, V v2) Construct a HierarchicalSet containing the edges leading from v1 to v2.
int[]	hashCodeArray() Returns an array of integers containing the hash codes of all of the edges in this graph.
Graph<V,E>	inducedSubGraph(java.util.Set<V> subSet) Returns the subgraph induced by the specified subset of vertices.
HierarchicalSet<E>	inEdges(V v) Return all the edges leading to v in this graph.
HierarchicalSet<V>	inNeighborhood(V v) Returns the specified vertex's in neighborhood in this graph.
HierarchicalSet<E>	inOutEdges(V v) Return all the edges connected to this vertex in this graph.
Graph<V,E>	inverse() Returns the inverse of this graph.
HierarchicalSet<V>	neighborhood(V v) The vertices connected to the specified vertex.
HierarchicalSet<E>	outEdges(V v) Return all the edges leaving v in this graph.
HierarchicalSet<V>	outNeighborhood(V v) Returns the specified vertex's out neighborhood in this graph.
boolean	removeEdge(java.lang.Object e) Remove operation of the edge
boolean	removeEdge(java.lang.Object o1, java.lang.Object o2) Remove all edges between two vertices.
boolean	removeVertex(V o) Remove an vertex to the graph.
java.lang.String	toString() Converts this Grqph in string to be printed.
HierarchicalSet<V>	vertexSet() Returns a set view of the vertices of this graph.

Method Detail

addEdge

boolean addEdge(V o1,
                V o2)

Add operation of the edge

Parameters:

o1 - first vertex

o2 - second vertex

Returns:

true if the graph is modified as a result of this operation.

addEdge

boolean addEdge(E e)

Add operation of the edge

Parameters:

e - the Edge

Returns:

true if the graph is modified as a result of this operation.

addVertex

boolean addVertex(V o)

Add an vertex to the graph.

Parameters:

o - The vertex that we want to add to the graph.

Returns:

true if the graph is modified as a result of this operation.

removeEdge

boolean removeEdge(java.lang.Object o1,
                   java.lang.Object o2)

Remove all edges between two vertices.

Parameters:

o1 - first vertex

o2 - second vertex

Returns:

true if the graph is modified as a result of this operation.

removeEdge

boolean removeEdge(java.lang.Object e)

Remove operation of the edge

Parameters:

e - the Edge

Returns:

true if the graph is modified as a result of this operation.

removeVertex

boolean removeVertex(V o)

Remove an vertex to the graph.

Parameters:

o - The vertex that we want to remove to the graph.

Returns:

true if the graph is modified as a result of this operation.

outNeighborhood

HierarchicalSet<V> outNeighborhood(V v)

Returns the specified vertex's out neighborhood in this graph. Returns null if the vertex set does not contain the specified vertex. More formally, if this graph contains an edge that maps the specified element to every vertex in a subset r (possibly empty) of the vertex set, then this method returns r; otherwise it returns null.

Parameters:

v - the vertex whose out neighborhood is to be returned.

Returns:

the out neighborhood of the specified vertex in this graph, or null if the graph does not contain this vertex.

Throws:

java.lang.NullPointerException - the specified vertex is null.

inNeighborhood

HierarchicalSet<V> inNeighborhood(V v)

Returns the specified vertex's in neighborhood in this graph. Returns null if the vertex set does not contain the specified vertex. More formally, if this graph contains an edge that maps the specified element to every vertex in a subset r (possibly empty) of the vertex set, then this method returns r; otherwise it returns null.

Parameters:

v - the vertex whose in neighborhood is to be returned.

Returns:

the in neighborhood of the specified vertex in this graph, or null if the graph does not contain this vertex.

Throws:

java.lang.NullPointerException - the specified vertex is null.

neighborhood

HierarchicalSet<V> neighborhood(V v)

The vertices connected to the specified vertex. If the graph is undirected, then it returns the out neighborhood (the outNeighborhood() may be used for this purpose). Otherwise, it returns a set that is the union of the in and out neighborhoods (similarly, they may be obtained with the inNeighborhood() and outNeighborhood() methods, respectively).

Parameters:

v - the vertex whose neighborhood is returned.

Returns:

the set of vertices connected to the specified vertex by an edge.

inEdges

HierarchicalSet<E> inEdges(V v)

Return all the edges leading to v in this graph.

Parameters:

v - The vertex

Returns:

The set of all edges leading to this vertex in this graph.

outEdges

HierarchicalSet<E> outEdges(V v)

Return all the edges leaving v in this graph.

Parameters:

v - The vertex

Returns:

The set of all edges leaving this vertex in this graph.

inOutEdges

HierarchicalSet<E> inOutEdges(V v)

Return all the edges connected to this vertex in this graph.

Parameters:

v - The vertex

Returns:

The set of edges connected to this vertex in this graph.

inducedSubGraph

Graph<V,E> inducedSubGraph(java.util.Set<V> subSet)

Returns the subgraph induced by the specified subset of vertices.

Parameters:

subSet - the vertex set of the returned graph.

Returns:

the subgraph induced by the specified subset of vertices of this graph.

inverse

Graph<V,E> inverse()

Returns the inverse of this graph. The returned graph is defined by a vertex set which is equal to the vertex set of this graph, and the edge set contains exactly the edges that are in this graph in the inverse direction.

Returns:

the inverse of this graph.

complement

Graph<V,E> complement()

Returns the complement of this graph. The returned graph is defined by a vertex set which is equal to the vertex set of this graph, and the edge set contains exactly the edges that are not in this graph (excepting loop edges).

Returns:

the complement of this graph.

vertexSet

HierarchicalSet<V> vertexSet()

Returns a set view of the vertices of this graph. The returned set supports vertex removal, which removes the incident edges from the graph, via the Iterator.remove,Set.remove,removeAll, retainAll, and clear operations. The set also supports the add or addAll operations, in which cases the new vertices added become isolated vertices of the graph.

Returns:

a set view of the vertex set of this graph.

edgeSet

HierarchicalSet<E> edgeSet()

Returns a set view of the edges of this graph. The returned set supports edges removal, via the Iterator.remove,Set.remove,removeAll, retainAll, and clear operations. The set also supports the add or addAll operations.

Returns:

the set view of the edges of the graph.

hashCodeArray

int[] hashCodeArray()

Returns an array of integers containing the hash codes of all of the edges in this graph. The positions of the array contain the edges of the graph. Each edge occupies two consecutive positions of the array: the first position with the first vertex, and the second position with the second vertex. The integer representation of a vertex v is the value returned by v.hashCode().

If the graph makes any guarantees as to what order its edges are returned by the edgeSet.iterator(), this method must return the edges in the same order. The returned array will be "safe" in that no references to it are maintained by the graph. (In other words, this method must allocate a new array even if the graph is backed by an Array). The caller is thus free to modify the returned array.

This implementation allocates the array to be returned, and iterates over the edges in the graph, storing each vertex representation in the next consecutive element of the array, starting with element 0.

Returns:

an array of integers containing all of the edges in this graph.

toString

java.lang.String toString()

Converts this Grqph in string to be printed.

Overrides:

toString in class java.lang.Object

getEdgesConnected

HierarchicalSet<E> getEdgesConnected(V v1,
                                     V v2)

Construct a HierarchicalSet containing the edges leading from v1 to v2.

Parameters:

v1 - the first vertex

v2 - the second vertex to reach

Returns:

a hierarchical set of edges leading from v1 to v2 in this graph.